Scippy

SCIP

Solving Constraint Integer Programs

heur_slackprune.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-2018 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_slackprune.c
17  * @brief dual-ascent and reduction based primal heuristic for Steiner problems
18  * @author Daniel Rehfeldt
19  *
20  * This file implements a dual-ascent and reduction based heuristic for Steiner problems. It is based on an approach
21  * described in T. Polzin's "Algorithms for the Steiner problem in networks".
22  *
23  * A list of all interface methods can be found in heur_slackprune.h
24  *
25  */
26 
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
28 #include <assert.h>
29 #include <string.h>
30 #include <stdio.h>
31 #include "scip/scip.h"
32 #include "scip/scipdefplugins.h"
33 #include "scip/cons_linear.h"
34 #include "heur_slackprune.h"
35 #include "heur_ascendprune.h"
36 #include "heur_local.h"
37 #include "heur_prune.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 #include "prop_stp.h"
44 
45 #define HEUR_NAME "slackprune"
46 #define HEUR_DESC "Reduction based heuristic for Steiner problems"
47 #define HEUR_DISPCHAR 'S'
48 #define HEUR_PRIORITY 1
49 #define HEUR_FREQ 1
50 #define HEUR_FREQOFS 0
51 #define HEUR_MAXDEPTH -1
52 #define HEUR_TIMING (SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE)
53 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
54 
55 #define DEFAULT_SLACKPRUNE_MAXFREQ FALSE /**< executions of the heuristic at maximum frequency? */
56 #define SLACKPRUNE_MINREDELIMS 2 /**< minimum number of eliminations for reduction package when called by slack-and-prune heuristic */
57 #define SLACKPRUNE_MAXREDROUNDS 10 /**< maximum number of reduction rounds in slack-prune heuristic */
58 #define SLACKPRUNE_MINSTALLPROPORTION 0.25 /**< minimum proportion of arcs to be fixed before restarting slack-prune heuristic */
59 #define SLACKPRUNE_MAXSTALLPROPORTION 0.5 /**< maximum proportion of arcs to be fixed before restarting slack-prune heuristic */
60 #define BREAKONERROR FALSE
61 #define MAXNTERMINALS 500
62 #define MAXNEDGES 10000
63 #define SLACK_MAXTOTNEDGES 5000
64 
65 #ifdef WITH_UG
66 extern
67 int getUgRank(void);
68 #endif
69 
70 /*
71  * Data structures
72  */
73 
74 /** primal heuristic data */
75 struct SCIP_HeurData
76 {
77  int lastnfixededges; /**< number of fixed edges before the previous run */
78  int bestsolindex; /**< best solution during the previous run */
79  int nfailures; /**< number of failures since last successful call */
80  SCIP_Bool maxfreq; /**< should the heuristic be called at maximum frequency? */
81 };
82 
83 /*
84  * Local methods
85  */
86 
87 /* get reduction bound */
88 static
90  int nrounds,
91  int nedges
92  )
93 {
94  if( nrounds == 0)
95  return (MAX(nedges / 2000, SLACKPRUNE_MINREDELIMS));
96  if( nrounds == 1)
97  return (MAX(nedges / 1000, SLACKPRUNE_MINREDELIMS));
98  return(MAX(nedges / 500, SLACKPRUNE_MINREDELIMS));
99 }
100 
101 
102 static
104  SCIP* scip,
105  int* minnelims,
106  int* lminnelims,
107  int annodes,
108  int anedges,
109  int anterms,
110  int nround,
111  int maxnrounds
112  )
113 {
114  int min;
115  int totminnelims;
116  SCIP_Real factor;
117 
118  assert(scip != NULL);
119  assert(minnelims != NULL);
120  assert(lminnelims != NULL);
121  assert(annodes > 0);
122  assert(nround >= 0);
123  assert(maxnrounds >= 1);
124 
125  anedges = anedges / 2;
126 
127  totminnelims = MAX(SLACKPRUNE_MINREDELIMS, (anedges / 25));
128 
129  min = (int) (anedges * 0.15);
130  min -= (int) (((double) min * anterms) / (annodes));
131  min = MAX(min, 1);
132 
133  factor = (double) anedges / min;
134  factor = ((double) nround / (2.5 * maxnrounds)) * factor;
135 #if 1
136  if( SCIPisGT(scip, factor, 1.0) )
137  {
138  SCIP_Real tmp = min * factor;
139  min = (int) tmp;
140  }
141 #endif
142  min = MAX(totminnelims, min);
143 
144  min = MIN(min, (anedges - 1));
145  min = MAX(min, 1);
146 
147  *lminnelims = min / 2;
148  *lminnelims = MAX(*lminnelims, 1);
149 
150  *minnelims = min;
151 
152 }
153 
154 static
156  GRAPH* graph,
157  int* soledge,
158  int* solnode,
159  int nnodes,
160  int nnedges
161  )
162 {
163  int j;
164  int e;
165 
166  for( j = 0; j < nnodes; j++ )
167  solnode[j] = UNKNOWN;
168 
169  /* reset vertices that are to be kept */
170  for( e = 0; e < nnedges; e++ )
171  {
172  if( soledge[e] == CONNECT )
173  {
174  solnode[graph->tail[e]] = CONNECT;
175  solnode[graph->head[e]] = CONNECT;
176  }
177  }
178 }
179 
180 /*
181  * Callback methods of primal heuristic
182  */
183 
184 #if 0
185 /** for debug purposes only */
186 static
187 SCIP_RETCODE printGraph(
188  SCIP* scip,
189  const GRAPH* graph, /**< Graph to be printed */
190  const char filename, /**< Name of the output file */
191  int* result
192  )
193 {
194  char label[SCIP_MAXSTRLEN];
195  FILE* file;
196  int e;
197  int n;
198  int m;
199  STP_Bool* stnodes;
200  SCIP_CALL( SCIPallocBufferArray(scip, &stnodes, graph->knots ) );
201 
202  assert(graph != NULL);
203  file = fopen((filename != NULL) ? filename : "graphX.gml", "w");
204 
205  for( e = 0; e < graph->knots; e++ )
206  {
207  stnodes[e] = FALSE;
208  }
209  for( e = 0; e < graph->edges; e++ )
210  {
211  if( result[e] == CONNECT )
212  {
213  stnodes[graph->tail[e]] = TRUE;
214  stnodes[graph->head[e]] = TRUE;
215  }
216  }
217 
218  /* write GML format opening, undirected */
219  SCIPgmlWriteOpening(file, FALSE);
220 
221  /* write all nodes, discriminate between root, terminals and the other nodes */
222  e = 0;
223  m = 0;
224  for( n = 0; n < graph->knots; ++n )
225  {
226  if( stnodes[n] )
227  {
228  if( n == graph->source )
229  {
230  (void)SCIPsnprintf(label, SCIP_MAXSTRLEN, "(%d) Root", n);
231  SCIPgmlWriteNode(file, (unsigned int)n, label, "rectangle", "#666666", NULL);
232  m = 1;
233  }
234  else if( graph->term[n] == 0 )
235  {
236  (void)SCIPsnprintf(label, SCIP_MAXSTRLEN, "(%d) Terminal %d", n, e + 1);
237  SCIPgmlWriteNode(file, (unsigned int)n, label, "circle", "#ff0000", NULL);
238  e += 1;
239  }
240  else
241  {
242  (void)SCIPsnprintf(label, SCIP_MAXSTRLEN, "(%d) Node %d", n, n + 1 - e - m);
243  SCIPgmlWriteNode(file, (unsigned int)n, label, "circle", "#336699", NULL);
244  }
245  }
246  }
247 
248  /* write all edges (undirected) */
249  for( e = 0; e < graph->edges; e ++ )
250  {
251  if( result[e] == CONNECT )
252  {
253  (void)SCIPsnprintf(label, SCIP_MAXSTRLEN, "%8.2f", graph->cost[e]);
254 
255  SCIPgmlWriteEdge(file, (unsigned int)graph->tail[e], (unsigned int)graph->head[e], label, "#ff0000");
256  }
257  }
258  SCIPfreeBufferArray(scip, &stnodes);
259  /* write GML format closing */
260  SCIPgmlWriteClosing(file);
261 
262  return SCIP_OKAY;
263 }
264 #endif
265 
266 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
267 static
268 SCIP_DECL_HEURCOPY(heurCopySlackPrune)
269 { /*lint --e{715}*/
270  assert(scip != NULL);
271  assert(heur != NULL);
272  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
273 
274  /* call inclusion method of primal heuristic */
276 
277  return SCIP_OKAY;
278 }
279 
280 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
281 static
282 SCIP_DECL_HEURFREE(heurFreeSlackPrune)
283 { /*lint --e{715}*/
284  SCIP_HEURDATA* heurdata;
285 
286  assert(heur != NULL);
287  assert(scip != NULL);
288 
289  /* get heuristic data */
290  heurdata = SCIPheurGetData(heur);
291  assert(heurdata != NULL);
292 
293  /* free heuristic data */
294  SCIPfreeMemory(scip, &heurdata);
295  SCIPheurSetData(heur, NULL);
296 
297  return SCIP_OKAY;
298 }
299 
300 
301 /** initialization method of primal heuristic (called after problem was transformed) */
302 
303 static
304 SCIP_DECL_HEURINIT(heurInitSlackPrune)
305 { /*lint --e{715}*/
306 
307 
308  return SCIP_OKAY;
309 }
310 
311 
312 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
313 static
314 SCIP_DECL_HEURINITSOL(heurInitsolSlackPrune)
315 { /*lint --e{715}*/
316  SCIP_HEURDATA* heurdata;
317 
318  assert(heur != NULL);
319  assert(scip != NULL);
320 
321  /* get heuristic's data */
322  heurdata = SCIPheurGetData(heur);
323 
324  assert(heurdata != NULL);
325 
326  /* initialize data */
327  heurdata->nfailures = 0;
328  heurdata->bestsolindex = -1;
329  heurdata->lastnfixededges = -1;
330 
331  return SCIP_OKAY;
332 }
333 
334 
335 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
336 static
337 SCIP_DECL_HEUREXITSOL(heurExitsolSlackPrune)
338 { /*lint --e{715}*/
339 
340 
341  return SCIP_OKAY;
342 }
343 
344 
345 /** execution method of primal heuristic */
346 static
347 SCIP_DECL_HEUREXEC(heurExecSlackPrune)
348 { /*lint --e{715}*/
349  SCIP_HEURDATA* heurdata;
350  SCIP_PROBDATA* probdata;
351  SCIP_VAR** vars;
352  SCIP_SOL* bestsol;
353  GRAPH* graph;
354  SCIP_Real* xval;
355  SCIP_Bool success;
356  int e;
357  int nvars;
358  int nedges;
359  int* soledge;
360 
361  assert(heur != NULL);
362  assert(scip != NULL);
363  assert(result != NULL);
364  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
365 
366  /* get heuristic data */
367  heurdata = SCIPheurGetData(heur);
368  assert(heurdata != NULL);
369 
370  /* get problem data */
371  probdata = SCIPgetProbData(scip);
372  assert(probdata != NULL);
373 
374  /* get graph */
375  graph = SCIPprobdataGetGraph(probdata);
376  assert(graph != NULL);
377 
378  nedges = graph->edges;
379  *result = SCIP_DIDNOTRUN;
380 
381  /* if not STP like variant, return */
382  if( graph->stp_type != STP_SPG && graph->stp_type != STP_RSMT && graph->stp_type != STP_OARSMT && graph->stp_type != STP_GSTP )
383  return SCIP_OKAY;
384 
385  if( (graph->edges > MAXNEDGES) && (graph->terms > MAXNTERMINALS) )
386  return SCIP_OKAY;
387 
388  if( !(heurdata->maxfreq) && heurdata->nfailures > 0 )
389  return SCIP_OKAY;
390 
391  /* get best current solution */
392  bestsol = SCIPgetBestSol(scip);
393 
394  /* no solution available? */
395  if( bestsol == NULL )
396  return SCIP_OKAY;
397 
398  /* heuristic not at maximum or ...*/
399  if( !(heurdata->maxfreq)
400  /* has the new solution been found by this very heuristic or is new best solution available? */
401  || (SCIPsolGetHeur(bestsol) == heur || heurdata->bestsolindex == SCIPsolGetIndex(SCIPgetBestSol(scip))) )
402  {
403  if( heurdata->lastnfixededges >= 0 )
404  {
405  SCIP_Real stallproportion;
406 
407  stallproportion = (1.0 + heurdata->nfailures) * SLACKPRUNE_MINSTALLPROPORTION;
408 
409  if( SCIPisGT(scip, stallproportion, SLACKPRUNE_MAXSTALLPROPORTION) )
410  stallproportion = SLACKPRUNE_MAXSTALLPROPORTION;
411 
412  if( (SCIPStpNfixedEdges(scip) - heurdata->lastnfixededges) < (int) (stallproportion * nedges) )
413  return SCIP_OKAY;
414  }
415  }
416 
417  /* deactivate as expensive is too expensive to be reiterated todo: do this properly */
418  heurdata->nfailures = 1;
419 
420  xval = SCIPprobdataGetXval(scip, bestsol);
421 
422  if( xval == NULL )
423  return SCIP_OKAY;
424 
425  heurdata->lastnfixededges = SCIPStpNfixedEdges(scip);
426 
427  vars = SCIPprobdataGetVars(scip);
428  nvars = SCIPprobdataGetNVars(scip);
429 
430  assert(vars != NULL);
431 
432  /* allocate array to store primal solution */
433  SCIP_CALL( SCIPallocBufferArray(scip, &soledge, nedges) );
434 
435  for( e = 0; e < nedges; e++ )
436  {
437  if( SCIPisEQ(scip, xval[e], 1.0) )
438  soledge[e] = CONNECT;
439  else
440  soledge[e] = UNKNOWN;
441  }
442 
443  /* execute slackprune heuristic */
444  SCIP_CALL( SCIPStpHeurSlackPruneRun(scip, vars, graph, soledge, &success, FALSE, (graph->edges < SLACK_MAXTOTNEDGES)) );
445 
446  /* solution found by slackprune heuristic? */
447  if( success )
448  {
449  SCIP_SOL* sol;
450  SCIP_Real pobj;
451  SCIP_Real* nval;
452 
453  pobj = 0.0;
454 
455  /* allocate memory to store solution */
456  SCIP_CALL( SCIPallocBufferArray(scip, &nval, nvars) );
457 
458  for( e = 0; e < nedges; e++ )
459  {
460  if( soledge[e] == CONNECT )
461  {
462  nval[e] = 1.0;
463  pobj += graph->cost[e];
464  }
465  else
466  {
467  nval[e] = 0.0;
468  }
469  }
470 
471  SCIPdebugMessage("SP final solution: best: old %f, new %f \n", SCIPgetSolOrigObj(scip, bestsol), pobj + SCIPprobdataGetOffset(scip));
472 
473  /* try to add new solution to pool */
474  sol = NULL;
475  SCIP_CALL( SCIPprobdataAddNewSol(scip, nval, sol, heur, &success) );
476 
477  /* has solution been added? */
478  if( success )
479  {
480  SCIPdebugMessage("better solution added by SLACKPRUNE %f \n", pobj + SCIPprobdataGetOffset(scip));
481  *result = SCIP_FOUNDSOL;
482 
483  assert(graph_sol_valid(scip, graph, soledge));
484 
485  /* is the solution the new incumbent? */
486  if( SCIPisGT(scip, SCIPgetSolOrigObj(scip, bestsol) - SCIPprobdataGetOffset(scip), pobj) )
487  {
488  /* deactivated subsequent runs since heuristics seems to be to expensive */
489  heurdata->nfailures = 1;
490  }
491  else
492  {
493  success = FALSE;
494  }
495  }
496 
497  /* free memory */
498  SCIPfreeBufferArray(scip, &nval);
499  }
500  else
501  {
502  SCIPdebugMessage("slack-prune: solution not valid \n");
503  }
504 
505  /* solution could not be found, added or is not best? */
506  if( !success )
507  heurdata->nfailures++;
508 
509  /* store index of incumbent solution */
510  heurdata->bestsolindex = SCIPsolGetIndex(SCIPgetBestSol(scip));
511 
512  /* free memory */
513  SCIPfreeBufferArray(scip, &soledge);
514  SCIPdebugMessage("leaving slack and prune heuristic \n");
515 
516  return SCIP_OKAY;
517 }
518 
519 
520 /*
521  * primal heuristic specific interface methods
522  */
523 
524 /** execute slack-and-prune heuristic on given graph */
526  SCIP* scip, /**< SCIP data structure */
527  SCIP_VAR** vars, /**< problem variables or NULL */
528  GRAPH* g, /**< graph data structure */
529  int* soledge, /**< array to 1. provide and 2. return primal solution */
530  SCIP_Bool* success, /**< feasible solution found? */
531  SCIP_Bool reducegraph, /**< try to reduce graph initially? */
532  SCIP_Bool fullreduce /**< use full reduction techniques? */
533  )
534 {
535  GRAPH* prunegraph;
536  PATH* vnoi;
537  PATH* path;
538  GNODE** gnodearr;
539  SCIP_Real ubnew;
540  SCIP_Real ubbest;
541  SCIP_Real offsetnew;
542  SCIP_Real globalobj;
543  SCIP_Real* cost;
544  SCIP_Real* costrev;
545  SCIP_Real* nodearrreal;
546  int i;
547  int k;
548  int e;
549  int nterms;
550  int nnodes;
551  int nedges;
552  int anterms;
553  int anedges;
554  int annodes;
555  int probtype;
556  int minnelims;
557  int lminnelims;
558  int reductbound;
559  int* heap;
560  int* state;
561  int* vbase;
562  int* solnode;
563  int* edgearrint2;
564  int* nodearrint;
565  int* nodearrint2;
566  int* globalsoledge;
567  STP_Bool* nodearrchar;
568  STP_Bool* edgearrchar;
569 
570  assert(g != NULL);
571  assert(scip != NULL);
572  assert(soledge != NULL);
573  assert(graph_sol_valid(scip, g, soledge));
574 
575  nterms = g->terms;
576  nedges = g->edges;
577  nnodes = g->knots;
578  probtype = g->stp_type;
579 
580  /* allocate memory */
581  SCIP_CALL( SCIPallocBufferArray(scip, &solnode, nnodes) );
582  SCIP_CALL( SCIPallocBufferArray(scip, &cost, nedges) );
583  SCIP_CALL( SCIPallocBufferArray(scip, &costrev, nedges) );
584 
585  /* mark solution vertices */
586  for( k = 0; k < nnodes; k++ )
587  solnode[k] = UNKNOWN;
588 
589  ubbest = 0.0;
590 
591  /* set solution array and get solution value */
592  for( e = 0; e < nedges; e++ )
593  {
594  if( soledge[e] == CONNECT )
595  {
596  ubbest += g->cost[e];
597  solnode[g->tail[e]] = CONNECT;
598  solnode[g->head[e]] = CONNECT;
599  }
600  }
601 
602  globalobj = ubbest;
603 
604  /* set offset (within new graph) to 0.0 */
605  offsetnew = 0.0;
606 
607  /* allocate memory for reduction methods */
608  SCIP_CALL( SCIPallocBufferArray(scip, &gnodearr, nterms - 1) );
609  for( i = 0; i < nterms - 1; i++ )
610  {
611  SCIP_CALL( SCIPallocBlockMemory(scip, &(gnodearr[i])) ); /*lint !e866*/
612  }
613 
614  SCIP_CALL( SCIPallocBufferArray(scip, &globalsoledge, nedges) );
615  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrchar, nnodes) );
616  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrchar, nedges) );
617  SCIP_CALL( SCIPallocBufferArray(scip, &heap, nnodes + 1) );
618  SCIP_CALL( SCIPallocBufferArray(scip, &state, 4 * nnodes) );
619  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrreal, nnodes) );
620  SCIP_CALL( SCIPallocBufferArray(scip, &vbase, 4 * nnodes) );
621  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint, nnodes) );
622  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint2, nnodes) );
623  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrint2, nedges) );
624  SCIP_CALL( SCIPallocBufferArray(scip, &vnoi, 4 * nnodes) );
625  SCIP_CALL( SCIPallocBufferArray(scip, &path, nnodes) );
626 
627  BMScopyMemoryArray(globalsoledge, soledge, nedges);
628 
629 
630  if( probtype == STP_RSMT || probtype == STP_OARSMT || probtype == STP_GSTP )
631  g->stp_type = STP_SPG;
632 
633  /* copy the graph */
634  SCIP_CALL( graph_copy(scip, g, &prunegraph) );
635 
636  if( probtype == STP_RSMT || probtype == STP_OARSMT || probtype == STP_GSTP )
637  g->stp_type = probtype;
638 
639  /* set ancestors of the new graph */
640  SCIP_CALL( graph_init_history(scip, prunegraph) );
641 
642  reductbound = getRedBound(0, nedges);
643 
644  /* variables given? */
645  if( vars != NULL )
646  {
647  int nfixedges = 0;
648 
649  /* delete fixed edges from the new graph */
650  for( e = 0; e < nedges; e += 2 )
651  {
652  /* both e and its anti-parallel edge fixed to zero? */
653  if( SCIPvarGetUbLocal(vars[e]) < 0.5 && SCIPvarGetUbLocal(vars[e + 1]) < 0.5
654  && soledge[e] != CONNECT && soledge[e + 1] != CONNECT )
655  {
656  graph_edge_del(scip, prunegraph, e, TRUE);
657  nfixedges++;
658  }
659  }
660  SCIPdebugMessage("fixed edges in slack and prune: %d \n", nfixedges);
661 
662  if( nfixedges > reductbound && reducegraph )
663  {
664  graph_get_NVET(prunegraph, &annodes, &anedges, &anterms);
665  reductbound = getRedBound(0, anedges);
666  }
667  }
668 
669  SCIP_CALL( graph_path_init(scip, prunegraph) );
670 
671  /* perform initial reductions? */
672  if( reducegraph )
673  {
674  SCIP_CALL( redLoopStp(scip, prunegraph, vnoi, path, NULL, nodearrreal, cost, costrev, heap, state,
675  vbase, nodearrint, soledge, nodearrint2, solnode, nodearrchar, &offsetnew, -1.0, TRUE, FALSE, TRUE, reductbound, TRUE, fullreduce) );
676  }
677 
678  /* get number of remaining vertices, edges and terminals */
679  graph_get_NVET(prunegraph, &annodes, &anedges, &anterms);
680 
681  /* main reduction loop */
682  for( i = 0; i < SLACKPRUNE_MAXREDROUNDS && anterms > 2; i++ )
683  {
684  SCIP_Real obj;
685  SCIP_Bool apsuccess;
686  int danelims;
687 
688  /* update reduction bounds */
689  setMinMaxElims(scip, &minnelims, &lminnelims, annodes, anedges, anterms, i + 1, SLACKPRUNE_MAXREDROUNDS);
690 #if BREAKONERROR
691  if( minnelims > (anedges / 2) )
692  return SCIP_ERROR;
693 #endif
694 
695  /* perform reductions */
696  SCIP_CALL( reduce_daSlackPrune(scip, vars, prunegraph, vnoi, gnodearr, cost, costrev, nodearrreal, &ubnew,
697  soledge, edgearrint2, vbase, nodearrint, state, solnode, nodearrchar, edgearrchar, &danelims, minnelims, ((i == 0) && !reducegraph)) );
698 
699  /* delete all vertices not reachable from the root */
700  SCIP_CALL( level0(scip, prunegraph) );
701 
702  assert(graph_valid(prunegraph));
703 
704  graph_get_NVET(prunegraph, &annodes, &anedges, &anterms);
705 
706  if( anterms <= 2 )
707  break;
708 
709  SCIPdebugMessage("minelims %d really reduced: %d \n", minnelims, danelims);
710 
711  /* not enough reductions possible? */
712  if( danelims < lminnelims )
713  {
714  SCIPdebugMessage("too little elims in DA, break %d < %d\n\n", danelims, lminnelims);
716  }
717 
718  /* compute potential new guiding solution */
719  SCIP_CALL( SCIPStpHeurAscendPruneRun(scip, NULL, prunegraph, cost, soledge, nodearrint, prunegraph->source, nodearrchar, &apsuccess, FALSE) );
720 
721  /* solution found by ascend and prune? */
722  if( apsuccess )
723  {
724  SCIP_CALL( SCIPStpHeurLocalRun(scip, prunegraph, prunegraph->cost, soledge) );
725 
726  assert(graph_sol_valid(scip, prunegraph, soledge));
727 
728  SCIP_CALL( SCIPStpHeurPruneUpdateSols(scip, g, prunegraph, path, nodearrint, edgearrint2, solnode, soledge,
729  globalsoledge, nodearrchar, &globalobj, TRUE, success) );
730 
731  /* calculate objective value of solution */
732  obj = graph_sol_getObj(prunegraph->cost, soledge, offsetnew, nedges);
733 
734  /* obj <= incumbent objective value? */
735  if( SCIPisLE(scip, obj, ubbest) )
736  ubbest = obj;
737 
738  SCIPdebugMessage("old solution: %f new solution %f \n\n", ubbest + SCIPprobdataGetOffset(scip), obj + SCIPprobdataGetOffset(scip));
739  }
740 
741  /* get number of remaining edges */
742  graph_get_NVET(prunegraph, &annodes, &anedges, &anterms);
743 
744  reductbound = getRedBound(i, anedges);
745 
746  /* reduce graph, using the new upper bound and not letting BND eliminate solution edges */
747  SCIP_CALL( redLoopStp(scip, prunegraph, vnoi, path, NULL, nodearrreal, cost, costrev, heap, state,
748  vbase, nodearrint, soledge, nodearrint2, solnode, nodearrchar, &offsetnew, -1.0, TRUE, FALSE, TRUE, reductbound, TRUE, fullreduce) );
749 
750  /* graph vanished? */
751  if( prunegraph->grad[prunegraph->source] == 0 )
752  break;
753 
754  /* get number of remaining edges */
755  graph_get_NVET(prunegraph, &annodes, &anedges, &anterms);
756 
757  } /* reduction loop */
758 
759  SCIP_CALL(SCIPStpHeurLocalRun(scip, g, g->cost, globalsoledge));
760 
761  graph_path_exit(scip, prunegraph);
762 
763  *success = graph_sol_valid(scip, g, globalsoledge);
764  BMScopyMemoryArray(soledge, globalsoledge, nedges);
765 
766 #if BREAKONERROR
767  if( !(*success) )
768  {
769  printf("slack prune solution not valid %d \n", 0);
770  return SCIP_ERROR;
771  }
772 #endif
773 
774  /* free memory */
775  graph_free(scip, &prunegraph, TRUE);
776 
777  SCIPfreeBufferArray(scip, &path);
778  SCIPfreeBufferArray(scip, &vnoi);
779  SCIPfreeBufferArray(scip, &edgearrint2);
780  SCIPfreeBufferArray(scip, &nodearrint2);
781  SCIPfreeBufferArray(scip, &nodearrint);
782  SCIPfreeBufferArray(scip, &vbase);
783  SCIPfreeBufferArray(scip, &nodearrreal);
784  SCIPfreeBufferArray(scip, &state);
785  SCIPfreeBufferArray(scip, &heap);
786  SCIPfreeBufferArray(scip, &edgearrchar);
787  SCIPfreeBufferArray(scip, &nodearrchar);
788  SCIPfreeBufferArray(scip, &globalsoledge);
789 
790  for( i = nterms - 2; i >= 0; i-- )
791  SCIPfreeBlockMemory(scip, &(gnodearr[i]));
792  SCIPfreeBufferArray(scip, &gnodearr);
793 
794  SCIPfreeBufferArray(scip, &costrev);
795  SCIPfreeBufferArray(scip, &cost);
796  SCIPfreeBufferArray(scip, &solnode);
797 
798  return SCIP_OKAY;
799 }
800 
801 
802 /** execute slack-and-prune heuristic on given graph */
804  SCIP* scip, /**< SCIP data structure */
805  SCIP_VAR** vars, /**< problem variables or NULL */
806  GRAPH* g, /**< graph data structure */
807  int* soledge, /**< array to 1. provide and 2. return primal solution */
808  SCIP_Bool* success /**< feasible solution found? */
809  )
810 {
811  GRAPH* prunegraph;
812  PATH* vnoi;
813  PATH* path;
814  GNODE** gnodearr;
815  SCIP_Real ubbest;
816  SCIP_Real offsetnew;
817  SCIP_Real* cost;
818  SCIP_Real* costrev;
819  SCIP_Real* nodearrreal;
820  int i;
821  int k;
822  int e;
823  int nterms;
824  int nnodes;
825  int nedges;
826  int anterms;
827  int anedges;
828  int annodes;
829  int minnelims;
830  int lminnelims;
831  int reductbound;
832  int nprunenodes;
833  int npruneedges;
834  int* state;
835  int* vbase;
836  int* solnode;
837  int* edgearrint;
838  int* nodearrint;
839  int* nodearrint2;
840  int* nodearrint3;
841  STP_Bool* nodearrchar;
842 
843  assert(g != NULL);
844  assert(scip != NULL);
845  assert(soledge != NULL);
846  assert(graph_sol_valid(scip, g, soledge));
847 
848  nterms = g->terms;
849  nedges = g->edges;
850  nnodes = g->knots;
851 
852  /* allocate memory */
853  SCIP_CALL( SCIPallocBufferArray(scip, &solnode, nnodes) );
854  SCIP_CALL( SCIPallocBufferArray(scip, &cost, nedges) );
855  SCIP_CALL( SCIPallocBufferArray(scip, &costrev, nedges) );
856 
857  /* mark solution vertices */
858  for( k = 0; k < nnodes; k++ )
859  solnode[k] = UNKNOWN;
860 
861  ubbest = 0.0;
862 
863  /* set solution array and get solution value (with respect to current, possibly reduced, graph) */
864  for( e = 0; e < nedges; e++ )
865  {
866  if( soledge[e] == CONNECT )
867  {
868  ubbest += g->cost[e];
869  solnode[g->tail[e]] = CONNECT;
870  solnode[g->head[e]] = CONNECT;
871  }
872  }
873 
874  /* set offset (within new graph) to 0.0 */
875  offsetnew = 0.0;
876 
877  /* allocate memory for reduction methods */
878  SCIP_CALL( SCIPallocBufferArray(scip, &gnodearr, nterms - 1) );
879  for( i = 0; i < nterms - 1; i++ )
880  {
881  SCIP_CALL( SCIPallocBuffer(scip, &gnodearr[i]) ); /*lint !e866*/
882  }
883 
884  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrreal, nnodes + 1) );
885  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint, nnodes + 1) );
886  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint2, nnodes) );
887  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint3, nnodes) );
888  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrchar, nnodes + 1) );
889  SCIP_CALL( SCIPallocBufferArray(scip, &state, 3 * nnodes) );
890  SCIP_CALL( SCIPallocBufferArray(scip, &vbase, 3 * nnodes) );
891  SCIP_CALL( SCIPallocBufferArray(scip, &vnoi, 3 * nnodes) );
892  SCIP_CALL( SCIPallocBufferArray(scip, &path, nnodes) );
893 
894  /* copy the graph */
895  SCIP_CALL( graph_copy(scip, g, &prunegraph) );
896 
897  /* set ancestors of the new graph */
898  SCIP_CALL( graph_init_history(scip, prunegraph) );
899 
900  edgearrint = soledge;
901 
902  /* variables given? */
903  if( vars != NULL )
904  {
905  /* delete fixed edges from the new graph */
906  for( e = 0; e < nedges; e += 2 )
907  {
908  /* both e and its anti-parallel edge fixed to zero? */
909  if( SCIPvarGetUbLocal(vars[e]) < 0.5 && SCIPvarGetUbLocal(vars[e + 1]) < 0.5
910  && soledge[e] != CONNECT && soledge[e + 1] != CONNECT && !Is_term(g->term[g->tail[e]]) && !Is_term(g->term[g->head[e]]) )
911  {
912  graph_edge_del(scip, prunegraph, e, TRUE);
913  }
914  }
915  }
916 
917  SCIP_CALL( graph_path_init(scip, prunegraph) );
918 
919  npruneedges = prunegraph->edges;
920  nprunenodes = prunegraph->knots;
921  prunegraph->norgmodeledges = npruneedges;
922  prunegraph->norgmodelknots = nprunenodes;
923 
924  /* get number of remaining vertices, edges and terminals */
925  graph_get_NVET(prunegraph, &annodes, &anedges, &anterms);
926 
927  /* main reduction loop */
928  for( i = 0; i < SLACKPRUNE_MAXREDROUNDS && anterms > 3; i++ )
929  {
930  SCIP_Real obj;
931  SCIP_Bool apsuccess;
932  int danelims;
933 
934  /* update reduction bounds */
935  setMinMaxElims(scip, &minnelims, &lminnelims, annodes, anedges, anterms, i + 1, SLACKPRUNE_MAXREDROUNDS);
936 
937 #if BREAKONERROR
938  if( minnelims > (anedges / 2) )
939  {
940  printf("too many elim %d \n", minnelims);
941  return SCIP_ERROR;
942  }
943 #endif
944 
945  /* perform heuristic reductions */
946  SCIP_CALL( reduce_daSlackPruneMw(scip, prunegraph, vnoi, gnodearr, cost, costrev, nodearrreal, vbase, nodearrint,
947  edgearrint, nodearrint2, solnode, nodearrchar, &danelims, minnelims, ((i == 0))) );
948 
949  updateSolNodeArray(prunegraph, edgearrint, solnode, nprunenodes, npruneedges);
950 
951  /* calculate objective value of solution */
952  obj = graph_sol_getObj(prunegraph->cost, edgearrint, offsetnew, npruneedges);
953 
954  ubbest = obj;
955 
956  /* delete all vertices not reachable from the root */
957  SCIP_CALL( level0(scip, prunegraph) );
958 
959  assert(graph_valid(prunegraph));
960 
961  /* get number of remaining vertices, edges and terminals */
962  graph_get_NVET(prunegraph, &annodes, &anedges, &anterms);
963 
964  /* update reduction bounds */
965  setMinMaxElims(scip, &minnelims, &lminnelims, annodes, anedges, anterms, i + 1, SLACKPRUNE_MAXREDROUNDS);
966 
967  if( anterms <= 3 )
968  {
969  SCIPdebugMessage("graph vanished in SLACKPRUNE \n\n");
970  break;
971  }
972 
973  SCIPdebugMessage("SP: minelimsx %d really reduced: %d \n", minnelims, danelims);
974 
975  /* not enough reductions possible? */
976  if( danelims < lminnelims )
977  {
978  SCIPdebugMessage("too little elims in DA OUT !! %d < %d\n\n", danelims, lminnelims);
980  }
981 
982  /* compute new guiding solution */
983  SCIP_CALL( SCIPStpHeurAscendPruneRun(scip, NULL, prunegraph, cost, edgearrint, vbase, -1, nodearrchar, &apsuccess, FALSE) );
984 
985  /* solution found by ascend and prune? */
986  if( apsuccess )
987  {
988  /* calculate objective value of solution */
989  obj = graph_sol_getObj(prunegraph->cost, edgearrint, offsetnew, npruneedges);
990 
991  SCIPdebugMessage(" old solution: %f AP solution %f \n", ubbest + SCIPprobdataGetOffset(scip), obj + SCIPprobdataGetOffset(scip));
992  SCIPdebugMessage("offsetnew %f \n", offsetnew);
993 
994  /* obj <= incumbent objective value? */
995  if( SCIPisLT(scip, obj, ubbest) )
996  updateSolNodeArray(prunegraph, edgearrint, solnode, nprunenodes, npruneedges);
997  }
998 
999  /* get number of remaining edges */
1000  graph_get_NVET(prunegraph, &annodes, &anedges, &anterms);
1001 
1002  reductbound = getRedBound(i, anedges);
1003 
1004  /* reduction loop */
1005  SCIP_CALL( redLoopMw(scip, prunegraph, vnoi, path, NULL, NULL, NULL, NULL, state,
1006  vbase, nodearrint, NULL, nodearrint2, nodearrint3, solnode, nodearrchar, &offsetnew, FALSE, FALSE, FALSE, reductbound, TRUE) );
1007 
1008  assert(graph_valid(prunegraph));
1009 
1010 #if BREAKONERROR
1011  if( !graph_valid(prunegraph) )
1012  {
1013  printf("SP: not valid2 %d \n", 0);
1014  return SCIP_ERROR;
1015  }
1016 #endif
1017 
1018  /* get number of remaining edges */
1019  graph_get_NVET(prunegraph, &annodes, &anedges, &anterms);
1020  } /* reduction loop */
1021 
1022  /* if graph not vanished, compute solution */
1023  if( prunegraph->grad[prunegraph->source] > 0 )
1024  {
1025  IDX** ancestors = prunegraph->ancestors;
1026  SCIP_Real objorg;
1027  SCIP_Real objprune;
1028 
1029  /* build solution on solnode nodes */
1030 
1031  for( e = 0; e < nedges; e++ )
1032  soledge[e] = UNKNOWN;
1033 
1034  for( k = 0; k < nnodes; k++ )
1035  nodearrchar[k] = (solnode[k] == CONNECT);
1036 
1037  SCIP_CALL( SCIPStpHeurTMPrunePc(scip, prunegraph, prunegraph->cost, soledge, nodearrchar) );
1038 
1039  for( k = 0; k < nnodes; k++ )
1040  nodearrchar[k] = FALSE;
1041 
1042  for( e = 0; e < nedges; e++ )
1043  if( soledge[e] == CONNECT )
1044  graph_sol_setNodeList(g, nodearrchar, ancestors[e]);
1045 
1046  /* calculate objective value of solution */
1047  objorg = graph_sol_getObj(prunegraph->cost, soledge, offsetnew, nedges);
1048 
1049  /* compute new solution on heuristically reduced graph */
1050 
1051 #ifdef SCIP_DEBUG
1052  graph_get_NVET(prunegraph, &annodes, &anedges, &anterms);
1053  printf("final SP anedges: %d anterms: %d \n", anedges, anterms);
1054 #endif
1055 
1056  SCIP_CALL( SCIPStpHeurPruneRun(scip, NULL, prunegraph, soledge, success, FALSE, TRUE) );
1057 
1058  if( !(*success) )
1059  {
1060 #if BREAKONERROR
1061  printf("Xfailed to build tree\n");
1062  return SCIP_ERROR;
1063 #endif
1064  goto TERMINATE;
1065  }
1066 
1067  /* calculate objective value of solution */
1068  objprune = graph_sol_getObj(prunegraph->cost, soledge, offsetnew, nedges);
1069 
1070  if( SCIPisLT(scip, objprune, objorg) )
1071  {
1072  /* mark vertices of solution found by prune heuristic */
1073 
1074  for( k = 0; k < nnodes; k++ )
1075  nodearrchar[k] = FALSE;
1076 
1077  for( e = 0; e < nedges; e++ )
1078  if( soledge[e] == CONNECT )
1079  graph_sol_setNodeList(g, nodearrchar, ancestors[e]);
1080 
1081  }
1082  }
1083  else
1084  {
1085  for( k = 0; k < nnodes; k++ )
1086  nodearrchar[k] = FALSE;
1087  }
1088 
1089  /* retransform edges fixed during graph reduction */
1090  graph_sol_setNodeList(g, nodearrchar, prunegraph->fixedges);
1091 
1092  SCIP_CALL( graph_sol_markPcancestors(scip, prunegraph->pcancestors, prunegraph->orgtail, prunegraph->orghead, nnodes,
1093  nodearrchar, NULL, NULL, NULL, NULL) );
1094 
1095  for( e = 0; e < nedges; e++ )
1096  soledge[e] = UNKNOWN;
1097 
1098  SCIP_CALL( SCIPStpHeurTMPrunePc(scip, g, g->cost, soledge, nodearrchar) );
1099  *success = graph_sol_valid(scip, g, soledge);
1100 
1101  TERMINATE:
1102 
1103  /* free memory */
1104  graph_path_exit(scip, prunegraph);
1105  graph_free(scip, &prunegraph, TRUE);
1106 
1107  SCIPfreeBufferArray(scip, &path);
1108  SCIPfreeBufferArray(scip, &vnoi);
1109  SCIPfreeBufferArray(scip, &vbase);
1110  SCIPfreeBufferArray(scip, &state);
1111  SCIPfreeBufferArray(scip, &nodearrchar);
1112  SCIPfreeBufferArray(scip, &nodearrint3);
1113  SCIPfreeBufferArray(scip, &nodearrint2);
1114  SCIPfreeBufferArray(scip, &nodearrint);
1115  SCIPfreeBufferArray(scip, &nodearrreal);
1116 
1117  for( i = nterms - 2; i >= 0; i-- )
1118  SCIPfreeBuffer(scip, &gnodearr[i]);
1119  SCIPfreeBufferArray(scip, &gnodearr);
1120 
1121  SCIPfreeBufferArray(scip, &costrev);
1122  SCIPfreeBufferArray(scip, &cost);
1123  SCIPfreeBufferArray(scip, &solnode);
1124 
1125  return SCIP_OKAY;
1126 }
1127 
1128 
1129 /** creates the slackprune primal heuristic and includes it in SCIP */
1131  SCIP* scip /**< SCIP data structure */
1132  )
1133 {
1134  SCIP_HEURDATA* heurdata;
1135  SCIP_HEUR* heur;
1136 
1137  /* create slackprune primal heuristic data */
1138  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
1139 
1140  /* include primal heuristic */
1141  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1143  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecSlackPrune, heurdata) );
1144 
1145  assert(heur != NULL);
1146 
1147  /* set non fundamental callbacks via setter functions */
1148  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopySlackPrune) );
1149  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeSlackPrune) );
1150  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitSlackPrune) );
1151  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolSlackPrune) );
1152  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolSlackPrune) );
1153 
1154  /* add slackprune primal heuristic parameters */
1155  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/maxfreq",
1156  "should the heuristic be executed at maximum frequeny?",
1157  &heurdata->maxfreq, FALSE, DEFAULT_SLACKPRUNE_MAXFREQ, NULL, NULL) );
1158 
1159 
1160  return SCIP_OKAY;
1161 }
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
Definition: grphpath.c:444
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:312
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:598
static volatile int nterms
Definition: interrupt.c:37
#define HEUR_MAXDEPTH
void graph_get_NVET(const GRAPH *, int *, int *, int *)
Definition: grphbase.c:3382
#define NULL
Definition: def.h:239
static void updateSolNodeArray(GRAPH *graph, int *soledge, int *solnode, int nnodes, int nnedges)
int *RESTRICT head
Definition: grph.h:96
int *RESTRICT orgtail
Definition: grph.h:97
Definition: grph.h:57
int source
Definition: grph.h:67
#define STP_GSTP
Definition: grph.h:49
Constraint handler for Steiner problems.
int SCIPStpNfixedEdges(SCIP *scip)
Definition: prop_stp.c:865
#define SCIP_MAXSTRLEN
Definition: def.h:260
SCIP_Bool graph_valid(const GRAPH *)
Definition: grphbase.c:4324
int terms
Definition: grph.h:64
SCIP_VAR ** SCIPprobdataGetVars(SCIP *scip)
SCIP_RETCODE graph_copy(SCIP *, const GRAPH *, GRAPH **)
Definition: grphbase.c:3896
SCIP_RETCODE graph_init_history(SCIP *, GRAPH *)
Definition: grphbase.c:3569
#define MAXNTERMINALS
static void setMinMaxElims(SCIP *scip, int *minnelims, int *lminnelims, int annodes, int anedges, int anterms, int nround, int maxnrounds)
int norgmodeledges
Definition: grph.h:88
void SCIPgmlWriteNode(FILE *file, unsigned int id, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor)
Definition: misc.c:485
SCIP_RETCODE reduce_daSlackPrune(SCIP *, SCIP_VAR **, GRAPH *, PATH *, GNODE **, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *, int *, STP_Bool *, STP_Bool *, int *, int, SCIP_Bool)
Definition: reduce_bnd.c:3279
void SCIPgmlWriteClosing(FILE *file)
Definition: misc.c:687
dual-ascent and reduction based primal heuristic for Steiner problems
reduction and dual-cost based primal heuristic for Steiner problems
#define FALSE
Definition: def.h:65
#define HEUR_PRIORITY
static SCIP_DECL_HEURINIT(heurInitSlackPrune)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10017
void graph_free(SCIP *, GRAPH **, SCIP_Bool)
Definition: grphbase.c:3674
Problem data for stp problem.
#define TRUE
Definition: def.h:64
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
void graph_path_exit(SCIP *, GRAPH *)
Definition: grphpath.c:466
int SCIPprobdataGetNVars(SCIP *scip)
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
SCIP_RETCODE SCIPStpHeurSlackPruneRunPcMw(SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success)
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
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:187
#define SCIPdebugMessage
Definition: pub_message.h:77
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define HEUR_NAME
#define DEFAULT_SLACKPRUNE_MAXFREQ
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1175
int *RESTRICT orghead
Definition: grph.h:98
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
static SCIP_DECL_HEURFREE(heurFreeSlackPrune)
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
SCIP_RETCODE SCIPStpHeurAscendPruneRun(SCIP *scip, SCIP_HEUR *heur, const GRAPH *g, const SCIP_Real *redcosts, int *edgearrint, int *nodearrint, int root, STP_Bool *nodearrchar, SCIP_Bool *solfound, SCIP_Bool addsol)
#define HEUR_TIMING
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:482
IDX * fixedges
Definition: grph.h:85
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:1409
#define CONNECT
Definition: grph.h:154
#define HEUR_FREQ
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:296
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1254
int stp_type
Definition: grph.h:127
IDX ** ancestors
Definition: grph.h:86
SCIP_RETCODE level0(SCIP *, GRAPH *)
Definition: reduce.c:153
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:248
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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)
#define SCIPallocBuffer(scip, ptr)
Definition: scip_mem.h:128
#define SLACKPRUNE_MAXSTALLPROPORTION
#define SLACKPRUNE_MINREDELIMS
int *RESTRICT grad
Definition: grph.h:73
static SCIP_DECL_HEURINITSOL(heurInitsolSlackPrune)
static SCIP_DECL_HEUREXITSOL(heurExitsolSlackPrune)
SCIP_Bool graph_sol_valid(SCIP *, const GRAPH *, const int *)
Definition: grphbase.c:3066
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
Definition: sol.c:2553
#define MAXNEDGES
void SCIPgmlWriteEdge(FILE *file, unsigned int source, unsigned int target, const char *label, const char *color)
Definition: misc.c:583
int knots
Definition: grph.h:62
#define SCIP_CALL(x)
Definition: def.h:351
IDX ** pcancestors
Definition: grph.h:87
SCIP_RETCODE SCIPStpHeurSlackPruneRun(SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success, SCIP_Bool reducegraph, SCIP_Bool fullreduce)
Improvement heuristic for Steiner problems.
reduction-based primal heuristic for Steiner problems
#define STP_SPG
Definition: grph.h:38
propagator for Steiner tree problems, using the LP reduced costs
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:62
#define SLACKPRUNE_MAXREDROUNDS
int *RESTRICT tail
Definition: grph.h:95
#define MIN(x, y)
Definition: def.h:209
static SCIP_DECL_HEUREXEC(heurExecSlackPrune)
SCIP_RETCODE graph_sol_markPcancestors(SCIP *, IDX **, const int *, const int *, int, STP_Bool *, STP_Bool *, int *, int *, int *)
Definition: grphbase.c:3288
int *RESTRICT term
Definition: grph.h:68
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:116
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1493
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:86
#define SCIPfreeBuffer(scip, ptr)
Definition: scip_mem.h:140
#define Is_term(a)
Definition: grph.h:168
#define MAX(x, y)
Definition: def.h:208
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2379
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:1020
SCIP_Real * cost
Definition: grph.h:94
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:264
#define SCIP_Real
Definition: def.h:150
SCIP_Real * SCIPprobdataGetXval(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE SCIPStpHeurTMPrunePc(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int *result, STP_Bool *connected)
Definition: heur_tm.c:168
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
int edges
Definition: grph.h:92
SCIP_RETCODE SCIPStpIncludeHeurSlackPrune(SCIP *scip)
static SCIP_DECL_HEURCOPY(heurCopySlackPrune)
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:70
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define UNKNOWN
Definition: sepa_mcf.c:4081
#define STP_RSMT
Definition: grph.h:45
SCIP_RETCODE reduce_daSlackPruneMw(SCIP *, GRAPH *, PATH *, GNODE **, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *, STP_Bool *, int *, int, SCIP_Bool)
Definition: reduce_bnd.c:4237
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:232
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17409
#define nnodes
Definition: gastrans.c:65
void SCIPgmlWriteOpening(FILE *file, SCIP_Bool directed)
Definition: misc.c:671
#define STP_OARSMT
Definition: grph.h:46
#define SLACK_MAXTOTNEDGES
#define HEUR_DESC
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1165
#define HEUR_DISPCHAR
default SCIP plugins
#define HEUR_FREQOFS
static int getRedBound(int nrounds, int nedges)
#define SLACKPRUNE_MINSTALLPROPORTION
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2584
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:129
void graph_sol_setNodeList(const GRAPH *, STP_Bool *, IDX *)
Definition: grphbase.c:3170
int norgmodelknots
Definition: grph.h:60
#define HEUR_USESSUBSCIP
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:921