Scippy

SCIP

Solving Constraint Integer Programs

heur_prune.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-2021 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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_prune.c
17  * @brief reduction-based primal heuristic for Steiner problems
18  * @author Daniel Rehfeldt
19  *
20  * This file implements a reduction based heuristic for Steiner problems. See
21  * "SCIP-Jack - A solver for STP and variants with parallelization extensions" (2016) by
22  * Gamrath, Koch, Maher, Rehfeldt and Shinano
23  *
24  * A list of all interface methods can be found in heur_prune.h
25  *
26  */
27 
28 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
29 //#define SCIP_DEBUG
30 #include <assert.h>
31 #include <string.h>
32 #include <stdio.h>
33 #include "scip/scip.h"
34 #include "scip/scipdefplugins.h"
35 #include "scip/cons_linear.h"
36 #include "heur_prune.h"
37 #include "heur_local.h"
38 #include "graph.h"
39 #include "reduce.h"
40 #include "heur_tm.h"
41 #include "solstp.h"
42 #include "cons_stp.h"
43 #include "scip/pub_misc.h"
44 #include "probdata_stp.h"
45 
46 #define HEUR_NAME "prune"
47 #define HEUR_DESC "Reduction based heuristic for Steiner problems"
48 #define HEUR_DISPCHAR 'P'
49 #define HEUR_PRIORITY 2
50 #define HEUR_FREQ -1
51 #define HEUR_FREQOFS 0
52 #define HEUR_MAXDEPTH -1
53 #define HEUR_TIMING (SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE)
54 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
55 
56 #define DEFAULT_PRUNE_MAXFRQ FALSE /**< executions of the heuristic at maximum frequency? */
57 #define PRUNE_TMRUNS 100 /**< number of runs in TM heuristic when called by prune heuristic */
58 #define PRUNE_TMRUNS_FAST 70 /**< number of runs in TM heuristic when called by prune heuristic */
59 #define PRUNE_MINREDELIMS 2 /**< maximum number of eliminations for reduction package when called by prune heuristic */
60 #define PRUNE_MAXREDROUNDS 6 /**< maximum number of reduction rounds in prune heuristic */
61 #define MAXNTERMINALS 500
62 #define MAXNEDGES 10000
63 
64 
65 /*
66  * Data structures
67  */
68 
69 /** primal heuristic data */
70 struct SCIP_HeurData
71 {
72  int bestsolindex; /**< best solution during the previous run */
73  int ntmruns; /**< number of runs in TM heuristic */
74  int nfailures; /**< number of failures since last successful call */
75  SCIP_Bool maxfreq; /**< should the heuristic be called at maximum frequency? */
76 };
77 
78 /*
79  * Local methods
80  */
81 
82 
83 
84 /* set node solution array and get solution value */
85 static
87  const GRAPH* g,
88  SCIP_Real* RESTRICT uborg,
89  int* RESTRICT solnode,
90  const int* soledge
91  )
92 {
93  SCIP_Real ub = 0.0;
94  const int nnodes = graph_get_nNodes(g);
95  const int nedges = graph_get_nEdges(g);
96 
97  assert(solnode != NULL);
98  assert(soledge != NULL);
99 
100  for( int k = 0; k < nnodes; k++ )
101  solnode[k] = UNKNOWN;
102 
103  solnode[g->source] = CONNECT;
104 
105  for( int e = 0; e < nedges; e++ )
106  {
107  if( soledge[e] == CONNECT )
108  {
109  ub += g->cost[e];
110  solnode[g->head[e]] = CONNECT;
111  }
112  }
113 
114 #ifndef NDEBUG
115  for( int e = 0; e < nedges; e++ )
116  {
117  if( soledge[e] == CONNECT )
118  {
119  assert(solnode[g->tail[e]] == CONNECT);
120  assert(solnode[g->head[e]] == CONNECT);
121  }
122  }
123 #endif
124 
125  if( uborg != NULL)
126  *uborg = ub;
127 }
128 
129 /** computes new solution during execution of prune and updates best global one if possible */
130 static
132  SCIP* scip, /**< SCIP data structure */
133  GRAPH* g, /**< graph data structure */
134  GRAPH* prunegraph, /**< pruned graph data structure */
135  int* nodearrint, /**< array */
136  int* solnode, /**< array for best solution nodes wrt prunegraph */
137  int* soledge, /**< array for best solution edges wrt prunegraph */
138  int* globalsoledge, /**< array storing best solution wrt g */
139  SCIP_Real* globalobj, /**< pointer to objective value of best solution wrt g */
140  SCIP_Bool incumbentgiven, /**< incumbent solution for pruned graph given? */
141  SCIP_Bool beFast, /**< use fast mode? */
142  SCIP_Bool* success /**< pointer to store whether a solution could be found */
143 )
144 {
145  int* const pmark = prunegraph->mark;
146  SCIP_Real dummyhop = 0.0;
147  int nruns;
148  const int nnodes = g->knots;
149 
150  assert(graph_valid(scip, prunegraph));
151  assert(g->edges == prunegraph->edges);
152 
153  /*
154  * compute new solution on pruned graph
155  */
156 
157  nruns = 0;
158  for( int k = 0; k < nnodes; k++ )
159  {
160  pmark[k] = (prunegraph->grad[k] > 0);
161  if( pmark[k] )
162  nruns++;
163  }
164 
165  if( beFast )
166  {
167  nruns = MIN(nruns, PRUNE_TMRUNS);
168  nruns = MIN(prunegraph->terms, nruns);
169  }
170  else
171  {
172  nruns = MIN(nruns, PRUNE_TMRUNS);
173  }
174  SCIPStpHeurTMCompStarts(prunegraph, nodearrint, &nruns);
175 
176  /* run shortest path heuristic */
177  SCIP_CALL( SCIPStpHeurTMRun(scip, pcmode_fromheurdata, prunegraph, nodearrint, NULL, soledge, nruns,
178  prunegraph->source, prunegraph->cost, prunegraph->cost, &dummyhop, NULL, success));
179 
180  SCIP_CALL( SCIPStpHeurLocalRun(scip, prunegraph, soledge) );
181 
182  SCIP_CALL( SCIPStpHeurPruneUpdateSols(scip, g, prunegraph, solnode, soledge,
183  globalsoledge, globalobj, incumbentgiven, success) );
184 
185  return SCIP_OKAY;
186 }
187 
188 /* get reduction bound */
189 /* todo tune, rather random values at the moment */
190 static
192  int nround,
193  int nedges
194  )
195 {
196  if( nround == 0 )
197  return(MAX(nedges / 1000, PRUNE_MINREDELIMS));
198  if( nround == 1 )
199  return(MAX(nedges / 500, PRUNE_MINREDELIMS));
200  return(MAX(nedges / 200, PRUNE_MINREDELIMS));
201 }
202 
203 
204 /* todo tune, rather random values at the moment */
205 static
207  SCIP* scip,
208  int* minnelims,
209  int* lminnelims,
210  int annodes,
211  int anedges,
212  int anterms,
213  int nround,
214  int maxrounds
215  )
216 {
217  int min;
218  int totminnelims;
219  SCIP_Real factor;
220 
221  assert(scip != NULL);
222  assert(minnelims != NULL);
223  assert(lminnelims != NULL);
224  assert(annodes > 0);
225  assert(nround >= 0);
226  assert(maxrounds >= 1);
227 
228  anedges = anedges / 2;
229 
230  totminnelims = MAX(PRUNE_MINREDELIMS, (anedges / 20));
231 
232  min = (anedges / 10);
233  min -= (int) ( ((SCIP_Real) min * anterms) / ( (SCIP_Real) annodes) );
234  min = MAX(min, 1);
235 
236  factor = (SCIP_Real) anedges / min;
237  factor = ((SCIP_Real) nround / (3.0 * maxrounds)) * factor;
238 
239  if( SCIPisGT(scip, factor, 1.0) )
240  min = (int) ((SCIP_Real) min * factor);
241 
242  min = MAX(totminnelims, min);
243  min = MIN(min, (anedges - 1));
244  min = MAX(min, 1);
245 
246  *lminnelims = min / 2;
247  *lminnelims = MAX(*lminnelims, 1);
248 
249  *minnelims = min;
250 }
251 
252 /*
253  * Callback methods of primal heuristic
254  */
255 
256 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
257 static
258 SCIP_DECL_HEURCOPY(heurCopyPrune)
259 { /*lint --e{715}*/
260  assert(scip != NULL);
261  assert(heur != NULL);
262  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
263 
264  /* call inclusion method of primal heuristic */
266 
267  return SCIP_OKAY;
268 }
269 
270 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
271 static
272 SCIP_DECL_HEURFREE(heurFreePrune)
273 { /*lint --e{715}*/
274  SCIP_HEURDATA* heurdata;
275 
276  assert(heur != NULL);
277  assert(scip != NULL);
278 
279  /* get heuristic data */
280  heurdata = SCIPheurGetData(heur);
281  assert(heurdata != NULL);
282 
283  /* free heuristic data */
284  SCIPfreeMemory(scip, &heurdata);
285  SCIPheurSetData(heur, NULL);
286 
287  return SCIP_OKAY;
288 }
289 
290 
291 /** initialization method of primal heuristic (called after problem was transformed) */
292 static
293 SCIP_DECL_HEURINIT(heurInitPrune)
294 { /*lint --e{715}*/
295 
296 
297  return SCIP_OKAY;
298 }
299 
300 
301 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
302 static
303 SCIP_DECL_HEURINITSOL(heurInitsolPrune)
304 { /*lint --e{715}*/
305  SCIP_HEURDATA* heurdata;
306 
307  assert(heur != NULL);
308  assert(scip != NULL);
309 
310  /* get heuristic's data */
311  heurdata = SCIPheurGetData(heur);
312 
313  assert(heurdata != NULL);
314 
315  /* initialize data */
316  heurdata->ntmruns = PRUNE_TMRUNS;
317  heurdata->nfailures = 0;
318  heurdata->bestsolindex = -1;
319 
320  return SCIP_OKAY;
321 }
322 
323 
324 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
325 static
326 SCIP_DECL_HEUREXITSOL(heurExitsolPrune)
327 { /*lint --e{715}*/
328 
329  return SCIP_OKAY;
330 }
331 
332 
333 /** execution method of primal heuristic */
334 static
335 SCIP_DECL_HEUREXEC(heurExecPrune)
336 { /*lint --e{715}*/
337  SCIP_HEURDATA* heurdata;
338  SCIP_PROBDATA* probdata;
339  SCIP_VAR** vars;
340  SCIP_SOL* bestsol; /* best known solution */
341  GRAPH* graph;
342  SCIP_Real* xval;
343  SCIP_Bool success;
344  int e;
345  int nvars;
346  int nedges;
347  int* soledge;
348 
349  assert(heur != NULL);
350  assert(scip != NULL);
351  assert(result != NULL);
352  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
353 
354  /* get heuristic data */
355  heurdata = SCIPheurGetData(heur);
356  assert(heurdata != NULL);
357 
358  /* get problem data */
359  probdata = SCIPgetProbData(scip);
360  assert(probdata != NULL);
361 
362  /* get graph */
363  graph = SCIPprobdataGetGraph(probdata);
364  assert(graph != NULL);
365 
366  nedges = graph->edges;
367  *result = SCIP_DIDNOTRUN;
368 
369  /* if not STP like variant, return */
370  if( graph->stp_type != STP_SPG && graph->stp_type != STP_RSMT && graph->stp_type != STP_OARSMT &&
371  graph->stp_type != STP_GSTP )
372  return SCIP_OKAY;
373 
374  if( (graph->edges > MAXNEDGES) && (graph->terms > MAXNTERMINALS) )
375  return SCIP_OKAY;
376 
377  /* get best current solution */
378  bestsol = SCIPgetBestSol(scip);
379 
380  /* no solution available? */
381  if( bestsol == NULL )
382  return SCIP_OKAY;
383 
384  /* has the new solution been found by this very heuristic? */
385  if( SCIPsolGetHeur(bestsol) == heur || heurdata->bestsolindex == SCIPsolGetIndex(SCIPgetBestSol(scip)) )
386  return SCIP_OKAY;
387 
388  xval = SCIPprobdataGetXval(scip, bestsol);
389 
390  if( xval == NULL )
391  return SCIP_OKAY;
392 
393  vars = SCIPprobdataGetVars(scip);
394  nvars = SCIPprobdataGetNVars(scip);
395 
396  SCIPdebugMessage("START prune heuristic \n");
397 
398  assert(vars != NULL);
399 
400  /* allocate array to store primal solution */
401  SCIP_CALL( SCIPallocBufferArray(scip, &soledge, nedges) );
402 
403  for( e = 0; e < nedges; e++ )
404  {
405  if( SCIPisEQ(scip, xval[e], 1.0) )
406  soledge[e] = CONNECT;
407  else
408  soledge[e] = UNKNOWN;
409  }
410 
411  /* execute prune heuristic */
412  SCIP_CALL( SCIPStpHeurPruneRun(scip, vars, graph, soledge, &success, TRUE, FALSE) );
413 
414  /* solution found by prune heuristic? */
415  if( success )
416  {
417  SCIP_Real pobj;
418  SCIP_Real* nval;
419 
420  SCIPdebugMessage("ADDED valid solution in prune \n");
421 
422  assert(solstp_isValid(scip, graph, soledge));
423  pobj = 0.0;
424 
425  /* allocate memory to store solution */
426  SCIP_CALL( SCIPallocBufferArray(scip, &nval, nvars) );
427 
428  for( e = 0; e < nedges; e++ )
429  {
430  if( soledge[e] == CONNECT )
431  {
432  nval[e] = 1.0;
433  pobj += graph->cost[e];
434  }
435  else
436  {
437  nval[e] = 0.0;
438  }
439  }
440 
441  SCIPdebugMessage("prune, best: old %f, new %f \n \n", SCIPgetSolOrigObj(scip, bestsol) - SCIPprobdataGetOffset(scip), pobj);
442 
443  /* try to add new solution to pool */
444  SCIP_CALL( SCIPprobdataAddNewSol(scip, nval, heur, &success) );
445 
446  /* has solution been added? */
447  if( success )
448  {
449  SCIPdebugMessage("solution added by PRUNE \n \n");
450 
451  *result = SCIP_FOUNDSOL;
452 
453  assert(solstp_isValid(scip, graph, soledge));
454 
455  /* is the solution the new incumbent? */
456  if( SCIPisGT(scip, SCIPgetSolOrigObj(scip, bestsol) - SCIPprobdataGetOffset(scip), pobj) )
457  {
458  heurdata->nfailures = 0;
459  }
460  else
461  {
462  success = FALSE;
463  }
464  }
465 
466  /* solution could not be added or is not best? */
467  if( !success )
468  heurdata->nfailures++;
469 
470  /* free memory */
471  SCIPfreeBufferArray(scip, &nval);
472  }
473 
474  /* store index of incumbent solution */
475  heurdata->bestsolindex = SCIPsolGetIndex(SCIPgetBestSol(scip));
476 
477  /* free memory */
478  SCIPfreeBufferArray(scip, &soledge);
479 
480  return SCIP_OKAY;
481 }
482 
483 
484 /*
485  * primal heuristic specific interface methods
486  */
487 
488 /** updates solutions for pruned graph */
490  SCIP* scip, /**< SCIP data structure */
491  GRAPH* g, /**< graph data structure */
492  GRAPH* prunegraph, /**< pruned graph data structure */
493  int* solnode, /**< array for best solution nodes wrt prunegraph */
494  int* soledge, /**< array for best solution edges wrt prunegraph */
495  int* globalsoledge, /**< array storing best solution wrt g */
496  SCIP_Real* globalobj, /**< pointer to objective value of best solution wrt g */
497  SCIP_Bool incumbentgiven, /**< incumbent solution for pruned graph given? */
498  SCIP_Bool* success /**< pointer to store whether a solution could be found */
499  )
500 {
501  SCIP_Real objnew;
502  int* RESTRICT edgearrint;
503  const int nnodes = g->knots;
504  const int nedges = g->edges;
505  const int probtype = g->stp_type;
506  const SCIP_Bool pcmw = (probtype == STP_MWCSP || probtype == STP_RMWCSP || probtype == STP_RPCSPG || probtype == STP_PCSPG);
507 
508  assert(g != NULL);
509  assert(scip != NULL);
510  assert(soledge != NULL);
511  assert(solnode != NULL);
512 
513  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrint, nedges) );
514 
515  /*
516  * compare new solution on pruned graph with (reconstructed) incumbent
517  */
518 
519  if( incumbentgiven )
520  {
521  PATH* path;
522  SCIP_Real objold;
523 
524  SCIP_CALL( SCIPallocBufferArray(scip, &path, nnodes) );
525 
526  objnew = solstp_getObjBounded(prunegraph, soledge, 0.0, nedges);
527 
528  if( pcmw )
529  SCIP_CALL( SCIPStpHeurTMBuildTreePcMw(scip, prunegraph, FALSE, path, prunegraph->cost, &objold, solnode) );
530  else
531  SCIPStpHeurTMBuildTree(scip, prunegraph, path, prunegraph->cost, &objold, solnode);
532 
533  SCIPdebugMessage("objold %f objnew %f \n", objold, objnew);
534 
535  /* keep (reconstructed) old solution? */
536  if( LT(objold, objnew) )
537  {
538  for( int e = 0; e < nedges; e++ )
539  soledge[e] = UNKNOWN;
540  for( int k = 0; k < nnodes; k++ )
541  {
542  const int e = path[k].edge;
543 
544  if( e >= 0 )
545  soledge[e] = CONNECT;
546  }
547 
548  assert(SCIPisEQ(scip, objold, solstp_getObjBounded(prunegraph, soledge, 0.0, nedges)));
549  }
550 
551  SCIPfreeBufferArray(scip, &path);
552  }
553 
554  assert(solstp_isValid(scip, prunegraph, soledge));
555 
556  setNodeSolArray(prunegraph, NULL, solnode, soledge);
557 
558  /*
559  * retransform new solution and compare with best global one
560  */
561 
562  SCIP_CALL( solstp_getOrg(scip, prunegraph, g, soledge, edgearrint) );
563 
564  assert(solstp_isValid(scip, g, edgearrint));
565 
566  objnew = solstp_getObjBounded(g, edgearrint, 0.0, nedges);
567 
568  SCIPdebugMessage("old global obj: %f ... new global obj: %f \n", *globalobj, objnew);
569 
570  if( LT(objnew, (*globalobj)) )
571  {
572  SCIPdebugMessage("new global solution is better \n");
573  *globalobj = objnew;
574 
575  SCIP_CALL( SCIPStpHeurLocalRun(scip, g, edgearrint) );
576 
577  objnew = solstp_getObjBounded(g, edgearrint, 0.0, nedges);
578 
579  assert(SCIPisLE(scip, objnew, *globalobj));
580 
581  if( objnew < (*globalobj) )
582  *globalobj = objnew;
583 
584  BMScopyMemoryArray(globalsoledge, edgearrint, nedges);
585  }
586 
587  assert(*globalobj < FARAWAY);
588 
589  graph_mark(prunegraph);
590 
591  *success = TRUE;
592 
593  SCIPfreeBufferArray(scip, &edgearrint);
594 
595  return SCIP_OKAY;
596 }
597 
598 /** execute prune heuristic on given graph */
600  SCIP* scip, /**< SCIP data structure */
601  SCIP_VAR** vars, /**< problem variables or NULL (need to be provided whenever available) */
602  GRAPH* g, /**< the graph */
603  int* soledge, /**< array to store primal solution (if no solution is provided,
604  withinitialsol must be set to FALSE) */
605  SCIP_Bool* success, /**< feasible solution found? */
606  const SCIP_Bool withinitialsol, /**< solution given? */
607  const SCIP_Bool reducegraph /**< try to reduce graph initially? */
608  )
609 {
610  GRAPH* prunegraph;
611  PATH* vnoi;
612  PATH* path;
613  SCIP_Real globalobj;
614  SCIP_Real uborg = 0.0;
615  SCIP_Real offset;
616  SCIP_Real* cost;
617  SCIP_Real* costrev;
618  SCIP_Real* nodearrreal;
619  const int probtype = g->stp_type;
620  const SCIP_Bool pc = (probtype == STP_RPCSPG || probtype == STP_PCSPG);
621  const SCIP_Bool mw = (probtype == STP_MWCSP || probtype == STP_RMWCSP);
622  const SCIP_Bool pcmw = (pc || mw);
623  const int nnodes = g->knots;
624  const int nedges = g->edges;
625  int annodes;
626  int anedges;
627  int anterms;
628  int reductbound;
629  int* heap;
630  int* state;
631  int* vbase;
632  int* solnode;
633  int* nodearrint;
634  int* edgearrint;
635  int* nodearrint2;
636  int* globalsoledge;
637  STP_Bool* nodearrchar;
638  SCIP_Bool solgiven;
639 
640  assert(g != NULL);
641  assert(scip != NULL);
642  assert(soledge != NULL);
643  assert(probtype != STP_DHCSTP);
644  assert(!(withinitialsol && reducegraph));
645 
646  *success = TRUE;
647 
648  if( reducegraph )
649  solgiven = FALSE;
650  else
651  solgiven = withinitialsol;
652 
653  if( g->terms <= 1)
654  {
655  for( int e = 0; e < nedges; e++ )
656  soledge[e] = UNKNOWN;
657  return SCIP_OKAY;
658  }
659 
660  /* allocate memory */
661  SCIP_CALL( SCIPallocBufferArray(scip, &globalsoledge, nedges) );
662  SCIP_CALL( SCIPallocBufferArray(scip, &solnode, nnodes) );
663  SCIP_CALL( SCIPallocBufferArray(scip, &cost, nedges) );
664  SCIP_CALL( SCIPallocBufferArray(scip, &costrev, nedges) );
665  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrchar, nnodes + 1) );
666  SCIP_CALL( SCIPallocBufferArray(scip, &heap, nnodes + 1) );
667  SCIP_CALL( SCIPallocBufferArray(scip, &state, 4 * nnodes) );
668  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrreal, nnodes) );
669  SCIP_CALL( SCIPallocBufferArray(scip, &vbase, 4 * nnodes) );
670  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint, nnodes + 1) );
671  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrint, nedges) );
672  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint2, nnodes + 1) );
673  SCIP_CALL( SCIPallocBufferArray(scip, &vnoi, 4 * nnodes) );
674  SCIP_CALL( SCIPallocBufferArray(scip, &path, nnodes + 1) );
675 
676  if( probtype == STP_RSMT || probtype == STP_OARSMT || probtype == STP_GSTP )
677  g->stp_type = STP_SPG;
678 
679  /* copy the graph */
680  SCIP_CALL( graph_copy(scip, g, &prunegraph) );
681 
682  if( vars != NULL )
683  {
684  prunegraph->norgmodeledges = prunegraph->edges;
685  prunegraph->norgmodelknots = prunegraph->knots;
686  }
687 
688  /* set ancestors of the new graph */
689  SCIP_CALL( graph_initHistory(scip, prunegraph) );
690 
691  /* set offset (within new graph) to 0.0 */
692  offset = 0.0;
693 
694  reductbound = getRedBound(0, nedges);
695 
696  SCIPdebugMessage("Starting prune... \n");
697 
698  assert(!pcmw || g->extended);
699 
700  /* problem variables given? */
701  if( vars != NULL )
702  {
703  int nfixededges = 0;
704 
705  /* delete fixed edges from the new graph */
706  for( int e = 0; e < nedges; e += 2 )
707  {
708  /* both e and its anti-parallel edge fixed to zero? */
709  if( SCIPvarGetUbLocal(vars[e]) < 0.5 && SCIPvarGetUbLocal(vars[e + 1]) < 0.5 )
710  {
711  if( pcmw )
712  {
713  if( (!solgiven || (soledge[e] != CONNECT && soledge[e + 1] != CONNECT))
714  && !Is_term(prunegraph->head[e]) && !Is_term(prunegraph->tail[e]) )
715  {
716  graph_edge_del(scip, prunegraph, e, TRUE);
717  nfixededges++;
718  }
719  }
720  else
721  {
722  if( !solgiven || (soledge[e] != CONNECT && soledge[e + 1] != CONNECT) )
723  {
724  graph_edge_del(scip, prunegraph, e, TRUE);
725  nfixededges++;
726  }
727  }
728  }
729  }
730  SCIPdebugMessage("fixed edges in prune: %d \n", nfixededges);
731 
732  if( nfixededges >= reductbound )
733  {
734  graph_get_nVET(prunegraph, &annodes, &anedges, &anterms);
735  reductbound = getRedBound(0, anedges);
736  }
737  }
738 
739  SCIP_CALL(graph_path_init(scip, prunegraph));
740 
741  /* perform initial reductions? */
742  if( reducegraph )
743  {
744  REDSOL* redsol;
745  SCIP_CALL( reduce_solInit(scip, prunegraph, TRUE, &(redsol)) );
746 
747  if( pc )
748  {
749  SCIP_CALL( reduce_redLoopPc(scip, redsol, prunegraph, vnoi, path, nodearrreal, heap, state,
750  vbase, nodearrint, edgearrint, nodearrint2, nodearrchar, FALSE, FALSE, FALSE, reductbound, FALSE, TRUE, TRUE) );
751  }
752  else if( mw )
753  {
754  SCIP_CALL( reduce_redLoopMw(scip, redsol, prunegraph, vnoi, nodearrreal, state,
755  vbase, nodearrint, nodearrchar, FALSE, FALSE, FALSE, reductbound, FALSE, TRUE) );
756  }
757  else
758  {
759  RPARAMS parameters = { .dualascent = FALSE, .boundreduce = FALSE, .nodereplacing = TRUE, .reductbound_min = PRUNE_MINREDELIMS,
760  .reductbound = reductbound, .userec = FALSE, .fullreduce = FALSE, .usestrongreds = TRUE };
761  BIDECPARAMS decparameters = { .depth = 0, .maxdepth = 2, .newLevelStarted = FALSE };
762  REDBASE redbase = { .redparameters = &parameters, .bidecompparams = &decparameters,
763  .solnode = NULL, .redsol = redsol,
764  .vnoi = vnoi, .path = path, .heap = heap,
765  .nodearrreal = nodearrreal,
766  .state = state, .vbase = vbase, .nodearrint = nodearrint,
767  .edgearrint = edgearrint, .nodearrint2 = nodearrint2, .nodearrchar = nodearrchar };
768 
769  SCIP_CALL( reduce_redLoopStp(scip, prunegraph, &redbase) );
770  }
771 
772  offset = reduce_solGetOffset(redsol);
773  reduce_solFree(scip, &(redsol));
774  }
775 
776  /* get number of remaining nodes, edges and terminals */
777  graph_get_nVET(prunegraph, &annodes, &anedges, &anterms);
778 
779  if( solgiven )
780  {
781  BMScopyMemoryArray(globalsoledge, soledge, nedges);
782  globalobj = solstp_getObjBounded(g, soledge, 0.0, nedges);
783  setNodeSolArray(g, &uborg, solnode, soledge);
784  }
785  else
786  {
787  globalobj = FARAWAY;
788  SCIP_CALL( computeNewSols(scip, g, prunegraph, nodearrint, solnode, soledge, globalsoledge, &globalobj, FALSE, FALSE, success) );
789 
790  assert(*success);
791  }
792 
793  SCIPdebugMessage("initially reduced graph: |V| = %d, |E| = %d, |T| = %d \n", annodes, anedges, anterms);
794  SCIPdebugMessage("entering prune \n\n");
795 
796  prunegraph->withInexactReductions = TRUE;
797  if( annodes > 0 )
798  {
799  /* main prune reduction loop */
800  for( int i = 0; i < PRUNE_MAXREDROUNDS; i++ )
801  {
802  REDSOL* redsol;
803  int minnelims = 0;
804  int brednelims = 0;
805  int lminnelims = 0;
806 
807  /* get number of remaining edges */
808  graph_get_nVET(prunegraph, &annodes, &anedges, &anterms);
809 
810  if( anterms <= 2 )
811  {
812  SCIPdebugMessage("less than two terminals, break !! \n");
813  break;
814  }
815 
816  setMinMaxElims(scip, &minnelims, &lminnelims, annodes, anedges, anterms, i + 1, PRUNE_MAXREDROUNDS);
817 
818  if( i > 0 )
819  {
820  SCIP_CALL( computeNewSols(scip, g, prunegraph, nodearrint, solnode, soledge, globalsoledge,
821  &globalobj, TRUE, TRUE, success) );
822  }
823 
824  if( pcmw )
825  graph_pc_2org(scip, prunegraph);
826 
827  SCIP_CALL( reduce_boundPruneHeur(scip, prunegraph, vnoi, cost, nodearrreal, costrev,
828  &offset, heap, state, vbase, solnode, soledge, &brednelims, minnelims));
829 
830  if( pcmw )
831  graph_pc_2trans(scip, prunegraph);
832 
833 #ifdef SCIP_DEBUG
834  graph_get_nVET(prunegraph, &annodes, &anedges, &anterms);
835  printf("PRUNE round: %d edges %d nodes: %d \n", i, anedges / 2, annodes);
836  printf("PRUNE round: %d minelims %d really reduced: %d \n", i, minnelims, brednelims);
837 #endif
838 
839  /* not enough reductions possible? */
840  if( brednelims < lminnelims )
841  {
842  SCIPdebugMessage("not enough elims in PRUNE; exit %d \n\n", brednelims);
843  i = PRUNE_MAXREDROUNDS;
844  }
845 
846 
847  /* delete all vertices not reachable from the root */
848  if( graph_pc_isRootedPcMw(prunegraph) )
849  SCIP_CALL(reduce_unconnectedRpcRmw(scip, prunegraph, &offset));
850  else
851  SCIP_CALL(reduce_unconnected(scip, prunegraph));
852 
853  assert(graph_valid(scip, prunegraph));
854 
855  /* is the reduced graph still feasible? */
856  if( !graph_valid(scip, prunegraph) )
857  break;
858 
859  /* get number of remaining edges */
860  graph_get_nVET(prunegraph, &annodes, &anedges, &anterms);
861 
862  reductbound = getRedBound(i + 1, anedges);
863 
864  SCIP_CALL( reduce_solInit(scip, prunegraph, TRUE, &(redsol)) );
865  SCIP_CALL( reduce_solAddNodesol(prunegraph, solnode, redsol) );
866 
867  /* reduce graph */
868  if( pc )
869  {
870  SCIP_CALL( reduce_redLoopPc(scip, redsol, prunegraph, vnoi, path, nodearrreal, heap, state,
871  vbase, nodearrint, edgearrint, nodearrint2, nodearrchar, FALSE, FALSE, FALSE, reductbound, FALSE, TRUE, TRUE) );
872  }
873  else if( mw )
874  {
875  SCIP_CALL( reduce_redLoopMw(scip, redsol, prunegraph, vnoi, nodearrreal, state,
876  vbase, nodearrint, nodearrchar, FALSE, FALSE, FALSE, reductbound, FALSE, TRUE) );
877  }
878  else
879  {
880  RPARAMS parameters = { .dualascent = FALSE, .boundreduce = FALSE, .nodereplacing = TRUE, .reductbound_min = PRUNE_MINREDELIMS,
881  .reductbound = reductbound, .userec = FALSE, .fullreduce = FALSE, .usestrongreds = TRUE };
882  BIDECPARAMS decparameters = { .depth = 0, .maxdepth = 2, .newLevelStarted = FALSE };
883  REDBASE redbase = { .redparameters = &parameters, .bidecompparams = &decparameters,
884  .solnode = NULL, .redsol = redsol,
885  .vnoi = vnoi, .path = path, .heap = heap,
886  .nodearrreal = nodearrreal,
887  .state = state, .vbase = vbase, .nodearrint = nodearrint,
888  .edgearrint = edgearrint, .nodearrint2 = nodearrint2, .nodearrchar = nodearrchar };
889 
890  SCIP_CALL( reduce_redLoopStp(scip, prunegraph, &redbase) );
891  }
892 
893  reduce_solGetNodesol(prunegraph, redsol, solnode);
894 
895  offset += reduce_solGetOffset(redsol);
896  reduce_solFree(scip, &(redsol));
897 
898  /* delete all vertices not reachable from the root */
899  if( graph_pc_isRootedPcMw(prunegraph) )
900  SCIP_CALL(reduce_unconnectedRpcRmw(scip, prunegraph, &offset));
901  else
902  SCIP_CALL(reduce_unconnected(scip, prunegraph));
903 
904  graph_get_nVET(prunegraph, &annodes, &anedges, &anterms);
905 
906  if( anterms <= 2 )
907  {
908  SCIPdebugMessage("less than two terminals, break! \n");
909  SCIP_CALL( computeNewSols(scip, g, prunegraph, nodearrint, solnode, soledge, globalsoledge,
910  &globalobj, TRUE, TRUE, success) );
911  break;
912  }
913  } /* reduction loop */
914  } /* main prune loop */
915 
916  graph_path_exit(scip, prunegraph);
917 
918  *success = TRUE;
919  assert(solstp_isValid(scip, g, globalsoledge));
920 
921  SCIPdebugMessage("obj of best prune sol: %f \n", solstp_getObjBounded(g, globalsoledge, 0.0, nedges));
922 
923  BMScopyMemoryArray(soledge, globalsoledge, nedges);
924 
925  /* free memory */
926  graph_free(scip, &prunegraph, TRUE);
927 
928  SCIPfreeBufferArray(scip, &path);
929  SCIPfreeBufferArray(scip, &vnoi);
930  SCIPfreeBufferArray(scip, &nodearrint2);
931  SCIPfreeBufferArray(scip, &edgearrint);
932  SCIPfreeBufferArray(scip, &nodearrint);
933  SCIPfreeBufferArray(scip, &vbase);
934  SCIPfreeBufferArray(scip, &nodearrreal);
935  SCIPfreeBufferArray(scip, &state);
936  SCIPfreeBufferArray(scip, &heap);
937  SCIPfreeBufferArray(scip, &nodearrchar);
938  SCIPfreeBufferArray(scip, &costrev);
939  SCIPfreeBufferArray(scip, &cost);
940  SCIPfreeBufferArray(scip, &solnode);
941  SCIPfreeBufferArray(scip, &globalsoledge);
942 
943  if( probtype == STP_RSMT || probtype == STP_OARSMT || probtype == STP_GSTP )
944  g->stp_type = probtype;
945 
946  return SCIP_OKAY;
947 }
948 
949 
950 /** creates the prune primal heuristic and includes it in SCIP */
952  SCIP* scip /**< SCIP data structure */
953  )
954 {
955  SCIP_HEURDATA* heurdata;
956  SCIP_HEUR* heur;
957 
958  /* create prune primal heuristic data */
959  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
960 
961  /* include primal heuristic */
962  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
964  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecPrune, heurdata) );
965 
966  assert(heur != NULL);
967 
968  /* set non fundamental callbacks via setter functions */
969  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyPrune) );
970  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreePrune) );
971  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitPrune) );
972  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolPrune) );
973  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolPrune) );
974 
975  /* add prune primal heuristic parameters */
976  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/maxfreq",
977  "should the heuristic be executed at maximum frequeny?",
978  &heurdata->maxfreq, FALSE, DEFAULT_PRUNE_MAXFRQ, NULL, NULL) );
979 
980  return SCIP_OKAY;
981 }
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:233
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
static void setNodeSolArray(const GRAPH *g, SCIP_Real *RESTRICT uborg, int *RESTRICT solnode, const int *soledge)
Definition: heur_prune.c:86
SCIP_RETCODE SCIPStpHeurPruneRun(SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success, const SCIP_Bool withinitialsol, const SCIP_Bool reducegraph)
Definition: heur_prune.c:599
#define HEUR_TIMING
Definition: heur_prune.c:53
int *RESTRICT head
Definition: graphdefs.h:224
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_edge.c:368
int source
Definition: graphdefs.h:195
SCIP_Bool graph_pc_isRootedPcMw(const GRAPH *)
static int getRedBound(int nround, int nedges)
Definition: heur_prune.c:191
SCIP_RETCODE SCIPStpHeurPruneUpdateSols(SCIP *scip, GRAPH *g, GRAPH *prunegraph, int *solnode, int *soledge, int *globalsoledge, SCIP_Real *globalobj, SCIP_Bool incumbentgiven, SCIP_Bool *success)
Definition: heur_prune.c:489
#define Is_term(a)
Definition: graphdefs.h:102
static SCIP_DECL_HEURINITSOL(heurInitsolPrune)
Definition: heur_prune.c:303
Constraint handler for Steiner problems.
signed int edge
Definition: graphdefs.h:287
SCIP_Bool graph_valid(SCIP *, const GRAPH *)
Definition: graph_base.c:1480
SCIP_RETCODE reduce_solInit(SCIP *, const GRAPH *, SCIP_Bool, REDSOL **)
Definition: reduce_sol.c:687
int terms
Definition: graphdefs.h:192
SCIP_VAR ** SCIPprobdataGetVars(SCIP *scip)
static SCIP_RETCODE computeNewSols(SCIP *scip, GRAPH *g, GRAPH *prunegraph, int *nodearrint, int *solnode, int *soledge, int *globalsoledge, SCIP_Real *globalobj, SCIP_Bool incumbentgiven, SCIP_Bool beFast, SCIP_Bool *success)
Definition: heur_prune.c:131
SCIP_RETCODE reduce_redLoopPc(SCIP *, REDSOL *, GRAPH *, PATH *, PATH *, SCIP_Real *, int *, int *, int *, int *, int *, int *, STP_Bool *, SCIP_Bool, SCIP_Bool, SCIP_Bool, int, SCIP_Bool, SCIP_Bool, SCIP_Bool)
Definition: reduce_base.c:1896
#define HEUR_DISPCHAR
Definition: heur_prune.c:48
SCIP_RETCODE solstp_getOrg(SCIP *scip, const GRAPH *transgraph, const GRAPH *orggraph, const int *transsoledge, int *orgsoledge)
Definition: solstp.c:2148
void graph_mark(GRAPH *)
Definition: graph_base.c:1130
int norgmodeledges
Definition: graphdefs.h:215
includes methods for Steiner tree problem solutions
SCIP_RETCODE SCIPStpHeurTMRun(SCIP *scip, enum PCMW_TmMode pcmw_tmmode, GRAPH *graph, int *starts, const SCIP_Real *prize, int *best_result, int runs, int bestincstart, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *hopfactor, SCIP_Real *nodepriority, SCIP_Bool *success)
Definition: heur_tm.c:3418
void graph_free(SCIP *, GRAPH **, SCIP_Bool)
Definition: graph_base.c:796
void graph_pc_2org(SCIP *, GRAPH *)
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
Definition: graph_path.c:480
#define FALSE
Definition: def.h:87
SCIP_RETCODE reduce_boundPruneHeur(SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, const int *, const int *, int *, int)
Definition: reduce_bnd.c:1237
Problem data for stp problem.
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
SCIP_RETCODE reduce_redLoopMw(SCIP *, REDSOL *, GRAPH *, PATH *, SCIP_Real *, int *, int *, int *, STP_Bool *, STP_Bool, STP_Bool, STP_Bool, int, SCIP_Bool, SCIP_Bool)
Definition: reduce_base.c:1771
void reduce_solGetNodesol(const GRAPH *, REDSOL *, int *)
Definition: reduce_sol.c:1176
int SCIPprobdataGetNVars(SCIP *scip)
#define PRUNE_TMRUNS
Definition: heur_prune.c:57
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:108
#define STP_SPG
Definition: graphdefs.h:42
#define SCIPdebugMessage
Definition: pub_message.h:87
#define FARAWAY
Definition: graphdefs.h:89
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1362
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
int *RESTRICT mark
Definition: graphdefs.h:198
SCIP_RETCODE SCIPStpIncludeHeurPrune(SCIP *scip)
Definition: heur_prune.c:951
#define STP_RSMT
Definition: graphdefs.h:49
static SCIP_DECL_HEURCOPY(heurCopyPrune)
Definition: heur_prune.c:258
static SCIP_DECL_HEUREXEC(heurExecPrune)
Definition: heur_prune.c:335
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:217
SCIP_Bool withInexactReductions
Definition: graphdefs.h:266
void graph_pc_2trans(SCIP *, GRAPH *)
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1441
SCIP_Bool extended
Definition: graphdefs.h:267
int stp_type
Definition: graphdefs.h:264
void graph_get_nVET(const GRAPH *, int *, int *, int *)
Definition: graph_stats.c:571
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
SCIP_Real SCIPprobdataGetOffset(SCIP *scip)
void SCIPStpHeurTMCompStarts(GRAPH *graph, int *starts, int *runs)
Definition: heur_tm.c:2879
SCIP_RETCODE graph_initHistory(SCIP *, GRAPH *)
Definition: graph_base.c:695
SCIP_RETCODE SCIPprobdataAddNewSol(SCIP *scip, SCIP_Real *nval, SCIP_HEUR *heur, SCIP_Bool *success)
int *RESTRICT grad
Definition: graphdefs.h:201
SCIP_RETCODE reduce_unconnected(SCIP *, GRAPH *)
#define HEUR_FREQOFS
Definition: heur_prune.c:51
SCIP_Bool dualascent
Definition: reducedefs.h:77
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
Definition: sol.c:2604
#define STP_DHCSTP
Definition: graphdefs.h:52
SCIP_Real reduce_solGetOffset(const REDSOL *)
Definition: reduce_sol.c:1137
#define MAXNEDGES
Definition: heur_prune.c:62
SCIP_RETCODE SCIPStpHeurLocalRun(SCIP *scip, GRAPH *graph, int *solEdges)
Definition: heur_local.c:3883
#define STP_RMWCSP
Definition: graphdefs.h:54
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
void reduce_solFree(SCIP *, REDSOL **)
Definition: reduce_sol.c:818
#define STP_PCSPG
Definition: graphdefs.h:44
static void setMinMaxElims(SCIP *scip, int *minnelims, int *lminnelims, int annodes, int anedges, int anterms, int nround, int maxrounds)
Definition: heur_prune.c:206
#define LT(a, b)
Definition: portab.h:81
#define STP_OARSMT
Definition: graphdefs.h:50
Improvement heuristic for Steiner problems.
unsigned char STP_Bool
Definition: portab.h:34
reduction-based primal heuristic for Steiner problems
void SCIPStpHeurTMBuildTree(SCIP *scip, GRAPH *g, PATH *mst, const SCIP_Real *cost, SCIP_Real *objresult, int *connected)
Definition: heur_tm.c:2932
SCIP_Real solstp_getObjBounded(const GRAPH *g, const int *soledge, SCIP_Real offset, int nedges)
Definition: solstp.c:1833
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:84
int *RESTRICT tail
Definition: graphdefs.h:223
#define MAX(x, y)
Definition: tclique_def.h:83
#define HEUR_DESC
Definition: heur_prune.c:47
static SCIP_DECL_HEUREXITSOL(heurExitsolPrune)
Definition: heur_prune.c:326
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1435
Constraint handler for linear constraints in their most general form, .
void graph_path_exit(SCIP *, GRAPH *)
Definition: graph_path.c:515
#define CONNECT
Definition: graphdefs.h:87
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
#define HEUR_USESSUBSCIP
Definition: heur_prune.c:54
#define PRUNE_MINREDELIMS
Definition: heur_prune.c:59
#define PRUNE_MAXREDROUNDS
Definition: heur_prune.c:60
#define MAXNTERMINALS
Definition: heur_prune.c:61
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2304
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
#define HEUR_MAXDEPTH
Definition: heur_prune.c:52
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:962
SCIP_RETCODE reduce_unconnectedRpcRmw(SCIP *, GRAPH *, SCIP_Real *)
SCIP_Real * cost
Definition: graphdefs.h:221
#define HEUR_PRIORITY
Definition: heur_prune.c:49
SCIP_RETCODE SCIPStpHeurTMBuildTreePcMw(SCIP *scip, const GRAPH *g, SCIP_Bool useRootSym, PATH *mst, const SCIP_Real *cost, SCIP_Real *objresult, int *connected)
Definition: heur_tm.c:3012
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
SCIP_RETCODE reduce_solAddNodesol(const GRAPH *, const int *, REDSOL *)
Definition: reduce_sol.c:1150
#define SCIP_Real
Definition: def.h:177
#define DEFAULT_PRUNE_MAXFRQ
Definition: heur_prune.c:56
SCIP_Real * SCIPprobdataGetXval(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE graph_copy(SCIP *, const GRAPH *, GRAPH **)
Definition: graph_base.c:939
shortest paths based primal heuristics for Steiner problems
int edges
Definition: graphdefs.h:219
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
#define STP_GSTP
Definition: graphdefs.h:53
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
RPARAMS * redparameters
Definition: reducedefs.h:102
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define UNKNOWN
Definition: sepa_mcf.c:4095
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
#define nnodes
Definition: gastrans.c:65
static SCIP_DECL_HEURINIT(heurInitPrune)
Definition: heur_prune.c:293
SCIP_RETCODE reduce_redLoopStp(SCIP *, GRAPH *, REDBASE *)
Definition: reduce_base.c:2074
#define HEUR_NAME
Definition: heur_prune.c:46
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1352
static SCIP_DECL_HEURFREE(heurFreePrune)
Definition: heur_prune.c:272
includes various reduction methods for Steiner tree problems
default SCIP plugins
#define STP_RPCSPG
Definition: graphdefs.h:45
#define STP_MWCSP
Definition: graphdefs.h:51
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2635
#define HEUR_FREQ
Definition: heur_prune.c:50
SCIP callable library.
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
int norgmodelknots
Definition: graphdefs.h:187