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