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-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_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 //#define SCIP_DEBUG
30 //#define DEBUG_ASCENDPRUNE
31 #include <assert.h>
32 #include <string.h>
33 #include <stdio.h>
34 #include "scip/scip.h"
35 #include "scip/scipdefplugins.h"
36 #include "scip/cons_linear.h"
37 #include "heur_ascendprune.h"
38 #include "heur_local.h"
39 #include "heur_prune.h"
40 #include "graph.h"
41 #include "reduce.h"
42 #include "heur_tm.h"
43 #include "solstp.h"
44 #include "solpool.h"
45 #include "redcosts.h"
46 #include "cons_stp.h"
47 #include "probdata_stp.h"
48 
49 #define HEUR_NAME "ascendprune"
50 #define HEUR_DESC "Dual-cost reduction heuristic for Steiner problems"
51 #define HEUR_DISPCHAR 'A'
52 #define HEUR_PRIORITY 2
53 #define HEUR_FREQ -1
54 #define HEUR_FREQOFS 0
55 #define HEUR_MAXDEPTH -1
56 #define HEUR_TIMING (SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE)
57 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
58 
59 #define DEFAULT_MAXFREQPRUNE FALSE /**< executions of the heuristic at maximum frequency? */
60 #define ASCENPRUNE_MINLPIMPROVE 0.2 /**< minimum percentual improvement of dual bound (wrt to gap) mandatory to execute heuristic */
61 
62 #ifdef WITH_UG
63 int getUgRank(void);
64 #endif
65 
66 /*
67  * Data structures
68  */
69 
70 /** primal heuristic data */
71 struct SCIP_HeurData
72 {
73  SCIP_Real lastdualbound; /**< dual bound after the previous run */
74  int bestsolindex; /**< best solution during the previous run */
75  int nfailures; /**< number of failures since last successful call */
76  SCIP_Bool maxfreq; /**< should the heuristic be called at maximum frequency? */
77 };
78 
79 
80 /** subgraph data */
81 typedef struct redcost0_graph
82 {
83  const SCIP_Real* redcosts; /**< the reduced costs */
84  GRAPH* newgraph; /**< graph */
85  int* edgelist; /**< edge list for new graph */
88  int nnodes; /**< nodes */
89  int nedges_half; /**< edges */
90  int root; /**< red cost root */
91 } RCGRAPH;
92 
93 
94 /*
95  * Local methods
96  */
97 
98 
99 #ifdef DEBUG_ASCENDPRUNE
100 /** debug method */
101 static
102 SCIP_RETCODE checkRedCostGraph(
103  const GRAPH* g, /**< the graph */
104  const RCGRAPH* redcostgraph /**< the redcost graph */
105 )
106 {
107  GRAPH* redgraph = redcostgraph->newgraph;
108  const SCIP_Bool pcmw = graph_pc_isPcMw(g);
109  const int nnodes = graph_get_nNodes(g);
110  const int *nodechild = redcostgraph->nodeOrg2NewMap;
111 
112  if( graph_pc_isRootedPcMw(g) )
113  {
114  for( int k = 0; k < nnodes; k++ )
115  {
116  if( graph_pc_knotIsFixedTerm(g, k) )
117  {
118  if( nodechild[k] < 0 || !graph_pc_knotIsFixedTerm(redgraph, nodechild[k]) )
119  {
120  printf("RPCMW child FAIL in AP \n\n\n");
121  return SCIP_ERROR;
122  }
123  }
124  }
125  }
126 
127  for( int k = 0; k < nnodes && !pcmw; k++ )
128  {
129  if( Is_term(g->term[k]) )
130  {
131  const int i = nodechild[k];
132  if( i < 0 )
133  {
134  printf("FAIL in AP \n\n\n");
135  return SCIP_ERROR;
136  }
137 
138  if( redgraph->grad[i] == 0 && redgraph->knots > 1 )
139  {
140  printf("FAIL GRAD \n\n\n");
141  return SCIP_ERROR;
142  }
143  }
144  }
145 
146  return SCIP_OKAY;
147 }
148 
149 
150 static
151 SCIP_RETCODE checkRedCostEdges(
152  SCIP* scip, /**< SCIP data structure */
153  const GRAPH* g, /**< the graph */
154  const RCGRAPH* redcostgraph /**< the redcost graph */
155 )
156 {
157  const int* const subgraphedges = redcostgraph->edgelist;
158  SCIP_Bool* halfedge_mark;
159  const int nedges = graph_get_nEdges(g);
160  const int nedges_redocst = redcostgraph->nedges_half;
161 
162  assert(subgraphedges);
163 
164  SCIP_CALL( SCIPallocMemoryArray(scip, &halfedge_mark, nedges / 2) );
165  BMSclearMemoryArray(halfedge_mark, nedges / 2);
166 
167  for( int e = 0; e < nedges_redocst; e++ )
168  {
169  const int halfedge = subgraphedges[e] / 2;
170 
171  if( halfedge_mark[halfedge] )
172  {
173  printf("checkRedCostEdges FAIL at %d \n", e);
174  return SCIP_ERROR;
175  }
176 
177  halfedge_mark[halfedge] = TRUE;
178  }
179 
180  SCIPfreeMemoryArray(scip, &halfedge_mark);
181 
182  return SCIP_OKAY;
183 }
184 #endif
185 
186 #ifndef NDEBUG
187 /** gets number of terms that are marked */
188 static
190  const GRAPH* g, /**< the graph */
191  const RCGRAPH* redcostgraph /**< reduced cost graph data */
192  )
193 {
194  int nterms = 0;
195  const int nnodes = graph_get_nNodes(g);
196 
197  for( int i = 0; i < nnodes; i++ )
198  {
199  if( g->mark[i] && Is_term(g->term[i]) )
200  nterms++;
201  }
202 
203  return nterms;
204 }
205 #endif
206 
207 
208 /** marks part of graph corresponding to zero cost paths from the root to all terminals */
209 static
211  SCIP* scip, /**< SCIP data structure */
212  const GRAPH* g, /**< the graph */
213  RCGRAPH* redcostgraph /**< reduced cost graph data structure */
214  )
215 {
216  int* RESTRICT mark = g->mark;
217  int* RESTRICT queue;
218  STP_Bool* RESTRICT scanned;
219  int* RESTRICT subgraphedges;
220  const SCIP_Real* redcosts = redcostgraph->redcosts;
221  int qsize;
222  int nnewnodes = 0;
223  int nnewedges = 0;
224  const int nnodes = graph_get_nNodes(g);
225  const int nedges = graph_get_nEdges(g);
226  const SCIP_Bool pcmw = graph_pc_isPcMw(g);
227  const int root_redcost = redcostgraph->root;
228 
229  assert(graph_knot_isInRange(g, root_redcost));
230 
231  /* perform DFS to identify 0-redcost subgraph.
232  */
233 
234  SCIP_CALL( SCIPallocBufferArray(scip, &queue, nnodes ) );
235  SCIP_CALL( SCIPallocBufferArray(scip, &scanned, nnodes) );
236  SCIP_CALL( SCIPallocBufferArray(scip, &subgraphedges, nedges) );
237  redcostgraph->edgelist = subgraphedges;
238 
239  BMSclearMemoryArray(mark, nnodes);
240  BMSclearMemoryArray(scanned, nnodes);
241 
242  qsize = 0;
243  mark[root_redcost] = TRUE;
244  queue[qsize++] = root_redcost;
245  nnewnodes++;
246 
247  /* DFS */
248  while( qsize > 0 )
249  {
250  const int k = queue[--qsize];
251  scanned[k] = TRUE;
252 
253  for( int a = g->outbeg[k]; a != EAT_LAST; a = g->oeat[a] )
254  {
255  const int head = g->head[a];
256 
257  if( SCIPisZero(scip, redcosts[a]) )
258  {
259  SCIP_Bool isRootEdge;
260  /* NOTE: avoid dummy edges */
261  if( pcmw && k == g->source && graph_pc_knotIsDummyTerm(g, head) )
262  continue;
263 
264  /* vertex not visited yet? */
265  if( !mark[head] )
266  {
267  mark[head] = TRUE;
268  nnewnodes++;
269  queue[qsize++] = head;
270  }
271 
272  isRootEdge = (k == root_redcost || head == root_redcost);
273 
274  /* NOTE: we need to be careful to not mark anti-parallel edges. We also do not mark out-going edges from the root */
275  if( !isRootEdge && (!scanned[head] || !SCIPisZero(scip, redcosts[flipedge(a)])) )
276  {
277  assert(g->tail[a] != root_redcost && g->head[a] != root_redcost);
278 
279  subgraphedges[nnewedges++] = a;
280  }
281  }
282  }
283  }
284 
285 #ifndef NDEBUG
286  for( int k = 0; k < nnewedges && pcmw; k++ )
287  {
288  const int e = subgraphedges[k];
289  assert(g->tail[e] != root_redcost && g->head[e] != root_redcost);
290  }
291 #endif
292 
293  for( int a = g->outbeg[root_redcost]; a != EAT_LAST; a = g->oeat[a] )
294  {
295  const int head = g->head[a];
296  if( mark[head] )
297  {
298  subgraphedges[nnewedges++] = a;
299  }
300  }
301 
302  /* we need to make sure that the dummy terminals are connected from the root */
303  if( pcmw && root_redcost != g->source )
304  {
305  assert(graph_pc_isRootedPcMw(g));
306  assert(mark[g->source]);
307 
308  for( int a = g->outbeg[g->source]; a != EAT_LAST; a = g->oeat[a] )
309  {
310  const int head = g->head[a];
311  if( mark[head] && graph_pc_knotIsDummyTerm(g, head) )
312  {
313  subgraphedges[nnewedges++] = a;
314  }
315  }
316  }
317 
318  SCIPfreeBufferArray(scip, &scanned);
319  SCIPfreeBufferArray(scip, &queue);
320 
321  redcostgraph->nnodes = nnewnodes;
322  redcostgraph->nedges_half = nnewedges;
323 
324 #ifdef SCIP_DEBUG
325  SCIPdebugMessage("redcost graph: |V|=%d, |A|=%d ... original graph: \n", nnewnodes, nnewedges);
327 #endif
328 
329 #ifdef DEBUG_ASCENDPRUNE
330  SCIP_CALL( checkRedCostEdges(scip, g, redcostgraph) );
331 #endif
332 
333  assert(graph_typeIsUndirected(g) || g->terms == redcostGetNTermsMarked(g, redcostgraph));
334  assert(graph_pc_isPcMw(g) || redcostGetNTermsMarked(g, redcostgraph) == g->terms);
335 
336  return SCIP_OKAY;
337 }
338 
339 
340 /** builds graphs */
341 static
343  SCIP* scip, /**< SCIP data structure */
344  const GRAPH* g, /**< the graph */
345  RCGRAPH* redcostgraph /**< reduced cost graph data structure */
346  )
347 {
348  GRAPH* newgraph;
349  const int nnodes = graph_get_nNodes(g);
350  const SCIP_Bool pcmw = graph_pc_isPcMw(g);
351  const int probtype = g->stp_type;
352  const int* const nodes_isMarked = g->mark;
353  const int* const newedges = redcostgraph->edgelist;
354  const int nnewnodes = redcostgraph->nnodes;
355  const int nnewedges = redcostgraph->nedges_half;
356  int* edgeNew2OrgMap;
357  int* nodeOrg2NewMap;
358 
359  assert(newedges);
360  assert(nnewnodes > 0 && nnewedges > 0);
361  assert(graph_knot_isInRange(g, redcostgraph->root));
362 
363  SCIP_CALL( SCIPallocBufferArray(scip, &nodeOrg2NewMap, nnodes ) );
364  SCIP_CALL( SCIPallocBufferArray(scip, &edgeNew2OrgMap, 2 * nnewedges) );
365  redcostgraph->edgeNew2OrgMap = edgeNew2OrgMap;
366  redcostgraph->nodeOrg2NewMap = nodeOrg2NewMap;
367 
368 #ifndef NDEBUG
369  for( int e = 0; e < 2 * nnewedges; e++ )
370  edgeNew2OrgMap[e] = UNKNOWN;
371 #endif
372 
373  /* initialize new graph */
374  SCIP_CALL( graph_init(scip, &(redcostgraph->newgraph), nnewnodes, 2 * nnewedges, 1) );
375  newgraph = redcostgraph->newgraph;
376  newgraph->hoplimit = g->hoplimit;
377 
378  if( graph_typeIsSpgLike(g) )
379  newgraph->stp_type = STP_SPG;
380  else
381  newgraph->stp_type = probtype;
382 
383  if( pcmw )
384  SCIP_CALL( graph_pc_initSubgraph(scip, newgraph) );
385 
386  for( int k = 0; k < nnodes; k++ )
387  {
388  if( nodes_isMarked[k] )
389  {
390  if( pcmw )
391  {
392  assert(g->extended);
393  newgraph->prize[newgraph->knots] = g->prize[k];
394 
395  assert(!graph_pc_knotIsDummyTerm(g, k) || 0.0 == newgraph->prize[newgraph->knots]);
396  }
397 
398  nodeOrg2NewMap[k] = newgraph->knots;
399  graph_knot_add(newgraph, g->term[k]);
400  }
401  else
402  {
403  nodeOrg2NewMap[k] = UNKNOWN;
404  }
405  }
406 
407  if( pcmw )
408  {
409  newgraph->norgmodelknots = nnewnodes;
410  newgraph->extended = TRUE;
411  }
412 
413  assert(nnewnodes == newgraph->knots);
414 
415  /* set root of new graph */
416  if( pcmw )
417  newgraph->source = nodeOrg2NewMap[g->source];
418  else
419  newgraph->source = nodeOrg2NewMap[redcostgraph->root];
420 
421  assert(newgraph->source >= 0);
422  assert(!graph_pc_isRootedPcMw(g) || newgraph->prize[newgraph->source] == FARAWAY);
423 
424  /* add edges to new graph */
425  for( int a = 0; a < nnewedges; a++ )
426  {
427  int i;
428  const int e = newedges[a];
429  const int tail = nodeOrg2NewMap[g->tail[e]];
430  const int head = nodeOrg2NewMap[g->head[e]];
431 
432  assert(tail >= 0);
433  assert(head >= 0);
434 
435  for( i = newgraph->outbeg[tail]; i != EAT_LAST; i = newgraph->oeat[i] )
436  {
437  if( newgraph->head[i] == head )
438  break;
439  }
440 
441  // todo should always hold?
442  assert(i == EAT_LAST);
443 
444  /* edge not added yet? */
445  if( i == EAT_LAST )
446  {
447  edgeNew2OrgMap[newgraph->edges] = e;
448  edgeNew2OrgMap[newgraph->edges + 1] = flipedge(e);
449 
450  graph_edge_addSubgraph(scip, g, nodeOrg2NewMap, e, newgraph);
451  }
452  }
453 
454  if( probtype == STP_DCSTP )
455  {
456  assert(g->maxdeg && !newgraph->maxdeg);
457  SCIP_CALL( SCIPallocMemoryArray(scip, &(newgraph->maxdeg), nnewnodes ) );
458 #ifndef NDEBUG
459  for( int k = 0; k < nnewnodes; k++ )
460  newgraph->maxdeg[k] = -1;
461 #endif
462 
463  for( int k = 0; k < nnodes; k++ )
464  {
465  const int subnode = nodeOrg2NewMap[k];
466  if( subnode >= 0 )
467  {
468  assert(graph_knot_isInRange(newgraph, subnode));
469  assert(newgraph->maxdeg[subnode] == -1);
470 
471  newgraph->maxdeg[subnode] = g->maxdeg[k];
472  }
473  }
474 
475 #ifndef NDEBUG
476  for( int k = 0; k < nnewnodes; k++ )
477  assert(newgraph->maxdeg[k] >= 1);
478 #endif
479  }
480 
481  newgraph->norgmodeledges = newgraph->edges;
482 
483  assert(!pcmw || TERM2EDGE_FIXEDTERM == newgraph->term2edge[newgraph->source]);
484 
485  SCIP_CALL( graph_pc_finalizeSubgraph(scip, newgraph) );
486  SCIP_CALL( graph_initHistory(scip, newgraph) );
487 
488  assert(graph_pc_isPcMw(g) || graph_valid(scip, newgraph));
489 
490  return SCIP_OKAY;
491 }
492 
493 
494 /** frees members */
495 static
497  SCIP* scip, /**< SCIP data structure */
498  RCGRAPH* redcostgraph /**< reduced cost graph data structure */
499  )
500 {
501  if( redcostgraph->newgraph )
502  {
503  graph_free(scip, &(redcostgraph->newgraph), TRUE);
504  }
505  SCIPfreeBufferArrayNull(scip, &(redcostgraph->edgeNew2OrgMap));
506  SCIPfreeBufferArrayNull(scip, &(redcostgraph->nodeOrg2NewMap));
507  SCIPfreeBufferArrayNull(scip, &(redcostgraph->edgelist));
508 }
509 
510 
511 /** retransforms solution on subgraph */
512 static
514  SCIP* scip, /**< SCIP data structure */
515  const GRAPH* g, /**< the graph */
516  const RCGRAPH* redcostgraph, /**< reduced cost graph data structure */
517  const int* subresult, /**< solution for new graph, can also be NULL */
518  int* result /**< solution for original graph; for STP like also keeps sub-solution */
519  )
520 {
521  const GRAPH* newgraph = redcostgraph->newgraph;
522  const int* const edgeNew2OrgMap = redcostgraph->edgeNew2OrgMap;
523  const int nnewedges = graph_get_nEdges(newgraph);
524 
525  if( g->stp_type == STP_DCSTP || graph_typeIsDirected(g) )
526  {
527  const int nedges = graph_get_nEdges(g);
528 
529  assert(subresult);
530  assert(solstp_isValid(scip, newgraph, subresult));
531 
532  for( int e = 0; e < nedges; e++ )
533  result[e] = UNKNOWN;
534 
535  for( int e = 0; e < nnewedges; e++ )
536  {
537  if( subresult[e] == CONNECT )
538  {
539  const int eorg = edgeNew2OrgMap[e];
540  assert(graph_edge_isInRange(g, eorg));
541  result[eorg] = CONNECT;
542  }
543  }
544 
545  if( redcostgraph->root != g->source )
546  {
547  assert(g->stp_type == STP_DCSTP);
548  solstp_reroot(scip, g, result, g->source);
549  }
550 
551  assert(solstp_isValid(scip, g, result));
552  }
553  else
554  {
555  STP_Bool* RESTRICT nodearrchar;
556  const int nnodes = graph_get_nNodes(g);
557 
558  assert(!subresult);
559  assert(solstp_isValid(scip, newgraph, result));
560 
561  /* NOTE: here we also prune solution in original graph */
562  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrchar, nnodes ) );
563  BMSclearMemoryArray(nodearrchar, nnodes);
564 
565  for( int e = 0; e < nnewedges; e++ )
566  {
567  if( result[e] == CONNECT )
568  {
569  const int eorg = edgeNew2OrgMap[e];
570  assert(graph_edge_isInRange(g, eorg));
571 
572  nodearrchar[g->tail[eorg]] = TRUE;
573  nodearrchar[g->head[eorg]] = TRUE;
574  }
575  }
576 
577  if( newgraph->knots == 1 )
578  nodearrchar[g->source] = TRUE;
579 
580  SCIP_CALL( solstp_prune(scip, g, result, nodearrchar) );
581 
582  SCIPfreeBufferArray(scip, &nodearrchar);
583  }
584 
585  SCIPdebugMessage("obj after retransformation %f \n", solstp_getObj(g, result, 0.0));
586 
587  assert(solstp_isValid(scip, g, result));
588 
589  return SCIP_OKAY;
590 }
591 
592 
593 /** builds Steiner tree on subgraph */
594 static
596  SCIP* scip, /**< SCIP data structure */
597  const GRAPH* g, /**< the graph */
598  RCGRAPH* redcostgraph, /**< reduced cost graph data structure */
599  int* result /**< solution array */
600  )
601 {
602  GRAPH* newgraph = redcostgraph->newgraph;
603  SCIP_Bool success;
604 
605  SCIP_CALL( graph_path_init(scip, newgraph) );
606  SCIP_CALL( reduce_unconnected(scip, newgraph) );
607  assert(graph_valid(scip, newgraph));
608 
609 #ifdef DEBUG_ASCENDPRUNE
610  SCIP_CALL( checkRedCostGraph(g, redcostgraph) );
611 #endif
612 
613  /* get solution on new graph by PRUNE heuristic */
614  SCIP_CALL( SCIPStpHeurPruneRun(scip, NULL, newgraph, result, &success, FALSE, TRUE) );
615 
616 #ifndef NDEBUG
617  for( int k = 0; k < newgraph->knots; ++k )
618  {
619  assert( !(Is_term(newgraph->term[k]) && newgraph->grad[k] == 0 && k != newgraph->source) );
620  }
621  assert(solstp_isValid(scip, newgraph, result));
622 #endif
623 
624  assert(success && solstp_isValid(scip, newgraph, result));
625 
626  SCIPdebugMessage("obj after prune %f \n", solstp_getObjBounded(newgraph, result, 0.0, newgraph->edges));
627 
628  SCIP_CALL( SCIPStpHeurLocalRun(scip, newgraph, result) );
629 
630  SCIPdebugMessage("obj after local %f \n", solstp_getObjBounded(newgraph, result, 0.0, newgraph->edges));
631 
632  assert(solstp_isValid(scip, newgraph, result));
633  graph_path_exit(scip, newgraph);
634 
635  SCIP_CALL( redcostGraphSolRetransform(scip, g, redcostgraph, NULL, result) );
636 
637  return SCIP_OKAY;
638 }
639 
640 
641 /** builds Steiner tree on directed subgraph */
642 static
644  SCIP* scip, /**< SCIP data structure */
645  const GRAPH* g, /**< the graph */
646  RCGRAPH* redcostgraph, /**< reduced cost graph data structure */
647  int* result, /**< solution array */
648  SCIP_Bool* solfound /**< has a solution been found? */
649  )
650 {
651  GRAPH* const subgraph = redcostgraph->newgraph;
652  int* startstm = NULL;
653  int* subresult;
654  SCIP_Real* cost;
655  SCIP_Real* costrev;
656  const int nsubnodes = graph_get_nNodes(subgraph);
657  const int nsubedges = graph_get_nEdges(subgraph);
658  int runstm = 50;
659  SCIP_Real hopfactor = 10.0;
660 
661  assert(TRUE == *solfound);
662 
663  SCIP_CALL( graph_path_init(scip, subgraph) );
664  SCIP_CALL( reduce_unconnectedForDirected(scip, subgraph) );
665  assert(graph_valid(scip, subgraph));
666 
667 #ifdef DEBUG_ASCENDPRUNE
668  SCIP_CALL( checkRedCostGraph(g, redcostgraph) );
669 #endif
670 
671  SCIP_CALL( SCIPallocBufferArray(scip, &subresult, nsubedges ) );
672 
673  /* build solution on new graph */
674 
675  if( g->stp_type != STP_NWPTSPG )
676  {
677  SCIP_CALL( SCIPallocBufferArray(scip, &startstm, nsubnodes) );
678  SCIPStpHeurTMCompStarts(subgraph, startstm, &runstm);
679  assert(startstm[0] == subgraph->source);
680  }
681 
682  SCIP_CALL( SCIPallocBufferArray(scip, &cost, nsubedges) );
683  SCIP_CALL( SCIPallocBufferArray(scip, &costrev, nsubedges) );
684 
685  graph_getEdgeCosts(subgraph, cost, costrev);
686 
688  subgraph, startstm, NULL, subresult, runstm, subgraph->source, cost, costrev, &hopfactor, NULL, solfound) );
689 
690  SCIPfreeBufferArray(scip, &costrev);
691  SCIPfreeBufferArray(scip, &cost);
692  SCIPfreeBufferArrayNull(scip, &startstm);
693 
694  graph_path_exit(scip, subgraph);
695 
696  if( FALSE == *solfound )
697  {
698  assert(subgraph->stp_type == STP_DHCSTP);
699  SCIPdebugMessage("ascend-and-prune did not find a feasible solution, aborting... \n");
700 
701  SCIPfreeBufferArray(scip, &subresult);
702  return SCIP_OKAY;
703  }
704 
705  SCIPdebugMessage("sub-obj after TM %f \n", solstp_getObj(subgraph, subresult, 0.0));
706  assert(solstp_isValid(scip, subgraph, subresult));
707 
708  SCIP_CALL( redcostGraphSolRetransform(scip, g, redcostgraph, subresult, result) );
709 
710  SCIPfreeBufferArray(scip, &subresult);
711 
712  return SCIP_OKAY;
713 }
714 
715 
716 
717 /** builds Steiner tree for DCSTP */
718 static
720  SCIP* scip, /**< SCIP data structure */
721  const GRAPH* g, /**< the graph */
722  RCGRAPH* redcostgraph, /**< reduced cost graph data structure */
723  int* result, /**< solution array */
724  SCIP_Bool* solfound /**< has a solution been found? */
725  )
726 {
727  GRAPH* const subgraph = redcostgraph->newgraph;
728  int* subresult;
729  SCIP_Real* cost;
730  SCIP_Real* costrev;
731  const int nsubedges = graph_get_nEdges(subgraph);
732  int runstm = 100;
733 
734  assert(TRUE == *solfound);
735  assert(g->stp_type == STP_DCSTP);
736 
737  SCIP_CALL( graph_path_init(scip, subgraph) );
738  SCIP_CALL( reduce_unconnected(scip, subgraph) );
739  assert(graph_valid(scip, subgraph));
740 
741 #ifdef DEBUG_ASCENDPRUNE
742  SCIP_CALL( checkRedCostGraph(g, redcostgraph) );
743 #endif
744 
745  SCIP_CALL( SCIPallocBufferArray(scip, &subresult, nsubedges ) );
746  SCIP_CALL( SCIPallocBufferArray(scip, &cost, nsubedges) );
747  SCIP_CALL( SCIPallocBufferArray(scip, &costrev, nsubedges) );
748 
749  graph_getEdgeCosts(subgraph, cost, costrev);
750 
751  /* build solution on new graph */
753  subgraph, NULL, NULL, subresult, runstm, subgraph->source, cost, costrev, NULL, NULL, solfound) );
754 
755  SCIPfreeBufferArray(scip, &costrev);
756  SCIPfreeBufferArray(scip, &cost);
757 
758  graph_path_exit(scip, subgraph);
759 
760  if( FALSE == *solfound )
761  {
762  SCIPdebugMessage("ascend-and-prune did not find a feasible solution, aborting... \n");
763 
764  SCIPfreeBufferArray(scip, &subresult);
765  return SCIP_OKAY;
766  }
767 
768  SCIPdebugMessage("sub-obj after TM %f \n", solstp_getObj(subgraph, subresult, 0.0));
769  assert(solstp_isValid(scip, subgraph, subresult));
770 
771  SCIP_CALL( redcostGraphSolRetransform(scip, g, redcostgraph, subresult, result) );
772 
773  SCIPfreeBufferArray(scip, &subresult);
774 
775  return SCIP_OKAY;
776 }
777 
778 
779 /*
780  * Callback methods of primal heuristic
781  */
782 
783 
784 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
785 static
786 SCIP_DECL_HEURCOPY(heurCopyAscendPrune)
787 { /*lint --e{715}*/
788  assert(scip != NULL);
789  assert(heur != NULL);
790  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
791 
792  /* call inclusion method of primal heuristic */
794 
795  return SCIP_OKAY;
796 }
797 
798 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
799 static
800 SCIP_DECL_HEURFREE(heurFreeAscendPrune)
801 { /*lint --e{715}*/
802  SCIP_HEURDATA* heurdata;
803 
804  assert(heur != NULL);
805  assert(scip != NULL);
806 
807  /* get heuristic data */
808  heurdata = SCIPheurGetData(heur);
809  assert(heurdata != NULL);
810 
811  /* free heuristic data */
812  SCIPfreeMemory(scip, &heurdata);
813  SCIPheurSetData(heur, NULL);
814 
815  return SCIP_OKAY;
816 }
817 
818 
819 /** initialization method of primal heuristic (called after problem was transformed) */
820 
821 static
822 SCIP_DECL_HEURINIT(heurInitAscendPrune)
823 { /*lint --e{715}*/
824  SCIP_HEURDATA* heurdata;
825 
826  assert(heur != NULL);
827  assert(scip != NULL);
828 
829  /* get heuristic's data */
830  heurdata = SCIPheurGetData(heur);
831 
832  assert(heurdata != NULL);
833 
834  /* initialize data */
835  heurdata->nfailures = 0;
836  heurdata->bestsolindex = -1;
837  heurdata->lastdualbound = 0.0;
838 
839  return SCIP_OKAY;
840 }
841 
842 /** execution method of primal heuristic */
843 static
844 SCIP_DECL_HEUREXEC(heurExecAscendPrune)
845 { /*lint --e{715}*/
846  SCIP_HEURDATA* heurdata;
847  SCIP_PROBDATA* probdata;
848  SCIP_VAR** vars;
849  SCIP_SOL* bestsol; /* best known solution */
850  GRAPH* graph;
851  SCIP_Real dualbound;
852  SCIP_Real gap;
853  SCIP_Real* redcosts;
854  SCIP_Bool solAdded;
855  int nedges;
856  int* edgearrint;
857 
858  assert(heur != NULL);
859  assert(scip != NULL);
860  assert(result != NULL);
861  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
862 
863  heurdata = SCIPheurGetData(heur);
864  assert(heurdata != NULL);
865 
866  probdata = SCIPgetProbData(scip);
867  assert(probdata != NULL);
868 
869  graph = SCIPprobdataGetGraph(probdata);
870  assert(graph != NULL);
871 
872  vars = SCIPprobdataGetVars(scip);
873  assert(vars != NULL);
874 
875  *result = SCIP_DIDNOTRUN;
876 
877  if( !redcosts_forLPareAvailable(scip) )
878  return SCIP_OKAY;
879 
880  nedges = graph->edges;
881  solAdded = FALSE;
882 
883  bestsol = SCIPgetBestSol(scip);
884 
885  /* no solution available? */
886  if( bestsol == NULL )
887  return SCIP_OKAY;
888 
889  /* get dual bound */
890  dualbound = SCIPgetDualbound(scip);
891 
892  /* no new best solution available? */
893  if( heurdata->bestsolindex == SCIPsolGetIndex(SCIPgetBestSol(scip)) && !(heurdata->maxfreq) )
894  {
895  /* current optimality gap */
896  gap = SCIPgetSolOrigObj(scip, bestsol) - dualbound;
897 
898  if( SCIPisLT(scip, dualbound - heurdata->lastdualbound, gap * ASCENPRUNE_MINLPIMPROVE ) )
899  return SCIP_OKAY;
900  }
901 
902  printf("CALL ascend-prune \n");
903 
904  heurdata->lastdualbound = dualbound;
905 
906  /* allocate memory for ascend-and-prune */
907  SCIP_CALL( SCIPallocBufferArray(scip, &redcosts, nedges) );
908  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrint, nedges) );
909 
910  redcosts_forLPget(scip, vars, graph, redcosts);
911 
912  /* perform ascent and prune */
913  SCIP_CALL( SCIPStpHeurAscendPruneRun(scip, heur, graph, redcosts, edgearrint, graph->source, &solAdded, TRUE) );
914 
915  if( solAdded )
916  {
917  heurdata->nfailures = 0;
918  *result = SCIP_FOUNDSOL;
919  }
920  else
921  {
922  heurdata->nfailures++;
923  }
924 
925  heurdata->bestsolindex = SCIPsolGetIndex(SCIPgetBestSol(scip));
926 
927  SCIPfreeBufferArray(scip, &edgearrint);
928  SCIPfreeBufferArray(scip, &redcosts);
929 
930  return SCIP_OKAY;
931 }
932 
933 
934 /*
935  * primal heuristic specific interface methods
936  */
937 
938 
939 /** ascent and prune */
941  SCIP* scip, /**< SCIP data structure */
942  SCIP_HEUR* heur, /**< heuristic data structure or NULL */
943  const GRAPH* g, /**< the graph */
944  const SCIP_Real* redcosts, /**< the reduced costs */
945  int* result, /**< int edges array to store solution */
946  int root, /**< the root (used for dual ascent) */
947  SCIP_Bool* solfound, /**< has a solution been found? And added, if requested? */
948  SCIP_Bool addsol /**< should the solution be added to SCIP by this method? */
949  )
950 {
951  RCGRAPH redcostgraph = { .newgraph = NULL, .redcosts = redcosts, .edgelist = NULL, .nodeOrg2NewMap = NULL, .edgeNew2OrgMap = NULL,
952  .nnodes = -1, . nedges_half = -1, .root = root };
953 
954  assert(scip && redcosts && result && solfound);
955  assert(!graph_pc_isPcMw(g) || g->extended);
956  assert(graph_valid(scip, g));
957 
958  *solfound = TRUE;
959 
960  if( root < 0 )
961  redcostgraph.root = g->source;
962 
963  assert(Is_term(g->term[redcostgraph.root]));
964  assert(!graph_pc_isPcMw(g) || graph_pc_knotIsFixedTerm(g, redcostgraph.root));
965 
966  SCIP_CALL( redcostGraphMark(scip, g, &redcostgraph) );
967 
968  if( redcostgraph.nedges_half == 0 )
969  {
970  assert(g->stp_type == STP_RMWCSP);
971  solstp_getTrivialSol(g, result);
972  redcostGraphFree(scip, &redcostgraph);
973 
974  return SCIP_OKAY;
975  }
976 
977  SCIP_CALL( redcostGraphBuild(scip, g, &redcostgraph) );
978 
979  if( g->stp_type == STP_DCSTP )
980  {
981  SCIP_CALL( redcostGraphComputeSteinerTreeDegCons(scip, g, &redcostgraph, result, solfound) );
982  }
983  else if( graph_typeIsUndirected(g) )
984  {
985  SCIP_CALL( redcostGraphComputeSteinerTree(scip, g, &redcostgraph, result) );
986  }
987  else
988  {
989  SCIP_CALL( redcostGraphComputeSteinerTreeDirected(scip, g, &redcostgraph, result, solfound) );
990  }
991 
992  assert(!(*solfound) || solstp_isValid(scip, g, result));
993 
994 #ifdef SCIP_DEBUG
995  if( *solfound )
996  {
997  graph_printInfo(g);
998  printf("ascend-prune obj=%f \n", solstp_getObj(g, result, 0.0));
999  }
1000 #endif
1001 
1002  if( *solfound && addsol )
1003  {
1004  SCIP_CALL( solpool_addSolToScip(scip, heur, g, result, solfound) );
1005  SCIPdebugMessage("Ascend-and-prune adding solution....success=%d \n", *solfound);
1006  }
1007 
1008  redcostGraphFree(scip, &redcostgraph);
1009 
1010  return SCIP_OKAY;
1011 }
1012 
1013 
1014 /** creates the prune primal heuristic and includes it in SCIP */
1016  SCIP* scip /**< SCIP data structure */
1017  )
1018 {
1019  SCIP_HEURDATA* heurdata;
1020  SCIP_HEUR* heur;
1021 
1022  /* create prune primal heuristic data */
1023  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
1024 
1025  /* include primal heuristic */
1026  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1028  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecAscendPrune, heurdata) );
1029 
1030  assert(heur != NULL);
1031 
1032  /* set non fundamental callbacks via setter functions */
1033  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyAscendPrune) );
1034  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeAscendPrune) );
1035  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitAscendPrune) );
1036 
1037  /* add ascend and prune primal heuristic parameters */
1038  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/maxfreq",
1039  "should the heuristic be executed at maximum frequeny?",
1040  &heurdata->maxfreq, FALSE, DEFAULT_MAXFREQPRUNE, NULL, NULL) );
1041 
1042  return SCIP_OKAY;
1043 }
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
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:599
static volatile int nterms
Definition: interrupt.c:38
int *RESTRICT head
Definition: graphdefs.h:224
SCIP_Bool graph_typeIsDirected(const GRAPH *)
Definition: graph_stats.c:83
int source
Definition: graphdefs.h:195
static SCIP_RETCODE redcostGraphSolRetransform(SCIP *scip, const GRAPH *g, const RCGRAPH *redcostgraph, const int *subresult, int *result)
SCIP_Bool graph_pc_isRootedPcMw(const GRAPH *)
#define Is_term(a)
Definition: graphdefs.h:102
static SCIP_RETCODE redcostGraphComputeSteinerTree(SCIP *scip, const GRAPH *g, RCGRAPH *redcostgraph, int *result)
Constraint handler for Steiner problems.
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
SCIP_Bool graph_valid(SCIP *, const GRAPH *)
Definition: graph_base.c:1480
static int redcostGetNTermsMarked(const GRAPH *g, const RCGRAPH *redcostgraph)
int terms
Definition: graphdefs.h:192
SCIP_VAR ** SCIPprobdataGetVars(SCIP *scip)
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
int norgmodeledges
Definition: graphdefs.h:215
includes methods for Steiner tree problem solutions
int *RESTRICT maxdeg
Definition: graphdefs.h:206
SCIP_RETCODE SCIPStpHeurTMRun(SCIP *scip, enum PCMW_TmMode pcmw_tmmode, GRAPH *graph, int *starts, const SCIP_Real *prize, int *best_result, int runs, int bestincstart, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *hopfactor, SCIP_Real *nodepriority, SCIP_Bool *success)
Definition: heur_tm.c:3418
#define HEUR_TIMING
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_DESC
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
static SCIP_RETCODE redcostGraphBuild(SCIP *scip, const GRAPH *g, RCGRAPH *redcostgraph)
#define STP_DCSTP
Definition: graphdefs.h:47
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 EAT_LAST
Definition: graphdefs.h:58
#define STP_SPG
Definition: graphdefs.h:42
#define SCIPdebugMessage
Definition: pub_message.h:87
#define FARAWAY
Definition: graphdefs.h:89
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1362
void graph_printInfo(const GRAPH *)
Definition: graph_stats.c:299
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
int *RESTRICT mark
Definition: graphdefs.h:198
SCIP_RETCODE graph_pc_initSubgraph(SCIP *, GRAPH *)
Definition: graph_pcbase.c:763
int *RESTRICT oeat
Definition: graphdefs.h:231
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1441
SCIP_Bool extended
Definition: graphdefs.h:267
int stp_type
Definition: graphdefs.h:264
SCIP_RETCODE SCIPStpHeurAscendPruneRun(SCIP *scip, SCIP_HEUR *heur, const GRAPH *g, const SCIP_Real *redcosts, int *result, int root, SCIP_Bool *solfound, SCIP_Bool addsol)
#define HEUR_DISPCHAR
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void graph_edge_addSubgraph(SCIP *, const GRAPH *, const int *, int, GRAPH *)
Definition: graph_edge.c:341
SCIP_Real SCIPgetDualbound(SCIP *scip)
void SCIPStpHeurTMCompStarts(GRAPH *graph, int *starts, int *runs)
Definition: heur_tm.c:2879
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:128
SCIP_Real * prize
Definition: graphdefs.h:210
static void redcostGraphFree(SCIP *scip, RCGRAPH *redcostgraph)
SCIP_RETCODE graph_initHistory(SCIP *, GRAPH *)
Definition: graph_base.c:695
#define TERM2EDGE_FIXEDTERM
Definition: graphdefs.h:73
int *RESTRICT grad
Definition: graphdefs.h:201
SCIP_RETCODE reduce_unconnected(SCIP *, GRAPH *)
void graph_knot_add(GRAPH *, int)
Definition: graph_node.c:64
#define NULL
Definition: lpi_spx1.cpp:155
#define ASCENPRUNE_MINLPIMPROVE
#define STP_DHCSTP
Definition: graphdefs.h:52
SCIP_RETCODE SCIPStpHeurLocalRun(SCIP *scip, GRAPH *graph, int *solEdges)
Definition: heur_local.c:3899
#define STP_RMWCSP
Definition: graphdefs.h:54
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
int * term2edge
Definition: graphdefs.h:208
Improvement heuristic for Steiner problems.
includes solution pool for Steiner tree problems
unsigned char STP_Bool
Definition: portab.h:34
reduction-based primal heuristic for Steiner problems
void solstp_getTrivialSol(const GRAPH *g, int *soledge)
Definition: solstp.c:2020
SCIP_Real solstp_getObjBounded(const GRAPH *g, const int *soledge, SCIP_Real offset, int nedges)
Definition: solstp.c:1833
#define HEUR_PRIORITY
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define HEUR_NAME
SCIP_RETCODE graph_pc_finalizeSubgraph(SCIP *, GRAPH *)
Definition: graph_pcbase.c:795
static SCIP_RETCODE redcostGraphComputeSteinerTreeDirected(SCIP *scip, const GRAPH *g, RCGRAPH *redcostgraph, int *result, SCIP_Bool *solfound)
#define SCIP_Bool
Definition: def.h:84
static SCIP_DECL_HEUREXEC(heurExecAscendPrune)
#define STP_NWPTSPG
Definition: graphdefs.h:48
const SCIP_Real * redcosts
int *RESTRICT tail
Definition: graphdefs.h:223
#define HEUR_MAXDEPTH
#define flipedge(edge)
Definition: graphdefs.h:84
static SCIP_DECL_HEURINIT(heurInitAscendPrune)
SCIP_RETCODE SCIPStpIncludeHeurAscendPrune(SCIP *scip)
void graph_getEdgeCosts(const GRAPH *, SCIP_Real *RESTRICT, SCIP_Real *RESTRICT)
int *RESTRICT term
Definition: graphdefs.h:196
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1435
static SCIP_DECL_HEURFREE(heurFreeAscendPrune)
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE reduce_unconnectedForDirected(SCIP *, GRAPH *)
void graph_path_exit(SCIP *, GRAPH *)
Definition: graph_path.c:515
#define CONNECT
Definition: graphdefs.h:87
SCIP_Bool graph_typeIsUndirected(const GRAPH *)
Definition: graph_stats.c:69
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
#define HEUR_FREQ
SCIP_Bool redcosts_forLPareAvailable(SCIP *scip)
Definition: redcosts.c:767
Reduced cost based routines for Steiner problems.
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2304
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
struct redcost0_graph RCGRAPH
static SCIP_RETCODE redcostGraphMark(SCIP *scip, const GRAPH *g, RCGRAPH *redcostgraph)
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:962
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
static SCIP_DECL_HEURCOPY(heurCopyAscendPrune)
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
SCIP_Bool graph_edge_isInRange(const GRAPH *, int)
Definition: graph_stats.c:110
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
SCIP_RETCODE solstp_reroot(SCIP *scip, const GRAPH *g, int *result, int newroot)
Definition: solstp.c:1559
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
SCIP_VAR * a
Definition: circlepacking.c:57
#define SCIP_Real
Definition: def.h:177
int *RESTRICT outbeg
Definition: graphdefs.h:204
shortest paths based primal heuristics for Steiner problems
int edges
Definition: graphdefs.h:219
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
#define DEFAULT_MAXFREQPRUNE
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
#define HEUR_USESSUBSCIP
SCIP_Bool graph_knot_isInRange(const GRAPH *, int)
Definition: graph_node.c:52
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
#define UNKNOWN
Definition: sepa_mcf.c:4095
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
#define nnodes
Definition: gastrans.c:65
SCIP_RETCODE graph_init(SCIP *, GRAPH **, int, int, int)
Definition: graph_base.c:607
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:123
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
static SCIP_RETCODE redcostGraphComputeSteinerTreeDegCons(SCIP *scip, const GRAPH *g, RCGRAPH *redcostgraph, int *result, SCIP_Bool *solfound)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1352
SCIP_RETCODE solstp_prune(SCIP *scip, const GRAPH *g, int *result, STP_Bool *connected)
Definition: solstp.c:1366
SCIP_Bool graph_typeIsSpgLike(const GRAPH *)
Definition: graph_stats.c:57
int hoplimit
Definition: graphdefs.h:216
#define HEUR_FREQOFS
SCIP_RETCODE solpool_addSolToScip(SCIP *scip, SCIP_HEUR *heur, const GRAPH *g, const int *result, SCIP_Bool *success)
Definition: solpool.c:150
includes various reduction methods for Steiner tree problems
default SCIP plugins
SCIP_Real solstp_getObj(const GRAPH *g, const int *soledge, SCIP_Real offset)
Definition: solstp.c:1859
void graph_printInfoReduced(const GRAPH *)
Definition: graph_stats.c:375
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2635
SCIP callable library.
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
int norgmodelknots
Definition: graphdefs.h:187
void redcosts_forLPget(SCIP *scip, SCIP_VAR **vars, const GRAPH *graph, SCIP_Real *redcosts)
Definition: redcosts.c:861