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