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-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit 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 //#define SCIP_DEBUG
29 #include <assert.h>
30 #include <string.h>
31 #include <stdio.h>
32 #include "scip/scip.h"
33 #include "scip/scipdefplugins.h"
34 #include "scip/cons_linear.h"
35 #include "heur_slackprune.h"
36 #include "heur_ascendprune.h"
37 #include "heur_local.h"
38 #include "heur_prune.h"
39 #include "graph.h"
40 #include "reduce.h"
41 #include "heur_tm.h"
42 #include "solstp.h"
43 #include "cons_stp.h"
44 #include "scip/pub_misc.h"
45 #include "probdata_stp.h"
46 #include "prop_stp.h"
47 
48 #define HEUR_NAME "slackprune"
49 #define HEUR_DESC "Reduction based heuristic for Steiner problems"
50 #define HEUR_DISPCHAR 'S'
51 #define HEUR_PRIORITY 1
52 #define HEUR_FREQ 1
53 #define HEUR_FREQOFS 0
54 #define HEUR_MAXDEPTH -1
55 #define HEUR_TIMING (SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE)
56 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
57 
58 #define DEFAULT_SLACKPRUNE_MAXFREQ FALSE /**< executions of the heuristic at maximum frequency? */
59 #define SLACKPRUNE_MINREDELIMS 2 /**< minimum number of eliminations for reduction package when called by slack-and-prune heuristic */
60 #define SLACKPRUNE_MAXREDROUNDS 10 /**< maximum number of reduction rounds in slack-prune heuristic */
61 #define SLACKPRUNE_MINSTALLPROPORTION 0.2 /**< minimum proportion of arcs to be fixed before restarting slack-prune heuristic */
62 #define SLACKPRUNE_MAXSTALLPROPORTION 0.5 /**< maximum proportion of arcs to be fixed before restarting slack-prune heuristic */
63 #define SLACKPRUNE_HARDREDRATIO 0.97
64 
65 #define MAXNTERMINALS 1000
66 #define MAXNEDGES 20000
67 #define MAXNEDGES_SPG 10000
68 
69 #define SLACK_MAXTOTNEDGES 5000
70 
71 /*
72  * Data structures
73  */
74 
75 /** primal heuristic data */
76 struct SCIP_HeurData
77 {
78  int lastnfixededges; /**< number of fixed edges before the previous run */
79  int bestsolindex; /**< best solution during the previous run */
80  int nfailures; /**< number of failures since last successful call */
81  int nexecuted; /**< number of executions */
82  SCIP_Bool maxfreq; /**< should the heuristic be called at maximum frequency? */
83 };
84 
85 /*
86  * Local methods
87  */
88 
89 /* get reduction bound */
90 static
92  int nrounds,
93  int nedges
94  )
95 {
96  if( nrounds == 0)
97  return (MAX(nedges / 2000, SLACKPRUNE_MINREDELIMS));
98  if( nrounds == 1)
99  return (MAX(nedges / 1000, SLACKPRUNE_MINREDELIMS));
100  return(MAX(nedges / 500, SLACKPRUNE_MINREDELIMS));
101 }
102 
103 
104 static
106  SCIP* scip,
107  int* minnelims,
108  int* lminnelims,
109  int annodes,
110  int anedges,
111  int anterms,
112  int nround,
113  int maxnrounds
114  )
115 {
116  int min;
117  int totminnelims;
118  SCIP_Real factor;
119 
120  assert(scip != NULL);
121  assert(minnelims != NULL);
122  assert(lminnelims != NULL);
123  assert(annodes > 0);
124  assert(nround >= 0);
125  assert(maxnrounds >= 1);
126 
127  anedges = anedges / 2;
128 
129  totminnelims = MAX(SLACKPRUNE_MINREDELIMS, (anedges / 25));
130 
131  min = (int) (anedges * 0.15);
132  min -= (int) (((double) min * anterms) / (annodes));
133  min = MAX(min, 1);
134 
135  factor = (double) anedges / min;
136  factor = ((double) nround / (2.5 * maxnrounds)) * factor;
137 
138  if( SCIPisGT(scip, factor, 1.0) )
139  {
140  SCIP_Real tmp = min * factor;
141  min = (int) tmp;
142  }
143 
144  min = MAX(totminnelims, min);
145 
146  min = MIN(min, (anedges - 1));
147  min = MAX(min, 1);
148 
149  *lminnelims = min / 2;
150  *lminnelims = MAX(*lminnelims, 1);
151 
152  *minnelims = min;
153 
154 }
155 
156 
157 /** can the problem class be used? */
158 static inline
160  const GRAPH* graph /**< graph data structure */
161 )
162 {
163  const int probtype = graph->stp_type;
164  return (graph_typeIsSpgLike(graph) || probtype == STP_RMWCSP || probtype == STP_RPCSPG);
165 }
166 
167 
168 /** should we abort early? */
169 static inline
171  SCIP* scip, /**< SCIP data structure */
172  const GRAPH* graph, /**< graph data structure */
173  SCIP_HEURDATA* heurdata /**< heuristic's data */
174 )
175 {
176  const int nedges = graph->edges;
177  SCIP_Bool beAggressive;
178  SCIP_Real redratio;
179 
180  assert(nedges > 0);
181  assert(SCIPprobdataGetNorgEdges(scip) >= nedges);
182 
183  if( !probtypeIsValidForSlackPrune(graph) )
184  return TRUE;
185 
186  redratio = (SCIP_Real) nedges / (SCIP_Real) SCIPprobdataGetNorgEdges(scip);
187  beAggressive = (redratio > SLACKPRUNE_HARDREDRATIO);
188 
189  if( !beAggressive && heurdata->nexecuted >= 3 )
190  return TRUE;
191 
192  if( !beAggressive && heurdata->nfailures >= 1 )
193  return TRUE;
194 
195  if( heurdata->nexecuted >= 1 && SCIPgetNSols(scip) <= 5 )
196  return TRUE;
197 
198  if( (graph->edges > MAXNEDGES) && (graph->terms > MAXNTERMINALS) )
199  return TRUE;
200 
201  if( graph_typeIsSpgLike(graph) && !beAggressive
202  && (graph->edges > MAXNEDGES_SPG) && (graph->terms > MAXNTERMINALS) )
203  return TRUE;
204 
205  if( heurdata->bestsolindex == SCIPsolGetIndex(SCIPgetBestSol(scip)) )
206  return TRUE;
207 
208  /* after first call? Then only execute once enough edges have been fixed */
209  if( !beAggressive && heurdata->nexecuted >= 1 )
210  {
211  const SCIP_Real stallproportion = SLACKPRUNE_MINSTALLPROPORTION;
212 
213  if( (SCIPStpNfixedEdges(scip) - heurdata->lastnfixededges) < (int) (stallproportion * nedges) )
214  return TRUE;
215  }
216 
217  return FALSE;
218 }
219 
220 
221 /** does exact reductions */
222 static
224  SCIP* scip, /**< SCIP data structure */
225  GRAPH* prunegraph, /**< graph data structure */
226  int reductbound, /**< reduction bound */
227  SCIP_Bool fullreduce, /**< use full reduction techniques? */
228  int* soledge, /**< solution edges (in/out) */
229  int* solnode, /**< array of nodes of current solution that is not to be destroyed (in/out) */
230  SCIP_Real* offset /**< objective offset */
231  )
232 {
233  REDSOL* redsol;
234  PATH* vnoi;
235  PATH* path;
236  SCIP_Real* nodearrreal;
237  int* heap;
238  int* state;
239  int* vbase;
240  int* nodearrint;
241  int* edgearrint;
242  int* nodearrint2;
243  STP_Bool* nodearrchar;
244  const int nnodes = graph_get_nNodes(prunegraph);
245  const int nedges = graph_get_nEdges(prunegraph);
246 
247  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrchar, nnodes + 1) );
248  SCIP_CALL( SCIPallocBufferArray(scip, &heap, nnodes + 1) );
249  SCIP_CALL( SCIPallocBufferArray(scip, &state, 4 * nnodes) );
250  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrreal, nnodes) );
251  SCIP_CALL( SCIPallocBufferArray(scip, &vbase, 4 * nnodes) );
252  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint, nnodes + 1) );
253  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrint, nedges) );
254  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint2, nnodes + 1) );
255  SCIP_CALL( SCIPallocBufferArray(scip, &vnoi, 4 * nnodes) );
256  SCIP_CALL( SCIPallocBufferArray(scip, &path, nnodes + 1) );
257 
258  SCIP_CALL( reduce_solInit(scip, prunegraph, TRUE, &(redsol)) );
259  SCIP_CALL( reduce_solAddNodesol(prunegraph, solnode, redsol) );
260 
261  if( graph_pc_isPc(prunegraph) )
262  {
263  SCIP_CALL( reduce_redLoopPc(scip, redsol, prunegraph, vnoi, path, nodearrreal, heap, state,
264  vbase, nodearrint, edgearrint, nodearrint2, nodearrchar,
265  FALSE, FALSE, FALSE, reductbound, FALSE, TRUE, TRUE) );
266  }
267  else if( graph_pc_isMw(prunegraph) )
268  {
269  SCIP_CALL( reduce_redLoopMw(scip, redsol, prunegraph, vnoi, nodearrreal, state,
270  vbase, nodearrint, nodearrchar,
271  FALSE, FALSE, FALSE, reductbound, FALSE, TRUE) );
272  }
273  else
274  {
275  RPARAMS parameters = { .dualascent = FALSE, .boundreduce = FALSE, .nodereplacing = TRUE, .reductbound_min = SLACKPRUNE_MINREDELIMS,
276  .reductbound = reductbound, .userec = FALSE, .fullreduce = fullreduce, .usestrongreds = TRUE };
277  BIDECPARAMS decparameters = { .depth = 0, .maxdepth = 2, .newLevelStarted = FALSE };
278  REDBASE redbase = { .redparameters = &parameters, .bidecompparams = &decparameters,
279  .solnode = NULL, .redsol = redsol,
280  .vnoi = vnoi, .path = path, .heap = heap,
281  .nodearrreal = nodearrreal,
282  .state = state, .vbase = vbase, .nodearrint = nodearrint,
283  .edgearrint = edgearrint, .nodearrint2 = nodearrint2, .nodearrchar = nodearrchar };
284 
285  SCIP_CALL( reduce_redLoopStp(scip, prunegraph, &redbase) );
286  }
287 
288  reduce_solGetNodesol(prunegraph, redsol, solnode);
289 
290  *offset = reduce_solGetOffset(redsol);
291  reduce_solFree(scip, &(redsol));
292 
293  SCIPfreeBufferArray(scip, &path);
294  SCIPfreeBufferArray(scip, &vnoi);
295  SCIPfreeBufferArray(scip, &nodearrint2);
296  SCIPfreeBufferArray(scip, &edgearrint);
297  SCIPfreeBufferArray(scip, &nodearrint);
298  SCIPfreeBufferArray(scip, &vbase);
299  SCIPfreeBufferArray(scip, &nodearrreal);
300  SCIPfreeBufferArray(scip, &state);
301  SCIPfreeBufferArray(scip, &heap);
302  SCIPfreeBufferArray(scip, &nodearrchar);
303 
304  return SCIP_OKAY;
305 }
306 
307 /*
308  * Callback methods of primal heuristic
309  */
310 
311 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
312 static
313 SCIP_DECL_HEURCOPY(heurCopySlackPrune)
314 { /*lint --e{715}*/
315  assert(scip != NULL);
316  assert(heur != NULL);
317  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
318 
319  /* call inclusion method of primal heuristic */
321 
322  return SCIP_OKAY;
323 }
324 
325 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
326 static
327 SCIP_DECL_HEURFREE(heurFreeSlackPrune)
328 { /*lint --e{715}*/
329  SCIP_HEURDATA* heurdata;
330 
331  assert(heur != NULL);
332  assert(scip != NULL);
333 
334  /* get heuristic data */
335  heurdata = SCIPheurGetData(heur);
336  assert(heurdata != NULL);
337 
338  /* free heuristic data */
339  SCIPfreeMemory(scip, &heurdata);
340  SCIPheurSetData(heur, NULL);
341 
342  return SCIP_OKAY;
343 }
344 
345 
346 /** initialization method of primal heuristic (called after problem was transformed) */
347 
348 static
349 SCIP_DECL_HEURINIT(heurInitSlackPrune)
350 { /*lint --e{715}*/
351 
352 
353  return SCIP_OKAY;
354 }
355 
356 
357 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
358 static
359 SCIP_DECL_HEURINITSOL(heurInitsolSlackPrune)
360 { /*lint --e{715}*/
361  SCIP_HEURDATA* heurdata;
362 
363  assert(heur != NULL);
364  assert(scip != NULL);
365 
366  /* get heuristic's data */
367  heurdata = SCIPheurGetData(heur);
368 
369  assert(heurdata != NULL);
370 
371  /* initialize data */
372  heurdata->nexecuted = 0;
373  heurdata->nfailures = 0;
374  heurdata->bestsolindex = -1;
375 
376  /* NOTE: postpones slack-prune */
377  heurdata->lastnfixededges = 0;
378 
379  return SCIP_OKAY;
380 }
381 
382 
383 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
384 static
385 SCIP_DECL_HEUREXITSOL(heurExitsolSlackPrune)
386 { /*lint --e{715}*/
387 
388 
389  return SCIP_OKAY;
390 }
391 
392 
393 /** execution method of primal heuristic */
394 static
395 SCIP_DECL_HEUREXEC(heurExecSlackPrune)
396 { /*lint --e{715}*/
397  SCIP_HEURDATA* heurdata;
398  SCIP_PROBDATA* probdata;
399  SCIP_VAR** vars;
400  SCIP_SOL* bestsol;
401  GRAPH* graph;
402  SCIP_Real* xval;
403  SCIP_Bool success;
404  int e;
405  int nvars;
406  int nedges;
407  int* soledge;
408 
409  assert(heur != NULL);
410  assert(scip != NULL);
411  assert(result != NULL);
412  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
413 
414  heurdata = SCIPheurGetData(heur);
415  probdata = SCIPgetProbData(scip);
416  graph = SCIPprobdataGetGraph(probdata);
417 
418  assert(heurdata && graph);
419 
420  *result = SCIP_DIDNOTRUN;
421 
422  bestsol = SCIPgetBestSol(scip);
423 
424  /* NOTE: might be the case for UG that no feasible solution is available */
425  if( bestsol == NULL )
426  return SCIP_OKAY;
427 
428  if( abortSlackPruneEarly(scip, graph, heurdata) )
429  return SCIP_OKAY;
430 
431  xval = SCIPprobdataGetXval(scip, bestsol);
432  if( xval == NULL )
433  return SCIP_OKAY;
434 
435  *result = SCIP_DIDNOTFIND;
436  heurdata->nexecuted++;
437  heurdata->lastnfixededges = SCIPStpNfixedEdges(scip);
438 
439  vars = SCIPprobdataGetVars(scip);
440  nvars = SCIPprobdataGetNVars(scip);
441  nedges = graph->edges;
442 
443  assert(vars != NULL);
444  assert(nvars == nedges);
445 
446  /* allocate array to store primal solution */
447  SCIP_CALL( SCIPallocBufferArray(scip, &soledge, nedges) );
448 
449  for( e = 0; e < nedges; e++ )
450  {
451  if( SCIPisEQ(scip, xval[e], 1.0) )
452  soledge[e] = CONNECT;
453  else
454  soledge[e] = UNKNOWN;
455  }
456 
457  /* execute actual slackprune heuristic */
458  SCIP_CALL( SCIPStpHeurSlackPruneRun(scip, vars, graph, soledge, &success, FALSE, FALSE) );
459 
460  /* solution found by slackprune heuristic? */
461  if( success )
462  {
463  SCIP_Real pobj = 0.0;
464  SCIP_Real* nval;
465 
466  /* allocate memory to store solution */
467  SCIP_CALL( SCIPallocBufferArray(scip, &nval, nvars) );
468 
469  for( e = 0; e < nedges; e++ )
470  {
471  if( soledge[e] == CONNECT )
472  {
473  nval[e] = 1.0;
474  pobj += graph->cost[e];
475  }
476  else
477  {
478  nval[e] = 0.0;
479  }
480  }
481 
482  SCIPdebugMessage("SP final solution: best: old %f, new %f \n", SCIPgetSolOrigObj(scip, bestsol), pobj + SCIPprobdataGetOffset(scip));
483 
484  /* try to add new solution to pool */
485  SCIP_CALL( SCIPprobdataAddNewSol(scip, nval, heur, &success) );
486 
487  /* has solution been added? */
488  if( success )
489  {
490  SCIPdebugMessage("better solution added by SLACKPRUNE %f \n", pobj + SCIPprobdataGetOffset(scip));
491  *result = SCIP_FOUNDSOL;
492 
493  assert(solstp_isValid(scip, graph, soledge));
494 
495  /* is the solution NOT the new incumbent? */
496  if( SCIPisLE(scip, SCIPgetSolOrigObj(scip, bestsol) - SCIPprobdataGetOffset(scip), pobj) )
497  {
498  success = FALSE;
499  }
500  }
501 
502  /* free memory */
503  SCIPfreeBufferArray(scip, &nval);
504  }
505  else
506  {
507  SCIPdebugMessage("slack-prune: solution not valid \n");
508  }
509 
510  /* solution could not be found, added or is not best? */
511  if( !success )
512  {
513  heurdata->nfailures++;
514  }
515 
516  /* store index of incumbent solution */
517  heurdata->bestsolindex = SCIPsolGetIndex(SCIPgetBestSol(scip));
518 
519  /* free memory */
520  SCIPfreeBufferArray(scip, &soledge);
521  SCIPdebugMessage("leaving slack and prune heuristic \n");
522 
523  return SCIP_OKAY;
524 }
525 
526 
527 /*
528  * primal heuristic specific interface methods
529  */
530 
531 /** execute slack-and-prune heuristic on given graph */
533  SCIP* scip, /**< SCIP data structure */
534  SCIP_VAR** vars, /**< problem variables or NULL */
535  GRAPH* g, /**< graph data structure */
536  int* soledge, /**< array to 1. provide and 2. return primal solution */
537  SCIP_Bool* success, /**< feasible solution found? */
538  SCIP_Bool initialreduce, /**< try to reduce graph initially? */
539  SCIP_Bool fullreduce /**< use full reduction techniques? */
540  )
541 {
542  GRAPH* prunegraph;
543  SCIP_Real ubnew;
544  SCIP_Real ubbest;
545  SCIP_Real offsetnew;
546  SCIP_Real globalobj;
547  int i;
548  int k;
549  int e;
550  const int nnodes = graph_get_nNodes(g);
551  const int nedges = graph_get_nEdges(g);
552  int anterms;
553  int anedges;
554  int annodes;
555  int probtype;
556  int minnelims;
557  int lminnelims;
558  int reductbound;
559  int* solnode;
560  int* globalsoledge;
561  const SCIP_Bool isPcMw = graph_pc_isPcMw(g);
562 
563  assert(scip != NULL);
564  assert(soledge != NULL);
565  assert(solstp_isValid(scip, g, soledge));
566 
567  probtype = g->stp_type;
568  *success = FALSE;
569 
570  SCIP_CALL( SCIPallocBufferArray(scip, &solnode, nnodes) );
571  SCIP_CALL( SCIPallocBufferArray(scip, &globalsoledge, nedges) );
572  BMScopyMemoryArray(globalsoledge, soledge, nedges);
573 
574  /* mark solution vertices */
575  for( k = 0; k < nnodes; k++ )
576  solnode[k] = UNKNOWN;
577 
578  for( e = 0; e < nedges; e++ )
579  {
580  if( soledge[e] == CONNECT )
581  {
582  solnode[g->tail[e]] = CONNECT;
583  solnode[g->head[e]] = CONNECT;
584  }
585  }
586 
587  ubbest = solstp_getObjBounded(g, soledge, 0.0, nedges);
588  globalobj = ubbest;
589  offsetnew = 0.0; /* set offset (within new graph) to 0.0 */
590 
591  if( probtype == STP_RSMT || probtype == STP_OARSMT || probtype == STP_GSTP )
592  g->stp_type = STP_SPG;
593 
594  SCIP_CALL( graph_copy(scip, g, &prunegraph) );
595  SCIP_CALL( graph_initHistory(scip, prunegraph) );
596  if( graph_pc_isPcMw(prunegraph) )
597  prunegraph->norgmodelknots = prunegraph->knots;
598  SCIP_CALL( graph_path_init(scip, prunegraph) );
599 
600  reductbound = getRedBound(0, nedges);
601 
602  /* variables given? */
603  if( vars != NULL )
604  {
605  int nfixededges = 0;
606 
607  /* delete fixed edges from the new graph */
608  for( e = 0; e < nedges; e += 2 )
609  {
610  /* both e and its anti-parallel edge fixed to zero? */
611  if( SCIPvarGetUbLocal(vars[e]) < 0.5 && SCIPvarGetUbLocal(vars[e + 1]) < 0.5
612  && soledge[e] != CONNECT && soledge[e + 1] != CONNECT )
613  {
614  if( isPcMw && graph_pc_edgeIsExtended(g, e) )
615  continue;
616  graph_edge_del(scip, prunegraph, e, TRUE);
617  nfixededges++;
618  }
619  }
620 
621  SCIPdebugMessage("fixed edges in slack and prune: %d \n", nfixededges);
622 
623  if( nfixededges > reductbound && initialreduce )
624  {
625  graph_get_nVET(prunegraph, &annodes, &anedges, &anterms);
626  reductbound = getRedBound(0, anedges);
627  }
628  }
629 
630  /* perform initial reductions? */
631  if( initialreduce )
632  {
633  SCIP_CALL( reduceExact(scip, prunegraph, reductbound, fullreduce, soledge, solnode, &offsetnew) );
634  }
635 
636  /* get number of remaining vertices, edges and terminals */
637  graph_get_nVET(prunegraph, &annodes, &anedges, &anterms);
638 
639  /* main reduction loop */
640  for( i = 0; i < SLACKPRUNE_MAXREDROUNDS && anterms > 2; i++ )
641  {
642  SCIP_Bool solIsImproved;
643  SCIP_Bool solIsRebuilt;
644  int danelims;
645  SCIP_Bool solgiven;
646 
647  SCIPdebugMessage("starting round %d \n", i);
648 
649  /* update reduction bounds */
650  setMinMaxElims(scip, &minnelims, &lminnelims, annodes, anedges, anterms, i + 1, SLACKPRUNE_MAXREDROUNDS);
651 
652  solgiven = ((i == 0) && !initialreduce);
653 
654  /* perform heuristic reductions */
655  SCIP_CALL( reduce_daSlackPrune(scip, prunegraph, minnelims, solgiven, soledge, solnode, &danelims, &ubnew, &solIsImproved, &solIsRebuilt) );
656 
657  /* delete all vertices not reachable from the root */
658  SCIP_CALL( reduce_unconnected(scip, prunegraph) );
659 
660  assert(graph_valid(scip, prunegraph));
661 
662  graph_get_nVET(prunegraph, &annodes, &anedges, &anterms);
663 
664  if( anterms <= 2 )
665  break;
666 
667  SCIPdebugMessage("minelims %d really reduced: %d \n", minnelims, danelims);
668 
669  /* not enough reductions possible? */
670  if( danelims < lminnelims )
671  {
672  SCIPdebugMessage("too few elims in DA, break %d < %d\n\n", danelims, lminnelims);
674  }
675 
676  /* solution found by ascend and prune? */
677  if( solIsImproved )
678  {
679  assert(solstp_isValid(scip, prunegraph, soledge));
680  SCIP_CALL( SCIPStpHeurLocalRun(scip, prunegraph, soledge) );
681 
682  SCIP_CALL( SCIPStpHeurPruneUpdateSols(scip, g, prunegraph, solnode, soledge,
683  globalsoledge, &globalobj, TRUE, success) );
684  }
685  else if( solIsRebuilt )
686  {
687  assert(solstp_isValid(scip, prunegraph, soledge));
688  SCIP_CALL( SCIPStpHeurPruneUpdateSols(scip, g, prunegraph, solnode, soledge,
689  globalsoledge, &globalobj, FALSE, success) );
690  }
691 
692  if( solIsImproved || solIsRebuilt )
693  {
694  const SCIP_Real obj = solstp_getObj(prunegraph, soledge, offsetnew);
695  SCIPdebugMessage("old solution: %f new solution %f \n\n", ubbest + SCIPprobdataGetOffset(scip), obj + SCIPprobdataGetOffset(scip));
696 
697  if( SCIPisLE(scip, obj, ubbest) )
698  ubbest = obj;
699  }
700  graph_get_nVET(prunegraph, &annodes, &anedges, &anterms);
701  reductbound = getRedBound(i, anedges);
702 
703  SCIP_CALL( reduceExact(scip, prunegraph, reductbound, fullreduce, soledge, solnode, &offsetnew) );
704 
705  graph_get_nVET(prunegraph, &annodes, &anedges, &anterms);
706  } /* reduction loop */
707 
708  /* NOTE: might still help, even though heuristic was already called */
709  SCIP_CALL(SCIPStpHeurLocalRun(scip, g, globalsoledge));
710 
711  graph_path_exit(scip, prunegraph);
712 
713  *success = solstp_isValid(scip, g, globalsoledge);
714  BMScopyMemoryArray(soledge, globalsoledge, nedges);
715 
716  assert(*success);
717 
718  graph_free(scip, &prunegraph, TRUE);
719  SCIPfreeBufferArray(scip, &globalsoledge);
720  SCIPfreeBufferArray(scip, &solnode);
721 
722  if( probtype == STP_RSMT || probtype == STP_OARSMT || probtype == STP_GSTP )
723  g->stp_type = probtype;
724 
725  return SCIP_OKAY;
726 }
727 
728 
729 /** creates the slackprune primal heuristic and includes it in SCIP */
731  SCIP* scip /**< SCIP data structure */
732  )
733 {
734  SCIP_HEURDATA* heurdata;
735  SCIP_HEUR* heur;
736 
737  /* create slackprune primal heuristic data */
738  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
739 
740  /* include primal heuristic */
741  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
743  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecSlackPrune, heurdata) );
744 
745  assert(heur != NULL);
746 
747  /* set non fundamental callbacks via setter functions */
748  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopySlackPrune) );
749  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeSlackPrune) );
750  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitSlackPrune) );
751  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolSlackPrune) );
752  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolSlackPrune) );
753 
754  /* add slackprune primal heuristic parameters */
755  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/maxfreq",
756  "should the heuristic be executed at maximum frequeny?",
757  &heurdata->maxfreq, FALSE, DEFAULT_SLACKPRUNE_MAXFREQ, NULL, NULL) );
758 
759 
760  return SCIP_OKAY;
761 }
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:233
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
#define HEUR_MAXDEPTH
SCIP_Bool graph_pc_isMw(const GRAPH *)
int *RESTRICT head
Definition: graphdefs.h:224
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_edge.c:368
#define MAXNEDGES_SPG
SCIP_RETCODE SCIPStpHeurPruneUpdateSols(SCIP *scip, GRAPH *g, GRAPH *prunegraph, int *solnode, int *soledge, int *globalsoledge, SCIP_Real *globalobj, SCIP_Bool incumbentgiven, SCIP_Bool *success)
Definition: heur_prune.c:489
Constraint handler for Steiner problems.
int SCIPStpNfixedEdges(SCIP *scip)
Definition: prop_stp.c:2467
SCIP_Bool graph_valid(SCIP *, const GRAPH *)
Definition: graph_base.c:1480
SCIP_RETCODE reduce_solInit(SCIP *, const GRAPH *, SCIP_Bool, REDSOL **)
Definition: reduce_sol.c:687
int terms
Definition: graphdefs.h:192
SCIP_VAR ** SCIPprobdataGetVars(SCIP *scip)
SCIP_RETCODE reduce_redLoopPc(SCIP *, REDSOL *, GRAPH *, PATH *, PATH *, SCIP_Real *, int *, int *, int *, int *, int *, int *, STP_Bool *, SCIP_Bool, SCIP_Bool, SCIP_Bool, int, SCIP_Bool, SCIP_Bool, SCIP_Bool)
Definition: reduce_base.c:1896
#define MAXNTERMINALS
static void setMinMaxElims(SCIP *scip, int *minnelims, int *lminnelims, int annodes, int anedges, int anterms, int nround, int maxnrounds)
includes methods for Steiner tree problem solutions
dual-ascent and reduction based primal heuristic for Steiner problems
reduction and dual-cost based primal heuristic for Steiner problems
void graph_free(SCIP *, GRAPH **, SCIP_Bool)
Definition: graph_base.c:796
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
Definition: graph_path.c:480
#define FALSE
Definition: def.h:87
#define HEUR_PRIORITY
static SCIP_DECL_HEURINIT(heurInitSlackPrune)
Problem data for stp problem.
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
SCIP_RETCODE reduce_redLoopMw(SCIP *, REDSOL *, GRAPH *, PATH *, SCIP_Real *, int *, int *, int *, STP_Bool *, STP_Bool, STP_Bool, STP_Bool, int, SCIP_Bool, SCIP_Bool)
Definition: reduce_base.c:1771
void reduce_solGetNodesol(const GRAPH *, REDSOL *, int *)
Definition: reduce_sol.c:1176
int SCIPprobdataGetNVars(SCIP *scip)
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:108
#define STP_SPG
Definition: graphdefs.h:42
#define SCIPdebugMessage
Definition: pub_message.h:87
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:127
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1362
static SCIP_DECL_HEURFREE(heurFreeSlackPrune)
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
#define HEUR_TIMING
#define STP_RSMT
Definition: graphdefs.h:49
SCIP_Bool graph_pc_edgeIsExtended(const GRAPH *, int)
#define HEUR_FREQ
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:217
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1441
int stp_type
Definition: graphdefs.h:264
static SCIP_RETCODE reduceExact(SCIP *scip, GRAPH *prunegraph, int reductbound, SCIP_Bool fullreduce, int *soledge, int *solnode, SCIP_Real *offset)
void graph_get_nVET(const GRAPH *, int *, int *, int *)
Definition: graph_stats.c:571
static SCIP_Bool probtypeIsValidForSlackPrune(const GRAPH *graph)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
SCIP_Real SCIPprobdataGetOffset(SCIP *scip)
SCIP_RETCODE graph_initHistory(SCIP *, GRAPH *)
Definition: graph_base.c:695
SCIP_RETCODE SCIPprobdataAddNewSol(SCIP *scip, SCIP_Real *nval, SCIP_HEUR *heur, SCIP_Bool *success)
#define SLACKPRUNE_MINREDELIMS
SCIP_RETCODE reduce_unconnected(SCIP *, GRAPH *)
SCIP_Bool dualascent
Definition: reducedefs.h:77
static SCIP_DECL_HEURINITSOL(heurInitsolSlackPrune)
static SCIP_DECL_HEUREXITSOL(heurExitsolSlackPrune)
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_Real reduce_solGetOffset(const REDSOL *)
Definition: reduce_sol.c:1137
SCIP_RETCODE SCIPStpHeurLocalRun(SCIP *scip, GRAPH *graph, int *solEdges)
Definition: heur_local.c:3899
#define MAXNEDGES
#define STP_RMWCSP
Definition: graphdefs.h:54
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
void reduce_solFree(SCIP *, REDSOL **)
Definition: reduce_sol.c:818
#define STP_OARSMT
Definition: graphdefs.h:50
Improvement heuristic for Steiner problems.
unsigned char STP_Bool
Definition: portab.h:34
reduction-based primal heuristic for Steiner problems
SCIP_Real solstp_getObjBounded(const GRAPH *g, const int *soledge, SCIP_Real offset, int nedges)
Definition: solstp.c:1833
propagator for Steiner tree problems, using the LP reduced costs
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:84
#define SLACKPRUNE_MAXREDROUNDS
int *RESTRICT tail
Definition: graphdefs.h:223
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_RETCODE SCIPStpHeurSlackPruneRun(SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success, SCIP_Bool initialreduce, SCIP_Bool fullreduce)
static SCIP_DECL_HEUREXEC(heurExecSlackPrune)
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2205
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1435
Constraint handler for linear constraints in their most general form, .
void graph_path_exit(SCIP *, GRAPH *)
Definition: graph_path.c:515
SCIP_Bool graph_pc_isPc(const GRAPH *)
#define CONNECT
Definition: graphdefs.h:87
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2304
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPprobdataGetNorgEdges(SCIP *scip)
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:962
SCIP_Real * cost
Definition: graphdefs.h:221
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
static SCIP_Bool abortSlackPruneEarly(SCIP *scip, const GRAPH *graph, SCIP_HEURDATA *heurdata)
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
SCIP_RETCODE reduce_solAddNodesol(const GRAPH *, const int *, REDSOL *)
Definition: reduce_sol.c:1150
#define SLACKPRUNE_HARDREDRATIO
#define SCIP_Real
Definition: def.h:177
SCIP_Real * SCIPprobdataGetXval(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE graph_copy(SCIP *, const GRAPH *, GRAPH **)
Definition: graph_base.c:939
shortest paths based primal heuristics for Steiner problems
int edges
Definition: graphdefs.h:219
SCIP_RETCODE SCIPStpIncludeHeurSlackPrune(SCIP *scip)
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
static SCIP_DECL_HEURCOPY(heurCopySlackPrune)
#define STP_GSTP
Definition: graphdefs.h:53
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
RPARAMS * redparameters
Definition: reducedefs.h:102
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define UNKNOWN
Definition: sepa_mcf.c:4095
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
#define nnodes
Definition: gastrans.c:65
SCIP_RETCODE reduce_redLoopStp(SCIP *, GRAPH *, REDBASE *)
Definition: reduce_base.c:2074
#define HEUR_DESC
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1352
SCIP_Bool graph_typeIsSpgLike(const GRAPH *)
Definition: graph_stats.c:57
#define HEUR_DISPCHAR
includes various reduction methods for Steiner tree problems
default SCIP plugins
#define HEUR_FREQOFS
SCIP_Real solstp_getObj(const GRAPH *g, const int *soledge, SCIP_Real offset)
Definition: solstp.c:1859
#define STP_RPCSPG
Definition: graphdefs.h:45
static int getRedBound(int nrounds, int nedges)
#define SLACKPRUNE_MINSTALLPROPORTION
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2635
SCIP callable library.
SCIP_RETCODE reduce_daSlackPrune(SCIP *, GRAPH *, int, SCIP_Bool, int *, int *, int *, SCIP_Real *, SCIP_Bool *, SCIP_Bool *)
Definition: reduce_da.c:2741
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
int norgmodelknots
Definition: graphdefs.h:187
#define HEUR_USESSUBSCIP