Scippy

SCIP

Solving Constraint Integer Programs

dpterms_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 dpterms_base.c
17  * @brief Dynamic programming solver for Steiner tree (sub-) problems with small number of terminals
18  * @author Daniel Rehfeldt
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include "scip/scipdefplugins.h"
24 #include "scip/rbtree.h"
25 #include "dpterms.h"
26 #include "dptermsinterns.h"
27 #include "stpbitset.h"
28 #include "stpvector.h"
29 #include "stpprioqueue.h"
30 #include "solstp.h"
31 #ifdef STP_DPTERM_USEDA
32 #include "dualascent.h"
33 #include "heur_ascendprune.h"
34 #include "heur_local.h"
35 #endif
36 
37 
38 // todo more or less random values, tune them!
39 #define PROMISING_FULL_MAXNTERMS 20
40 #define PROMISING_FULL_MAXNTERMS_LARGE 15
41 #define PROMISING_PARTLY_MAXDENSITY 2.2
42 #define PROMISING_PARTLY_SMALL_MAXNTERMS 45
43 #define PROMISING_PARTLY_SMALL_MINNEDGES 1100
44 #define PROMISING_PARTLY_MEDIUM_MAXNTERMS 55
45 #define PROMISING_PARTLY_MEDIUM_MINNEDGES 1500
46 #define PROMISING_PARTLY_LARGE_MAXNTERMS 65
47 #define PROMISING_PARTLY_LARGE_MINNEDGES 3000
48 #define PROMISING_FULL_LARGE_MINNEDGES 100000
49 #define PROMISING_FULL_MAXAVGDEG 5.0
50 
51 
52 /*
53  * Local methods
54  */
55 
56 #ifdef STP_DPTERM_USEDA
57 
58 /** initializes */
59 static
60 SCIP_RETCODE dpredcostsInit(
61  SCIP* scip, /**< SCIP data structure */
62  GRAPH* graph, /**< original graph */
63  DPREDCOST** dpredcosts /**< DP graph */
64 )
65 {
66  SCIP_Real* redcosts_tmp;
67  int* soledges_tmp;
68  DAPARAMS daparams = { .addcuts = FALSE, .ascendandprune = FALSE, .root = graph->source,
69  .is_pseudoroot = FALSE, .damaxdeviation = -1.0 };
70  DPREDCOST* dprc;
71  SCIP_Real dualobjval = -1.0;
72  SCIP_Real primalobjval;
73  SCIP_Bool success;
74  int* pathedge;
75  const int nnodes = graph_get_nNodes(graph);
76  const int nedges = graph_get_nEdges(graph);
77 
78  SCIP_CALL( SCIPallocMemory(scip, dpredcosts) );
79  dprc = *dpredcosts;
80 
81  SCIP_CALL( SCIPallocMemoryArray(scip, &(redcosts_tmp), nedges) );
82  SCIP_CALL( SCIPallocMemoryArray(scip, &(soledges_tmp), nedges) );
83  SCIP_CALL( SCIPallocMemoryArray(scip, &(dprc->csr_redcosts), nedges) );
84 
85  SCIP_CALL( dualascent_exec(scip, graph, NULL, &daparams, redcosts_tmp, &dualobjval) );
86 
87  SCIP_CALL( SCIPStpHeurAscendPruneRun(scip, NULL, graph, redcosts_tmp, soledges_tmp, graph->source, &success, FALSE));
88  assert(success);
89  SCIP_CALL(SCIPStpHeurLocalRun(scip, graph, soledges_tmp));
90  assert(solstp_isValid(scip, graph, soledges_tmp));
91 
92  primalobjval = solstp_getObj(graph, soledges_tmp, 0.0);
93  assert(GE(primalobjval, dualobjval));
94  dprc->cutoffbound = primalobjval - dualobjval;
95  dprc->upperbound = primalobjval;
96 
97  SCIP_CALL( SCIPallocMemoryArray(scip, &(dprc->nodes_rootdist), nnodes) );
98  SCIP_CALL( SCIPallocBufferArray(scip, &pathedge, nnodes + 1) );
99  graph_mark(graph);
100  graph_path_execX(scip, graph, graph->source, redcosts_tmp, dprc->nodes_rootdist, pathedge);
101  SCIPfreeBufferArray(scip, &pathedge);
102 
103  printf("dual=%f primal =%f \n", dualobjval, primalobjval);
104  printf("cutoffbound=%f \n", dprc->cutoffbound);
105 
106  // todo extra method
107  {
108  const CSR* const csr = graph->csr_storage;
109  const int* const edgeid_csr = csr->edge_id;
110  const int* const start_csr = csr->start;
111 
112  assert(csr && edgeid_csr && start_csr);
113 
114  for( int k = 0; k < nnodes; k++ )
115  {
116  for( int j = start_csr[k]; j != start_csr[k + 1]; j++ )
117  {
118  const int edge = edgeid_csr[j];
119  const SCIP_Real rc = MIN(redcosts_tmp[edge], redcosts_tmp[flipedge(edge)]);
120 
121  assert(EQ(graph->cost[edge], csr->cost[j]));
122  assert(GE(rc, 0.0));
123  assert(0 <= j && j < nedges);
124 
125  dprc->csr_redcosts[j] = rc;
126  }
127  }
128  }
129 
130  SCIPfreeMemoryArray(scip, &soledges_tmp);
131  SCIPfreeMemoryArray(scip, &redcosts_tmp);
132 
133  return SCIP_OKAY;
134 }
135 
136 
137 /** frees */
138 static
139 void dpredcostsFree(
140  SCIP* scip, /**< SCIP data structure */
141  DPREDCOST** dpredcosts /**< DP graph */
142 )
143 {
144  DPREDCOST* dprc = *dpredcosts;
145 
146  assert(dprc);
147  assert(dprc->csr_redcosts);
148 
149  SCIPfreeMemoryArray(scip, &(dprc->nodes_rootdist));
150  SCIPfreeMemoryArray(scip, &(dprc->csr_redcosts));
151 
152  SCIPfreeMemory(scip, dpredcosts);
153 }
154 #endif
155 
156 
157 /** initializes */
158 static
160  SCIP* scip, /**< SCIP data structure */
161  const GRAPH* graph, /**< original graph */
162  DPGRAPH** dpgraph /**< DP graph */
163 )
164 {
165  DPGRAPH* dpg;
166  int* terminals;
167  int* nodes_termId;
168  const int nnodes = graph_get_nNodes(graph);
169  const int nedges = graph_get_nEdges(graph);
170  const int nterms = graph_get_nTerms(graph);
171  int termscount = 0;
172 
173  assert(nterms >= 2);
174 
175  SCIP_CALL( SCIPallocMemory(scip, dpgraph) );
176  dpg = *dpgraph;
177  dpg->nnodes = nnodes;
178  dpg->nterms = nterms;
179  dpg->nedges = nedges;
180 
181  SCIP_CALL( SCIPallocMemoryArray(scip, &terminals, nterms) );
182  SCIP_CALL( SCIPallocMemoryArray(scip, &nodes_termId, nnodes) );
183 
184  for( int i = 0; i < nnodes; i++ )
185  {
186  if( Is_term(graph->term[i]) )
187  {
188  assert(termscount < nterms);
189  nodes_termId[i] = termscount;
190  terminals[termscount++] = i;
191  }
192  else
193  {
194  nodes_termId[i] = -1;
195  }
196  }
197  assert(termscount == nterms);
198 
199  dpg->terminals = terminals;
200  dpg->nodes_termId = nodes_termId;
201 
202 #ifndef NDEBUG
203  for( int i = 0; i < nterms; i++ )
204  {
205  const int term = terminals[i];
206  assert(graph_knot_isInRange(graph, term));
207  assert(nodes_termId[term] == i);
208  }
209 #endif
210 
211  return SCIP_OKAY;
212 }
213 
214 
215 /** frees */
216 static
218  SCIP* scip, /**< SCIP data structure */
219  DPGRAPH** dpgraph /**< DP graph */
220 )
221 {
222  DPGRAPH* dpg = *dpgraph;
223 
224  assert(dpg);
225  assert(dpg->terminals && dpg->nodes_termId);
226 
227  SCIPfreeMemoryArray(scip, &(dpg->nodes_termId));
228  SCIPfreeMemoryArray(scip, &(dpg->terminals));
229 
230  SCIPfreeMemory(scip, dpgraph);
231 }
232 
233 
234 /** initializes */
235 static
237  SCIP* scip, /**< SCIP data structure */
238  const GRAPH* graph, /**< original graph */
239  DPMISC** dpmisc /**< to initialize */
240 )
241 {
242  DPMISC* misc;
243  SCIP_CALL( SCIPallocMemory(scip, dpmisc) );
244  misc = *dpmisc;
245 
246  misc->opt_obj = FARAWAY;
247  misc->opt_root = -1;
248  misc->opt_prev[0] = -1;
249  misc->opt_prev[1] = -1;
250  misc->global_termbits = NULL;
251  misc->global_termbitscount = NULL;
252  misc->global_traces = NULL;
253  misc->global_starts = NULL;
254  misc->global_size = 0;
255 
256  StpVecPushBack(scip, misc->global_starts, 0);
257 
258  return SCIP_OKAY;
259 }
260 
261 
262 /** frees */
263 static
265  SCIP* scip, /**< SCIP data structure */
266  DPMISC** dpmisc /**< to free */
267 )
268 {
269  DPMISC* misc = *dpmisc;
270  assert(misc);
271 
272  if( misc->global_termbitscount )
273  {
274  StpVecFree(scip, misc->global_termbitscount);
275  }
276 
277  if( misc->global_termbits )
278  {
279  const int size = StpVecGetSize(misc->global_termbits);
280  for( int i = 0; i < size; i++ )
281  stpbitset_free(scip, &(misc->global_termbits[i]));
282 
283  StpVecFree(scip, misc->global_termbits);
284  }
285 
286  if( misc->global_starts )
287  {
288  StpVecFree(scip, misc->global_starts);
289  }
290 
291  if( misc->global_traces )
292  {
293  StpVecFree(scip, misc->global_traces);
294  }
295 
296  SCIPfreeMemory(scip, dpmisc);
297 }
298 
299 
300 /** initializes data */
301 static
303  SCIP* scip, /**< SCIP data structure */
304  GRAPH* graph, /**< graph of sub-problem */
305  DPSOLVER* dpsolver /**< solver */
306 )
307 {
308  DPSUBSOL* soltree_root = NULL;
309  DPSUBSOL* soltree_parent;
310  const int nterms = graph->terms;
311  const int nnodes = graph->knots;
312  const int* terminals;
313  assert(nterms >= 2);
314 
315  SCIP_CALL( graph_heap_create(scip, nnodes, NULL, NULL, &(dpsolver->dheap) ));
316  SCIP_CALL( stpprioqueue_create(scip, nnodes, &(dpsolver->solpqueue)) );
317  SCIP_CALL( dpterms_streeInit(scip, nterms, nnodes, &(dpsolver->dpstree)) );
318  SCIP_CALL( dpmiscInit(scip, graph, &(dpsolver->dpmisc)) );
319  SCIP_CALL( dpgraphInit(scip, graph, &(dpsolver->dpgraph)) );
320  terminals = dpsolver->dpgraph->terminals;
321 
322 #ifdef STP_DPTERM_USEDA
323  SCIP_CALL( dpredcostsInit(scip, graph, &(dpsolver->dpredcosts)) );
324 #endif
325 
326  for( int i = 0; i < nterms; i++ )
327  {
328  DPSUBSOL* singleton_sol;
329  const int term = terminals[i];
330  int pos;
331 #ifdef STP_DPTERM_USEDA
332  SOLTRACE trace = { .prevs = {-1,-1},
333  .cost = 0.0,
334  .redcost = 0.0,
335  .root = term};
336 #else
337  SOLTRACE trace = { .prevs = {-1,-1},
338  .cost = 0.0,
339  .root = term};
340 #endif
341 
342 
343  assert(Is_term(graph->term[term]));
344  SCIPdebugMessage("add term %d (index=%d) \n", term, i);
345 
346  SCIP_CALL( dpterms_dpsubsolInit(scip, &singleton_sol) );
347  singleton_sol->bitkey = stpbitset_new(scip, nterms);
348  stpbitset_setBitTrue(singleton_sol->bitkey, i);
349 
350  SCIP_CALL( stpprioqueue_insert(scip, ((void*) stpbitset_newCopy(scip, singleton_sol->bitkey)),
351  1, dpsolver->solpqueue) );
352 
353  assert(NULL == singleton_sol->traces);
354  StpVecPushBack(scip, singleton_sol->traces, trace);
355 
356  pos = findSubsol(soltree_root, singleton_sol->bitkey, &soltree_parent);
357  assert(pos != 0); /* not found */
358 
359  SCIPrbtreeInsert(&soltree_root, soltree_parent, pos, singleton_sol);
360  }
361 
362  dpsolver->soltree_root = soltree_root;
363  dpsolver->solnodes = NULL;
364 
365  return SCIP_OKAY;
366 }
367 
368 
369 /** frees data*/
370 static
372  SCIP* scip, /**< SCIP data structure */
373  DPSOLVER* dpsolver /**< solver */
374 )
375 {
376  assert(dpsolver->dpgraph && dpsolver->dpstree && dpsolver->solpqueue);
377  assert(dpsolver->dheap);
378  assert(SCIPisStopped(scip) || stpprioqueue_isClean(dpsolver->solpqueue));
379 
380  StpVecFree(scip, dpsolver->solnodes);
381 
382  if( dpsolver->soltree_root )
383  {
384  FOR_EACH_NODE(DPSUBSOL*, node, dpsolver->soltree_root,
385  {
386  assert(node);
387  SCIPrbtreeDelete(&(dpsolver->soltree_root), node);
388  dpterms_dpsubsolFree(scip, &node);
389  })
390 
391  assert(!dpsolver->soltree_root);
392  }
393 
394 #ifdef STP_DPTERM_USEDA
395  dpredcostsFree(scip, &(dpsolver->dpredcosts));
396 #endif
397 
398  dpgraphFree(scip, &(dpsolver->dpgraph));
399  dpmiscFree(scip, &(dpsolver->dpmisc));
400  dpterms_streeFree(scip, &(dpsolver->dpstree));
401  stpprioqueue_free(scip, &(dpsolver->solpqueue));
402  graph_heap_free(scip, TRUE, TRUE, &(dpsolver->dheap));
403 }
404 
405 
406 /** solve problem */
407 static
409  SCIP* scip, /**< SCIP data structure */
410  GRAPH* g, /**< graph of sub-problem */
411  DPSOLVER* dpsolver, /**< solver */
412  SCIP_Bool* wasSolved /**< was problem solved to optimality? */
413 )
414 {
415  SCIP_CALL( dpterms_coreSolve(scip, g, dpsolver, wasSolved) );
416 
417  return SCIP_OKAY;
418 }
419 
420 
421 /** gets optimal solution */
422 static
424  SCIP* scip, /**< SCIP data structure */
425  GRAPH* graph, /**< graph of sub-problem */
426  DPSOLVER* dpsolver, /**< the solver */
427  int* solution /**< to store solution */
428 )
429 {
430  STP_Bool* connected;
431  STP_Vectype(int) solnodes = dpsolver->solnodes;
432 
433  assert(solnodes);
434 
435  SCIP_CALL( SCIPallocClearBufferArray(scip, &connected, graph->knots) );
436 
437  for( int i = 0; i < StpVecGetSize(solnodes); i++ )
438  {
439  const int node = solnodes[i];
440  assert(graph_knot_isInRange(graph, node));
441  assert(!connected[node]);
442 
443  connected[node] = TRUE;
444  }
445 
446  SCIP_CALL( solstp_pruneFromNodes(scip, graph, solution, connected) );
447 
448  SCIPfreeBufferArray(scip, &connected);
449 
450  return SCIP_OKAY;
451 }
452 
453 
454 /** initializes */
455 static
457  SCIP* scip, /**< SCIP data structure */
458  GRAPH* graph, /**< graph of sub-problem */
459  DPSOLVER** dpsolver /**< solver */
460 )
461 {
462  SCIP_CALL( SCIPallocMemory(scip, dpsolver) );
463 
464  SCIP_CALL( dpsolverInitData(scip, graph, *dpsolver) );
465 
466  return SCIP_OKAY;
467 }
468 
469 
470 /** frees */
471 static
473  SCIP* scip, /**< SCIP data structure */
474  DPSOLVER** dpsolver /**< solver */
475 )
476 {
477  dpsolverFreeData(scip, *dpsolver);
478 
479  SCIPfreeMemory(scip, dpsolver);
480 }
481 
482 
483 /*
484  * Interface methods
485  */
486 
487 
488 /** solves problem given by graph */
490  SCIP* scip, /**< SCIP data structure */
491  GRAPH* graph, /**< graph of sub-problem */
492  int* solution, /**< optimal solution (out) */
493  SCIP_Bool* wasSolved /**< was problem solved to optimality? */
494 )
495 {
496  DPSOLVER* dpsolver;
497 
498  assert(scip && graph && solution);
499 
500  SCIP_CALL( graph_init_csrWithEdgeId(scip, graph) );
501  SCIP_CALL( dpsolverInit(scip, graph, &dpsolver) );
502 
503  SCIP_CALL( dpsolverSolve(scip, graph, dpsolver, wasSolved) );
504 
505  if( *wasSolved )
506  {
507  SCIP_CALL( dpsolverGetSolution(scip, graph, dpsolver, solution) );
508  assert(solstp_isValid(scip, graph, solution));
509  }
510 
511  dpsolverFree(scip, &dpsolver);
512  graph_free_csr(scip, graph);
513 
514  return SCIP_OKAY;
515 }
516 
517 /** is DP at least partly promising? */
519  const GRAPH* graph /**< graph */
520 )
521 {
522  /* NOTE: we count the undirected edges here */
523  const int nedges = (graph->edges / 2);
525 
526  assert(graph);
527 
528  if( dpterms_isPromisingFully(graph) )
529  return TRUE;
530 
531  density = nedges / graph->knots;
532 
533  if( GT(density, PROMISING_PARTLY_MAXDENSITY) )
534  return FALSE;
535 
537  return TRUE;
538 
540  return TRUE;
541 
543  return TRUE;
544 
545  // todo just a test, remove!
546  if( graph->terms == 73 && nedges >= 3500 && nedges <= 4000 )
547  return TRUE;
548 
549  return FALSE;
550 }
551 
552 
553 /** is DP embarrassingly promising? */
555  const GRAPH* graph /**< graph */
556 )
557 {
558  return ( graph->terms <= 3 );
559 }
560 
561 
562 /** is DP fully promising? */
564  const GRAPH* graph /**< graph */
565 )
566 {
567  assert(graph);
568 
569  if( graph->terms <= PROMISING_FULL_MAXNTERMS_LARGE )
570  return TRUE;
571 
572  if( graph->terms <= PROMISING_FULL_MAXNTERMS )
573  {
574  int nedges;
575  int nnodes;
576  graph_get_nVET(graph, &nnodes, &nedges, NULL);
577 
578  if( nedges < PROMISING_FULL_LARGE_MINNEDGES && LT((SCIP_Real) nedges / (SCIP_Real) nnodes, PROMISING_FULL_MAXAVGDEG) )
579  return TRUE;
580  }
581 
582  return FALSE;
583 }
static SCIP_RETCODE dpsolverInitData(SCIP *scip, GRAPH *graph, DPSOLVER *dpsolver)
Definition: dpterms_base.c:302
#define STP_Vectype(type)
Definition: stpvector.h:44
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
static volatile int nterms
Definition: interrupt.c:38
#define StpVecGetSize(vec)
Definition: stpvector.h:139
SCIP_RETCODE dpterms_streeInit(SCIP *scip, int nterms, int nnodes, DPSTREE **dpstree)
Definition: dpterms_util.c:533
#define PROMISING_PARTLY_SMALL_MINNEDGES
Definition: dpterms_base.c:43
int source
Definition: graphdefs.h:195
SCIP_RETCODE dpterms_solve(SCIP *scip, GRAPH *graph, int *solution, SCIP_Bool *wasSolved)
Definition: dpterms_base.c:489
#define Is_term(a)
Definition: graphdefs.h:102
SCIP_RETCODE stpprioqueue_create(SCIP *scip, int capacity, STP_PQ **prioqueue)
Definition: stpprioqueue.c:95
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:117
void stpprioqueue_free(SCIP *scip, STP_PQ **prioqueue)
Definition: stpprioqueue.c:121
#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
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
void graph_mark(GRAPH *)
Definition: graph_base.c:1130
#define PROMISING_PARTLY_MEDIUM_MAXNTERMS
Definition: dpterms_base.c:44
includes methods for Steiner tree problem solutions
reduction and dual-cost based primal heuristic for Steiner problems
#define FALSE
Definition: def.h:87
Includes dual-ascent for classic Steiner tree and some variants.
SCIP_Real * cost
Definition: graphdefs.h:142
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
static void dpsolverFree(SCIP *scip, DPSOLVER **dpsolver)
Definition: dpterms_base.c:472
SCIP_RETCODE dpterms_coreSolve(SCIP *scip, GRAPH *graph, DPSOLVER *dpsolver, SCIP_Bool *wasSolved)
SCIP_Bool dpterms_isPromisingFully(const GRAPH *graph)
Definition: dpterms_base.c:563
Dynamic programming solver for Steiner tree (sub-) problems with small number of terminals.
#define SCIPdebugMessage
Definition: pub_message.h:87
#define FARAWAY
Definition: graphdefs.h:89
#define FOR_EACH_NODE(type, n, r, body)
Definition: rbtree.h:68
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_RETCODE stpprioqueue_insert(SCIP *scip, void *data, int newkey, STP_PQ *prioqueue)
Definition: stpprioqueue.c:236
int * start
Definition: graphdefs.h:140
header only, simple implementation of an STL like vector
CSR * csr_storage
Definition: graphdefs.h:270
#define PROMISING_FULL_MAXNTERMS
Definition: dpterms_base.c:39
SCIP_RETCODE dualascent_exec(SCIP *scip, const GRAPH *g, const int *result, const DAPARAMS *daparams, SCIP_Real *RESTRICT redcost, SCIP_Real *objval)
Definition: dualascent.c:1191
static SCIP_RETCODE dpgraphInit(SCIP *scip, const GRAPH *graph, DPGRAPH **dpgraph)
Definition: dpterms_base.c:159
#define PROMISING_PARTLY_MAXDENSITY
Definition: dpterms_base.c:41
#define GE(a, b)
Definition: portab.h:85
void graph_path_execX(SCIP *, const GRAPH *, int, const SCIP_Real *, SCIP_Real *, int *)
Definition: graph_path.c:905
int graph_get_nTerms(const GRAPH *)
Definition: graph_stats.c:560
SCIP_RETCODE SCIPStpHeurAscendPruneRun(SCIP *scip, SCIP_HEUR *heur, const GRAPH *g, const SCIP_Real *redcosts, int *result, int root, SCIP_Bool *solfound, SCIP_Bool addsol)
void graph_get_nVET(const GRAPH *, int *, int *, int *)
Definition: graph_stats.c:571
priority queue with integer keys
static void dpsolverFreeData(SCIP *scip, DPSOLVER *dpsolver)
Definition: dpterms_base.c:371
static SCIP_RETCODE dpsolverSolve(SCIP *scip, GRAPH *g, DPSOLVER *dpsolver, SCIP_Bool *wasSolved)
Definition: dpterms_base.c:408
static SCIP_RETCODE dpsolverGetSolution(SCIP *scip, GRAPH *graph, DPSOLVER *dpsolver, int *solution)
Definition: dpterms_base.c:423
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_RETCODE SCIPStpHeurLocalRun(SCIP *scip, GRAPH *graph, int *solEdges)
Definition: heur_local.c:3899
#define EQ(a, b)
Definition: portab.h:79
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
header only, simple implementation of a bitset
#define LT(a, b)
Definition: portab.h:81
#define PROMISING_FULL_MAXNTERMS_LARGE
Definition: dpterms_base.c:40
Improvement heuristic for Steiner problems.
unsigned char STP_Bool
Definition: portab.h:34
static void dpgraphFree(SCIP *scip, DPGRAPH **dpgraph)
Definition: dpterms_base.c:217
#define PROMISING_PARTLY_MEDIUM_MINNEDGES
Definition: dpterms_base.c:45
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
void graph_heap_free(SCIP *, SCIP_Bool, SCIP_Bool, DHEAP **)
Definition: graph_util.c:1034
#define GT(a, b)
Definition: portab.h:84
#define SCIP_Bool
Definition: def.h:84
static STP_Bitset stpbitset_newCopy(SCIP *scip, STP_Bitset bitsetOrg)
Definition: stpbitset.h:267
static STP_Bitset stpbitset_new(SCIP *scip, int maxnbits)
Definition: stpbitset.h:75
#define flipedge(edge)
Definition: graphdefs.h:84
static SCIP_RETCODE dpmiscInit(SCIP *scip, const GRAPH *graph, DPMISC **dpmisc)
Definition: dpterms_base.c:236
static void stpbitset_free(SCIP *scip, STP_Bitset *bitset)
Definition: stpbitset.h:100
int *RESTRICT term
Definition: graphdefs.h:196
SCIP_RETCODE graph_init_csrWithEdgeId(SCIP *, GRAPH *)
Definition: graph_util.c:1603
Dynamic programming internals for Steiner tree (sub-) problems with small number of terminals...
static const SCIP_Real density
Definition: gastrans.c:136
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
int * edge_id
Definition: graphdefs.h:143
#define PROMISING_FULL_LARGE_MINNEDGES
Definition: dpterms_base.c:48
#define PROMISING_FULL_MAXAVGDEG
Definition: dpterms_base.c:49
static SCIP_RETCODE dpsolverInit(SCIP *scip, GRAPH *graph, DPSOLVER **dpsolver)
Definition: dpterms_base.c:456
SCIP_Real * cost
Definition: graphdefs.h:221
SCIP_Bool stpprioqueue_isClean(const STP_PQ *prioqueue)
Definition: stpprioqueue.c:78
SCIP_RETCODE graph_heap_create(SCIP *, int, int *, DENTRY *, DHEAP **)
Definition: graph_util.c:992
#define SCIPrbtreeInsert(r, p, c, n)
Definition: rbtree.h:61
#define SCIP_Real
Definition: def.h:177
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:694
#define StpVecFree(scip, vec)
Definition: stpvector.h:153
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
static void dpmiscFree(SCIP *scip, DPMISC **dpmisc)
Definition: dpterms_base.c:264
intrusive red black tree datastructure
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
SCIP_Bool graph_knot_isInRange(const GRAPH *, int)
Definition: graph_node.c:52
#define nnodes
Definition: gastrans.c:65
#define StpVecPushBack(scip, vec, value)
Definition: stpvector.h:167
static void stpbitset_setBitTrue(STP_Bitset bitset, int index)
Definition: stpbitset.h:129
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
#define PROMISING_PARTLY_SMALL_MAXNTERMS
Definition: dpterms_base.c:42
#define PROMISING_PARTLY_LARGE_MAXNTERMS
Definition: dpterms_base.c:46
SCIP_Bool dpterms_isPromisingEmbarrassingly(const GRAPH *graph)
Definition: dpterms_base.c:554
default SCIP plugins
SCIP_Real solstp_getObj(const GRAPH *g, const int *soledge, SCIP_Real offset)
Definition: solstp.c:1859
SCIP_Bool dpterms_isPromisingPartly(const GRAPH *graph)
Definition: dpterms_base.c:518
#define PROMISING_PARTLY_LARGE_MINNEDGES
Definition: dpterms_base.c:47
void dpterms_streeFree(SCIP *scip, DPSTREE **dpstree)
Definition: dpterms_util.c:560