Scippy

SCIP

Solving Constraint Integer Programs

prop_stp.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file prop_stp.c
17  * @brief propagator for Steiner tree problems, using the LP reduced costs
18  * @author Daniel Rehfeldt
19  *
20  * This propagator makes use of the reduced cost of an optimally solved LP relaxation to propagate the variables
21  *
22  */
23 
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25 
26 #include <assert.h>
27 #include <string.h>
28 #include "prop_stp.h"
29 #include "grph.h"
30 #include "branch_stp.h"
31 #include "scip/tree.h"
32 
33 
34 /**@name Propagator properties
35  *
36  * @{
37  */
38 
39 #define PROP_NAME "stp"
40 #define PROP_DESC "stp propagator"
41 #define PROP_TIMING SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP
42 #define PROP_PRIORITY 1000000 /**< propagator priority */
43 #define PROP_FREQ 1 /**< propagator frequency */
44 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
45 
46 #define PROP_STP_EDGE_KILLED -1
47 #define PROP_STP_EDGE_UNSET 0
48 #define PROP_STP_EDGE_SET 1
49 #define PROP_STP_EDGE_FIXED 2
50 
51 /**@} */
52 
53 /**@name Default parameter values
54  *
55  * @{
56  */
57 
58 #define DEFAULT_MAXNWAITINGROUNDS 2 /**< maximum number of rounds to wait until propagating again */
59 #define REDUCTION_WAIT_RATIO 0.02 /**< ratio of edges to be newly fixed before performing reductions for additional fixing */
60 
61 /**@} */
62 
63 /*
64  * Data structures
65  */
66 
67 
68 /** propagator data */
69 struct SCIP_PropData
70 {
71  GRAPH* propgraph; /**< graph data */
72  SCIP_Real* fixingbounds; /**< saves largest upper bound to each variable that would allow to fix it */
73  SCIP_Longint nfails; /**< number of failures since last successful call */
74  SCIP_Longint ncalls; /**< number of calls */
75  SCIP_Longint nlastcall; /**< number of last call */
76  SCIP_Longint lastnodenumber; /**< number of last call */
77  SCIP_Longint propgraphnodenumber;/**< b&b node number at which propgraph was updated */
78  int nfixededges; /**< total number of arcs fixed by 'fixedgevar' method of this propagator */
79  int postrednfixededges; /**< total number of arcs fixed by 'fixedgevar' method of this propagator after the last reductions */
80  int maxnwaitrounds; /**< maximum number of rounds to wait until propagating again */
81  SCIP_Bool aggressive; /**< be aggressive? */
82 };
83 
84 /**@name Local methods
85  *
86  * @{
87  */
88 
89 #if 0
90 static
91 SCIP_RETCODE fixedgevarTo1(
92  SCIP* scip, /**< SCIP data structure */
93  SCIP_VAR* edgevar, /**< the variable to be fixed */
94  int* nfixed /**< counter that is incriminated if variable could be fixed */
95  )
96 {
97  assert(scip != NULL);
98 
99  if( SCIPvarGetLbLocal(edgevar) < 0.5 && SCIPvarGetUbLocal(edgevar) > 0.5 )
100  {
101  SCIP_PROPDATA* propdata;
102 
103  assert(SCIPisEQ(scip, SCIPvarGetUbLocal(edgevar), 1.0));
104 
105  /* get propagator data */
106  assert(SCIPfindProp(scip, "stp") != NULL);
107  propdata = SCIPpropGetData(SCIPfindProp(scip, "stp"));
108  assert(propdata != NULL);
109 
110  SCIP_CALL( SCIPchgVarLb(scip, edgevar, 1.0) );
111  (*nfixed)++;
112  propdata->nfixededges++;
113  propdata->postrednfixededges++;
114  }
115  return SCIP_OKAY;
116 }
117 #endif
118 
119 /** try to make global fixings */
120 static
122  SCIP* scip, /**< SCIP structure */
123  SCIP_VAR** vars, /**< variables */
124  int* nfixededges, /**< points to number of fixed edges */
125  const SCIP_Real* fixingbounds, /**< fixing bounds */
126  const GRAPH* graph, /**< graph structure */
127  SCIP_Real cutoffbound, /**< cutoff bound */
128  int nedges /**< number of edges */
129  )
130 {
131  for( int e = 0; e < nedges; e++ )
132  {
133  if( SCIPisLT(scip, cutoffbound, fixingbounds[e]) )
134  {
135  SCIP_VAR* const edgevar = vars[e];
136 
137  if( SCIPvarGetLbGlobal(edgevar) < 0.5 && SCIPvarGetUbGlobal(edgevar) > 0.5 )
138  {
139  assert(SCIPisEQ(scip, SCIPvarGetUbGlobal(edgevar), 1.0));
140 
141  SCIPchgVarUbGlobal(scip, edgevar, 0.0);
142  (*nfixededges)++;
143  }
144  }
145  }
146 
147  return SCIP_OKAY;
148 }
149 
150 static
152  SCIP* scip /**< SCIP structure */
153 )
154 {
155  /* only execute dualcostVarfixing if current node has an LP */
156  if( !SCIPhasCurrentNodeLP(scip) )
157  return FALSE;
158 
159  /* only execute dualcostVarfixing if optimal LP solution is at hand */
161  return FALSE;
162 
163  /* only execute dualcostVarfixing if current LP is valid relaxation */
164  if( !SCIPisLPRelax(scip) )
165  return FALSE;
166 
167  /* we cannot apply reduced cost strengthening if no simplex basis is available */
168  if( !SCIPisLPSolBasic(scip) )
169  return FALSE;
170 
171  /* reduced cost strengthening can only be applied if cutoff is finite */
172  if( SCIPisInfinity(scip, SCIPgetCutoffbound(scip)) )
173  return FALSE;
174 
175  return TRUE;
176 }
177 
178 /** initialize reduced costs*/
179 static
181  SCIP* scip, /**< SCIP structure */
182  SCIP_VAR** vars, /**< variables */
183  int nedges, /**< nedges */
184  SCIP_Real* cost /**< reduced costs */
185  )
186 {
187  assert(nedges >= 0);
188 
189  for( unsigned int e = 0; e < (unsigned) nedges; e++ )
190  {
191  assert(SCIPvarIsBinary(vars[e]));
192 
193  /* variable is already fixed, we must not trust the reduced cost */
194  if( SCIPvarGetLbLocal(vars[e]) + 0.5 > SCIPvarGetUbLocal(vars[e]) )
195  {
196  if( SCIPvarGetLbLocal(vars[e]) > 0.5 )
197  cost[e] = 0.0;
198  else
199  {
200  assert(SCIPvarGetUbLocal(vars[e]) < 0.5);
201  cost[e] = FARAWAY;
202  }
203  }
204  else
205  {
206  if( SCIPisFeasZero(scip, SCIPgetSolVal(scip, NULL, vars[e])) )
207  {
208  assert(!SCIPisDualfeasNegative(scip, SCIPgetVarRedcost(scip, vars[e])));
209  cost[e] = SCIPgetVarRedcost(scip, vars[e]);
210  }
211  else
212  {
213  assert(!SCIPisDualfeasPositive(scip, SCIPgetVarRedcost(scip, vars[e])));
214  assert(SCIPisFeasEQ(scip, SCIPgetSolVal(scip, NULL, vars[e]), 1.0) || SCIPisDualfeasZero(scip, SCIPgetVarRedcost(scip, vars[e])));
215  cost[e] = 0.0;
216  }
217  }
218 
219  if( cost[e] < 0.0 )
220  cost[e] = 0.0;
221  }
222 }
223 
224 
225 /** initialize (Voronoi) distances */
226 static
228  SCIP* scip, /**< SCIP structure */
229  const SCIP_Real* cost, /**< reduced costs */
230  const GRAPH* graph, /**< graph data structure */
231  PATH* vnoi, /**< Voronoi paths */
232  SCIP_Real* costrev, /**< reversed reduced costs */
233  SCIP_Real* pathdist, /**< path distance */
234  int* pathedge, /**< path edge */
235  int* vbase /**< Voronoi base */
236  )
237 {
238  const int nnodes = graph->knots;
239  const int nedges = graph->edges;
240 
241  for( int k = 0; k < nnodes; k++ )
242  graph->mark[k] = (graph->grad[k] > 0);
243 
244  /* distance from root to all nodes */
245  graph_path_execX(scip, graph, graph->source, cost, pathdist, pathedge);
246 
247  for( unsigned int e = 0; e < (unsigned) nedges; e++ )
248  costrev[e] = cost[flipedge(e)];
249 
250  /* no paths should go back to the root */
251  for( int e = graph->outbeg[graph->source]; e != EAT_LAST; e = graph->oeat[e] )
252  costrev[e] = FARAWAY;
253 
254  /* build voronoi diagram */
255  graph_voronoiTerms(scip, graph, costrev, vnoi, vbase, graph->path_heap, graph->path_state);
256 }
257 
258 /** updates fixing bounds for reduced cost fixings */
259 static
261  SCIP_Real* fixingbounds, /**< fixing bounds */
262  const GRAPH* graph, /**< graph data structure */
263  const SCIP_Real* cost, /**< reduced costs */
264  const SCIP_Real* pathdist, /**< shortest path distances */
265  const PATH* vnoi, /**< Voronoi paths */
266  SCIP_Real lpobjal /**< LP objective */
267  )
268 {
269  const int nnodes = graph->knots;
270 
271  for( int k = 0; k < nnodes; k++ )
272  {
273  if( Is_term(graph->term[k]) && (graph->stp_type == STP_MWCSP || graph->stp_type == STP_PCSPG) )
274  continue;
275 
276  for( int e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
277  {
278  const SCIP_Real fixbnd = pathdist[k] + cost[e] + vnoi[graph->head[e]].dist + lpobjal;
279  if( fixbnd > fixingbounds[e] )
280  fixingbounds[e] = fixbnd;
281  }
282  }
283 }
284 
285 /** dual cost based fixing of variables */
286 static
288  SCIP* scip, /**< SCIP data structure */
289  SCIP_Real lpobjval, /**< LP value */
290  SCIP_VAR** vars, /**< variables */
291  SCIP_PROPDATA* propdata, /**< propagator data */
292  int* nfixed, /**< pointer to number of fixed edges */
293  const GRAPH* graph /**< graph data structure */
294  )
295 {
296  PATH* vnoi;
297  SCIP_Real* cost;
298  SCIP_Real* costrev;
299  SCIP_Real* pathdist;
300  const SCIP_Real cutoffbound = SCIPgetCutoffbound(scip);
301  const SCIP_Real minpathcost = cutoffbound - lpobjval;
302  int* vbase;
303  int* pathedge;
304  const int nedges = graph->edges;
305  const int nnodes = graph->knots;
306 
307  assert(SCIPisGE(scip, minpathcost, 0.0));
308 
309  if( propdata->fixingbounds == NULL )
310  {
311  SCIP_CALL( SCIPallocMemoryArray(scip, &(propdata->fixingbounds), nedges) );
312  for( int i = 0; i < nedges; i++ )
313  propdata->fixingbounds[i] = -FARAWAY;
314  }
315 
316  SCIP_CALL( SCIPallocBufferArray(scip, &cost, nedges) );
317  SCIP_CALL( SCIPallocBufferArray(scip, &costrev, nedges) );
318  SCIP_CALL( SCIPallocBufferArray(scip, &pathdist, nnodes) );
319  SCIP_CALL( SCIPallocBufferArray(scip, &vbase, nnodes) );
320  SCIP_CALL( SCIPallocBufferArray(scip, &pathedge, nnodes) );
321  SCIP_CALL( SCIPallocBufferArray(scip, &vnoi, nnodes) );
322 
323  /* initialize reduced costs*/
324  setRedcosts(scip, vars, nedges, cost);
325 
326  /* initialize Voronoi structures */
327  setVnoiDistances(scip, cost, graph, vnoi, costrev, pathdist, pathedge, vbase);
328 
329  for( int k = 0; k < nnodes; k++ )
330  {
331  if( !Is_term(graph->term[k]) && SCIPisGT(scip, pathdist[k] + vnoi[k].dist, minpathcost) )
332  {
333  for( int e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
334  {
335  /* try to fix edge and reversed one */
336  SCIP_CALL( fixedgevar(scip, vars[e], nfixed) );
337  SCIP_CALL( fixedgevar(scip, vars[flipedge(e)], nfixed) );
338  }
339  }
340  else
341  {
342  for( int e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
343  if( SCIPisGT(scip, pathdist[k] + cost[e] + vnoi[graph->head[e]].dist, minpathcost) )
344  SCIP_CALL( fixedgevar(scip, vars[e], nfixed) );
345  }
346  }
347 
348  /* at root? */
349  if( SCIPgetDepth(scip) == 0 )
350  updateFixingBounds(propdata->fixingbounds, graph, cost, pathdist, vnoi, lpobjval);
351 
352  SCIP_CALL( globalfixing(scip, vars, nfixed, propdata->fixingbounds, graph, cutoffbound, nedges) );
353 
354  SCIPfreeBufferArray(scip, &vnoi);
355  SCIPfreeBufferArray(scip, &pathedge);
356  SCIPfreeBufferArray(scip, &vbase);
357  SCIPfreeBufferArray(scip, &pathdist);
358  SCIPfreeBufferArray(scip, &costrev);
359  SCIPfreeBufferArray(scip, &cost);
360 
361  return SCIP_OKAY;
362 }
363 
364 
365 /** extended reduced cost reduction */
366 static
368  SCIP* scip, /**< SCIP data structure */
369  SCIP_Real lpobjval, /**< LP value */
370  SCIP_VAR** vars, /**< variables */
371  GRAPH* propgraph /**< graph data structure */
372  )
373 {
374  PATH* vnoi;
375  SCIP_Real* redcost;
376  SCIP_Real* redcostrev;
377  SCIP_Real* pathdist;
378  int* nodearr;
379  int* pathedge;
380  int* vbase;
381  const SCIP_Real cutoffbound = SCIPgetCutoffbound(scip);
382  SCIP_Real minpathcost;
383  int extnfixed;
384  const int nnodes = propgraph->knots;
385  const int nedges = propgraph->edges;
386 
387  minpathcost = cutoffbound - lpobjval;
388 
389  SCIP_CALL( SCIPallocBufferArray(scip, &redcost, nedges) );
390  SCIP_CALL( SCIPallocBufferArray(scip, &redcostrev, nedges) );
391  SCIP_CALL( SCIPallocBufferArray(scip, &pathdist, nnodes) );
392  SCIP_CALL( SCIPallocBufferArray(scip, &vnoi, nnodes) );
393  SCIP_CALL( SCIPallocBufferArray(scip, &vbase, nnodes) );
394  SCIP_CALL( SCIPallocBufferArray(scip, &pathedge, nnodes) );
395  SCIP_CALL( SCIPallocBufferArray(scip, &nodearr, nnodes) );
396 
397  /* initialize reduced costs*/
398  setRedcosts(scip, vars, nedges, redcost);
399 
400  /* initialize Voronoi structures */
401  setVnoiDistances(scip, redcost, propgraph, vnoi, redcostrev, pathdist, pathedge, vbase);
402 
403  /* reduce graph */
404  extnfixed = reduce_extendedEdge(scip, propgraph, vnoi, redcost, pathdist, NULL, minpathcost, propgraph->source, nodearr, NULL);
405  SCIPdebugMessage("extended fixes: %d \n", extnfixed);
406 
407  SCIPfreeBufferArray(scip, &nodearr);
408  SCIPfreeBufferArray(scip, &pathedge);
409  SCIPfreeBufferArray(scip, &vbase);
410  SCIPfreeBufferArray(scip, &vnoi);
411  SCIPfreeBufferArray(scip, &pathdist);
412  SCIPfreeBufferArray(scip, &redcostrev);
413  SCIPfreeBufferArray(scip, &redcost);
414 
415  if( extnfixed < 0 )
416  return SCIP_ERROR;
417 
418  return SCIP_OKAY;
419 }
420 
421 /** This methods tries to fix edges by performing reductions on the current graph.
422  * To this end, the already 0-fixed edges are (temporarily) removed from the underlying graph to strengthen the reduction methods. */
423 static
425  SCIP* scip, /**< SCIP data structure */
426  SCIP_Real lpobjval, /**< LP value */
427  SCIP_VAR** vars, /**< variables */
428  SCIP_PROPDATA* propdata, /**< propagator data */
429  int* nfixed, /**< pointer to number of fixed edges */
430  SCIP_Bool* probisinfeas, /**< is problem infeasible? */
431  const GRAPH* g /**< graph data structure */
432  )
433 {
434  GRAPH* propgraph;
435  IDX* curr;
436  SCIP_Real offset;
437  int* remain;
438  const int nedges = g->edges;
439  const SCIP_Bool pc = (g->stp_type == STP_PCSPG || g->stp_type == STP_RPCSPG);
440 
441  assert(propdata != NULL);
442  assert(scip != NULL);
443  assert(g != NULL);
444  assert(vars != NULL);
445 
446  *probisinfeas = FALSE;
447  offset = 0.0;
448 
449  SCIP_CALL( SCIPallocBufferArray(scip, &remain, nedges) );
450 
451  propgraph = propdata->propgraph;
452  assert(propgraph != NULL);
453 
454  graph_free_history(scip, propgraph);
455  graph_free_historyDeep(scip, propgraph);
456 
457  /* copy the graph */
458  SCIP_CALL( graph_copy_data(scip, g, propgraph) );
459  propdata->propgraphnodenumber = SCIPnodeGetNumber(SCIPgetCurrentNode(scip));
460 
461  SCIP_CALL( graph_init_history(scip, propdata->propgraph) );
462 
463  for( int e = 0; e < nedges; e++ )
464  remain[e] = PROP_STP_EDGE_UNSET;
465 
466  for( int e = 0; e < nedges; e += 2 )
467  {
468  const int erev = e + 1;
469 
470  /* e or its anti-parallel edge fixed to one? */
471  if( SCIPvarGetLbLocal(vars[e]) > 0.5 || SCIPvarGetLbLocal(vars[erev]) > 0.5 )
472  {
473  const int tail = propgraph->tail[e];
474  const int head = propgraph->head[e];
475 
476  graph_knot_chg(propgraph, tail, 0);
477  graph_knot_chg(propgraph, head, 0);
478 
479  propgraph->cost[e] = 0.0;
480  propgraph->cost[erev] = 0.0;
481 
482  remain[e] = PROP_STP_EDGE_FIXED;
483  remain[erev] = PROP_STP_EDGE_FIXED;
484  }
485 
486  /* both e and its anti-parallel edge fixed to zero? */
487  if( SCIPvarGetUbLocal(vars[e]) < 0.5 && SCIPvarGetUbLocal(vars[erev]) < 0.5 )
488  {
489  assert(SCIPvarGetLbLocal(vars[e]) < 0.5 && SCIPvarGetLbLocal(vars[erev]) < 0.5);
490 
491  graph_edge_del(scip, propgraph, e, TRUE);
492  remain[e] = PROP_STP_EDGE_KILLED;
493  remain[erev] = PROP_STP_EDGE_KILLED;
494  }
495  }
496 
497  if( pc )
498  SCIP_CALL( reduce_contractZeroEdges(scip, propgraph, TRUE) );
499 
500  /* not at root? */
501  if( SCIPgetDepth(scip) > 0 )
502  {
503  /* then modify the graph according to vertex kills/fixes during branch-and-bound */
504  SCIP_CALL( SCIPStpBranchruleApplyVertexChgs(scip, NULL, propgraph) );
505  }
506 
507  if( !graph_valid(propgraph) )
508  {
509  *probisinfeas = TRUE;
510  goto TERMINATE;
511  }
512 
513  SCIP_CALL( graph_path_init(scip, propgraph) );
514 
515 
516  if( propdata->fixingbounds == NULL )
517  {
518  SCIP_CALL( SCIPallocMemoryArray(scip, &(propdata->fixingbounds), nedges) );
519  for( int i = 0; i < nedges; i++ )
520  propdata->fixingbounds[i] = -FARAWAY;
521  }
522 
523  /* reduce graph */
524  SCIP_CALL( reduceRedcostExtended(scip, lpobjval, vars, propgraph) );
525 
526  SCIP_CALL( level0(scip, propgraph) );
527  SCIP_CALL( reduceStp(scip, &propgraph, &offset, 2, FALSE, FALSE, FALSE) );
528 
529  assert(graph_valid(propgraph));
530 
531  graph_path_exit(scip, propgraph);
532 
533  /* try to fix edges ... */
534 
535  for( int e = 0; e < nedges; e++ )
536  {
537  if( propgraph->ieat[e] != EAT_FREE )
538  {
539  assert(propgraph->ieat[flipedge(e)] != EAT_FREE);
540 
541  curr = propgraph->ancestors[e];
542 
543  while( curr != NULL )
544  {
545  const int i = curr->index;
546  assert(i < nedges);
547  assert(remain[i] != PROP_STP_EDGE_KILLED);
548 
549  if( remain[i] == PROP_STP_EDGE_UNSET )
550  {
551  remain[i] = PROP_STP_EDGE_SET;
552  remain[flipedge(i)] = PROP_STP_EDGE_SET;
553  }
554 
555  curr = curr->parent;
556  }
557  }
558  }
559 
560  curr = propgraph->fixedges;
561 
562  while( curr != NULL )
563  {
564  const int e = curr->index;
565  assert(e < nedges);
566 
567  remain[e] = PROP_STP_EDGE_FIXED;
568  remain[flipedge(e)] = PROP_STP_EDGE_FIXED;
569 
570  curr = curr->parent;
571  }
572 
573  /* 1-fixed edge to be deleted? */
574  for( int e = 0; e < nedges; e++ )
575  if( (remain[e] == PROP_STP_EDGE_UNSET || remain[e] == PROP_STP_EDGE_KILLED) && (SCIPvarGetLbLocal(vars[e]) > 0.5) )
576  {
577  SCIPdebugMessage("1-fixed arc deleted by reduction methods ... can't propagate \n \n \n");
578  goto TERMINATE;
579  }
580 
581  /* fix to zero and one */
582  for( int e = 0; e < nedges; e += 2 )
583  {
584  const int erev = e + 1;
585  /* edge not set yet? */
586  if( remain[e] == PROP_STP_EDGE_UNSET )
587  {
588  assert(remain[erev] == PROP_STP_EDGE_UNSET);
589 
590  SCIP_CALL( fixedgevar(scip, vars[e], nfixed) );
591  SCIP_CALL( fixedgevar(scip, vars[erev], nfixed) );
592  }
593  }
594 
595  SCIPdebugMessage("reduction based fixings: %d \n", *nfixed);
596 
597 TERMINATE:
598 
599  SCIPfreeBufferArray(scip, &remain);
600 
601  return SCIP_OKAY;
602 }
603 
604 
605 /**@} */
606 
607 /**@name Callback methods of propagator
608  *
609  * @{
610  */
611 
612 /** copy method for propagator plugins (called when SCIP copies plugins) */
613 static
614 SCIP_DECL_PROPCOPY(propCopyStp)
615 { /*lint --e{715}*/
616  assert(scip != NULL);
617  assert(prop != NULL);
618  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
619 
620  /* call inclusion method of constraint handler */
621  SCIP_CALL( SCIPincludePropStp(scip) );
622 
623  return SCIP_OKAY;
624 }
625 
626 
627 /** destructor of propagator to free user data (called when SCIP is exiting) */
628 static
629 SCIP_DECL_PROPFREE(propFreeStp)
630 { /*lint --e{715}*/
631  SCIP_PROPDATA* propdata;
632 
633  /* free propagator data */
634  propdata = SCIPpropGetData(prop);
635  assert(propdata != NULL);
636 
637  SCIPfreeMemory(scip, &propdata);
638 
639  SCIPpropSetData(prop, NULL);
640 
641  return SCIP_OKAY;
642 }
643 
644 
645 /** reduced cost propagation method for an LP solution */
646 static
647 SCIP_DECL_PROPEXEC(propExecStp)
648 { /*lint --e{715}*/
649  SCIP_PROPDATA* propdata;
650  SCIP_PROBDATA* probdata;
651  SCIP_VAR** vars;
652  GRAPH* graph;
653  SCIP_Real lpobjval;
654  int nfixed;
655  SCIP_Bool callreduce;
656 
657  *result = SCIP_DIDNOTRUN;
658 
659  /* propagator can only be applied during solving stage */
660  if( SCIPgetStage(scip) < SCIP_STAGE_SOLVING )
661  return SCIP_OKAY;
662 
663  /* get problem data */
664  probdata = SCIPgetProbData(scip);
665  assert(probdata != NULL);
666 
667  /* get all variables (corresponding to the edges) */
668  vars = SCIPprobdataGetVars(scip);
669 
670  if( vars == NULL )
671  return SCIP_OKAY;
672 
673  /* check if all integral variables are fixed */
674  if( SCIPgetNPseudoBranchCands(scip) == 0 )
675  return SCIP_OKAY;
676 
677  if( !redcostAvailable(scip) )
678  return SCIP_OKAY;
679 
680  /* get propagator data */
681  propdata = SCIPpropGetData(prop);
682  assert(propdata != NULL);
683 
684  propdata->ncalls++;
685 
686  if( propdata->nfails > 0 && (propdata->nlastcall + propdata->maxnwaitrounds >= propdata->ncalls)
687  && (propdata->nlastcall + propdata->nfails > propdata->ncalls) )
688  return SCIP_OKAY;
689 
690  propdata->nlastcall = propdata->ncalls;
691 
692  graph = SCIPprobdataGetGraph(probdata);
693  assert(graph != NULL);
694 
695  nfixed = 0;
696  *result = SCIP_DIDNOTFIND;
697 
698  lpobjval = SCIPgetLPObjval(scip);
699 
700  /* call dual cost based variable fixing */
701  SCIP_CALL( dualcostVarfixing(scip, lpobjval, vars, propdata, &nfixed, graph) );
702 
703  callreduce = FALSE;
704 
705  if( graph->stp_type == STP_SPG || graph->stp_type == STP_RSMT )
706  {
707  const SCIP_Real redratio = ((SCIP_Real) propdata->postrednfixededges ) / (graph->edges);
708 
709  if( propdata->propgraph == NULL )
710  {
711  propdata->propgraphnodenumber = SCIPnodeGetNumber(SCIPgetCurrentNode(scip));
712  SCIP_CALL( graph_copy(scip, graph, &(propdata->propgraph)) );
713  SCIP_CALL( graph_init_history(scip, propdata->propgraph) );
714  assert(propdata->nfixededges == 0);
715  }
716 
717  /* in the tree? */
718  if( SCIPgetDepth(scip) > 0 )
719  {
720  SCIP_NODE* const currnode = SCIPgetCurrentNode(scip);
721  const SCIP_Longint nodenumber = SCIPnodeGetNumber(currnode);
722 
723  if( nodenumber != propdata->lastnodenumber || propdata->aggressive )
724  {
725  propdata->lastnodenumber = nodenumber;
726  callreduce = TRUE;
727  }
728  }
729  /* and root and is ratio of newly fixed edges higher than bound? */
730  else if( SCIPisGT(scip, redratio, REDUCTION_WAIT_RATIO) && SCIPgetDepth(scip) == 0 )
731  {
732  callreduce = TRUE;
733  }
734 #ifdef WITH_UG
735  if( propdata->ncalls == 1 && SCIPgetDepth(scip) == 0 )
736  {
737  SCIPdebugMessage("trigger UG root reductions \n");
738  callreduce = TRUE;
739  }
740 #endif
741  }
742 
743  if( callreduce )
744  {
745  SCIP_Bool probisinfeas;
746 
747  SCIPdebugMessage("use reduction techniques \n");
748 
749  /* call reduced cost based based variable fixing */
750  SCIP_CALL( redbasedVarfixing(scip, lpobjval, vars, propdata, &nfixed, &probisinfeas, graph) );
751 
752  propdata->postrednfixededges = 0;
753 
754  if( probisinfeas )
755  {
756  *result = SCIP_CUTOFF;
757  return SCIP_OKAY;
758  }
759  }
760 
761  if( nfixed > 0 )
762  {
763  SCIPdebugMessage("newly fixed by STP propagator: %d \n", nfixed );
764 
765  propdata->nfails = 0;
766  propdata->nfixededges += nfixed;
767  propdata->postrednfixededges += nfixed;
768 
769  *result = SCIP_REDUCEDDOM;
770 
771  if( graph->stp_type == STP_SPG || graph->stp_type == STP_RSMT || graph->stp_type == STP_RPCSPG ||
772  graph->stp_type == STP_PCSPG || graph->stp_type == STP_DCSTP )
773  {
774  for( int e = 0; e < graph->edges; e += 2 )
775  {
776  const int erev = e + 1;
777 
778  /* both e and its anti-parallel edge fixed to zero? */
779  if( SCIPvarGetUbGlobal(vars[e]) < 0.5 && SCIPvarGetUbGlobal(vars[erev]) < 0.5 && graph->cost[e] < BLOCKED )
780  {
781  assert(SCIPvarGetLbLocal(vars[e]) < 0.5 && SCIPvarGetLbLocal(vars[erev]) < 0.5);
782  if( graph->cost[e] == graph->cost[erev] )
783  {
784  graph->cost[e] = BLOCKED;
785  graph->cost[erev] = BLOCKED;
786  }
787  }
788  }
789  }
790  }
791  else
792  {
793  propdata->nfails++;
794  }
795 
796  return SCIP_OKAY;
797 }
798 
799 /** solving process initialization method of propagator (called when branch and bound process is about to begin) */
800 static
801 SCIP_DECL_PROPINITSOL(propInitsolStp)
802 { /*lint --e{715}*/
803  SCIP_PROPDATA* propdata;
804 
805  propdata = SCIPpropGetData(prop);
806  assert(propdata != NULL);
807 
808  propdata->nfails = 0;
809  propdata->ncalls = 0;
810  propdata->nlastcall = 0;
811  propdata->lastnodenumber = -1;
812  propdata->nfixededges = 0;
813  propdata->postrednfixededges = 0;
814  propdata->fixingbounds = NULL;
815  propdata->propgraph = NULL;
816  propdata->propgraphnodenumber = -1;
817 
818  return SCIP_OKAY;
819 }
820 
821 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
822 static
823 SCIP_DECL_PROPEXITSOL(propExitsolStp)
824 { /*lint --e{715}*/
825  SCIP_PROPDATA* propdata;
826 
827  /* free propagator data */
828  propdata = SCIPpropGetData(prop);
829  assert(propdata != NULL);
830 
831  SCIPfreeMemoryArrayNull(scip, &(propdata->fixingbounds));
832  if( propdata->propgraph != NULL )
833  graph_free(scip, &(propdata->propgraph), TRUE);
834 
835  return SCIP_OKAY;
836 }
837 
838 
839 /**@} */
840 
841 /**@name Interface methods
842  *
843  * @{
844  */
845 
846 
847 /** fix a variable (corresponding to an edge) to zero */
849  SCIP* scip, /**< SCIP data structure */
850  SCIP_VAR* edgevar, /**< the variable to be fixed */
851  int* nfixed /**< counter that is incriminated if variable could be fixed */
852  )
853 {
854  assert(scip != NULL);
855 
856  if( SCIPvarGetLbLocal(edgevar) < 0.5 && SCIPvarGetUbLocal(edgevar) > 0.5 )
857  {
858  SCIP_CALL( SCIPchgVarUb(scip, edgevar, 0.0) );
859  (*nfixed)++;
860  }
861  return SCIP_OKAY;
862 }
863 
864 /** return total number of arcs fixed by 'fixedgevar' method of this propagator */
866  SCIP* scip /**< SCIP data structure */
867  )
868 {
869  SCIP_PROPDATA* propdata;
870 
871  assert(scip != NULL);
872 
873  /* get propagator data */
874  assert(SCIPfindProp(scip, "stp") != NULL);
875  propdata = SCIPpropGetData(SCIPfindProp(scip, "stp"));
876 
877  assert(propdata != NULL);
878 
879  return (propdata->nfixededges);
880 }
881 
882 /** gets propagator graph */
884  SCIP* scip, /**< SCIP data structure */
885  GRAPH** graph, /**< graph data */
886  SCIP_Longint* graphnodenumber /**< point to b&b node for which graph is valid */
887  )
888 {
889  SCIP_PROPDATA* propdata;
890 
891  assert(scip != NULL);
892 
893  /* get propagator data */
894  assert(SCIPfindProp(scip, "stp") != NULL);
895  propdata = SCIPpropGetData(SCIPfindProp(scip, "stp"));
896  assert(propdata != NULL);
897 
898  *graph = (propdata->propgraph);
899  *graphnodenumber = propdata->propgraphnodenumber;
900 }
901 
902 
903 /** creates the stp propagator and includes it in SCIP */
905  SCIP* scip /**< SCIP data structure */
906  )
907 {
908  SCIP_PROP* prop;
909  SCIP_PROPDATA* propdata;
910 
911  /* create redcost propagator data */
912  SCIP_CALL( SCIPallocMemory(scip, &propdata) );
913 
914  /* include propagator */
916  propExecStp, propdata) );
917 
918  assert(prop != NULL);
919 
920  /* set optional callbacks via setter functions */
921  SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyStp) );
922  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeStp) );
923  SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolStp) );
924  SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolStp) );
925 
926  /* add parameters */
927  SCIP_CALL( SCIPaddIntParam(scip, "propagating/" PROP_NAME "/nwaitingrounds",
928  "maximum number of rounds before propagating again",
929  &propdata->maxnwaitrounds, FALSE, DEFAULT_MAXNWAITINGROUNDS, 1, INT_MAX, NULL, NULL) );
930 
931  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/"PROP_NAME"/aggressive",
932  "should the heuristic be executed at maximum frequeny?",
933  &propdata->aggressive, FALSE, FALSE, NULL, NULL) );
934 
935  return SCIP_OKAY;
936 }
937 
938 /**@} */
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
Definition: grphpath.c:444
static SCIP_DECL_PROPINITSOL(propInitsolStp)
Definition: prop_stp.c:801
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void SCIPStpPropGetGraph(SCIP *scip, GRAPH **graph, SCIP_Longint *graphnodenumber)
Definition: prop_stp.c:883
int *RESTRICT head
Definition: grph.h:96
Definition: grph.h:57
int source
Definition: grph.h:67
internal methods for branch and bound tree
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:70
SCIP_RETCODE fixedgevar(SCIP *scip, SCIP_VAR *edgevar, int *nfixed)
Definition: prop_stp.c:848
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1868
int SCIPStpNfixedEdges(SCIP *scip)
Definition: prop_stp.c:865
SCIP_Bool graph_valid(const GRAPH *)
Definition: grphbase.c:4328
static SCIP_DECL_PROPEXITSOL(propExitsolStp)
Definition: prop_stp.c:823
static SCIP_DECL_PROPCOPY(propCopyStp)
Definition: prop_stp.c:614
SCIP_VAR ** SCIPprobdataGetVars(SCIP *scip)
SCIP_RETCODE graph_copy(SCIP *, const GRAPH *, GRAPH **)
Definition: grphbase.c:3900
SCIP_RETCODE graph_init_history(SCIP *, GRAPH *)
Definition: grphbase.c:3573
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:53
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
SCIP_EXPORT SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7420
#define EAT_LAST
Definition: grph.h:31
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:81
SCIP_EXPORT SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17192
#define BLOCKED
Definition: grph.h:157
#define FALSE
Definition: def.h:73
SCIP_RETCODE reduce_contractZeroEdges(SCIP *, GRAPH *, SCIP_Bool)
int *RESTRICT path_state
Definition: grph.h:119
void graph_free(SCIP *, GRAPH **, SCIP_Bool)
Definition: grphbase.c:3678
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
void graph_path_exit(SCIP *, GRAPH *)
Definition: grphpath.c:466
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:962
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
#define STP_PCSPG
Definition: grph.h:40
#define SCIPdebugMessage
Definition: pub_message.h:87
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
Definition: prop.c:790
int reduce_extendedEdge(SCIP *, GRAPH *, const PATH *, const SCIP_Real *, const SCIP_Real *, const int *, SCIP_Real, int, int *, STP_Bool *)
Definition: reduce_bnd.c:2774
void graph_knot_chg(GRAPH *, int, int)
Definition: grphbase.c:2222
static SCIP_Bool redcostAvailable(SCIP *scip)
Definition: prop_stp.c:151
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:74
SCIP_Bool SCIPisDualfeasNegative(SCIP *scip, SCIP_Real val)
#define PROP_STP_EDGE_UNSET
Definition: prop_stp.c:47
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
int *RESTRICT mark
Definition: grph.h:70
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:142
SCIP_Bool SCIPisDualfeasZero(SCIP *scip, SCIP_Real val)
IDX * fixedges
Definition: grph.h:85
static SCIP_RETCODE globalfixing(SCIP *scip, SCIP_VAR **vars, int *nfixededges, const SCIP_Real *fixingbounds, const GRAPH *graph, SCIP_Real cutoffbound, int nedges)
Definition: prop_stp.c:121
SCIP_Bool SCIPisLPRelax(SCIP *scip)
Definition: scip_lp.c:216
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:749
void graph_path_execX(SCIP *, const GRAPH *, int, const SCIP_Real *, SCIP_Real *, int *)
Definition: grphpath.c:781
static SCIP_RETCODE reduceRedcostExtended(SCIP *scip, SCIP_Real lpobjval, SCIP_VAR **vars, GRAPH *propgraph)
Definition: prop_stp.c:367
int *RESTRICT oeat
Definition: grph.h:103
#define PROP_NAME
Definition: prop_stp.c:39
int stp_type
Definition: grph.h:127
IDX ** ancestors
Definition: grph.h:86
SCIP_RETCODE level0(SCIP *, GRAPH *)
Definition: reduce.c:153
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4677
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define STP_DCSTP
Definition: grph.h:43
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:932
SCIP_Real dist
Definition: grph.h:145
#define PROP_STP_EDGE_FIXED
Definition: prop_stp.c:49
int *RESTRICT grad
Definition: grph.h:73
#define PROP_STP_EDGE_KILLED
Definition: prop_stp.c:46
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:158
#define NULL
Definition: lpi_spx1.cpp:155
#define REDUCTION_WAIT_RATIO
Definition: prop_stp.c:59
int knots
Definition: grph.h:62
#define SCIP_CALL(x)
Definition: def.h:364
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip_prop.c:222
SCIP_RETCODE graph_copy_data(SCIP *, const GRAPH *, GRAPH *)
Definition: grphbase.c:3809
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:637
void graph_free_history(SCIP *, GRAPH *)
Definition: grphbase.c:3740
#define PROP_STP_EDGE_SET
Definition: prop_stp.c:48
static void setRedcosts(SCIP *scip, SCIP_VAR **vars, int nedges, SCIP_Real *cost)
Definition: prop_stp.c:180
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:238
static SCIP_RETCODE dualcostVarfixing(SCIP *scip, SCIP_Real lpobjval, SCIP_VAR **vars, SCIP_PROPDATA *propdata, int *nfixed, const GRAPH *graph)
Definition: prop_stp.c:287
#define FARAWAY
Definition: grph.h:156
SCIP_RETCODE SCIPincludePropStp(SCIP *scip)
Definition: prop_stp.c:904
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
#define STP_SPG
Definition: grph.h:38
propagator for Steiner tree problems, using the LP reduced costs
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:638
#define SCIP_Bool
Definition: def.h:70
static void updateFixingBounds(SCIP_Real *fixingbounds, const GRAPH *graph, const SCIP_Real *cost, const SCIP_Real *pathdist, const PATH *vnoi, SCIP_Real lpobjal)
Definition: prop_stp.c:260
int *RESTRICT ieat
Definition: grph.h:102
int *RESTRICT path_heap
Definition: grph.h:118
#define PROP_DELAY
Definition: prop_stp.c:44
static SCIP_RETCODE redbasedVarfixing(SCIP *scip, SCIP_Real lpobjval, SCIP_VAR **vars, SCIP_PROPDATA *propdata, int *nfixed, SCIP_Bool *probisinfeas, const GRAPH *g)
Definition: prop_stp.c:424
#define STP_MWCSP
Definition: grph.h:47
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17672
int *RESTRICT tail
Definition: grph.h:95
static SCIP_DECL_PROPFREE(propFreeStp)
Definition: prop_stp.c:629
SCIP_Bool SCIPisDualfeasPositive(SCIP *scip, SCIP_Real val)
SCIP_PROP * SCIPfindProp(SCIP *scip, const char *name)
Definition: scip_prop.c:320
#define PROP_PRIORITY
Definition: prop_stp.c:42
#define PROP_FREQ
Definition: prop_stp.c:43
int *RESTRICT term
Definition: grph.h:68
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: grphbase.c:2841
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4767
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17718
includes various files containing graph methods used for Steiner tree problems
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:67
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17728
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:780
Steiner vertex branching rule.
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:5030
#define Is_term(a)
Definition: grph.h:168
#define EAT_FREE
Definition: grph.h:30
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
SCIP_RETCODE SCIPStpBranchruleApplyVertexChgs(SCIP *scip, int *vertexchgs, GRAPH *graph)
Definition: branch_stp.c:708
SCIP_RETCODE reduceStp(SCIP *, GRAPH **, SCIP_Real *, int, SCIP_Bool, SCIP_Bool, SCIP_Bool)
Definition: reduce.c:223
SCIP_Real * cost
Definition: grph.h:94
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17662
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
#define DEFAULT_MAXNWAITINGROUNDS
Definition: prop_stp.c:58
#define SCIP_Real
Definition: def.h:163
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:43
#define PROP_DESC
Definition: prop_stp.c:40
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int *RESTRICT outbeg
Definition: grph.h:76
#define SCIP_Longint
Definition: def.h:148
int edges
Definition: grph.h:92
#define flipedge(edge)
Definition: grph.h:150
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
#define STP_RSMT
Definition: grph.h:45
#define nnodes
Definition: gastrans.c:65
static SCIP_DECL_PROPEXEC(propExecStp)
Definition: prop_stp.c:647
struct Int_List_Node * parent
Definition: misc_stp.h:76
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
Definition: scip_prop.c:105
static void setVnoiDistances(SCIP *scip, const SCIP_Real *cost, const GRAPH *graph, PATH *vnoi, SCIP_Real *costrev, SCIP_Real *pathdist, int *pathedge, int *vbase)
Definition: prop_stp.c:227
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITSOL((*propinitsol)))
Definition: scip_prop.c:206
#define STP_RPCSPG
Definition: grph.h:41
#define PROP_TIMING
Definition: prop_stp.c:41
void graph_free_historyDeep(SCIP *, GRAPH *)
Definition: grphbase.c:3764
void graph_voronoiTerms(SCIP *, const GRAPH *, const SCIP_Real *, PATH *, int *, int *, int *)
Definition: grphpath.c:2307