Scippy

SCIP

Solving Constraint Integer Programs

heur_ascendprune.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2019 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_ascendprune.c
17  * @brief reduction-based primal heuristic for Steiner problems
18  * @author Daniel Rehfeldt
19  *
20  * This file implements a reduction and dual-cost based heuristic for Steiner problems. See
21  * "SCIP-Jack - A solver for STP and variants with parallelization extensions" (2016) by
22  * Gamrath, Koch, Maher, Rehfeldt and Shinano
23  *
24  * A list of all interface methods can be found in heur_ascendprune.h
25  *
26  */
27 
28 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
29 
30 #include <assert.h>
31 #include <string.h>
32 #include <stdio.h>
33 #include "scip/scip.h"
34 #include "scip/scipdefplugins.h"
35 #include "scip/cons_linear.h"
36 #include "heur_ascendprune.h"
37 #include "heur_local.h"
38 #include "heur_prune.h"
39 #include "grph.h"
40 #include "heur_tm.h"
41 #include "cons_stp.h"
42 #include "scip/pub_misc.h"
43 #include "probdata_stp.h"
44 
45 #define HEUR_NAME "ascendprune"
46 #define HEUR_DESC "Dual-cost reduction heuristic for Steiner problems"
47 #define HEUR_DISPCHAR 'A'
48 #define HEUR_PRIORITY 2
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_MAXFREQPRUNE FALSE /**< executions of the heuristic at maximum frequency? */
56 #define ASCENPRUNE_MINLPIMPROVE 0.05 /**< minimum percentual improvement of dual bound (wrt to gap) mandatory to execute heuristic */
57 
58 #ifdef WITH_UG
59 extern
60 int getUgRank(void);
61 #endif
62 
63 /*
64  * Data structures
65  */
66 
67 /** primal heuristic data */
68 struct SCIP_HeurData
69 {
70  SCIP_Real lastdualbound; /**< dual bound after the previous run */
71  int bestsolindex; /**< best solution during the previous run */
72  int nfailures; /**< number of failures since last successful call */
73  SCIP_Bool maxfreq; /**< should the heuristic be called at maximum frequency? */
74 };
75 
76 
77 /*
78  * Local methods
79  */
80 
81 /* put your local methods here, and declare them static */
82 
83 
84 /*
85  * Callback methods of primal heuristic
86  */
87 
88 
89 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
90 static
91 SCIP_DECL_HEURCOPY(heurCopyAscendPrune)
92 { /*lint --e{715}*/
93  assert(scip != NULL);
94  assert(heur != NULL);
95  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
96 
97  /* call inclusion method of primal heuristic */
99 
100  return SCIP_OKAY;
101 }
102 
103 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
104 static
105 SCIP_DECL_HEURFREE(heurFreeAscendPrune)
106 { /*lint --e{715}*/
107  SCIP_HEURDATA* heurdata;
108 
109  assert(heur != NULL);
110  assert(scip != NULL);
111 
112  /* get heuristic data */
113  heurdata = SCIPheurGetData(heur);
114  assert(heurdata != NULL);
115 
116  /* free heuristic data */
117  SCIPfreeMemory(scip, &heurdata);
118  SCIPheurSetData(heur, NULL);
119 
120  return SCIP_OKAY;
121 }
122 
123 
124 /** initialization method of primal heuristic (called after problem was transformed) */
125 
126 static
127 SCIP_DECL_HEURINIT(heurInitAscendPrune)
128 { /*lint --e{715}*/
129  SCIP_HEURDATA* heurdata;
130 
131  assert(heur != NULL);
132  assert(scip != NULL);
133 
134  /* get heuristic's data */
135  heurdata = SCIPheurGetData(heur);
136 
137  assert(heurdata != NULL);
138 
139  /* initialize data */
140  heurdata->nfailures = 0;
141  heurdata->bestsolindex = -1;
142  heurdata->lastdualbound = 0.0;
143 
144  return SCIP_OKAY;
145 }
146 
147 /** execution method of primal heuristic */
148 static
149 SCIP_DECL_HEUREXEC(heurExecAscendPrune)
150 { /*lint --e{715}*/
151  SCIP_HEURDATA* heurdata;
152  SCIP_PROBDATA* probdata;
153  SCIP_VAR** vars;
154  SCIP_SOL* bestsol; /* best known solution */
155  GRAPH* graph;
156  SCIP_Real dualbound;
157  SCIP_Real gap;
158  SCIP_Real* redcosts;
159  SCIP_Bool success;
160  int e;
161  int nnodes;
162  int nedges;
163  int* edgearrint;
164  int* nodearrint;
165  STP_Bool* nodearrchar;
166 
167  assert(heur != NULL);
168  assert(scip != NULL);
169  assert(result != NULL);
170  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
171 
172  /* get heuristic data */
173  heurdata = SCIPheurGetData(heur);
174  assert(heurdata != NULL);
175 
176  /* get problem data */
177  probdata = SCIPgetProbData(scip);
178  assert(probdata != NULL);
179 
180  /* get graph */
181  graph = SCIPprobdataGetGraph(probdata);
182  assert(graph != NULL);
183 
184  vars = SCIPprobdataGetVars(scip);
185  assert(vars != NULL);
186 
187  *result = SCIP_DIDNOTRUN;
188 
189  /* todo: delete this file and move to slack-prune */
190 
191  nedges = graph->edges;
192  nnodes = graph->knots;
193  success = FALSE;
194 
195  /* get best current solution */
196  bestsol = SCIPgetBestSol(scip);
197 
198  /* no solution available? */
199  if( bestsol == NULL )
200  return SCIP_OKAY;
201 
202  /* get dual bound */
203  dualbound = SCIPgetDualbound(scip);
204 
205  /* no new best solution available? */
206  if( heurdata->bestsolindex == SCIPsolGetIndex(SCIPgetBestSol(scip)) && !(heurdata->maxfreq) )
207  {
208  /* current optimality gap */
209  gap = SCIPgetSolOrigObj(scip, bestsol) - dualbound;
210 
211  if( SCIPisLT(scip, dualbound - heurdata->lastdualbound, gap * ASCENPRUNE_MINLPIMPROVE ) )
212  return SCIP_OKAY;
213  }
214 
215  heurdata->lastdualbound = dualbound;
216 
217  /* allocate memory for ascent and prune */
218  SCIP_CALL( SCIPallocBufferArray(scip, &redcosts, nedges) );
219  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrint, nedges) );
220  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint, nnodes ) );
221  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrchar, nnodes) );
222 
223  for( e = 0; e < nedges; e++ )
224  {
225  assert(SCIPvarIsBinary(vars[e]));
226 
227  /* variable is already fixed, we must not trust the reduced cost */
228  if( SCIPvarGetLbLocal(vars[e]) + 0.5 > SCIPvarGetUbLocal(vars[e]) )
229  {
230  if( SCIPvarGetLbLocal(vars[e]) > 0.5 )
231  redcosts[e] = 0.0;
232  else
233  {
234  assert(SCIPvarGetUbLocal(vars[e]) < 0.5);
235  redcosts[e] = FARAWAY;
236  }
237  }
238  else
239  {
240  if( SCIPisFeasZero(scip, SCIPgetSolVal(scip, NULL, vars[e])) )
241  {
242  assert(!SCIPisDualfeasNegative(scip, SCIPgetVarRedcost(scip, vars[e])));
243  redcosts[e] = SCIPgetVarRedcost(scip, vars[e]);
244  }
245  else
246  {
247  assert(!SCIPisDualfeasPositive(scip, SCIPgetVarRedcost(scip, vars[e])));
248  assert(SCIPisFeasEQ(scip, SCIPgetSolVal(scip, NULL, vars[e]), 1.0) || SCIPisDualfeasZero(scip, SCIPgetVarRedcost(scip, vars[e])));
249  redcosts[e] = 0.0;
250  }
251  }
252 
253  if( SCIPisLT(scip, redcosts[e], 0.0) )
254  redcosts[e] = 0.0;
255 
256  assert(SCIPisGE(scip, redcosts[e], 0.0));
257  assert(!SCIPisEQ(scip, redcosts[e], SCIP_INVALID));
258  }
259 
260  /* perform ascent and prune */
261  SCIP_CALL( SCIPStpHeurAscendPruneRun(scip, heur, graph, redcosts, edgearrint, nodearrint, graph->source, nodearrchar, &success, TRUE) );
262 
263  if( success )
264  {
265  heurdata->nfailures = 0;
266  *result = SCIP_FOUNDSOL;
267  }
268  else
269  {
270  heurdata->nfailures++;
271  }
272 
273  heurdata->bestsolindex = SCIPsolGetIndex(SCIPgetBestSol(scip));
274 
275  /* free memory */
276  SCIPfreeBufferArray(scip, &nodearrchar);
277  SCIPfreeBufferArray(scip, &nodearrint);
278  SCIPfreeBufferArray(scip, &edgearrint);
279  SCIPfreeBufferArray(scip, &redcosts);
280 
281  return SCIP_OKAY;
282 }
283 
284 
285 /*
286  * primal heuristic specific interface methods
287  */
288 
289 
290 /** ascent and prune */
292  SCIP* scip, /**< SCIP data structure */
293  SCIP_HEUR* heur, /**< heuristic data structure or NULL */
294  const GRAPH* g, /**< the graph */
295  const SCIP_Real* redcosts, /**< the reduced costs */
296  int* edgearrint, /**< int edges array to store solution */
297  int* nodearrint, /**< int vertices array for internal computations */
298  int root, /**< the root (used for dual ascent) */
299  STP_Bool* nodearrchar, /**< STP_Bool vertices array for internal computations */
300  SCIP_Bool* solfound, /**< has a solution been found? */
301  SCIP_Bool addsol /**< should the solution be added to SCIP by this method? */
302  )
303 {
304  GRAPH* newgraph;
305  SCIP_Real* nval;
306  int* const mark = g->mark;
307  int* const newedges = edgearrint;
308  int* const nodechild = nodearrint;
309  int* edgeancestor;
310  const int nnodes = g->knots;
311  const int nedges = g->edges;
312  const int probtype = g->stp_type;
313  int nnewnodes = 0;
314  int nnewedges = 0;
315  const SCIP_Bool pcmw = (probtype == STP_PCSPG || probtype == STP_MWCSP || probtype == STP_RPCSPG || probtype == STP_RMWCSP);
316  SCIP_Bool success;
317 
318  assert(g != NULL);
319  assert(scip != NULL);
320  assert(redcosts != NULL);
321  assert(edgearrint != NULL);
322  assert(nodearrint != NULL);
323  assert(nodearrchar != NULL);
324 
325  if( root < 0 )
326  root = g->source;
327 
328  assert(Is_term(g->term[root]));
329  assert(graph_valid(g));
330 
331  if( addsol )
332  {
333  const int nvars = SCIPprobdataGetNVars(scip);
334  SCIP_CALL( SCIPallocBufferArray(scip, &nval, nvars) );
335  }
336  else
337  {
338  nval = NULL;
339  }
340 
341  /* DFS to identify 0-redcost subgraph */
342  {
343  int* const queue = nodearrint;
344  STP_Bool* const scanned = nodearrchar;
345  int qsize;
346 
347  /*
348  * construct new graph corresponding to zero cost paths from the root to all terminals
349  */
350 
351  BMSclearMemoryArray(mark, nnodes);
352  BMSclearMemoryArray(scanned, nnodes);
353 
354  qsize = 0;
355  mark[root] = TRUE;
356  queue[qsize++] = root;
357  nnewnodes++;
358 
359  /* DFS */
360  while( qsize )
361  {
362  const int k = queue[--qsize];
363  scanned[k] = TRUE;
364 
365  /* traverse outgoing arcs */
366  for( int a = g->outbeg[k]; a != EAT_LAST; a = g->oeat[a] )
367  {
368  const int head = g->head[a];
369 
370  if( SCIPisZero(scip, redcosts[a]) )
371  {
372  if( pcmw && k == root && Is_term(g->term[head]) )
373  continue;
374 
375  /* vertex not labeled yet? */
376  if( !mark[head] )
377  {
378  mark[head] = TRUE;
379  nnewnodes++;
380  queue[qsize++] = head;
381  }
382 
383  if( (!scanned[head] || !SCIPisZero(scip, redcosts[flipedge(a)])) && k != root )
384  {
385  assert(g->tail[a] != root);
386  assert(g->head[a] != root);
387 
388  newedges[nnewedges++] = a;
389  }
390  }
391  }
392  }
393 
394 #ifndef NDEBUG
395  for( int k = 0; k < nnewedges && pcmw; k++ )
396  {
397  const int e = newedges[k];
398  assert(!(g->tail[e] == root && Is_pterm(g->term[g->head[e]])));
399  assert(!(g->head[e] == root && Is_pterm(g->term[g->tail[e]])));
400  }
401 #endif
402 
403  for( int a = g->outbeg[root]; a != EAT_LAST; a = g->oeat[a] )
404  {
405  const int head = g->head[a];
406  if( mark[head] )
407  newedges[nnewedges++] = a;
408  }
409  }
410 
411  SCIP_CALL( SCIPallocBufferArray(scip, &edgeancestor, 2 * nnewedges) );
412 
413  /* initialize new graph */
414  SCIP_CALL( graph_init(scip, &newgraph, nnewnodes, 2 * nnewedges, 1) );
415 
416  if( probtype == STP_RSMT || probtype == STP_OARSMT || probtype == STP_GSTP )
417  newgraph->stp_type = STP_SPG;
418  else
419  newgraph->stp_type = probtype;
420 
421  if( pcmw )
422  SCIP_CALL( graph_pc_init(scip, newgraph, nnewnodes, nnewnodes) );
423 
424  for( int k = 0; k < nnodes; k++ )
425  {
426  if( mark[k] )
427  {
428  if( pcmw )
429  {
430  if( (!Is_term(g->term[k])) )
431  newgraph->prize[newgraph->knots] = g->prize[k];
432  else
433  newgraph->prize[newgraph->knots] = 0.0;
434  }
435 
436  nodechild[k] = newgraph->knots;
437  graph_knot_add(newgraph, g->term[k]);
438  }
439  }
440 
441  if( pcmw )
442  {
443  newgraph->norgmodelknots = nnewnodes;
444  newgraph->extended = TRUE;
445  }
446 
447  assert(nnewnodes == newgraph->knots);
448 
449  /* set root of new graph */
450  newgraph->source = nodechild[root];
451  assert(newgraph->source >= 0);
452 
453  if( g->stp_type == STP_RPCSPG || g->stp_type == STP_RMWCSP )
454  newgraph->prize[newgraph->source] = FARAWAY;
455 
456  /* add edges to new graph */
457  for( int a = 0; a < nnewedges; a++ )
458  {
459  int i;
460  const int e = newedges[a];
461  const int tail = nodechild[g->tail[e]];
462  const int head = nodechild[g->head[e]];
463 
464  assert(tail >= 0);
465  assert(head >= 0);
466 
467  for( i = newgraph->outbeg[tail]; i != EAT_LAST; i = newgraph->oeat[i] )
468  if( newgraph->head[i] == head )
469  break;
470 
471  if( i == EAT_LAST )
472  {
473  edgeancestor[newgraph->edges] = e;
474  edgeancestor[newgraph->edges + 1] = flipedge(e);
475 
476  if( pcmw )
477  graph_pc_updateTerm2edge(newgraph, g, tail, head, g->tail[e], g->head[e]);
478 
479  graph_edge_add(scip, newgraph, tail, head, g->cost[e], g->cost[flipedge(e)]);
480  }
481  }
482 
483  nnewedges = newgraph->edges;
484  newgraph->norgmodeledges = nnewedges;
485 
486  assert(!pcmw || -1 == newgraph->term2edge[newgraph->source]);
487 
488  /* initialize ancestors of new graph edges */
489  SCIP_CALL( graph_init_history(scip, newgraph) );
490 
491  /* initialize shortest path algorithm */
492  SCIP_CALL( graph_path_init(scip, newgraph) );
493 
494  SCIP_CALL( level0(scip, newgraph) );
495 
496 #ifdef DEBUG_ASCENDPRUNE
497  for( int k = 0; k < nnodes && !pcmw; k++ )
498  {
499  if( Is_term(g->term[k]) )
500  {
501  const int i = nodechild[k];
502  if( i < 0 )
503  {
504  printf("k %d root %d \n", k, root);
505  printf("FAIL in AP \n\n\n");
506  return SCIP_ERROR;
507  }
508 
509  if( newgraph->grad[i] == 0 && newgraph->knots > 1 )
510  {
511  printf("FAIL GRAD \n\n\n");
512  return SCIP_ERROR;
513 
514  }
515  }
516  }
517 #endif
518  assert(graph_valid(newgraph));
519 
520  /* get solution on new graph by PRUNE heuristic */
521  SCIP_CALL( SCIPStpHeurPruneRun(scip, NULL, newgraph, newedges, &success, FALSE, TRUE) );
522 
523 #ifdef DEBUG_ASCENDPRUNE
524  for( int k = 0; k < newgraph->knots; ++k )
525  {
526  if( Is_term(newgraph->term[k]) && newgraph->grad[k] == 0 && k != newgraph->source )
527  {
528  printf("after i %d r %d \n", k, root);
529  return SCIP_ERROR;
530  }
531  }
532 
533  if( !graph_sol_valid(scip, newgraph, newedges) )
534  {
535  printf("not valid %d \n", 0);
536  return SCIP_ERROR;
537  }
538 #endif
539  if( !success )
540  {
541  SCIPdebugMessage("failed to build tree in ascend-prune (by prune) \n");
542  goto TERMINATE;
543  }
544 
545  assert(success && graph_sol_valid(scip, newgraph, newedges));
546 
547  SCIPdebugMessage("obj after prune %f \n", graph_sol_getObj(newgraph->cost, newedges, 0.0, newgraph->edges));
548 
549  SCIP_CALL( SCIPStpHeurLocalRun(scip, newgraph, newgraph->cost, newedges) );
550 
551  SCIPdebugMessage("obj after local %f \n", graph_sol_getObj(newgraph->cost, newedges, 0.0, newgraph->edges));
552 
553  assert(graph_sol_valid(scip, newgraph, newedges));
554  graph_path_exit(scip, newgraph);
555 
556 
557  /*
558  * prune solution (in the original graph)
559  */
560 
561  BMSclearMemoryArray(nodearrchar, nnodes);
562 
563  for( int e = 0; e < nnewedges; e++ )
564  if( newedges[e] == CONNECT )
565  {
566  const int eorg = edgeancestor[e];
567  nodearrchar[g->tail[eorg]] = TRUE;
568  nodearrchar[g->head[eorg]] = TRUE;
569  }
570 
571  for( int e = 0; e < nedges; e++ )
572  newedges[e] = UNKNOWN;
573 
574  if( pcmw )
575  SCIP_CALL( SCIPStpHeurTMPrunePc(scip, g, g->cost, newedges, nodearrchar) );
576  else
577  SCIP_CALL( SCIPStpHeurTMPrune(scip, g, g->cost, 0, newedges, nodearrchar) );
578 
579  assert(graph_sol_valid(scip, g, newedges));
580 
581  if( addsol )
582  {
583  assert(nval != NULL);
584  for( int e = 0; e < nedges; e++ )
585  {
586  if( newedges[e] == CONNECT )
587  nval[e] = 1.0;
588  else
589  nval[e] = 0.0;
590  }
591  }
592 
593  success = graph_sol_valid(scip, g, newedges);
594 
595  if( success && addsol )
596  {
597  /* add solution */
598  SCIP_SOL* sol = NULL;
599  SCIP_CALL( SCIPprobdataAddNewSol(scip, nval, sol, heur, &success) );
600  SCIPdebugMessage("Ascend-and-prune added solution \n");
601  }
602 
603  *solfound = success;
604 
605  TERMINATE:
606 
607  for( int k = 0; k < nnodes; k++ )
608  mark[k] = (g->grad[k] > 0);
609 
610  /* free memory */
611  graph_free(scip, &newgraph, TRUE);
612  SCIPfreeBufferArray(scip, &edgeancestor);
613  SCIPfreeBufferArrayNull(scip, &nval);
614 
615  return SCIP_OKAY;
616 }
617 
618 
619 /** creates the prune primal heuristic and includes it in SCIP */
621  SCIP* scip /**< SCIP data structure */
622  )
623 {
624  SCIP_HEURDATA* heurdata;
625  SCIP_HEUR* heur;
626 
627  /* create prune primal heuristic data */
628  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
629 
630  /* include primal heuristic */
631  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
633  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecAscendPrune, heurdata) );
634 
635  assert(heur != NULL);
636 
637  /* set non fundamental callbacks via setter functions */
638  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyAscendPrune) );
639  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeAscendPrune) );
640  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitAscendPrune) );
641 
642  /* add ascend and prune primal heuristic parameters */
643  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/maxfreq",
644  "should the heuristic be executed at maximum frequeny?",
645  &heurdata->maxfreq, FALSE, DEFAULT_MAXFREQPRUNE, NULL, NULL) );
646 
647  return SCIP_OKAY;
648 }
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
Definition: grphpath.c:444
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
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
#define NULL
Definition: def.h:246
SCIP_RETCODE graph_pc_init(SCIP *, GRAPH *, int, int)
Definition: grphbase.c:766
int *RESTRICT head
Definition: grph.h:96
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: grph.h:57
int source
Definition: grph.h:67
#define STP_GSTP
Definition: grph.h:49
Constraint handler for Steiner problems.
SCIP_Bool graph_valid(const GRAPH *)
Definition: grphbase.c:4324
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1866
SCIP_VAR ** SCIPprobdataGetVars(SCIP *scip)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17400
SCIP_RETCODE graph_init_history(SCIP *, GRAPH *)
Definition: grphbase.c:3569
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int norgmodeledges
Definition: grph.h:88
#define EAT_LAST
Definition: grph.h:31
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16910
#define HEUR_TIMING
reduction and dual-cost based primal heuristic for Steiner problems
#define FALSE
Definition: def.h:72
#define HEUR_DESC
#define STP_RMWCSP
Definition: grph.h:50
void graph_free(SCIP *, GRAPH **, SCIP_Bool)
Definition: grphbase.c:3674
Problem data for stp problem.
#define TRUE
Definition: def.h:71
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
void graph_path_exit(SCIP *, GRAPH *)
Definition: grphpath.c:466
int SCIPprobdataGetNVars(SCIP *scip)
SCIP_Bool SCIPisDualfeasZero(SCIP *scip, SCIP_Real val)
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
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 STP_PCSPG
Definition: grph.h:40
#define SCIPdebugMessage
Definition: pub_message.h:77
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1175
void graph_pc_updateTerm2edge(GRAPH *, const GRAPH *, int, int, int, int)
Definition: grphbase.c:928
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)
int *RESTRICT mark
Definition: grph.h:70
int *RESTRICT oeat
Definition: grph.h:103
#define CONNECT
Definition: grph.h:154
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1254
SCIP_Bool extended
Definition: grph.h:128
int stp_type
Definition: grph.h:127
#define HEUR_DISPCHAR
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)
#define Is_pterm(a)
Definition: grph.h:169
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 SCIPgetDualbound(SCIP *scip)
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:143
SCIP_Real * prize
Definition: grph.h:82
int *RESTRICT grad
Definition: grph.h:73
SCIP_Bool graph_sol_valid(SCIP *, const GRAPH *, const int *)
Definition: grphbase.c:3066
#define ASCENPRUNE_MINLPIMPROVE
int knots
Definition: grph.h:62
#define SCIP_CALL(x)
Definition: def.h:358
int * term2edge
Definition: grph.h:80
Improvement heuristic for Steiner problems.
SCIP_Bool SCIPisDualfeasNegative(SCIP *scip, SCIP_Real val)
reduction-based primal heuristic for Steiner problems
#define FARAWAY
Definition: grph.h:156
#define HEUR_PRIORITY
#define STP_SPG
Definition: grph.h:38
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
public data structures and miscellaneous methods
#define HEUR_NAME
#define SCIP_Bool
Definition: def.h:69
static SCIP_DECL_HEUREXEC(heurExecAscendPrune)
#define STP_MWCSP
Definition: grph.h:47
int *RESTRICT tail
Definition: grph.h:95
#define HEUR_MAXDEPTH
static SCIP_DECL_HEURINIT(heurInitAscendPrune)
SCIP_RETCODE SCIPStpIncludeHeurAscendPrune(SCIP *scip)
int *RESTRICT term
Definition: grph.h:68
SCIP_Real graph_sol_getObj(const SCIP_Real *, const int *, SCIP_Real, int)
Definition: grphbase.c:3196
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1493
static SCIP_DECL_HEURFREE(heurFreeAscendPrune)
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 HEUR_FREQ
SCIP_Bool SCIPisDualfeasPositive(SCIP *scip, SCIP_Real val)
#define Is_term(a)
Definition: grph.h:168
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2362
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:1020
static SCIP_DECL_HEURCOPY(heurCopyAscendPrune)
SCIP_Real * cost
Definition: grph.h:94
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:264
SCIP_VAR * a
Definition: circlepacking.c:57
#define SCIP_Real
Definition: def.h:157
int *RESTRICT outbeg
Definition: grph.h:76
SCIP_RETCODE SCIPStpHeurTMPrunePc(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int *result, STP_Bool *connected)
Definition: heur_tm.c:168
#define SCIP_INVALID
Definition: def.h:177
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
#define flipedge(edge)
Definition: grph.h:150
void graph_knot_add(GRAPH *, int)
Definition: grphbase.c:2196
#define DEFAULT_MAXFREQPRUNE
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:70
#define HEUR_USESSUBSCIP
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
#define UNKNOWN
Definition: sepa_mcf.c:4081
#define STP_RSMT
Definition: grph.h:45
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:17410
#define nnodes
Definition: gastrans.c:65
#define STP_OARSMT
Definition: grph.h:46
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:119
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1165
#define HEUR_FREQOFS
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1410
SCIP_RETCODE SCIPStpHeurTMPrune(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int layer, int *result, STP_Bool *connected)
Definition: heur_tm.c:556
void graph_edge_add(SCIP *, GRAPH *, int, int, double, double)
default SCIP plugins
#define STP_RPCSPG
Definition: grph.h:41
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2584
SCIP callable library.
SCIP_RETCODE graph_init(SCIP *, GRAPH **, int, int, int)
Definition: grphbase.c:3491
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
int norgmodelknots
Definition: grph.h:60