Scippy

SCIP

Solving Constraint Integer Programs

dpborder_base.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file dpborder_base.c
17  * @brief Dynamic programming solver for Steiner tree (sub-) problems with small border
18  * @author Daniel Rehfeldt
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include "dpborder.h"
24 #include "dpborderinterns.h"
25 #include "stpvector.h"
26 #include "solstp.h"
27 
28 
29 #define DPB_MINTERMRATIO 0.4
30 #define DPB_MAXNNODES 1000
31 #define DPB_MINNNODES 100
32 #define DPB_MAXAVGDEG 4.5
33 
34 
35 
36 /*
37  * Local methods
38  */
39 
40 
41 /** non-promising? quick check */
42 static
44  const GRAPH* graph /**< original graph */
45 )
46 {
47  if( graph->knots > DPB_MAXNNODES )
48  return TRUE;
49 
50  if( graph->knots < DPB_MINNNODES )
51  return TRUE;
52 
53  if( ((SCIP_Real) graph->terms / (SCIP_Real) graph->knots) < DPB_MINTERMRATIO )
54  return TRUE;
55 
56  if( ((SCIP_Real) graph->edges / (SCIP_Real) graph->knots) > DPB_MAXAVGDEG )
57  return TRUE;
58 
59  return FALSE;
60 }
61 
62 
63 /** initializes helper */
64 static
66  SCIP* scip, /**< SCIP data structure */
67  GRAPH* graph, /**< graph of sub-problem */
68  DPBORDER* dpborder /**< border */
69  )
70 {
71  const int nnodes = graph_get_nNodes(graph);
72 
73  assert(nnodes == dpborder->nnodes);
74  assert(!dpborder->nodes_isBorder);
75  assert(!dpborder->nodes_outdeg);
76 
77  SCIP_CALL( dpborder_dpbsequenceInit(scip, graph, &(dpborder->dpbsequence)) );
78 
79  SCIP_CALL( SCIPallocClearMemoryArray(scip, &(dpborder->nodes_isBorder), nnodes) );
80  SCIP_CALL( SCIPallocMemoryArray(scip, &(dpborder->nodes_outdeg), nnodes) );
81 
84 
85  BMScopyMemoryArray(dpborder->nodes_outdeg, graph->grad, nnodes);
86 
87  return SCIP_OKAY;
88 }
89 
90 
91 /*
92  * Interface methods
93  */
94 
95 
96 /** initializes */
98  SCIP* scip, /**< SCIP data structure */
99  const GRAPH* graph, /**< original graph */
100  DPBSEQUENCE** dpbsequence /**< to initialize */
101 )
102 {
103  DPBSEQUENCE* seq;
104  const int nnodes = graph_get_nNodes(graph);
105 
106  SCIP_CALL( SCIPallocMemory(scip, dpbsequence) );
107  seq = *dpbsequence;
108 
109  SCIP_CALL( SCIPallocMemoryArray(scip, &(seq->nodessquence), nnodes) );
110  seq->maxnpartitions = 0;
111  seq->maxbordersize = nnodes + 1;
112  seq->nnodes = nnodes;
113 
114  return SCIP_OKAY;
115 }
116 
117 
118 /** copies */
120  const DPBSEQUENCE* dpbsequence_source, /**< to copy */
121  DPBSEQUENCE* dpbsequence_target /**< to copy to */
122 )
123 {
124  const int nnodes = dpbsequence_source->nnodes;
125  assert(dpbsequence_source->nnodes == dpbsequence_target->nnodes);
126 
127  BMScopyMemoryArray(dpbsequence_target->nodessquence, dpbsequence_source->nodessquence, nnodes);
128  dpbsequence_target->maxbordersize = dpbsequence_source->maxbordersize;
129  dpbsequence_target->maxnpartitions = dpbsequence_source->maxnpartitions;
130 }
131 
132 
133 /** frees */
135  SCIP* scip, /**< SCIP data structure */
136  DPBSEQUENCE** dpbsequence /**< to free */
137 )
138 {
139  DPBSEQUENCE* seq = *dpbsequence;
140 
141  assert(seq);
142 
143  SCIPfreeMemoryArray(scip, &(seq->nodessquence));
144  SCIPfreeMemory(scip, dpbsequence);
145 }
146 
147 
148 /** initializes */
150  SCIP* scip, /**< SCIP data structure */
151  DPBLEVEL** dpblevel /**< to initialize */
152 )
153 {
154  DPBLEVEL* level;
155 
156  SCIP_CALL( SCIPallocMemory(scip, dpblevel) );
157  level = *dpblevel;
158 
159  level->bordernodesMapToOrg = NULL;
160  level->nbordernodes = 0;
161  level->extnode = -1;
162  level->globalstartidx = -1;
163  level->exnodeIsTerm = FALSE;
164 
165  return SCIP_OKAY;
166 }
167 
168 
169 /** frees */
171  SCIP* scip, /**< SCIP data structure */
172  DPBLEVEL** dpblevel /**< to be freed */
173 )
174 {
175  DPBLEVEL* level = *dpblevel;
176 
177  assert(level);
178 
179  StpVecFree(scip, level->bordernodesMapToOrg);
180  SCIPfreeMemory(scip, dpblevel);
181 }
182 
183 
184 /** checks whether DP border has potential
185  * NOTE: needs to be called before dpborder_solve! */
187  SCIP* scip, /**< SCIP data structure */
188  GRAPH* graph, /**< graph of sub-problem */
189  DPBORDER* dpborder, /**< border */
190  SCIP_Bool* hasPotential /**< was problem solved to optimality? */
191 )
192 {
194  assert(scip && graph && dpborder && hasPotential);
195  assert(!dpborder->dpbsequence);
196 
197  *hasPotential = FALSE;
198 
199  /* make rough check */
200  if( dpborderIsNonPromising(graph) )
201  {
202  return SCIP_OKAY;
203  }
204 
205  SCIP_CALL( graph_init_csrWithEdgeId(scip, graph) );
206 
207  SCIP_CALL( dpborderInitHelper(scip, graph, dpborder) );
208  SCIP_CALL( dpborder_coreComputeOrderingSimple(scip, graph, dpborder) );
209 
210  dpbsequence = dpborder->dpbsequence;
211  *hasPotential = TRUE;
212 
213  if( dpbsequence->maxnpartitions >= BPBORDER_MAXNPARTITIONS )
214  {
215  *hasPotential = FALSE;
216  }
217 
218  if( dpbsequence->maxbordersize >= BPBORDER_MAXBORDERSIZE )
219  {
220  *hasPotential = FALSE;
221  }
222 
223  graph_free_csr(scip, graph);
224 
225  return SCIP_OKAY;
226 }
227 
228 
229 /** solves problem given by graph */
231  SCIP* scip, /**< SCIP data structure */
232  GRAPH* graph, /**< graph of sub-problem */
233  DPBORDER* dpborder, /**< border */
234  int* solution, /**< optimal solution (out) */
235  SCIP_Bool* wasSolved /**< was problem solved to optimality? */
236 )
237 {
238  uint64_t maxnpartitions;
239  assert(scip && graph && solution);
240  assert(dpborder->dpbsequence);
241 
242  SCIP_CALL( graph_init_csr(scip, graph) );
243 
244  SCIP_CALL( dpborder_coreUpdateOrdering(scip, graph, dpborder) );
245  maxnpartitions = pow(2, ceil(log(dpborder->dpbsequence->maxnpartitions)/log(2)));
246  assert(maxnpartitions >= dpborder->dpbsequence->maxnpartitions);
247 
248  SCIP_CALL( hashmap_create(DPBORDER_GROWTH_FACTOR * maxnpartitions, NULL, &dpborder->hashmap) );
249  SCIP_CALL( dpborder_coreSolve(scip, graph, dpborder, wasSolved) );
250 
251  if( *wasSolved )
252  {
253  STP_Bool* connected;
254  SCIP_CALL( SCIPallocBufferArray(scip, &connected, graph->knots) );
255 
256  dpborder_markSolNodes(dpborder, connected);
257  SCIP_CALL( solstp_pruneFromNodes(scip, graph, solution, connected) );
258  assert(solstp_isValid(scip, graph, solution));
259 
260  SCIPfreeBufferArray(scip, &connected);
261  }
262 
263 #ifndef NDEBUG
264  if( *wasSolved )
265  {
266  const SCIP_Real solval = solstp_getObj(graph, solution, 0.0);
267  assert(EQ(solval, dpborder->global_obj));
268  }
269 #endif
270 
271  graph_free_csr(scip, graph);
272 
273  return SCIP_OKAY;
274 }
275 
276 
277 /** initializes */
279  SCIP* scip, /**< SCIP data structure */
280  const GRAPH* graph, /**< original graph */
281  DPBORDER** dpborder /**< to initialize */
282 )
283 {
284  DPBORDER* dpb;
285  SCIP_CALL( SCIPallocMemory(scip, dpborder) );
286  dpb = *dpborder;
287 
288  assert(graph);
289 
290  dpb->global_partsUseExt = NULL;
291  dpb->bordercharmap = NULL;
292  dpb->borderchardists = NULL;
293  dpb->dpbsequence = NULL;
294  dpb->borderlevels = NULL;
295  dpb->bordernodes = NULL;
296  dpb->prevbordernodes = NULL;
297  dpb->global_partitions = NULL;
298  dpb->global_partstarts = NULL;
299  dpb->global_predparts = NULL;
300  dpb->global_partcosts = NULL;
301  dpb->nodes_isBorder = NULL;
302  dpb->nodes_outdeg = NULL;
303  dpb->global_obj = FARAWAY;
304  dpb->global_npartitions = 0;
305  dpb->global_partcap = 0;
306  dpb->nnodes = graph->knots;
307  dpb->nterms = graph->terms;
308  dpb->ntermsvisited = 0;
309  dpb->global_optposition = -1;
310  dpb->hashmap.elements = NULL;
311 
312  return SCIP_OKAY;
313 }
314 
315 
316 /** frees */
318  SCIP* scip, /**< SCIP data structure */
319  DPBORDER** dpborder /**< to be freed */
320 )
321 {
322  DPBORDER* dpb = *dpborder;
323 
324  StpVecFree(scip, dpb->global_partcosts);
325  StpVecFree(scip, dpb->global_predparts);
326  StpVecFree(scip, dpb->global_partstarts);
327  StpVecFree(scip, dpb->bordernodes);
328  StpVecFree(scip, dpb->prevbordernodes);
329  StpVecFree(scip, dpb->global_partsUseExt);
330 
331  SCIPfreeMemoryArrayNull(scip, &(dpb->bordercharmap));
335  SCIPfreeMemoryArrayNull(scip, &(dpb->nodes_outdeg));
336 
337  // todo make clean
338  if( dpb->hashmap.elements )
339  {
340  hashmap_destroy(&dpb->hashmap);
341  }
342 
343  if( dpb->dpbsequence )
344  {
345  dpborder_dpbsequenceFree(scip, &(dpb->dpbsequence));
346  }
347 
348  if( dpb->borderlevels )
349  {
350  for( int i = 0; i < StpVecGetSize(dpb->borderlevels); i++ )
351  {
352  dpborder_dpblevelFree(scip, &(dpb->borderlevels[i]));
353  assert(!dpb->borderlevels[i]);
354  }
355 
356  StpVecFree(scip, dpb->borderlevels);
357  }
358 
359  SCIPfreeMemory(scip, dpborder);
360 }
SCIP_RETCODE graph_init_csr(SCIP *, GRAPH *)
Definition: graph_util.c:1581
#define StpVecGetSize(vec)
Definition: stpvector.h:139
static void hashmap_destroy(struct hashmap_s *const hashmap) HASHMAP_USED
Destroy the hashmap.
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:72
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
SCIP_RETCODE solstp_pruneFromNodes(SCIP *scip, const GRAPH *g, int *result, STP_Bool *connected)
Definition: solstp.c:1415
int terms
Definition: graphdefs.h:192
void dpborder_dpbsequenceFree(SCIP *scip, DPBSEQUENCE **dpbsequence)
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
SCIP_RETCODE dpborder_coreSolve(SCIP *scip, const GRAPH *graph, DPBORDER *dpborder, SCIP_Bool *wasSolved)
includes methods for Steiner tree problem solutions
#define FALSE
Definition: def.h:87
#define DPB_MINNNODES
Definition: dpborder_base.c:31
static SCIP_Bool dpborderIsNonPromising(const GRAPH *graph)
Definition: dpborder_base.c:43
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define FARAWAY
Definition: graphdefs.h:89
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
#define SCIPallocClearMemoryArray(scip, ptr, num)
Definition: scip_mem.h:57
#define BPBORDER_MAXNPARTITIONS
void dpborder_markSolNodes(const DPBORDER *dpborder, STP_Bool *RESTRICT nodes_isSol)
header only, simple implementation of an STL like vector
SCIP_RETCODE dpborder_coreUpdateOrdering(SCIP *scip, const GRAPH *graph, DPBORDER *dpborder)
static SCIP_RETCODE hashmap_create(const unsigned initial_size, const char *keyarr, struct hashmap_s *const out_hashmap) HASHMAP_USED
Create a hashmap.
#define DPB_MAXNNODES
Definition: dpborder_base.c:30
SCIP_RETCODE dpborder_dpblevelInit(SCIP *scip, DPBLEVEL **dpblevel)
void dpborder_dpbsequenceCopy(const DPBSEQUENCE *dpbsequence_source, DPBSEQUENCE *dpbsequence_target)
int *RESTRICT grad
Definition: graphdefs.h:201
#define NULL
Definition: lpi_spx1.cpp:155
void dpborder_free(SCIP *scip, DPBORDER **dpborder)
#define EQ(a, b)
Definition: portab.h:79
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
void dpborder_dpblevelFree(SCIP *scip, DPBLEVEL **dpblevel)
SCIP_RETCODE dpborder_coreComputeOrderingSimple(SCIP *scip, const GRAPH *graph, DPBORDER *dpborder)
static SCIP_RETCODE dpborderInitHelper(SCIP *scip, GRAPH *graph, DPBORDER *dpborder)
Definition: dpborder_base.c:65
unsigned char STP_Bool
Definition: portab.h:34
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define SCIP_Bool
Definition: def.h:84
#define DPBORDER_GROWTH_FACTOR
struct hashmap_element_s * elements
SCIP_RETCODE dpborder_init(SCIP *scip, const GRAPH *graph, DPBORDER **dpborder)
#define DPB_MINTERMRATIO
Definition: dpborder_base.c:29
SCIP_RETCODE dpborder_probePotential(SCIP *scip, GRAPH *graph, DPBORDER *dpborder, SCIP_Bool *hasPotential)
#define BPBORDER_MAXBORDERSIZE
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
SCIP_RETCODE dpborder_dpbsequenceInit(SCIP *scip, const GRAPH *graph, DPBSEQUENCE **dpbsequence)
Definition: dpborder_base.c:97
SCIP_RETCODE graph_init_csrWithEdgeId(SCIP *, GRAPH *)
Definition: graph_util.c:1603
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
Dynamic programming solver for Steiner tree (sub-) problems with small border.
#define DPB_MAXAVGDEG
Definition: dpborder_base.c:32
#define SCIP_Real
Definition: def.h:177
Dynamic programming internals for Steiner tree (sub-) problems with small number of terminals...
#define StpVecFree(scip, vec)
Definition: stpvector.h:149
void graph_free_csr(SCIP *, GRAPH *)
Definition: graph_util.c:1623
int edges
Definition: graphdefs.h:219
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
SCIP_RETCODE dpborder_solve(SCIP *scip, GRAPH *graph, DPBORDER *dpborder, int *solution, SCIP_Bool *wasSolved)
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
#define nnodes
Definition: gastrans.c:65
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
SCIP_Real solstp_getObj(const GRAPH *g, const int *soledge, SCIP_Real offset)
Definition: solstp.c:1859