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-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 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 //#define SCIP_DEBUG
26 #include <assert.h>
27 #include <string.h>
28 #include <stdlib.h>
29 #include "prop_stp.h"
30 #include "graph.h"
31 #include "reduce.h"
32 #include "solstp.h"
33 #include "redcosts.h"
34 #include "extreduce.h"
35 #include "cons_stp.h"
36 #include "branch_stp.h"
37 #include "portab.h"
38 #include "scip/tree.h"
39 
40 
41 /**@name Propagator properties
42  *
43  * @{
44  */
45 
46 #define PROP_NAME "stp"
47 #define PROP_DESC "stp propagator"
48 #define PROP_TIMING SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP
49 #define PROP_PRIORITY 1000000 /**< propagator priority */
50 #define PROP_FREQ 1 /**< propagator frequency */
51 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
52 
53 #define PROP_STP_EDGE_KILLED -1
54 #define PROP_STP_EDGE_UNSET 0
55 #define PROP_STP_EDGE_SET 1
56 #define PROP_STP_EDGE_FIXED 2
57 
58 #define PROP_STP_REDCOST_LEVELS 5
59 
60 /**@} */
61 
62 /**@name Default parameter values
63  *
64  * @{
65  */
66 
67 #define DEFAULT_MAXNWAITINGROUNDS 2 /**< maximum number of rounds to wait until propagating again */
68 #define REDUCTION_WAIT_RATIO_INITIAL 0.01 /**< ratio of edges to be newly fixed before performing reductions for additional fixing */
69 #define REDUCTION_WAIT_FACTOR 2.0
70 /**@} */
71 
72 /*
73  * Data structures
74  */
75 
76 
77 /** propagator data */
78 struct SCIP_PropData
79 {
80  REDCOST* redcostdata; /**< reduced cost data */
81  GRAPH* propgraph; /**< graph data */
82  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
83  SCIP_Real* fixingbounds; /**< saves largest upper bound to each variable that would allow to fix it */
84  SCIP_Real* deg2bounds; /**< saves largest upper bound to each variable that would allow to set degree 2 constraint */
85  SCIP_Bool* deg2bounded; /**< maximum degree of vertex is 2? */
86  SCIP_Longint nfails; /**< number of failures since last successful call */
87  SCIP_Longint ncalls; /**< number of calls */
88  SCIP_Longint nlastcall; /**< number of last call */
89  SCIP_Longint nlastnlpiter; /**< number of last LP iterations */
90  SCIP_Longint lastnodenumber_red; /**< number for last reduction call */
91  SCIP_Longint lastnodenumber; /**< number nodes for last propagator call */
92  SCIP_Longint propgraphnodenumber;/**< B&B node number at which propgraph was updated */
93  SCIP_Real lpobjval; /**< value of current LP */
94  SCIP_Real lpobjval_last; /**< value of last LP */
95  SCIP_Real redwaitratio; /**< ratio */
96  int redcostnupdates; /**< number of reduced costs updates */
97  int nfixededges_bicurr; /**< number of arcs fixed by 'fixedgevar' method of this propagator in current run */
98  int nfixededges_curr; /**< number of arcs fixed by 'fixedgevar' method of this propagator in current run */
99  int nfixededges_all; /**< total number of arcs fixed by 'fixedgevar' method of this propagator */
100  int nfixededges_bipost; /**< total number of arcs fixed by 'fixedgevar' method of this propagator after the last reductions */
101  int maxnwaitrounds; /**< maximum number of rounds to wait until propagating again */
102  SCIP_Bool isInitialized; /**< already initialized? */
103  SCIP_Bool aggressive; /**< be aggressive? */
104 };
105 
106 /**@name Local methods
107  *
108  * @{
109  */
110 
111 #if 0
112 static
113 SCIP_RETCODE fixedgevarTo1(
114  SCIP* scip, /**< SCIP data structure */
115  SCIP_VAR* edgevar, /**< the variable to be fixed */
116  int* nfixed /**< counter that is incriminated if variable could be fixed */
117  )
118 {
119  assert(scip != NULL);
120 
121  if( SCIPvarGetLbLocal(edgevar) < 0.5 && SCIPvarGetUbLocal(edgevar) > 0.5 )
122  {
123  SCIP_PROPDATA* propdata;
124 
125  printf("FIXED TO ONE %d \n", 0);
126 
127  assert(SCIPisEQ(scip, SCIPvarGetUbLocal(edgevar), 1.0));
128 
129  /* get propagator data */
130  assert(SCIPfindProp(scip, "stp") != NULL);
131  propdata = SCIPpropGetData(SCIPfindProp(scip, "stp"));
132  assert(propdata != NULL);
133 
134  SCIP_CALL( SCIPchgVarLb(scip, edgevar, 1.0) );
135  (*nfixed)++;
136  propdata->nfixededges_all++;
137  propdata->nfixededges_bipost++;
138  }
139  return SCIP_OKAY;
140 }
141 #endif
142 
143 
144 
145 /** fix a variable (corresponding to an edge) to zero */
146 static
148  SCIP* scip, /**< SCIP data structure */
149  int edge, /**< the edge */
150  SCIP_VAR** vars, /**< variables */
151  SCIP_PROPDATA* propdata /**< propagator data */
152  )
153 {
154  assert(scip && vars && propdata);
155 
156  if( SCIPvarGetLbLocal(vars[edge]) < 0.5 && SCIPvarGetUbLocal(vars[edge]) > 0.5 )
157  {
158  SCIP_CALL( SCIPchgVarUb(scip, vars[edge], 0.0) );
159  propdata->nfixededges_curr++;
160 
161  /* opposite edge already fixed? */
162  if( SCIPvarGetUbLocal(vars[flipedge(edge)]) < 0.5 )
163  propdata->nfixededges_bicurr++;
164  }
165 
166  return SCIP_OKAY;
167 }
168 
169 
170 /** gets cutoff bound */
171 static
173  SCIP* scip, /**< SCIP data structure */
174  SCIP_Real lpbound /**< LP bound */
175  )
176 {
177  SCIP_Real cutoffbound;
178  const SCIP_Real cutoffbound_scip = SCIPgetCutoffbound(scip);
179  SCIP_Real cutoffbound_presol = SCIPprobdataGetPresolUpperBound(scip);
180 
181  // todo why doesnt that work???
182  /*
183  const SCIP_Bool objIsIntegral = SCIPprobdataObjIsIntegral(scip);
184 
185  if( objIsIntegral && LT(lpbound, cutoffbound_presol - 1.0) )
186  {
187  cutoffbound_presol = SCIPprobdataGetPresolCutoffbound(scip);
188  }
189  */
190 
191  SCIPdebugMessage("Cutoffbound SCIP vs Presol: %f vs %f \n", cutoffbound_scip, cutoffbound_presol);
192 
193  cutoffbound = MIN(cutoffbound_scip, cutoffbound_presol);
194 
195  return cutoffbound;
196 }
197 
198 
199 /** gets bound changes specific for PC/MW */
200 static
202  SCIP* scip, /**< SCIP structure */
203  SCIP_VAR** vars, /**< variables */
204  const GRAPH* propgraph, /**< graph data structure */
205  int* nodestate, /**< state */
206  SCIP_Bool* conflictFound /**< conflict found? */
207 )
208 {
209  const int nnodes = propgraph->knots;
210 
211  assert(graph_pc_isPcMw(propgraph));
212  assert(propgraph->extended);
213 
214  *conflictFound = FALSE;
215 
216  for( int k = 0; k < nnodes; k++ )
217  {
218  if( graph_pc_knotIsPropPotTerm(propgraph, k) )
219  {
220  const int pterm2term = propgraph->term2edge[k];
221  const int twinterm = graph_pc_getTwinTerm(propgraph, k);
222  const int root2term = graph_pc_getRoot2PtermEdge(propgraph, twinterm);
223 
224  assert(pterm2term >= 0);
225  assert(root2term >= 0);
226  assert(graph_pc_knotIsDummyTerm(propgraph, twinterm));
227  assert(SCIPisEQ(scip, propgraph->prize[k], propgraph->cost[root2term]));
228 
229  /* root->dummyterm edge fixed to 0? Then take terminal */
230  if( SCIPvarGetUbLocal(vars[root2term]) < 0.5 )
231  {
232  if( BRANCH_STP_VERTEX_KILLED == nodestate[k] )
233  {
234  *conflictFound = TRUE;
235  return;
236  }
237 
238  nodestate[k] = BRANCH_STP_VERTEX_TERM;
239  }
240  /* root->dummyterm edge fixed to 1? Then delete terminal */
241  else if( SCIPvarGetLbLocal(vars[root2term]) > 0.5 )
242  {
243  if( BRANCH_STP_VERTEX_TERM == nodestate[k] )
244  {
245  *conflictFound = TRUE;
246  return;
247  }
248 
249  nodestate[k] = BRANCH_STP_VERTEX_KILLED;
250  }
251 
252  /* term->dummyterm edge fixed to 0? Then delete terminal */
253  if( SCIPvarGetUbLocal(vars[pterm2term]) < 0.5 )
254  {
255  if( BRANCH_STP_VERTEX_TERM == nodestate[k] )
256  {
257  *conflictFound = TRUE;
258  return;
259  }
260 
261  nodestate[k] = BRANCH_STP_VERTEX_KILLED;
262  }
263  /* term->dummyterm edge fixed to 1? Then take terminal */
264  else if( SCIPvarGetLbLocal(vars[pterm2term]) > 0.5 )
265  {
266  if( BRANCH_STP_VERTEX_KILLED == nodestate[k] )
267  {
268  *conflictFound = TRUE;
269  return;
270  }
271 
272  nodestate[k] = BRANCH_STP_VERTEX_TERM;
273  }
274  }
275  }
276 }
277 
278 
279 /** gets bound changes */
280 static
282  SCIP* scip, /**< SCIP structure */
283  SCIP_VAR** vars, /**< variables */
284  const GRAPH* propgraph, /**< graph data structure */
285  int* nodestate, /**< node state (uninitialized) */
286  int* edgestate, /**< edge state (uninitialized) */
287  SCIP_Bool* probisinfeas /**< is problem infeasible? */
288 )
289 {
290  const int nnodes = graph_get_nNodes(propgraph);
291  const int nedges = graph_get_nEdges(propgraph);
292  const SCIP_Bool pcmw = graph_pc_isPcMw(propgraph);
293 
294  assert(!pcmw || propgraph->extended);
295  assert(!(*probisinfeas));
296 
297  for( int k = 0; k < nnodes; k++ )
298  nodestate[k] = BRANCH_STP_VERTEX_UNSET;
299 
300  for( int e = 0; e < nedges; e++ )
301  edgestate[e] = PROP_STP_EDGE_UNSET;
302 
303  for( int e = 0; e < nedges; e += 2 )
304  {
305  const int erev = e + 1;
306 
307  if( pcmw && graph_pc_edgeIsExtended(propgraph, e) )
308  continue;
309 
310  /* e OR its anti-parallel edge fixed to 1? */
311  if( SCIPvarGetLbLocal(vars[e]) > 0.5 || SCIPvarGetLbLocal(vars[erev]) > 0.5 )
312  {
313  const int tail = propgraph->tail[e];
314  const int head = propgraph->head[e];
315 
316  edgestate[e] = PROP_STP_EDGE_FIXED;
317  edgestate[erev] = PROP_STP_EDGE_FIXED;
318 
319  nodestate[tail] = BRANCH_STP_VERTEX_TERM;
320  nodestate[head] = BRANCH_STP_VERTEX_TERM;
321 
322  assert(!( SCIPvarGetUbLocal(vars[e]) < 0.5 && SCIPvarGetUbLocal(vars[erev]) < 0.5 ));
323  }
324  /* both e AND its anti-parallel edge fixed to 0? */
325  else if( SCIPvarGetUbLocal(vars[e]) < 0.5 && SCIPvarGetUbLocal(vars[erev]) < 0.5 )
326  {
327  assert(SCIPvarGetLbLocal(vars[e]) < 0.5 && SCIPvarGetLbLocal(vars[erev]) < 0.5);
328 
329  edgestate[e] = PROP_STP_EDGE_KILLED;
330  edgestate[erev] = PROP_STP_EDGE_KILLED;
331  }
332  }
333 
334  if( pcmw )
335  {
336  SCIP_Bool conflict = FALSE;
337 
338  getBoundchangesPcMW(scip, vars, propgraph, nodestate, &conflict);
339 
340 #ifndef NDEBUG
341  for( int k = 0; k < nnodes; k++ )
342  assert(!(BRANCH_STP_VERTEX_TERM == nodestate[k] && graph_pc_knotIsDummyTerm(propgraph, k)));
343 #endif
344 
345  if( conflict )
346  *probisinfeas = TRUE;
347  }
348 
349  /* not at root? */
350  if( SCIPgetDepth(scip) > 0 && !(*probisinfeas) )
351  {
352  SCIP_Bool conflict = FALSE;
353 
354  SCIP_CALL( SCIPStpBranchruleGetVertexChgs(scip, nodestate, &conflict) );
355 
356  if( conflict )
357  *probisinfeas = TRUE;
358  }
359 
360  return SCIP_OKAY;
361 }
362 
363 
364 
365 /** gets state of graph at current B&B node, including bound changes;
366  * takes direction of edges into account! */
367 static
369  SCIP* scip, /**< SCIP structure */
370  const GRAPH* graph, /**< graph data structure */
371  int* nodestate, /**< node state (uninitialized) */
372  int* edgestate, /**< edge state (uninitialized) */
373  SCIP_Bool* probisinfeas /**< is problem infeasible? */
374 )
375 {
376  SCIP_VAR** vars = SCIPprobdataGetVars(scip);
377  const int nedges = graph_get_nEdges(graph);
378  const SCIP_Bool isPcMw = graph_pc_isPcMw(graph);
379 
380  assert(vars);
381  assert(!isPcMw || graph->extended);
382  assert(!(*probisinfeas));
383 
384  SCIPStpBranchruleInitNodeState(graph, nodestate);
385 
386  for( int e = 0; e < nedges; e++ )
387  edgestate[e] = PROP_STP_EDGE_UNSET;
388 
389  for( int e = 0; e < nedges; e++ )
390  {
391  if( SCIPvarGetLbLocal(vars[e]) > 0.5 )
392  {
393  assert(SCIPvarGetUbLocal(vars[e]) > 0.5);
394  edgestate[e] = PROP_STP_EDGE_FIXED;
395  nodestate[graph->tail[e]] = BRANCH_STP_VERTEX_TERM;
396  nodestate[graph->head[e]] = BRANCH_STP_VERTEX_TERM;
397  }
398  else if( SCIPvarGetUbLocal(vars[e]) < 0.5 )
399  {
400  assert(SCIPvarGetLbLocal(vars[e]) < 0.5);
401  edgestate[e] = PROP_STP_EDGE_KILLED;
402  }
403  }
404 
405  if( isPcMw )
406  {
407  SCIP_Bool conflict = FALSE;
408 
409  getBoundchangesPcMW(scip, vars, graph, nodestate, &conflict);
410 
411  if( conflict )
412  *probisinfeas = TRUE;
413  }
414 
415  /* not at root? */
416  if( SCIPgetDepth(scip) > 0 && !(*probisinfeas) && SCIPStpBranchruleIsActive(scip) )
417  {
418  SCIP_Bool conflict = FALSE;
419 
420  SCIP_CALL( SCIPStpBranchruleGetVertexChgs(scip, nodestate, &conflict) );
421 
422  if( conflict )
423  *probisinfeas = TRUE;
424  }
425 
426  return SCIP_OKAY;
427 }
428 
429 
430 
431 /** trails graph and checks for infeasibility */
432 static
434  SCIP* scip, /**< SCIP structure */
435  const GRAPH* graph, /**< graph data structure */
436  const int* nodestate, /**< node state */
437  const int* edgestate, /**< edge state */
438  SCIP_Bool* probisinfeas /**< is problem infeasible? */
439 )
440 {
441  STP_Vectype(int) queue = NULL;
442  SCIP_Bool* nodes_isVisited;
443  int termcount = 0;
444  const int nnodes = graph_get_nNodes(graph);
445  const int root = graph->source;
446 
447  assert(!(*probisinfeas));
448  assert(nodestate[graph->source] == BRANCH_STP_VERTEX_TERM);
449 
450  for( int i = 0; i < nnodes; i++ )
451  {
452  if( nodestate[i] == BRANCH_STP_VERTEX_TERM )
453  termcount++;
454  }
455 
456  assert(termcount >= graph->terms);
457 
458  /* now do a BFS from the root */
459  SCIP_CALL( SCIPallocClearBufferArray(scip, &nodes_isVisited, nnodes) );
460 
461  assert(!nodes_isVisited[root]);
462  nodes_isVisited[root] = TRUE;
463  StpVecReserve(scip, queue, nnodes);
464  StpVecPushBack(scip, queue, root);
465 
466  /* BFS loop stopping at roots */
467  for( int i = 0; i < StpVecGetSize(queue); i++ )
468  {
469  const int node = queue[i];
470  assert(nodes_isVisited[node]);
471 
472  if( nodestate[node] == BRANCH_STP_VERTEX_TERM )
473  termcount--;
474 
475  for( int e = graph->outbeg[node]; e >= 0; e = graph->oeat[e] )
476  {
477  const int head = graph->head[e];
478  if( !nodes_isVisited[head] && edgestate[e] != PROP_STP_EDGE_KILLED )
479  {
480  nodes_isVisited[head] = TRUE;
481  StpVecPushBack(scip, queue, head);
482  assert(nodestate[head] != BRANCH_STP_VERTEX_KILLED);
483  }
484  }
485  }
486 
487  assert(termcount >= 0);
488 
489  if( termcount != 0 )
490  {
491  *probisinfeas = TRUE;
492  }
493 
494  StpVecFree(scip, queue);
495  SCIPfreeBufferArray(scip, &nodes_isVisited);
496 
497  return SCIP_OKAY;
498 }
499 
500 
501 /** initialize reduced cost distances */
502 static
504  SCIP* scip, /**< SCIP structure */
505  const SCIP_Real* redcost, /**< reduced costs */
506  GRAPH* g, /**< graph data structure */
507  PATH* vnoi, /**< Voronoi paths */
508  SCIP_Real* pathdist, /**< path distance */
509  int* vbase, /**< Voronoi base */
510  int* state /**< state */
511 )
512 {
513  SCIP_Real* redcostrev = NULL;
514  int* pathedge = NULL;
515  const int nedges = graph_get_nEdges(g);
516  const int nnodes = graph_get_nNodes(g);
517 
518  assert(graph_isMarked(g));
519 
520  SCIP_CALL( SCIPallocBufferArray(scip, &pathedge, nnodes) );
521  SCIP_CALL( SCIPallocBufferArray(scip, &redcostrev, nedges) );
522 
523  /* distance from root to all nodes */
524  graph_path_execX(scip, g, g->source, redcost, pathdist, pathedge);
525 
526  for( unsigned int e = 0; e < (unsigned) nedges; e++ )
527  redcostrev[e] = redcost[flipedge(e)];
528 
529  /* no paths should go back to the root */
530  for( int e = g->outbeg[g->source]; e != EAT_LAST; e = g->oeat[e] )
531  redcostrev[e] = FARAWAY;
532 
533  graph_get2nextTermPaths(g, redcostrev, redcostrev, vnoi, vbase, state);
534 
535  SCIPfreeBufferArray(scip, &redcostrev);
536  SCIPfreeBufferArray(scip, &pathedge);
537 
538  return SCIP_OKAY;
539 }
540 
541 
542 /** marks arcs fixed to 0 */
543 static inline
545  const GRAPH* graph, /**< graph structure */
546  SCIP_VAR** vars, /**< variables (in) */
547  STP_Bool* arcIs0Fixed /**< array (out) */
548  )
549 {
550  const int nedges = graph_get_nEdges(graph);
551 
552  assert(vars && arcIs0Fixed);
553 
554 #ifdef USE_EXTRED_FULL
555  for( int e = 0; e < nedges; e++ )
556  {
557  arcIs0Fixed[e] = (SCIPvarGetUbGlobal(vars[e]) < 0.5);
558  }
559 #else
560  for( int e = 0; e < nedges; e++ )
561  {
562  arcIs0Fixed[e] = (SCIPvarGetUbLocal(vars[e]) < 0.5);
563  }
564 #endif
565 }
566 
567 
568 /** some checks */
569 static
571  const GRAPH* graph, /**< graph structure */
572  const GRAPH* propgraph, /**< propagator graph */
573  /*const*/ SCIP_VAR** vars, /**< variables */
574  const int* edgestate, /**< edge state array */
575  SCIP_Bool* error /**< error during update? */
576 )
577 {
578  const int nedges = graph_get_nEdges(graph);
579  const SCIP_Bool pcmw = graph_pc_isPcMw(graph);
580 
581  *error = FALSE;
582 
583  /* 1-fixed edge to be deleted? */
584  for( int e = 0; e < nedges; e++ )
585  {
586  if( (edgestate[e] == PROP_STP_EDGE_UNSET || edgestate[e] == PROP_STP_EDGE_KILLED)
587  && (SCIPvarGetLbLocal(vars[e]) > 0.5) )
588  {
589  if( pcmw && graph_pc_edgeIsExtended(graph, e) )
590  continue;
591 
592  graph_edge_printInfo(propgraph, e);
593  printf(
594  "1-fixed arc deleted by reduction methods ... can't propagate \n \n \n");
595  *error = TRUE;
596  return;
597  }
598  }
599 
600  /* 0-fixed edge been contracted? */
601  for( int e = 0; e < nedges; e++ )
602  {
603  if( edgestate[e] == PROP_STP_EDGE_FIXED
604  && SCIPvarGetUbLocal(vars[e]) < 0.5
605  && SCIPvarGetUbLocal(vars[flipedge(e)]) < 0.5 )
606  {
607  graph_edge_printInfo(propgraph, e);
608  printf(
609  "0-fixed arc contracted by reduction methods ... can't propagate \n \n \n");
610  *error = TRUE;
611  return;
612  }
613  }
614 }
615 
616 
617 /** helper method for reduction based variable fixings */
618 static inline
620  const GRAPH* graph, /**< graph structure */
621  IDX* curr, /**< current ancestor */
622  int* RESTRICT edgestate /**< edge state array */
623 )
624 {
625  while( curr != NULL )
626  {
627  const int i = curr->index;
628 
629  assert(i < graph->edges);
630  assert(edgestate[i] != PROP_STP_EDGE_KILLED && edgestate[flipedge(i)] != PROP_STP_EDGE_KILLED);
631 
632  if( edgestate[i] == PROP_STP_EDGE_UNSET )
633  {
634 
635 #ifdef SCIP_DEBUG
636  printf("set remain edge ");
637  graph_edge_printInfo(graph, i);
638 #endif
639 
640  edgestate[i] = PROP_STP_EDGE_SET;
641  edgestate[flipedge(i)] = PROP_STP_EDGE_SET;
642  }
643  curr = curr->parent;
644  }
645 }
646 
647 
648 /** helper method for reduction based variable fixings */
649 static inline
651  const GRAPH* graph, /**< graph structure */
652  IDX* curr, /**< current ancestor */
653  int* RESTRICT edgestate /**< edge state array */
654 )
655 {
656  while( curr != NULL )
657  {
658  const int e = curr->index;
659  assert(e < graph->edges);
660 
661 #ifdef SCIP_DEBUG
662  printf("fix remain edge ");
663  graph_edge_printInfo(graph, e);
664 #endif
665 
666  edgestate[e] = PROP_STP_EDGE_FIXED;
667  edgestate[flipedge(e)] = PROP_STP_EDGE_FIXED;
668 
669  curr = curr->parent;
670  }
671 }
672 
673 
674 /** method for reduction based variable fixings */
675 static
677  SCIP* scip, /**< SCIP data structure */
678  const GRAPH* graph, /**< graph structure */
679  SCIP_VAR** vars, /**< variables */
680  const int* edgestate, /**< edge state array */
681  SCIP_PROPDATA* propdata /**< propagator data */
682 )
683 {
684  const int nedges = graph_get_nEdges(graph);
685  const SCIP_Bool pcmw = graph_pc_isPcMw(graph);
686 
687  /* fix edge variables to 0 */
688  for( int e = 0; e < nedges; e += 2 )
689  {
690  /* edge not set yet? */
691  if( edgestate[e] == PROP_STP_EDGE_UNSET )
692  {
693  const int erev = e + 1;
694 
695  assert(edgestate[erev] == PROP_STP_EDGE_UNSET);
696 
697  if( pcmw )
698  {
699  assert(graph->extended);
700 
701  if( SCIPisGE(scip, graph->cost[e], FARAWAY) || SCIPisGE(scip, graph->cost[erev], FARAWAY) )
702  continue;
703  }
704 
705 #ifdef SCIP_DEBUG
706  printf("red-based fixing of ");
707  graph_edge_printInfo(graph, e);
708 #endif
709 
710  SCIP_CALL( fixEdgeVar(scip, e, vars, propdata) );
711  SCIP_CALL( fixEdgeVar(scip, erev, vars, propdata) );
712  }
713  }
714 
715  return SCIP_OKAY;
716 }
717 
718 
719 /** update method for reduction based variable fixings */
720 static
722  const GRAPH* graph, /**< graph structure */
723  const GRAPH* propgraph, /**< propagator graph */
724  SCIP_VAR** vars, /**< variables */
725  const int* nodestate, /**< node state array */
726  int* edgestate, /**< edge state array */
727  SCIP_Bool* error /**< error during update? */
728 )
729 {
730  const int nedges = graph_get_nEdges(graph);
731  const SCIP_Bool pcmw = graph_pc_isPcMw(graph);
732 
733  assert(graph_pc_isPcMw(graph) == graph_pc_isPcMw(propgraph));
734 
735  if( pcmw )
736  {
737  assert(graph->extended);
738  setEdgestate(propgraph, propgraph->pcancestors[propgraph->source], edgestate);
739  }
740 
741  for( int e = 0; e < nedges; e++ )
742  {
743  if( propgraph->ieat[e] != EAT_FREE )
744  {
745  assert(propgraph->ieat[flipedge(e)] != EAT_FREE);
746  setEdgestate(propgraph, propgraph->ancestors[e], edgestate);
747  if( pcmw )
748  {
749  setEdgestate(propgraph, propgraph->pcancestors[propgraph->head[e]], edgestate);
750  setEdgestate(propgraph, propgraph->pcancestors[propgraph->tail[e]], edgestate);
751  }
752  }
753  }
754 
755  fixEdgestate(propgraph, graph_getFixedges(propgraph), edgestate);
756 
757  validateEdgestate(graph, propgraph, vars, edgestate, error);
758 }
759 
760 
761 /** update method for reduction based variable fixings */
762 static
764  SCIP* scip, /**< SCIP */
765  const GRAPH* graph, /**< graph structure */
766  const GRAPH* propgraph, /**< propagator graph */
767  SCIP_VAR** vars, /**< variables */
768  const int* nodestate, /**< node state array */
769  int* edgestate, /**< edge state array */
770  SCIP_Bool* error /**< error during update? */
771 )
772 {
773  const int nnodes = graph_get_nNodes(propgraph);
774  const int nedges = graph_get_nEdges(propgraph);
775  IDX** ancestors = propgraph->ancestors;
776  int nsetnodes = 0;
777  int nsetedges = 0;
778  STP_Bool* node_isSet;
779  STP_Bool* edge_isSet;
780  int* setnodesqueue;
781 
782  assert(graph_pc_isPcMw(propgraph));
783  assert(nnodes == graph->knots);
784  assert(nedges == graph->edges);
785 
786  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &node_isSet, nnodes) );
787  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &edge_isSet, nedges) );
788  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &setnodesqueue, nnodes) );
789 
790  for( int k = 0; k < nnodes; k++ )
791  node_isSet[k] = FALSE;
792 
793  for( int e = 0; e < nedges; e++ )
794  edge_isSet[e] = FALSE;
795 
796  if( graph_pc_isRootedPcMw(propgraph) )
797  {
798  setnodesqueue[nsetnodes++] = propgraph->source;
799  node_isSet[propgraph->source] = TRUE;
800  }
801 
802  for( int e = 0; e <= nedges; e++ )
803  {
804  if( e == nedges || propgraph->ieat[e] != EAT_FREE )
805  {
806  // ugly as hell, use extra method!
807  IDX* curr = (e < nedges) ? ancestors[e] : graph_getFixedges(propgraph);
808 
809  while( curr != NULL )
810  {
811  const int ancestoredge = curr->index;
812 
813  if( !edge_isSet[ancestoredge] )
814  {
815  edge_isSet[ancestoredge] = TRUE;
816  nsetedges++;
817  }
818  if( !node_isSet[propgraph->tail[ancestoredge]] )
819  {
820  node_isSet[propgraph->tail[ancestoredge]] = TRUE;
821  setnodesqueue[nsetnodes++] = propgraph->tail[ancestoredge];
822  }
823  if( !node_isSet[propgraph->head[ancestoredge]] )
824  {
825  node_isSet[propgraph->head[ancestoredge]] = TRUE;
826  setnodesqueue[nsetnodes++] = propgraph->head[ancestoredge];
827  }
828 
829  curr = curr->parent;
830  }
831  }
832  }
833 
834  SCIP_CALL_ABORT( solstp_markPcancestors(scip, propgraph->pcancestors, propgraph->tail, propgraph->head,
835  nnodes, node_isSet, edge_isSet, setnodesqueue, &nsetnodes, &nsetedges ) );
836 
837  for( int e = 0; e < nedges; e++ )
838  {
839  if( edge_isSet[e] )
840  {
841  if( edgestate[e] == PROP_STP_EDGE_UNSET )
842  {
843  edgestate[e] = PROP_STP_EDGE_SET;
844  edgestate[flipedge(e)] = PROP_STP_EDGE_SET;
845  }
846  }
847  }
848 
849  SCIPfreeBufferArray(scip, &setnodesqueue);
850  SCIPfreeBufferArray(scip, &edge_isSet);
851  SCIPfreeBufferArray(scip, &node_isSet);
852 
853  fixEdgestate(propgraph, graph_getFixedges(propgraph), edgestate);
854 
855  validateEdgestate(graph, propgraph, vars, edgestate, error);
856 }
857 
858 
859 
860 /** updates fixing bounds for reduced cost fixings */
861 static
863  const GRAPH* graph, /**< graph data structure */
864  const SCIP_Real* cost, /**< reduced costs */
865  const SCIP_Real* pathdist, /**< shortest path distances */
866  const PATH* vnoi, /**< Voronoi paths */
867  SCIP_Real lpobjal, /**< LP objective */
868  SCIP_Real* fixingbounds /**< fixing bounds */
869 )
870 {
871  const int nnodes = graph->knots;
872 
873  for( int k = 0; k < nnodes; k++ )
874  {
875  if( Is_term(graph->term[k]) && (graph->stp_type == STP_MWCSP || graph->stp_type == STP_PCSPG) )
876  continue;
877 
878  for( int e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
879  {
880  const SCIP_Real fixbnd = pathdist[k] + cost[e] + vnoi[graph->head[e]].dist + lpobjal;
881  if( fixbnd > fixingbounds[e] )
882  fixingbounds[e] = fixbnd;
883  }
884  }
885 }
886 
887 
888 /* updates fixing bounds for reduced cost based constraints */
889 static
891  const GRAPH* graph, /**< graph data structure */
892  const SCIP_Real* pathdist, /**< shortest path distances */
893  const PATH* vnoi, /**< Voronoi paths */
894  SCIP_Real lpobjal, /**< LP objective */
895  SCIP_Real* deg2bounds /**< bounds */
896 )
897 {
898  const int nnodes = graph->knots;
899 
900  for( int k = 0; k < nnodes; k++ )
901  {
902  if( !Is_term(graph->term[k]) )
903  {
904  const SCIP_Real fixbnd = pathdist[k] + vnoi[k].dist + vnoi[k + nnodes].dist + lpobjal;
905  if( fixbnd > deg2bounds[k] )
906  deg2bounds[k] = fixbnd;
907  }
908  }
909 }
910 
911 
912 /** fixes node of propgraph (ignores dummy terminals!) */
913 static inline
915  SCIP* scip, /**< SCIP data structure */
916  int node, /**< the node */
917  GRAPH* propgraph, /**< propagator graph */
918  SCIP_Real* offset /**< pointer to the offset (in/out) */
919  )
920 {
921  assert(node >= 0 && node < propgraph->knots);
922  assert(!propgraph->extended);
923 
924 #ifdef SCIP_DEBUG
925  SCIPdebugMessage("try to fix ");
926  graph_knot_printInfo(propgraph, node);
927 #endif
928 
929 
930  if( graph_pc_isPcMw(propgraph) )
931  {
932  assert(!graph_pc_knotIsDummyTerm(propgraph, node));
933 
934  if( graph_pc_isRootedPcMw(propgraph) )
935  {
936  if( !graph_pc_knotIsFixedTerm(propgraph, node) )
937  {
938  graph_pc_knotToFixedTerm(scip, propgraph, node, offset);
939 
940  SCIPdebugMessage("...fixed \n");
941  }
942  }
943  else
944  {
945  graph_pc_enforceNode(scip, propgraph, node, offset);
946 
947  SCIPdebugMessage("...enforced \n");
948  }
949  }
950  else
951  {
952  graph_knot_chg(propgraph, node, STP_TERM);
953 
954  SCIPdebugMessage("...made standard terminal \n");
955  }
956 }
957 
958 
959 /** deletes node of propgraph (ignores dummy terminals!) */
960 static inline
962  SCIP* scip, /**< SCIP data structure */
963  int node, /**< the node */
964  GRAPH* propgraph, /**< propagator graph */
965  SCIP_Real* offset /**< offset pointer */
966  )
967 {
968  assert(scip && propgraph && offset);
969  assert(node >= 0 && node < propgraph->knots);
970 
971 #ifdef SCIP_DEBUG
972  SCIPdebugMessage("try to delete ");
973  graph_knot_printInfo(propgraph, node);
974 #endif
975 
976  if( graph_pc_isPcMw(propgraph) )
977  {
978  assert(!graph_pc_knotIsDummyTerm(propgraph, node));
979  assert(!propgraph->extended);
980  assert(!graph_pc_knotIsFixedTerm(propgraph, node));
981 
982  if( Is_term(propgraph->term[node]) )
983  {
984  assert(graph_pc_knotIsPropPotTerm(propgraph, node) || graph_pc_knotIsNonLeafTerm(propgraph, node));
985 
986  graph_pc_deleteTerm(scip, propgraph, node, offset);
987 
988  SCIPdebugMessage("deleted term \n");
989  }
990  else
991  {
992  assert(!Is_anyTerm(propgraph->term[node]));
993 
994  graph_knot_del(scip, propgraph, node, TRUE);
995 
996  SCIPdebugMessage("deleted node \n");
997  }
998  }
999  else
1000  {
1001  assert(!Is_term(propgraph->term[node]));
1002 
1003  graph_knot_del(scip, propgraph, node, TRUE);
1004 
1005  SCIPdebugMessage("deleted node \n");
1006  }
1007 }
1008 
1009 
1010 /** fixes edge of propgraph */
1011 static
1013  SCIP* scip, /**< SCIP data structure */
1014  int e, /**< the edge */
1015  GRAPH* propgraph /**< propagator graph */
1016  )
1017 {
1018  const SCIP_Bool pcmw = graph_pc_isPcMw(propgraph);
1019  const int erev = flipedge(e);
1020 #ifndef NDEBUG
1021  const int tail = propgraph->tail[e];
1022  const int head = propgraph->head[e];
1023 #endif
1024 
1025  assert(!pcmw || !propgraph->extended);
1026  assert(e >= 0 && e < propgraph->edges);
1027 
1028  if( pcmw && (SCIPisGE(scip, propgraph->cost[e], FARAWAY) || SCIPisGE(scip, propgraph->cost[erev], FARAWAY)) )
1029  {
1030  assert(!SCIPisEQ(scip, propgraph->cost[e], propgraph->cost[erev]));
1031  return;
1032  }
1033 
1034  /* nothing has to be done here, because tail and head will be fixed
1035  * ...and later merged during presolving */
1036  if( graph_pc_isMw(propgraph) )
1037  {
1038  return;
1039  }
1040 
1041  assert(!pcmw || !graph_pc_knotIsDummyTerm(propgraph, tail));
1042  assert(!pcmw || !graph_pc_knotIsDummyTerm(propgraph, head));
1043 
1044  assert(graph_pc_isMw(propgraph) || SCIPisEQ(scip, propgraph->cost[e], propgraph->cost[erev]));
1045 
1046  propgraph->cost[e] = 0.0;
1047  propgraph->cost[erev] = 0.0;
1048 }
1049 
1050 
1051 /** deletes edge of propgraph */
1052 static
1054  SCIP* scip, /**< SCIP data structure */
1055  int e, /**< the edge */
1056  GRAPH* propgraph /**< propagator graph */
1057  )
1058 {
1059  const SCIP_Bool pcmw = graph_pc_isPcMw(propgraph);
1060  const int erev = flipedge(e);
1061 #ifndef NDEBUG
1062  const int tail = propgraph->tail[e];
1063  const int head = propgraph->head[e];
1064 #endif
1065 
1066  assert(!pcmw || !propgraph->extended);
1067  assert(e >= 0 && e < propgraph->edges);
1068 
1069  if( pcmw )
1070  {
1071  assert(!propgraph->extended);
1072 
1073  if( SCIPisGE(scip, propgraph->cost[e], FARAWAY) || SCIPisGE(scip, propgraph->cost[erev], FARAWAY) )
1074  {
1075  assert(Is_term(propgraph->term[tail]) || Is_term(propgraph->term[head]));
1076 
1077  return;
1078  }
1079 
1080  assert(!graph_pc_knotIsDummyTerm(propgraph, tail));
1081  assert(!graph_pc_knotIsDummyTerm(propgraph, head));
1082  }
1083 
1084  graph_edge_del(scip, propgraph, e, TRUE);
1085 
1086 }
1087 
1088 
1089 /** apply current bound changes to propgraph */
1090 static
1092  SCIP* scip, /**< SCIP data structure */
1093  const int* nodestate, /**< node state*/
1094  GRAPH* propgraph, /**< propagator graph */
1095  SCIP_Bool* hasFixedTerms /**< have terminals been fixed? */
1096 )
1097 {
1098  assert(hasFixedTerms && nodestate && scip && propgraph);
1099  assert(graph_pc_isPcMw(propgraph));
1100  assert(!propgraph->extended);
1101 
1102  *hasFixedTerms = FALSE;
1103 
1104  if( !graph_pc_isRootedPcMw(propgraph) )
1105  {
1106  const int nnodes = graph_get_nNodes(propgraph);
1107 
1108  for( int k = 0; k < nnodes; k++ )
1109  {
1110  if( nodestate[k] == BRANCH_STP_VERTEX_TERM && graph_pc_knotIsPropPotTerm(propgraph, k) )
1111  {
1112  graph_pc_knotChgPrize(propgraph, BLOCKED_MINOR, k);
1113  *hasFixedTerms = TRUE;
1114  }
1115  }
1116  }
1117 }
1118 
1119 /** helper method for propgraphApplyBoundchanges */
1120 static inline
1122  SCIP* scip, /**< SCIP data structure (in) */
1123  const int* nodestate, /**< node state (in) */
1124  const int* edgestate, /**< edge state (in) */
1125  GRAPH* propgraph, /**< propagator graph (in/out) */
1126  SCIP_Real* offset /**< pointer to the offset (in/out) */
1127  )
1128 {
1129  const int nnodes = graph_get_nNodes(propgraph);
1130  const int nedges = graph_get_nEdges(propgraph);
1131 
1132  for( int e = 0; e < nedges; e += 2 )
1133  {
1134  assert(edgestate[e] == edgestate[e + 1]);
1135  assert(e + 1 == flipedge(e));
1136 
1137  if( PROP_STP_EDGE_FIXED == edgestate[e] )
1138  {
1139 #ifndef NDEBUG
1140  const int tail = propgraph->tail[e];
1141  const int head = propgraph->tail[e];
1142  assert(BRANCH_STP_VERTEX_TERM == nodestate[tail]);
1143  assert(BRANCH_STP_VERTEX_TERM == nodestate[head]);
1144 #endif
1145 
1146  propgraphFixEdge(scip, e, propgraph);
1147  }
1148  else if( PROP_STP_EDGE_KILLED == edgestate[e] )
1149  {
1150  propgraphDeleteEdge(scip, e, propgraph);
1151  }
1152  }
1153 
1154  for( int k = 0; k < nnodes; k++ )
1155  {
1156  if( BRANCH_STP_VERTEX_TERM == nodestate[k] )
1157  {
1158  propgraphFixNode(scip, k, propgraph, offset);
1159  }
1160  else if( BRANCH_STP_VERTEX_KILLED == nodestate[k] )
1161  {
1162  propgraphDeleteNode(scip, k, propgraph, offset);
1163  }
1164  }
1165 }
1166 
1167 
1168 /** Apply current implications resulting from bound changes to propgraph. */
1169 static
1171  SCIP* scip, /**< SCIP data structure */
1172  const GRAPH* g, /**< the original graph */
1173  SCIP_VAR** vars, /**< variables */
1174  SCIP_PROPDATA* propdata, /**< propagator data */
1175  SCIP_Bool* probisinfeas, /**< is problem infeasible? */
1176  SCIP_Real* offset /**< pointer to the offset */
1177  )
1178 {
1179  const int* verts = SCIPStpGetPcImplVerts(scip);
1180  const int* start = SCIPStpGetPcImplStarts(scip);
1181  GRAPH* const propgraph = propdata->propgraph;
1182 
1183  assert(g && vars && propgraph && probisinfeas && offset);
1184  assert(graph_pc_isPcMw(propgraph));
1185  assert(g->extended);
1186  assert(!propgraph->extended);
1187 
1188  if( verts != NULL )
1189  {
1190  const int nnodes = graph_get_nNodes(propgraph);
1191  int ptermcount = 0;
1192 
1193  assert(start != NULL);
1194  assert(propgraph->knots == g->knots);
1195 
1196  for( int i = 0; i < nnodes && !(*probisinfeas); i++ )
1197  {
1198  if( !Is_pseudoTerm(g->term[i]) )
1199  continue;
1200 
1201  assert(graph_pc_knotIsPropPotTerm(g, i));
1202 
1203  ptermcount++;
1204 
1205  assert(ptermcount <= SCIPStpGetPcImplNstarts(scip));
1206 
1207  /* has the vertex 'i' been killed in propgraph? */
1208  if( propgraph->grad[i] == 0 )
1209  {
1210  assert(g->grad[i] > 0);
1211 
1212  for( int j = start[ptermcount - 1]; j < start[ptermcount]; j++ )
1213  {
1214  const int vert = verts[j];
1215 
1216  if( propgraph->grad[vert] == 0 )
1217  continue;
1218 
1219  if( graph_pc_knotIsFixedTerm(propgraph, vert) )
1220  {
1221  *probisinfeas = TRUE;
1222  SCIPdebugMessage("implication tries to kill fixed terminal -> problem is infeasible \n");
1223  break;
1224  }
1225 
1226  assert(!graph_pc_knotIsDummyTerm(propgraph, vert));
1227 
1228  if( Is_anyTerm((propgraph->term[vert])) )
1229  {
1230  assert(graph_pc_knotIsPropPotTerm(propgraph, vert) || graph_pc_knotIsNonLeafTerm(propgraph, vert));
1231 
1232  graph_pc_deleteTerm(scip, propgraph, vert, offset);
1233  }
1234  else
1235  {
1236  assert(!graph_pc_knotIsPropPotTerm(propgraph, vert) && !graph_pc_knotIsNonLeafTerm(propgraph, vert));
1237 
1238  graph_knot_del(scip, propgraph, vert, TRUE);
1239  }
1240  }
1241  }
1242  else if( graph_pc_knotIsPropPotTerm(propgraph, i) )
1243  {
1244  assert(SCIPisLT(scip, propgraph->prize[i], BLOCKED_MINOR)); // should have been fixed already!
1245 
1246  for( int j = start[ptermcount - 1]; j < start[ptermcount]; j++ )
1247  {
1248  const int vert = verts[j];
1249 
1250  assert(SCIPisLT(scip, propgraph->prize[vert], BLOCKED_MINOR) || graph_pc_knotIsFixedTerm(propgraph, vert) );
1251 
1252  /* is 'vert' fixed? */
1253  if( graph_pc_knotIsFixedTerm(propgraph, vert) )
1254  {
1255  const int twin = graph_pc_getTwinTerm(propgraph, i);
1256  const int rootedge = graph_pc_getRoot2PtermEdge(g, twin);
1257  SCIP_CALL( fixEdgeVar(scip, rootedge, vars, propdata ) );
1258 
1259  graph_pc_knotToFixedTerm(scip, propgraph, i, offset);
1260  break;
1261  }
1262  }
1263  }
1264  }
1265 
1266  assert(*probisinfeas || SCIPStpGetPcImplNstarts(scip) == ptermcount);
1267  assert(*probisinfeas || graph_pc_nNonFixedTerms(g) == ptermcount);
1268  } /* verts != NULL */
1269 
1270  return SCIP_OKAY;
1271 }
1272 
1273 /** Prunes unconnected vertices and edges.
1274  * Also checks for resulting infeasibility */
1275 static
1277  SCIP* scip, /**< SCIP data structure */
1278  GRAPH* propgraph, /**< propagator graph (in) */
1279  SCIP_Bool* probisinfeas, /**< is problem infeasible? */
1280  SCIP_Real* offset /**< pointer to the offset */
1281  )
1282 {
1283  assert(probisinfeas);
1284  assert(!(*probisinfeas));
1285 
1286  if( graph_pc_isRootedPcMw(propgraph) )
1287  SCIP_CALL( reduce_unconnectedRpcRmwInfeas(scip, propgraph, offset, probisinfeas) );
1288  else
1289  SCIP_CALL( reduce_unconnectedInfeas(scip, FALSE, propgraph, probisinfeas) );
1290 
1291  return SCIP_OKAY;
1292 }
1293 
1294 /** Apply current bound changes to propgraph.
1295  * Note that the graph type of propgraph might be changed! */
1296 static
1298  SCIP* scip, /**< SCIP data structure */
1299  SCIP_VAR** vars, /**< variables */
1300  const GRAPH* g, /**< graph data structure */
1301  int* nodestate, /**< node state (uninitialized) */
1302  int* edgestate, /**< edge state (uninitialized) */
1303  SCIP_PROPDATA* propdata, /**< propagator data */
1304  SCIP_Bool* probisinfeas, /**< is problem infeasible? */
1305  SCIP_Real* offset /**< pointer to the offset */
1306  )
1307 {
1308  GRAPH* const propgraph = propdata->propgraph;
1309  const SCIP_Bool pcmw = graph_pc_isPcMw(propgraph);
1310 
1311  assert(scip && vars && g && edgestate && nodestate && probisinfeas && offset);
1312  assert(g->stp_type == propgraph->stp_type);
1313  assert(propgraph->knots == g->knots);
1314  assert(propgraph->edges == g->edges);
1315  assert(!(*probisinfeas));
1316 
1317  SCIP_CALL( getBoundchanges(scip, vars, propgraph, nodestate, edgestate, probisinfeas) );
1318 
1319  if( *probisinfeas )
1320  {
1321  SCIP_CALL( graph_path_init(scip, propgraph) );
1322  return SCIP_OKAY;
1323  }
1324 
1325  if( pcmw )
1326  {
1327  SCIP_Bool rootable = FALSE;
1328  graph_pc_2org(scip, propgraph);
1329 
1330  propgraphMarkFixedTermsPcMw(scip, nodestate, propgraph, &rootable);
1331 
1332  if( rootable )
1333  {
1334  assert(!graph_pc_isRootedPcMw(propgraph));
1335 
1336  graph_transPcmw2rooted(scip, propgraph, BLOCKED_MINOR, FALSE);
1337 
1338  assert(graph_pc_isRootedPcMw(propgraph));
1339  }
1340  }
1341 
1342  SCIP_CALL( graph_path_init(scip, propgraph) );
1343 
1344  propgraphApplyStates(scip, nodestate, edgestate, propgraph, offset);
1345 
1346  *probisinfeas = FALSE;
1347 
1348  if( pcmw )
1349  {
1350  SCIP_CALL( propgraphApplyImplicationsPcMw(scip, g, vars, propdata, probisinfeas, offset) );
1351 
1352  graph_pc_2trans(scip, propgraph);
1353  }
1354 
1355  return SCIP_OKAY;
1356 }
1357 
1358 
1359 /** initializes */
1360 static inline
1362  SCIP* scip, /**< SCIP data structure */
1363  const GRAPH* graph, /**< graph structure to use for the update */
1364  SCIP_PROPDATA* propdata /**< propagator data */
1365 )
1366 {
1367  assert(scip && graph && propdata);
1368 
1369  assert(propdata->propgraph == NULL);
1370 
1371  propdata->propgraphnodenumber = SCIPnodeGetNumber(SCIPgetCurrentNode(scip));
1372 
1373  SCIP_CALL( graph_copy(scip, graph, &(propdata->propgraph)) );
1374 
1375  propdata->propgraph->norgmodeledges = propdata->propgraph->edges;
1376  propdata->propgraph->norgmodelknots = propdata->propgraph->knots;
1377 
1378  SCIP_CALL( graph_initHistory(scip, propdata->propgraph) );
1379 #ifndef WITH_UG
1380  SCIP_CALL( graph_copyPseudoAncestors(scip, graph, propdata->propgraph) );
1381 #endif
1382 
1383  assert(propdata->nfixededges_all == 0);
1384  assert(propdata->nfixededges_curr == 0);
1385  assert(propdata->nfixededges_bicurr == 0);
1386  assert(propdata->propgraph != NULL);
1387 
1388  return SCIP_OKAY;
1389 }
1390 
1391 
1392 /** initializes */
1393 static inline
1395  const GRAPH* graph /**< graph structure to use for the update */
1396 )
1397 {
1398  return (graph_typeIsSpgLike(graph) || graph_pc_isPc(graph));
1399 }
1400 
1401 
1402 /** writes reduced costs into given level */
1403 static
1405  SCIP* scip, /**< SCIP data structure */
1406  int level, /**< the level */
1407  const GRAPH* graph, /**< graph structure to use for the update */
1408  SCIP_VAR** vars, /**< variables */
1409  SCIP_PROPDATA* propdata /**< propagator data */
1410 )
1411 {
1412  REDCOST* redcostdata = propdata->redcostdata;
1413  SCIP_Real* const redcost = redcosts_getEdgeCosts(redcostdata, level);
1414  const SCIP_Real lpobjval = propdata->lpobjval;
1415  const SCIP_Real cutoffbound = getCutoffbound(scip, lpobjval);
1416  const SCIP_Real cutoffgap = cutoffbound - lpobjval;
1417 
1418  assert(GE(lpobjval, 0.0) && LE(lpobjval, cutoffbound));
1419  assert(GE(cutoffgap, 0.0));
1420 
1421  redcosts_forLPget(scip, vars, graph, redcost);
1422  redcosts_setDualBound(lpobjval, level, redcostdata);
1423  redcosts_setCutoff(cutoffgap, level, redcostdata);
1424  redcosts_setRoot(graph->source, level, redcostdata);
1425 }
1426 
1427 
1428 /** initializes */
1429 static inline
1431  SCIP* scip, /**< SCIP data structure */
1432  const GRAPH* graph, /**< graph structure to use for the update */
1433  SCIP_VAR** vars, /**< variables */
1434  SCIP_PROPDATA* propdata /**< propagator data */
1435 )
1436 {
1437  const int nnodes = graph_get_nNodes(graph);
1438  const int nedges = graph_get_nEdges(graph);
1439 #ifdef USE_EXTRED_FULL
1440  int nlevels = PROP_STP_REDCOST_LEVELS;
1441 #else
1442  int nlevels = 1;
1443 #endif
1444  RCPARAMS rcparams = { .cutoff = -1.0, .nLevels = nlevels, .nCloseTerms = 3,
1445  .nnodes = nnodes, .nedges = nedges, .redCostRoot = -1 };
1446 
1447  assert(scip && graph && propdata);
1448  assert(propdata->redcostdata == NULL);
1449  assert(propdata->redcostnupdates == 0);
1450 
1451  SCIP_CALL( redcosts_initFromParams(scip, &rcparams, &(propdata->redcostdata)) );
1452  writeRedcostdata(scip, 0, graph, vars, propdata);
1453 
1454  return SCIP_OKAY;
1455 }
1456 
1457 
1458 /** updates */
1459 static inline
1461  SCIP* scip, /**< SCIP data structure */
1462  const GRAPH* graph, /**< graph structure to use for the update */
1463  SCIP_VAR** vars, /**< variables */
1464  SCIP_PROPDATA* propdata /**< propagator data */
1465 )
1466 {
1467 #ifdef USE_EXTRED_FULL
1468  REDCOST* redcostdata = propdata->redcostdata;;
1469 #endif
1470 
1471  assert(propdata->redcostdata);
1472 
1473  /* NOTE: ugly workaround */
1474  if( propdata->redcostnupdates == 0 )
1475  {
1476  assert(redcosts_getNlevels(propdata->redcostdata) == 1);
1477  propdata->redcostnupdates++;
1478  return;
1479  }
1480 
1481 #ifdef USE_EXTRED_FULL
1482  assert(redcosts_getNlevels(redcostdata) >= 1);
1483 
1484  if( redcosts_getNlevels(redcostdata) < PROP_STP_REDCOST_LEVELS )
1485  {
1486  redcosts_addLevel(redcostdata);
1487  writeRedcostdata(scip, redcosts_getLevel(redcostdata), graph, vars, propdata);
1488 
1489  propdata->redcostnupdates++;
1490  }
1491  else
1492  {
1493  const SCIP_Bool overwrite = SCIPisGT(scip, propdata->lpobjval, propdata->lpobjval_last); //(SCIPrandomGetInt(propdata->randnumgen, 0, 1) == 0);
1494 
1495  assert(SCIPisGE(scip, propdata->lpobjval, propdata->lpobjval_last));
1496 
1497  if( overwrite )
1498  {
1499  const int level = SCIPrandomGetInt(propdata->randnumgen, 1, PROP_STP_REDCOST_LEVELS - 1);
1500 
1501  SCIPdebugMessage("overwrite level %d \n", level);
1502 
1503  writeRedcostdata(scip, level, graph, vars, propdata);
1504 
1505  propdata->redcostnupdates++;
1506  }
1507  }
1508 #endif
1509 
1510  propdata->lpobjval_last = propdata->lpobjval;
1511 }
1512 
1513 
1514 /** update the graph from propdata from given graph */
1515 static inline
1517  SCIP* scip, /**< SCIP data structure */
1518  const GRAPH* graph, /**< graph structure to use for the update */
1519  SCIP_PROPDATA* propdata /**< propagator data */
1520 )
1521 {
1522  GRAPH* propgraph = propdata->propgraph;
1523 
1524  assert(propgraph != NULL);
1525 
1526  graph_freeHistory(scip, propgraph);
1527  graph_freeHistoryDeep(scip, propgraph);
1528 
1529  SCIP_CALL( graph_copyData(scip, graph, propgraph) );
1530 
1531  propgraph->norgmodeledges = propgraph->edges;
1532  propgraph->norgmodelknots = propgraph->knots;
1533  propdata->propgraphnodenumber = SCIPnodeGetNumber(SCIPgetCurrentNode(scip));
1534 
1535  assert(!graph_pc_isRootedPcMw(graph) || graph_pc_nFixedTerms(graph) == graph_pc_nFixedTerms(propgraph));
1536 
1537  SCIP_CALL( graph_initHistory(scip, propdata->propgraph) );
1538 
1539  return SCIP_OKAY;
1540 }
1541 
1542 
1543 /** try to make global fixings based on lurking bounds */
1544 static
1546  SCIP* scip, /**< SCIP structure */
1547  const GRAPH* graph, /**< graph structure */
1548  SCIP_Real cutoffbound, /**< cutoff bound */
1549  SCIP_PROPDATA* propdata, /**< propagator data */
1550  SCIP_VAR** vars /**< variables */
1551 )
1552 {
1553  const SCIP_Real* fixingbounds = propdata->fixingbounds;
1554  const SCIP_Real* deg2bounds = propdata->deg2bounds;
1555  SCIP_Bool* deg2bounded = propdata->deg2bounded;
1556  const int nedges = graph->edges;
1557  const int nnodes = graph->knots;
1558 
1559  assert(fixingbounds != NULL && deg2bounds != NULL && deg2bounded != NULL);
1560 
1561  for( int e = 0; e < nedges; e++ )
1562  {
1563  if( SCIPisLT(scip, cutoffbound, fixingbounds[e]) )
1564  {
1565  SCIP_VAR* const edgevar = vars[e];
1566 
1567  if( SCIPvarGetLbGlobal(edgevar) < 0.5 && SCIPvarGetUbGlobal(edgevar) > 0.5 )
1568  {
1569  assert(SCIPisEQ(scip, SCIPvarGetUbGlobal(edgevar), 1.0));
1570 
1571  SCIPchgVarUbGlobal(scip, edgevar, 0.0);
1572  propdata->nfixededges_curr++;
1573  }
1574  }
1575  }
1576 
1577  for( int i = 0; i < nnodes; i++ )
1578  {
1579  if( SCIPisLT(scip, cutoffbound, deg2bounds[i]) && !Is_term(graph->term[i]) )
1580  deg2bounded[i] = TRUE;
1581  }
1582 
1583 #ifdef SCIP_DEBUG
1584  {
1585  int d2bounded = 0;
1586  for( int i = 0; i < nnodes; i++ )
1587  if( deg2bounded[i] )
1588  d2bounded++;
1589 
1590  printf("deg2bounded=%d \n", d2bounded);
1591 
1592  }
1593 #endif
1594 
1595  return SCIP_OKAY;
1596 }
1597 
1598 
1599 /** dual cost based fixing of variables */
1600 static
1602  SCIP* scip, /**< SCIP data structure */
1603  SCIP_VAR** vars, /**< variables */
1604  SCIP_PROPDATA* propdata, /**< propagator data */
1605  GRAPH* graph, /**< graph data structure */
1606  SCIP_Bool* probisinfeas /**< is problem infeasible? */
1607 )
1608 {
1609  PATH* vnoi;
1610  SCIP_Real* redcost;
1611  SCIP_Real* pathdist;
1612  const SCIP_Real lpobjval = propdata->lpobjval;
1613  const SCIP_Real cutoffbound = getCutoffbound(scip, lpobjval);
1614  const SCIP_Real cutoffgap = cutoffbound - lpobjval;
1615  int* vbase;
1616  int* state;
1617  int* termorg = NULL;
1618  const int nedges = graph->edges;
1619  const int nnodes = graph->knots;
1620 
1621  assert(FALSE == *probisinfeas);
1622  // printf("minpathcost=%f \n", minpathcost);
1623 
1624  if( SCIPisLT(scip, cutoffgap, 0.0) )
1625  {
1626  SCIPdebugMessage("infeasible sub-problem! \n");
1627  *probisinfeas = TRUE;
1628  return SCIP_OKAY;
1629  }
1630 
1631  if( propdata->fixingbounds == NULL )
1632  {
1633  assert(propdata->deg2bounds == NULL && propdata->deg2bounded == NULL);
1634 
1635  SCIP_CALL( SCIPallocMemoryArray(scip, &(propdata->deg2bounds), nnodes) );
1636  SCIP_CALL( SCIPallocMemoryArray(scip, &(propdata->deg2bounded), nnodes) );
1637  SCIP_CALL( SCIPallocMemoryArray(scip, &(propdata->fixingbounds), nedges) );
1638 
1639  for( int i = 0; i < nedges; i++ )
1640  propdata->fixingbounds[i] = -FARAWAY;
1641 
1642  for( int i = 0; i < nnodes; i++ )
1643  {
1644  propdata->deg2bounds[i] = -FARAWAY;
1645  propdata->deg2bounded[i] = FALSE;
1646  }
1647 
1648 #ifndef WITH_UG
1649  /* first call, so we can also fix incoming arcs of root to zero */
1650  for( int e = graph->inpbeg[graph->source]; e != EAT_LAST; e = graph->ieat[e] )
1651  SCIP_CALL( fixEdgeVar(scip, e, vars, propdata) );
1652 #endif
1653  }
1654 
1655 #ifdef WITH_UG
1656  if( !redcosts_forLPareReliable(scip, vars, graph) )
1657  {
1658  graph_mark(graph);
1659  return SCIP_OKAY;
1660  }
1661 #endif
1662 
1663  SCIP_CALL( SCIPallocBufferArray(scip, &state, 2 * nnodes) );
1664  SCIP_CALL( SCIPallocBufferArray(scip, &vbase, 2 * nnodes) );
1665  SCIP_CALL( SCIPallocBufferArray(scip, &vnoi, 2 * nnodes) );
1666  SCIP_CALL( SCIPallocBufferArray(scip, &redcost, nedges) );
1667  SCIP_CALL( SCIPallocBufferArray(scip, &pathdist, nnodes) );
1668 
1669  if( SCIPgetDepth(scip) > 0 && SCIPStpBranchruleIsActive(scip) )
1670  {
1671  int* nodestatenew;
1672  SCIP_Bool conflict = FALSE;
1673 
1674  SCIP_CALL( SCIPallocBufferArray(scip, &termorg, nnodes) );
1675  SCIP_CALL( SCIPallocBufferArray(scip, &nodestatenew, nnodes) );
1676 
1677  BMScopyMemoryArray(termorg, graph->term, nnodes);
1678  SCIPStpBranchruleInitNodeState(graph, nodestatenew);
1679  SCIP_CALL( SCIPStpBranchruleGetVertexChgs(scip, nodestatenew, &conflict) );
1680  assert(!conflict);
1681 
1682  for( int k = 0; k < nnodes; k++ )
1683  {
1684  if( nodestatenew[k] == BRANCH_STP_VERTEX_TERM && !Is_term(graph->term[k]) )
1685  graph_knot_chg(graph, k, STP_TERM);
1686 
1687  }
1688 
1689  SCIPfreeBufferArray(scip, &nodestatenew);
1690  }
1691 
1692  graph_mark(graph);
1693 
1694  redcosts_forLPget(scip, vars, graph, redcost);
1695  SCIP_CALL( getRedCost2ndNextDistances(scip, redcost, graph, vnoi, pathdist, vbase, state) );
1696 
1697  for( int k = 0; k < nnodes; k++ )
1698  {
1699  if( !Is_term(graph->term[k]) && SCIPisGT(scip, pathdist[k] + vnoi[k].dist, cutoffgap) )
1700  {
1701  for( int e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
1702  {
1703  /* try to fix edge and reversed one */
1704  SCIP_CALL( fixEdgeVar(scip, e, vars, propdata) );
1705  SCIP_CALL( fixEdgeVar(scip, flipedge(e), vars, propdata) );
1706  }
1707  }
1708  else
1709  {
1710  for( int e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
1711  {
1712  if( SCIPisGT(scip, pathdist[k] + redcost[e] + vnoi[graph->head[e]].dist, cutoffgap) )
1713  SCIP_CALL( fixEdgeVar(scip, e, vars, propdata) );
1714  }
1715  }
1716  }
1717 
1718  if( termorg )
1719  {
1720  for( int k = 0; k < nnodes; k++ )
1721  {
1722  if( graph->term[k] != termorg[k] )
1723  graph_knot_chg(graph, k, termorg[k]);
1724  }
1725  SCIPfreeBufferArray(scip, &termorg);
1726  }
1727 
1728  /* at root? */
1729  if( SCIPgetDepth(scip) == 0 )
1730  {
1731  updateEdgeLurkingBounds(graph, redcost, pathdist, vnoi, lpobjval, propdata->fixingbounds);
1732  updateDeg2LurkingBounds(graph, pathdist, vnoi, lpobjval, propdata->deg2bounds);
1733  }
1734 
1735  SCIP_CALL( fixVarsDualcostLurking(scip, graph, cutoffbound, propdata, vars) );
1736 
1737  SCIPfreeBufferArray(scip, &pathdist);
1738  SCIPfreeBufferArray(scip, &redcost);
1739  SCIPfreeBufferArray(scip, &vnoi);
1740  SCIPfreeBufferArray(scip, &state);
1741  SCIPfreeBufferArray(scip, &vbase);
1742 
1743  return SCIP_OKAY;
1744 }
1745 
1746 
1747 /** extended reduced cost reduction */
1748 static
1750  SCIP* scip, /**< SCIP data structure */
1751  const GRAPH* graph, /**< original graph data structure */
1752  SCIP_VAR** vars, /**< variables */
1753  SCIP_PROPDATA* propdata /**< propagator data */
1754  )
1755 {
1756  REDCOST* const redcostdata = propdata->redcostdata;
1757  GRAPH* const propgraph = propdata->propgraph;
1758  STP_Bool* arcdeleted = NULL;
1759  int nfixededges = 0;
1760  const int nedges = propgraph->edges;
1761  const SCIP_Bool isPcMw = graph_pc_isPcMw(propgraph);
1762 #ifdef USE_EXTRED_FULL
1763  const SCIP_Real cutoffbound = getCutoffbound(scip, propdata->lpobjval);
1764 #endif
1765 
1766  assert(redcostdata);
1767 
1768  /* in this case the reduced cost reductions are not valid anymore! (because the root has changed) */
1769  if( graph->stp_type != propgraph->stp_type )
1770  {
1771  assert(graph_pc_isRootedPcMw(propgraph));
1772  return SCIP_OKAY;
1773  }
1774 #ifdef WITH_UG
1775  return SCIP_OKAY;
1776 #endif
1777 
1778  SCIP_CALL( SCIPallocBufferArray(scip, &arcdeleted, nedges) );
1779  mark0FixedArcs(graph, vars, arcdeleted);
1780 
1781  graph_mark(propgraph);
1782 
1783  if( isPcMw )
1784  graph_pc_2org(scip, propgraph);
1785 #ifdef USE_EXTRED_FULL
1786  SCIPdebugMessage("starting extended reductions with %d red. cost levels \n", redcosts_getNlevels(redcostdata));
1787 
1788  for( int i = 0; i < redcosts_getNlevels(redcostdata); i++ )
1789  {
1790  redcosts_setCutoffFromBound(cutoffbound, i, redcostdata);
1791 
1792  redcosts_increaseOnDeletedArcs(propgraph, arcdeleted, i, redcostdata);
1793 
1794  redcosts_unifyBlockedEdgeCosts(propgraph, i, redcostdata);
1795 
1796  SCIP_CALL( redcosts_initializeDistances(scip, i, propgraph, redcostdata) );
1797 
1798  SCIPdebugMessage("cutoff for level %d: %f \n", i, redcosts_getCutoff(redcostdata, i));
1799  }
1800 
1801  /* Note that all in-root arcs will be set to 0! (w.r.t redCostRoot) */
1802  /* reduce graph and mark deletable arcs */
1803  SCIP_CALL( extreduce_deleteArcs(scip, redcostdata, NULL, propgraph,
1804  arcdeleted, &nfixededges) );
1805 #else
1806  writeRedcostdata(scip, 0, graph, vars, propdata);
1807  redcosts_increaseOnDeletedArcs(propgraph, arcdeleted, 0, redcostdata);
1808  SCIP_CALL( redcosts_initializeDistances(scip, 0, propgraph, redcostdata) );
1809 
1810  nfixededges = reduce_extendedEdge(scip, propgraph, redcosts_getNodeToTermsPathsTop(redcostdata),
1811  redcosts_getEdgeCostsTop(redcostdata), redcosts_getRootToNodeDistTop(redcostdata),
1812  NULL, redcosts_getCutoffTop(redcostdata), propgraph->source, arcdeleted, TRUE);
1813 #endif
1814 
1815  if( isPcMw )
1816  graph_pc_2trans(scip, propgraph);
1817 
1818  SCIPdebugMessage("extended-reduction graph deletions: %d \n", nfixededges);
1819 
1820  for( int e = 0; e < nedges; e++ )
1821  {
1822  if( SCIPvarGetUbLocal(vars[e]) > 0.5 && arcdeleted[e] )
1823  {
1824  if( isPcMw && graph_pc_edgeIsExtended(propgraph, e) )
1825  continue;
1826 
1827  SCIPdebugMessage("fix edge %d to 0 \n", e);
1828 
1829  SCIP_CALL(fixEdgeVar(scip, e, vars, propdata));
1830  }
1831  }
1832 
1833  SCIPdebugMessage("after extended-reduction number of fixed variables: %d \n", propdata->nfixededges_curr);
1834 
1835  SCIPfreeBufferArray(scip, &arcdeleted);
1836 
1837  assert(nfixededges >= 0);
1838 
1839  return SCIP_OKAY;
1840 }
1841 
1842 
1843 /** This methods tries to fix edges by performing reductions on the current graph.
1844  * To this end, the already 0-fixed edges are (temporarily) removed from the underlying graph to strengthen the reduction methods. */
1845 static
1847  SCIP* scip, /**< SCIP data structure */
1848  const GRAPH* graph, /**< graph data structure */
1849  SCIP_VAR** vars, /**< variables */
1850  SCIP_PROPDATA* propdata, /**< propagator data */
1851  SCIP_Bool* probisinfeas /**< is problem infeasible? */
1852  )
1853 {
1854  REDSOL* redsol;
1855  GRAPH* propgraph = NULL;
1856  int* nodestate = NULL;
1857  int* edgestate = NULL;
1858  SCIP_Real offset = -1.0; /* don't use it for pcmw! */
1859  const int nnodes = graph_get_nNodes(graph);
1860  const int nedges = graph_get_nEdges(graph);
1861  SCIP_Bool error;
1862 
1863  assert(propdata && scip && vars && probisinfeas);
1864  assert(!graph_pc_isPcMw(graph) || graph->extended);
1865 
1866  SCIPdebugMessage("start redbasedVarfixing, fixings: %d \n", propdata->nfixededges_curr);
1867 
1868  *probisinfeas = FALSE;
1869 
1870  SCIP_CALL( SCIPallocBufferArray(scip, &nodestate, nnodes) );
1871  SCIP_CALL( SCIPallocBufferArray(scip, &edgestate, nedges) );
1872 
1873  SCIP_CALL( updatePropgraph(scip, graph, propdata) );
1874  propgraph = propdata->propgraph;
1875 
1876  /* note: graph type might change (from PC/MW to RPC/RMW) */
1877  SCIP_CALL( propgraphApplyBoundchanges(scip, vars, graph, nodestate, edgestate, propdata, probisinfeas,
1878  &offset ) );
1879 
1880  if( *probisinfeas )
1881  {
1882  SCIPdebugMessage("problem has become infeasible after applying bound changes: terminating! \n");
1883  goto TERMINATE;
1884  }
1885 
1886  /* remove unconnected vertices and edges */
1887  SCIP_CALL( propgraphPruneUnconnected(scip, propgraph, probisinfeas, &offset ) );
1888 
1889  if( *probisinfeas )
1890  {
1891  SCIPdebugMessage("problem has become infeasible after pruning (terminals not connected): terminating! \n");
1892  goto TERMINATE;
1893  }
1894 
1895  assert(graph_valid(scip, propgraph));
1896 
1897  /* start with extended reductions based on reduced costs of LP */
1898  if( !graph_pc_isMw(propgraph) )
1899  {
1900  SCIP_CALL( fixVarsExtendedRed(scip, graph, vars, propdata) );
1901  }
1902 
1903  SCIP_CALL( reduce_solInit(scip, propgraph, FALSE, &redsol) );
1904 
1905  /* now reduce the graph by standard reductions */
1906  if( graph_pc_isPc(propgraph) )
1907  {
1908  SCIP_CALL( reduce_pc(scip, redsol, propgraph, 2, FALSE, FALSE, FALSE, FALSE) );
1909  }
1910  else if( graph_pc_isMw(propgraph) )
1911  {
1912  SCIPdebugMessage("starting MW reductions \n");
1913  SCIP_CALL( reduce_mw(scip, redsol, propgraph, 2, FALSE, FALSE, FALSE) );
1914  }
1915  else
1916  {
1917 
1918 #ifdef SCIP_DISABLED
1919  {
1920  DISTDATA* distdata;
1921  EXTPERMA* extpermanent;
1922  REDCOST* redcostdata = propdata->redcostdata;
1923  const SCIP_Real cutoffbound = getCutoffbound(scip, propdata->lpobjval);
1924 
1925  int ndeleted;
1926 
1927 
1928  for( int i = 0; i < redcosts_getNlevels(redcostdata); i++ )
1929  {
1930  redcosts_setCutoffFromBound(cutoffbound, i, redcostdata);
1931 
1932 // redcosts_increaseOnDeletedArcs(propgraph, arcdeleted, i, redcostdata);
1933 
1934  redcosts_unifyBlockedEdgeCosts(propgraph, i, redcostdata);
1935 
1936  SCIP_CALL( redcosts_initializeDistances(scip, i, propgraph, redcostdata) );
1937 
1938  SCIPdebugMessage("cutoff for level %d: %f \n", i, redcosts_getCutoff(redcostdata, i));
1939  }
1940 
1941  SCIP_CALL( graph_init_dcsr(scip, propgraph) );
1942  SCIP_CALL( extreduce_distDataInit(scip, propgraph, 40, TRUE, FALSE, &distdata) );
1943  SCIP_CALL( extreduce_extPermaInit(scip, extred_fast, propgraph, NULL, &extpermanent) );
1944 
1945  assert(!extpermanent->distdata_default);
1946 
1947  extpermanent->distdata_default = distdata;
1948  extpermanent->redcostdata = propdata->redcostdata;
1949  extpermanent->redcostEqualAllow = FALSE;
1950 
1951  SCIP_CALL( extreduce_pseudoDeleteNodes(scip, propdata->deg2bounded, extpermanent, propgraph, NULL, &ndeleted) );
1952 
1953  /* clean up */
1954  extreduce_distDataFree(scip, propgraph, &distdata);
1955 
1956  if( extpermanent->distdata_biased )
1957  extreduce_distDataFree(scip, propgraph, &(extpermanent->distdata_biased));
1958 
1959  extreduce_extPermaFree(scip, &extpermanent);
1960 
1961  printf("ndeleted=%d \n", ndeleted);
1962 
1963  graph_free_dcsr(scip, propgraph);
1964  }
1965 #endif
1966 
1967  // todo Call two times, and with node-replacing!
1968  // todo: before make all the node replacements from lurking bounds!
1969  assert(graph_typeIsSpgLike(propgraph));
1970  SCIP_CALL( reduce_unconnected(scip, propgraph) );
1971  SCIP_CALL( reduce_stp(scip, propgraph, redsol, 2, FALSE, FALSE, FALSE, FALSE) );
1972 
1973  // SCIP_CALL( reduceStp(scip, propgraph, redsol, 2, FALSE, TRUE, FALSE) );
1974 
1975  }
1976  offset += reduce_solGetOffset(redsol);
1977  reduce_solFree(scip, &redsol);
1978 
1979  assert(graph_valid(scip, propgraph));
1980 
1981  /* mark surviving original edges of propgraph reductions in array 'edgestate' */
1982  if( graph_pc_isPcMw(propgraph) )
1983  {
1984  updateEdgestateFromRedPcmw(scip, graph, propgraph, vars, nodestate, edgestate, &error);
1985  }
1986  else
1987  {
1988  updateEdgestateFromRed(graph, propgraph, vars, nodestate, edgestate, &error);
1989  }
1990 
1991  if( error )
1992  {
1993  return SCIP_ERROR; // todo check! is terminating enough?
1994  }
1995 
1996  SCIP_CALL( applyEdgestateToProb(scip, graph, vars, edgestate, propdata) );
1997 
1998  SCIPdebugMessage("number of reduction-based variable fixings: %d \n", propdata->nfixededges_curr);
1999 
2000 TERMINATE:
2001  graph_path_exit(scip, propgraph);
2002  SCIPfreeBufferArray(scip, &edgestate);
2003  SCIPfreeBufferArray(scip, &nodestate);
2004 
2005  return SCIP_OKAY;
2006 }
2007 
2008 
2009 
2010 /** promising? */
2011 static
2013  SCIP* scip, /**< SCIP data structure */
2014  const GRAPH* graph, /**< graph data structure */
2015  SCIP_VAR** vars, /**< variables */
2016  SCIP_PROPDATA* propdata /**< propagator data */
2017  )
2018 {
2019  SCIP_Bool callreduce = FALSE;
2020 
2021  assert(scip && graph && vars && propdata);
2022 
2023  if( graph_typeIsSpgLike(graph) || (graph_pc_isPcMw(graph) && graph->stp_type != STP_BRMWCSP) )
2024  {
2025  /* in the tree? */
2026  if( SCIPgetDepth(scip) > 0 )
2027  {
2028  SCIP_NODE* const currnode = SCIPgetCurrentNode(scip);
2029  const SCIP_Longint nodenumber = SCIPnodeGetNumber(currnode);
2030 
2031  if( nodenumber != propdata->lastnodenumber_red || propdata->aggressive )
2032  {
2033  propdata->lastnodenumber_red = nodenumber;
2034  callreduce = TRUE;
2035  }
2036  }
2037  /* at root (== 0 is necessary, could be -1) */
2038  else if( SCIPgetDepth(scip) == 0 )
2039  {
2040  const SCIP_Real redratio = (2.0 * (SCIP_Real) propdata->nfixededges_bipost) / ((SCIP_Real) graph->edges);
2041 
2042  assert(GE(propdata->redwaitratio, REDUCTION_WAIT_RATIO_INITIAL));
2043 
2044  if( useRedcostdata(graph) )
2045  updateRedcostdata(scip, graph, vars, propdata);
2046 
2047  if( SCIPisGT(scip, redratio, propdata->redwaitratio) || propdata->redcostnupdates == PROP_STP_REDCOST_LEVELS )
2048  {
2049  callreduce = TRUE;
2050  propdata->redwaitratio *= REDUCTION_WAIT_FACTOR;
2051  }
2052  }
2053 
2054 #ifdef WITH_UG
2055  if( propdata->ncalls == 1 && SCIPgetDepth(scip) == 0 )
2056  {
2057  SCIPdebugMessage("trigger UG root reductions \n");
2058  callreduce = TRUE;
2059  }
2060 #endif
2061  }
2062 
2063  return callreduce;
2064 }
2065 
2066 /** block edges of the underlying graphs by using global fixings */
2067 static inline
2069  SCIP* scip, /**< SCIP data structure */
2070  SCIP_VAR** vars, /**< variables */
2071  GRAPH* graph /**< graph data structure */
2072 )
2073 {
2074  const int nedges = graph_get_nEdges(graph);
2075 
2076  assert(vars && scip);
2077 
2078  if( !graph_typeIsSpgLike(graph) && !graph_pc_isPc(graph) && graph->stp_type != STP_DCSTP )
2079  {
2080  return;
2081  }
2082 
2083  for( int e = 0; e < nedges; e += 2 )
2084  {
2085  const int erev = e + 1;
2086 
2087  /* both e and its anti-parallel edge fixed to zero? */
2088  if( SCIPvarGetUbGlobal(vars[e]) < 0.5 && SCIPvarGetUbGlobal(vars[erev]) < 0.5 && LT(graph->cost[e], BLOCKED) )
2089  {
2090  assert(SCIPvarGetLbLocal(vars[e]) < 0.5 && SCIPvarGetLbLocal(vars[erev]) < 0.5);
2091 
2092  // todo for pc/rpc can we maybe also block edges with unequal costs? Seems to lead to bugs so far...
2093  if( EQ(graph->cost[e], graph->cost[erev]) )
2094  {
2095  graph->cost[e] = BLOCKED;
2096  graph->cost[erev] = BLOCKED;
2097  }
2098  }
2099  }
2100 }
2101 
2102 
2103 /** initializes for first call */
2104 static
2106  SCIP* scip, /**< SCIP data structure */
2107  const GRAPH* graph, /**< graph structure to use for the update */
2108  SCIP_VAR** vars, /**< variables */
2109  SCIP_PROPDATA* propdata /**< propagator data */
2110 )
2111 {
2112  assert(scip && graph && vars && propdata);
2113 
2114  if( graph_typeIsSpgLike(graph) || (graph_pc_isPcMw(graph) && graph->stp_type != STP_BRMWCSP) )
2115  {
2116  if( !propdata->propgraph )
2117  {
2118  assert(!propdata->isInitialized);
2119 
2120  SCIP_CALL( initPropgraph(scip, graph, propdata) );
2121 
2122  assert(propdata->propgraph);
2123  }
2124 
2125  if( !propdata->isInitialized && useRedcostdata(graph) )
2126  {
2127  SCIP_CALL( initRedcostdata(scip, graph, vars, propdata) );
2128  }
2129  }
2130 
2131  if( !propdata->isInitialized && graph->stp_type == STP_DCSTP )
2132  {
2133  const int nnodes = graph_get_nNodes(graph);
2134 
2135  assert(graph->maxdeg);
2136 
2137  for( int k = 0; k < nnodes; k++ )
2138  {
2139  if( graph->maxdeg[k] != 1 )
2140  continue;
2141 
2142  if( !Is_term(graph->term[k]) || k == graph->source )
2143  continue;
2144 
2145  for( int e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
2146  {
2147  if( SCIPvarGetUbLocal(vars[e]) > 0.5 )
2148  {
2149  assert(SCIPvarGetLbLocal(vars[e]) < 0.5);
2150  SCIP_CALL( SCIPchgVarUb(scip, vars[e], 0.0) );
2151  }
2152  }
2153  }
2154  }
2155 
2156  propdata->isInitialized = TRUE;
2157 
2158  return SCIP_OKAY;
2159 }
2160 
2161 
2162 
2163 /** applies vertex branching changes.
2164  * NOTE: this is necessary, because SCIP is crazy slow in propagating constraints,
2165  * so we do it ourselves */
2166 static
2168  SCIP* scip, /**< SCIP data structure */
2169  const GRAPH* graph, /**< graph structure to use for the update */
2170  SCIP_VAR** vars, /**< variables */
2171  SCIP_PROPDATA* propdata /**< propagator data */
2172 )
2173 {
2174  assert(SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) > 0);
2175 
2176  if( SCIPStpBranchruleIsActive(scip) )
2177  {
2178  int branchvertex;
2179  SCIP_Bool isDeleted = FALSE;
2180  SCIP_CALL( SCIPStpBranchruleGetVertexChgLast(scip, &branchvertex, &isDeleted) );
2181 
2182  if( isDeleted )
2183  {
2184  for( int e = graph->outbeg[branchvertex]; e != EAT_LAST; e = graph->oeat[e] )
2185  {
2186  SCIP_CALL( fixEdgeVar(scip, e, vars, propdata) );
2187  SCIP_CALL( fixEdgeVar(scip, flipedge(e), vars, propdata) );
2188  }
2189  }
2190  }
2191 
2192  return SCIP_OKAY;
2193 }
2194 
2195 
2196 /**@} */
2197 
2198 /**@name Callback methods of propagator
2199  *
2200  * @{
2201  */
2202 
2203 /** copy method for propagator plugins (called when SCIP copies plugins) */
2204 static
2206 { /*lint --e{715}*/
2207  assert(scip != NULL);
2208  assert(prop != NULL);
2209  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2210 
2211  /* call inclusion method of constraint handler */
2212  SCIP_CALL( SCIPincludePropStp(scip) );
2213 
2214  return SCIP_OKAY;
2215 }
2216 
2217 
2218 /** destructor of propagator to free user data (called when SCIP is exiting) */
2219 static
2221 { /*lint --e{715}*/
2222  SCIP_PROPDATA* propdata;
2223 
2224  /* free propagator data */
2225  propdata = SCIPpropGetData(prop);
2226  assert(propdata != NULL);
2227 
2228  SCIPfreeRandom(scip, &propdata->randnumgen);
2229 
2230  SCIPfreeMemory(scip, &propdata);
2231 
2232  SCIPpropSetData(prop, NULL);
2233 
2234  return SCIP_OKAY;
2235 }
2236 
2237 
2238 /** reduced cost propagation method for an LP solution */
2239 static
2241 { /*lint --e{715}*/
2242  SCIP_PROPDATA* propdata;
2243  SCIP_PROBDATA* probdata;
2244  SCIP_VAR** vars;
2245  GRAPH* graph;
2246  SCIP_Bool probisinfeas = FALSE;
2247  SCIP_NODE* currnode;
2248 
2249  *result = SCIP_DIDNOTRUN;
2250 
2251  /* propagator can only be applied during solving stage */
2252  if( SCIPgetStage(scip) < SCIP_STAGE_SOLVING )
2253  return SCIP_OKAY;
2254 
2255  probdata = SCIPgetProbData(scip);
2256  assert(probdata != NULL);
2257 
2258  vars = SCIPprobdataGetVars(scip);
2259  assert(vars);
2260 
2261  propdata = SCIPpropGetData(prop);
2262  graph = SCIPprobdataGetGraph(probdata);
2263  assert(graph);
2264 
2265  currnode = SCIPgetCurrentNode(scip);
2266 
2267  if( SCIPnodeGetDepth(currnode) > 0 && propdata->lastnodenumber != SCIPnodeGetNumber(currnode) )
2268  {
2269  /* propagate based on last vertex branching decision */
2270  SCIP_CALL( applyLastVertexBranch(scip, graph, vars, propdata) );
2271 
2272  SCIP_CALL( SCIPStpPropCheckForInfeas(scip, &probisinfeas) );
2273 
2274  propdata->lastnodenumber = SCIPnodeGetNumber(currnode);
2275  }
2276 
2277  if( probisinfeas )
2278  {
2279  *result = SCIP_CUTOFF;
2280  return SCIP_OKAY;
2281  }
2282 
2283  /* check if all integral variables are fixed */
2284  if( SCIPgetNPseudoBranchCands(scip) == 0 )
2285  return SCIP_OKAY;
2286 
2287  if( !redcosts_forLPareAvailable(scip) )
2288  return SCIP_OKAY;
2289 
2290  propdata->ncalls++;
2291 
2292  if( propdata->nfails > 0 && (propdata->nlastcall + propdata->maxnwaitrounds >= propdata->ncalls)
2293  && (propdata->nlastcall + propdata->nfails > propdata->ncalls) )
2294  return SCIP_OKAY;
2295 
2296  /* new LP needs to have been solved to avoid conflicts between reduction based and red. cost propagation */
2297  if( propdata->nlastnlpiter == SCIPgetNLPIterations(scip) )
2298  return SCIP_OKAY;
2299 
2300  propdata->nlastnlpiter = SCIPgetNLPIterations(scip);
2301  propdata->nlastcall = propdata->ncalls;
2302 
2303  propdata->nfixededges_curr = 0;
2304  propdata->nfixededges_bicurr = 0;
2305  *result = SCIP_DIDNOTFIND;
2306 
2307  propdata->lpobjval = SCIPgetLPObjval(scip);
2308 
2309  SCIP_CALL( initPropAtFirstCall(scip, graph, vars, propdata) );
2310 
2311  /* call dual cost based variable fixing */
2312  SCIP_CALL( fixVarsDualcost(scip, vars, propdata, graph, &probisinfeas) );
2313 
2314  if( !probisinfeas && fixVarsRedbasedIsPromising(scip, graph, vars, propdata) )
2315  {
2316  assert(!probisinfeas);
2317  SCIPdebugMessage("use reduction techniques \n");
2318 
2319  /* call reduced cost based based variable fixing */
2320  SCIP_CALL( fixVarsRedbased(scip, graph, vars, propdata, &probisinfeas) );
2321 
2322  propdata->nfixededges_bipost = 0;
2323  }
2324 
2325  if( probisinfeas )
2326  {
2327  *result = SCIP_CUTOFF;
2328  return SCIP_OKAY;
2329  }
2330 
2331  if( propdata->nfixededges_curr > 0 )
2332  {
2333  SCIPdebugMessage("newly fixed by STP propagator: %d of (%d) \n", propdata->nfixededges_curr, propdata->nfixededges_all);
2334 
2335  propdata->nfails = 0;
2336  propdata->nfixededges_all += propdata->nfixededges_curr;
2337  propdata->nfixededges_bipost += propdata->nfixededges_bicurr;
2338 
2339  *result = SCIP_REDUCEDDOM;
2340 
2341  /* translate the global fixings of variables into blocking of graph edges */
2342  blockEdgesWithGlobalFixings(scip, vars, graph);
2343  }
2344  else
2345  {
2346  propdata->nfails++;
2347  }
2348 
2349  return SCIP_OKAY;
2350 }
2351 
2352 /** solving process initialization method of propagator (called when branch and bound process is about to begin) */
2353 static
2354 SCIP_DECL_PROPINITSOL(propInitsolStp)
2355 { /*lint --e{715}*/
2356  SCIP_PROPDATA* propdata;
2357 
2358  propdata = SCIPpropGetData(prop);
2359  assert(propdata != NULL);
2360 
2361  propdata->nfails = 0;
2362  propdata->ncalls = 0;
2363  propdata->nlastcall = 0;
2364  propdata->nlastnlpiter = 0;
2365  propdata->lastnodenumber_red = -1;
2366  propdata->lastnodenumber = -1;
2367  propdata->nfixededges_all = 0;
2368  propdata->redwaitratio = REDUCTION_WAIT_RATIO_INITIAL;
2369  propdata->nfixededges_curr = 0;
2370  propdata->nfixededges_bicurr = 0;
2371  propdata->nfixededges_bipost = 0;
2372  propdata->fixingbounds = NULL;
2373  propdata->deg2bounded = NULL;
2374  propdata->deg2bounds = NULL;
2375  propdata->propgraph = NULL;
2376  propdata->redcostdata = NULL;
2377  propdata->redcostnupdates = 0;
2378  propdata->propgraphnodenumber = -1;
2379  propdata->lpobjval = -1.0;
2380  propdata->lpobjval_last = -1.0;
2381  propdata->isInitialized = FALSE;
2382 
2383  return SCIP_OKAY;
2384 }
2385 
2386 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
2387 static
2388 SCIP_DECL_PROPEXITSOL(propExitsolStp)
2389 { /*lint --e{715}*/
2390  SCIP_PROPDATA* propdata;
2391 
2392  /* free propagator data */
2393  propdata = SCIPpropGetData(prop);
2394  assert(propdata != NULL);
2395 
2396  SCIPfreeMemoryArrayNull(scip, &(propdata->fixingbounds));
2397  SCIPfreeMemoryArrayNull(scip, &(propdata->deg2bounded));
2398  SCIPfreeMemoryArrayNull(scip, &(propdata->deg2bounds));
2399 
2400  if( propdata->propgraph )
2401  graph_free(scip, &(propdata->propgraph), TRUE);
2402 
2403  if( propdata->redcostdata )
2404  redcosts_free(scip, &(propdata->redcostdata));
2405 
2406  return SCIP_OKAY;
2407 }
2408 
2409 
2410 /**@} */
2411 
2412 /**@name Interface methods
2413  *
2414  * @{
2415  */
2416 
2417 
2418 /** fix a variable (corresponding to an edge) to 0 */
2420  SCIP* scip, /**< SCIP data structure */
2421  SCIP_VAR* edgevar, /**< the variable to be fixed */
2422  SCIP_Bool* success /**< could variable be fixed? */
2423  )
2424 {
2425  assert(scip && edgevar && success);
2426 
2427  /* not fixed yet? */
2428  if( SCIPvarGetLbLocal(edgevar) < 0.5 && SCIPvarGetUbLocal(edgevar) > 0.5 )
2429  {
2430  SCIP_CALL( SCIPchgVarUb(scip, edgevar, 0.0) );
2431  *success = TRUE;
2432  }
2433  else
2434  {
2435  *success = FALSE;
2436  }
2437 
2438  return SCIP_OKAY;
2439 }
2440 
2441 
2442 /** fix a variable (corresponding to an edge) to 1 */
2444  SCIP* scip, /**< SCIP data structure */
2445  SCIP_VAR* edgevar, /**< the variable to be fixed */
2446  SCIP_Bool* success /**< could variable be fixed? */
2447  )
2448 {
2449  assert(scip && edgevar && success);
2450 
2451  /* not fixed yet? */
2452  if( SCIPvarGetLbLocal(edgevar) < 0.5 && SCIPvarGetUbLocal(edgevar) > 0.5 )
2453  {
2454  SCIP_CALL( SCIPchgVarLb(scip, edgevar, 1.0) );
2455  *success = TRUE;
2456  }
2457  else
2458  {
2459  *success = FALSE;
2460  }
2461 
2462  return SCIP_OKAY;
2463 }
2464 
2465 
2466 /** return total number of arcs fixed by 'fixedgevar' method of this propagator */
2468  SCIP* scip /**< SCIP data structure */
2469  )
2470 {
2471  SCIP_PROPDATA* propdata;
2472 
2473  assert(scip != NULL);
2474 
2475  /* get propagator data */
2476  assert(SCIPfindProp(scip, "stp") != NULL);
2477  propdata = SCIPpropGetData(SCIPfindProp(scip, "stp"));
2478 
2479  assert(propdata != NULL);
2480 
2481  return (propdata->nfixededges_all);
2482 }
2483 
2484 
2485 /** checks whether problem has become infeasible at current node
2486  * NOTE: we basically check whether all terminals (at given B&B node) are reachable from root,
2487  * taking bound changes into account */
2489  SCIP* scip, /**< SCIP data structure */
2490  SCIP_Bool* probisinfeas /**< is infeasible? */
2491 )
2492 {
2493  const GRAPH* orggraph = SCIPprobdataGetGraph2(scip);
2494  int* nodestate;
2495  int* edgestate;
2496  const int nnodes = graph_get_nNodes(orggraph);
2497  const int nedges = graph_get_nEdges(orggraph);
2498 
2499  assert(probisinfeas && orggraph);
2500 
2501  *probisinfeas = FALSE;
2502 
2503  SCIP_CALL( SCIPallocBufferArray(scip, &nodestate, nnodes) );
2504  SCIP_CALL( SCIPallocBufferArray(scip, &edgestate, nedges) );
2505 
2506  SCIP_CALL( getGraphStatesDirected(scip, orggraph, nodestate, edgestate, probisinfeas) );
2507 
2508  if( *probisinfeas == FALSE )
2509  {
2510  SCIP_CALL( trailGraphWithStates(scip, orggraph, nodestate, edgestate, probisinfeas) );
2511  }
2512 
2513  SCIPfreeBufferArray(scip, &edgestate);
2514  SCIPfreeBufferArray(scip, &nodestate);
2515 
2516  return SCIP_OKAY;
2517 }
2518 
2519 
2520 /** gives propagator graph */
2522  SCIP* scip, /**< SCIP data structure */
2523  GRAPH** graph, /**< graph data */
2524  SCIP_Longint* graphnodenumber, /**< point to b&b node for which graph is valid */
2525  SCIP_Bool* probisinfeas, /**< infeasible problem? */
2526  SCIP_Real* offset /**< needed for PC/MW */
2527  )
2528 {
2529  SCIP_PROPDATA* propdata = SCIPpropGetData(SCIPfindProp(scip, "stp"));
2530  SCIP_VAR** vars = SCIPprobdataGetVars(scip);
2531  const GRAPH* orggraph = SCIPprobdataGetGraph2(scip);
2532  int* nodestate ;
2533  int* edgestate;
2534  const int nnodes = graph_get_nNodes(orggraph);
2535  const int nedges = graph_get_nEdges(orggraph);
2536 
2537  assert(probisinfeas && offset);
2538  assert(vars && orggraph && propdata);
2539 
2540  *probisinfeas = FALSE;
2541  *graphnodenumber = -1;
2542  *graph = NULL;
2543 
2544  SCIP_CALL( SCIPallocBufferArray(scip, &nodestate, nnodes) );
2545  SCIP_CALL( SCIPallocBufferArray(scip, &edgestate, nedges) );
2546 
2547  if( !propdata->propgraph )
2548  {
2549  SCIP_CALL( initPropgraph(scip, orggraph, propdata) );
2550  }
2551  else
2552  {
2553  SCIP_CALL( updatePropgraph(scip, orggraph, propdata) );
2554  }
2555 
2556  assert(propdata->propgraph);
2557 
2558  /* note: graph type might change (from PC/MW to RPC/RMW) */
2559  SCIP_CALL( propgraphApplyBoundchanges(scip, vars, orggraph, nodestate, edgestate, propdata, probisinfeas,
2560  offset ) );
2561 
2562  if( *probisinfeas )
2563  {
2564  SCIPdebugMessage("problem has become infeasible after applying bound changes: terminating! \n");
2565  *probisinfeas = TRUE;
2566  }
2567  else
2568  {
2569  SCIP_CALL( propgraphPruneUnconnected(scip, propdata->propgraph, probisinfeas, offset ) );
2570 
2571  if( *probisinfeas )
2572  {
2573  SCIPdebugMessage("problem has become infeasible after pruning (terminals not connected): terminating! \n");
2574  *probisinfeas = TRUE;
2575  }
2576  }
2577 
2578  if( FALSE == *probisinfeas )
2579  {
2580  assert(graph_valid(scip, propdata->propgraph));
2581  *graph = propdata->propgraph;
2582  *graphnodenumber = propdata->propgraphnodenumber;
2583  }
2584 
2585  graph_path_exit(scip, propdata->propgraph);
2586  SCIPfreeBufferArray(scip, &edgestate);
2587  SCIPfreeBufferArray(scip, &nodestate);
2588 
2589  return SCIP_OKAY;
2590 }
2591 
2592 /** gives array indicating which nodes are degree-2 bounded */
2594  SCIP* scip /**< SCIP data structure */
2595 )
2596 {
2597  SCIP_PROPDATA* propdata;
2598  assert(scip != NULL);
2599 
2600  /* get propagator data */
2601  assert(SCIPfindProp(scip, "stp") != NULL);
2602  propdata = SCIPpropGetData(SCIPfindProp(scip, "stp"));
2603  assert(propdata != NULL);
2604 
2605  return propdata->deg2bounded;
2606 }
2607 
2608 
2609 /** creates the stp propagator and includes it in SCIP */
2611  SCIP* scip /**< SCIP data structure */
2612  )
2613 {
2614  SCIP_PROP* prop;
2615  SCIP_PROPDATA* propdata;
2616 
2617  /* create redcost propagator data */
2618  SCIP_CALL( SCIPallocMemory(scip, &propdata) );
2619 
2620  /* include propagator */
2622  propExecStp, propdata) );
2623 
2624  assert(prop != NULL);
2625 
2626  /* set optional callbacks via setter functions */
2627  SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyStp) );
2628  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeStp) );
2629  SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolStp) );
2630  SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolStp) );
2631 
2632  /* add parameters */
2633  SCIP_CALL( SCIPaddIntParam(scip, "propagating/" PROP_NAME "/nwaitingrounds",
2634  "maximum number of rounds before propagating again",
2635  &propdata->maxnwaitrounds, FALSE, DEFAULT_MAXNWAITINGROUNDS, 1, INT_MAX, NULL, NULL) );
2636 
2637  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/"PROP_NAME"/aggressive",
2638  "should the heuristic be executed at maximum frequeny?",
2639  &propdata->aggressive, FALSE, FALSE, NULL, NULL) );
2640 
2641  SCIP_CALL( SCIPcreateRandom(scip, &propdata->randnumgen, 0, TRUE) );
2642 
2643  return SCIP_OKAY;
2644 }
2645 
2646 /**@} */
#define STP_Vectype(type)
Definition: stpvector.h:44
static SCIP_DECL_PROPINITSOL(propInitsolStp)
Definition: prop_stp.c:2354
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
SCIP_RETCODE graph_transPcmw2rooted(SCIP *, GRAPH *, SCIP_Real, SCIP_Bool)
Definition: graph_trans.c:809
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
void graph_knot_chg(GRAPH *, int, int)
Definition: graph_node.c:86
#define BRANCH_STP_VERTEX_UNSET
Definition: branch_stp.h:36
static SCIP_RETCODE fixVarsExtendedRed(SCIP *scip, const GRAPH *graph, SCIP_VAR **vars, SCIP_PROPDATA *propdata)
Definition: prop_stp.c:1749
#define StpVecGetSize(vec)
Definition: stpvector.h:139
SCIP_Bool graph_pc_isMw(const GRAPH *)
static void propgraphMarkFixedTermsPcMw(SCIP *scip, const int *nodestate, GRAPH *propgraph, SCIP_Bool *hasFixedTerms)
Definition: prop_stp.c:1091
static SCIP_RETCODE applyEdgestateToProb(SCIP *scip, const GRAPH *graph, SCIP_VAR **vars, const int *edgestate, SCIP_PROPDATA *propdata)
Definition: prop_stp.c:676
static SCIP_RETCODE fixVarsDualcostLurking(SCIP *scip, const GRAPH *graph, SCIP_Real cutoffbound, SCIP_PROPDATA *propdata, SCIP_VAR **vars)
Definition: prop_stp.c:1545
int *RESTRICT head
Definition: graphdefs.h:224
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_edge.c:368
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:82
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
int source
Definition: graphdefs.h:195
internal methods for branch and bound tree
SCIP_RETCODE SCIPStpBranchruleGetVertexChgs(SCIP *scip, int *vertexchgs, SCIP_Bool *conflictFound)
Definition: branch_stp.c:977
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Bool graph_pc_isRootedPcMw(const GRAPH *)
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:72
SCIP_RETCODE SCIPStpFixEdgeVarTo1(SCIP *scip, SCIP_VAR *edgevar, SCIP_Bool *success)
Definition: prop_stp.c:2443
#define Is_term(a)
Definition: graphdefs.h:102
#define REDUCTION_WAIT_FACTOR
Definition: prop_stp.c:69
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
void redcosts_increaseOnDeletedArcs(const GRAPH *graph, const STP_Bool *arcsdeleted, int level, REDCOST *redcostdata)
Definition: redcosts.c:682
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:117
static void setEdgestate(const GRAPH *graph, IDX *curr, int *RESTRICT edgestate)
Definition: prop_stp.c:619
Constraint handler for Steiner problems.
int SCIPStpNfixedEdges(SCIP *scip)
Definition: prop_stp.c:2467
SCIP_PROP * SCIPfindProp(SCIP *scip, const char *name)
Definition: scip_prop.c:320
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
SCIP_Bool graph_valid(SCIP *, const GRAPH *)
Definition: graph_base.c:1480
int redcosts_getNlevels(const REDCOST *redcostdata)
Definition: redcosts.c:369
SCIP_RETCODE reduce_solInit(SCIP *, const GRAPH *, SCIP_Bool, REDSOL **)
Definition: reduce_sol.c:687
int terms
Definition: graphdefs.h:192
void extreduce_distDataFree(SCIP *, const GRAPH *, DISTDATA **)
static SCIP_DECL_PROPEXITSOL(propExitsolStp)
Definition: prop_stp.c:2388
static SCIP_DECL_PROPCOPY(propCopyStp)
Definition: prop_stp.c:2205
SCIP_Real redcosts_getCutoffTop(const REDCOST *redcostdata)
Definition: redcosts.c:300
SCIP_VAR ** SCIPprobdataGetVars(SCIP *scip)
static void updateRedcostdata(SCIP *scip, const GRAPH *graph, SCIP_VAR **vars, SCIP_PROPDATA *propdata)
Definition: prop_stp.c:1460
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:749
int graph_pc_nFixedTerms(const GRAPH *)
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPStpPropCheckForInfeas(SCIP *scip, SCIP_Bool *probisinfeas)
Definition: prop_stp.c:2488
void graph_mark(GRAPH *)
Definition: graph_base.c:1130
void graph_free_dcsr(SCIP *, GRAPH *)
Definition: graph_util.c:1807
int norgmodeledges
Definition: graphdefs.h:215
SCIP_RETCODE solstp_markPcancestors(SCIP *scip, IDX **pcancestors, const int *tails, const int *heads, int orgnnodes, STP_Bool *solnodemark, STP_Bool *soledgemark, int *solnodequeue, int *nsolnodes, int *nsoledges)
Definition: solstp.c:2200
includes methods for Steiner tree problem solutions
int *RESTRICT maxdeg
Definition: graphdefs.h:206
void redcosts_addLevel(REDCOST *redcostdata)
Definition: redcosts.c:460
void graph_knot_printInfo(const GRAPH *, int)
Definition: graph_stats.c:151
SCIP_RETCODE SCIPStpBranchruleGetVertexChgLast(SCIP *scip, int *vertex, SCIP_Bool *isDeleted)
Definition: branch_stp.c:1036
void graph_free(SCIP *, GRAPH **, SCIP_Bool)
Definition: graph_base.c:796
void graph_pc_2org(SCIP *, GRAPH *)
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
Definition: graph_path.c:480
#define EAT_FREE
Definition: graphdefs.h:57
static void propgraphDeleteEdge(SCIP *scip, int e, GRAPH *propgraph)
Definition: prop_stp.c:1053
#define FALSE
Definition: def.h:87
static void propgraphDeleteNode(SCIP *scip, int node, GRAPH *propgraph, SCIP_Real *offset)
Definition: prop_stp.c:961
int *RESTRICT inpbeg
Definition: graphdefs.h:202
void SCIPStpBranchruleInitNodeState(const GRAPH *g, int *nodestate)
Definition: branch_stp.c:954
#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
void redcosts_setDualBound(SCIP_Real dualbound, int level, REDCOST *redcostdata)
Definition: redcosts.c:406
static SCIP_RETCODE initPropgraph(SCIP *scip, const GRAPH *graph, SCIP_PROPDATA *propdata)
Definition: prop_stp.c:1361
#define STP_DCSTP
Definition: graphdefs.h:47
static void updateEdgeLurkingBounds(const GRAPH *graph, const SCIP_Real *cost, const SCIP_Real *pathdist, const PATH *vnoi, SCIP_Real lpobjal, SCIP_Real *fixingbounds)
Definition: prop_stp.c:862
SCIP_RETCODE extreduce_deleteArcs(SCIP *, REDCOST *, const int *, GRAPH *, STP_Bool *, int *)
static SCIP_RETCODE fixVarsRedbased(SCIP *scip, const GRAPH *graph, SCIP_VAR **vars, SCIP_PROPDATA *propdata, SCIP_Bool *probisinfeas)
Definition: prop_stp.c:1846
SCIP_RETCODE reduce_unconnectedRpcRmwInfeas(SCIP *, GRAPH *, SCIP_Real *, SCIP_Bool *)
void redcosts_free(SCIP *scip, REDCOST **redcostdata)
Definition: redcosts.c:743
static SCIP_Real getCutoffbound(SCIP *scip, SCIP_Real lpbound)
Definition: prop_stp.c:172
#define EAT_LAST
Definition: graphdefs.h:58
#define StpVecReserve(scip, vec, _size_)
Definition: stpvector.h:186
#define SCIPdebugMessage
Definition: pub_message.h:87
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10003
static SCIP_RETCODE initRedcostdata(SCIP *scip, const GRAPH *graph, SCIP_VAR **vars, SCIP_PROPDATA *propdata)
Definition: prop_stp.c:1430
#define FARAWAY
Definition: graphdefs.h:89
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4673
static SCIP_RETCODE propgraphApplyBoundchanges(SCIP *scip, SCIP_VAR **vars, const GRAPH *g, int *nodestate, int *edgestate, SCIP_PROPDATA *propdata, SCIP_Bool *probisinfeas, SCIP_Real *offset)
Definition: prop_stp.c:1297
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7444
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
static void fixEdgestate(const GRAPH *graph, IDX *curr, int *RESTRICT edgestate)
Definition: prop_stp.c:650
static void updateEdgestateFromRed(const GRAPH *graph, const GRAPH *propgraph, SCIP_VAR **vars, const int *nodestate, int *edgestate, SCIP_Bool *error)
Definition: prop_stp.c:721
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:5029
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
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
SCIP_RETCODE graph_init_dcsr(SCIP *, GRAPH *)
Definition: graph_util.c:1721
void graph_get2nextTermPaths(GRAPH *, const SCIP_Real *, const SCIP_Real *, PATH *, int *, int *)
Definition: graph_tpath.c:1542
#define PROP_STP_EDGE_UNSET
Definition: prop_stp.c:54
SCIP_Real * redcosts_getEdgeCosts(const REDCOST *redcostdata, int level)
Definition: redcosts.c:187
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7434
static void updateEdgestateFromRedPcmw(SCIP *scip, const GRAPH *graph, const GRAPH *propgraph, SCIP_VAR **vars, const int *nodestate, int *edgestate, SCIP_Bool *error)
Definition: prop_stp.c:763
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
int *RESTRICT oeat
Definition: graphdefs.h:231
This file implements extended reduction techniques for several Steiner problems.
SCIP_RETCODE SCIPStpFixEdgeVarTo0(SCIP *scip, SCIP_VAR *edgevar, SCIP_Bool *success)
Definition: prop_stp.c:2419
#define BLOCKED_MINOR
Definition: graphdefs.h:91
int graph_pc_getRoot2PtermEdge(const GRAPH *, int)
SCIP_Bool graph_pc_edgeIsExtended(const GRAPH *, int)
#define LE(a, b)
Definition: portab.h:83
#define PROP_NAME
Definition: prop_stp.c:46
#define GE(a, b)
Definition: portab.h:85
void graph_path_execX(SCIP *, const GRAPH *, int, const SCIP_Real *, SCIP_Real *, int *)
Definition: graph_path.c:905
void graph_pc_2trans(SCIP *, GRAPH *)
SCIP_Bool extended
Definition: graphdefs.h:267
int stp_type
Definition: graphdefs.h:264
IDX ** ancestors
Definition: graphdefs.h:234
SCIP_RETCODE extreduce_extPermaInit(SCIP *, enum EXTRED_MODE, const GRAPH *, STP_Bool *, EXTPERMA **)
SCIP_Real SCIPprobdataGetPresolUpperBound(SCIP *scip)
static SCIP_RETCODE trailGraphWithStates(SCIP *scip, const GRAPH *graph, const int *nodestate, const int *edgestate, SCIP_Bool *probisinfeas)
Definition: prop_stp.c:433
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real * redcosts_getEdgeCostsTop(const REDCOST *redcostdata)
Definition: redcosts.c:202
SCIP_Real * prize
Definition: graphdefs.h:210
void graph_freeHistoryDeep(SCIP *, GRAPH *)
Definition: graph_base.c:900
SCIP_RETCODE graph_initHistory(SCIP *, GRAPH *)
Definition: graph_base.c:695
SCIP_RETCODE SCIPStpPropGetGraph(SCIP *scip, GRAPH **graph, SCIP_Longint *graphnodenumber, SCIP_Bool *probisinfeas, SCIP_Real *offset)
Definition: prop_stp.c:2521
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4763
SCIP_Real dist
Definition: graphdefs.h:286
#define PROP_STP_EDGE_FIXED
Definition: prop_stp.c:56
int *RESTRICT grad
Definition: graphdefs.h:201
SCIP_RETCODE reduce_unconnected(SCIP *, GRAPH *)
#define PROP_STP_EDGE_KILLED
Definition: prop_stp.c:53
SCIP_RETCODE reduce_unconnectedInfeas(SCIP *, SCIP_Bool, GRAPH *, SCIP_Bool *)
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_Real reduce_solGetOffset(const REDSOL *)
Definition: reduce_sol.c:1137
#define EQ(a, b)
Definition: portab.h:79
static SCIP_RETCODE getRedCost2ndNextDistances(SCIP *scip, const SCIP_Real *redcost, GRAPH *g, PATH *vnoi, SCIP_Real *pathdist, int *vbase, int *state)
Definition: prop_stp.c:503
void graph_knot_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_node.c:111
SCIP_Bool SCIPStpBranchruleIsActive(SCIP *scip)
Definition: branch_stp.c:1099
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
static void getBoundchangesPcMW(SCIP *scip, SCIP_VAR **vars, const GRAPH *propgraph, int *nodestate, SCIP_Bool *conflictFound)
Definition: prop_stp.c:201
int * term2edge
Definition: graphdefs.h:208
IDX ** pcancestors
Definition: graphdefs.h:235
static SCIP_RETCODE updatePropgraph(SCIP *scip, const GRAPH *graph, SCIP_PROPDATA *propdata)
Definition: prop_stp.c:1516
SCIP_Real redcosts_getCutoff(const REDCOST *redcostdata, int level)
Definition: redcosts.c:288
void reduce_solFree(SCIP *, REDSOL **)
Definition: reduce_sol.c:818
static void propgraphApplyStates(SCIP *scip, const int *nodestate, const int *edgestate, GRAPH *propgraph, SCIP_Real *offset)
Definition: prop_stp.c:1121
#define STP_PCSPG
Definition: graphdefs.h:44
#define LT(a, b)
Definition: portab.h:81
#define PROP_STP_EDGE_SET
Definition: prop_stp.c:55
static void blockEdgesWithGlobalFixings(SCIP *scip, SCIP_VAR **vars, GRAPH *graph)
Definition: prop_stp.c:2068
const SCIP_Bool * SCIPStpPropGet2BoundedArr(SCIP *scip)
Definition: prop_stp.c:2593
SCIP_Bool graph_pc_knotIsPropPotTerm(const GRAPH *, int)
SCIP_RETCODE redcosts_initializeDistances(SCIP *scip, int level, GRAPH *g, REDCOST *redcostdata)
Definition: redcosts.c:473
unsigned char STP_Bool
Definition: portab.h:34
SCIP_RETCODE graph_copyData(SCIP *, const GRAPH *, GRAPH *)
Definition: graph_base.c:957
void extreduce_extPermaFree(SCIP *, EXTPERMA **)
SCIP_RETCODE SCIPincludePropStp(SCIP *scip)
Definition: prop_stp.c:2610
static SCIP_RETCODE getGraphStatesDirected(SCIP *scip, const GRAPH *graph, int *nodestate, int *edgestate, SCIP_Bool *probisinfeas)
Definition: prop_stp.c:368
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
propagator for Steiner tree problems, using the LP reduced costs
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
void graph_pc_knotChgPrize(GRAPH *, SCIP_Real, int)
#define SCIP_Bool
Definition: def.h:84
int *RESTRICT ieat
Definition: graphdefs.h:230
#define PROP_DELAY
Definition: prop_stp.c:51
static void writeRedcostdata(SCIP *scip, int level, const GRAPH *graph, SCIP_VAR **vars, SCIP_PROPDATA *propdata)
Definition: prop_stp.c:1404
static SCIP_RETCODE fixVarsDualcost(SCIP *scip, SCIP_VAR **vars, SCIP_PROPDATA *propdata, GRAPH *graph, SCIP_Bool *probisinfeas)
Definition: prop_stp.c:1601
static SCIP_RETCODE propgraphApplyImplicationsPcMw(SCIP *scip, const GRAPH *g, SCIP_VAR **vars, SCIP_PROPDATA *propdata, SCIP_Bool *probisinfeas, SCIP_Real *offset)
Definition: prop_stp.c:1170
SCIP_Bool graph_isMarked(const GRAPH *)
Definition: graph_base.c:1165
int *RESTRICT tail
Definition: graphdefs.h:223
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:661
static SCIP_RETCODE propgraphPruneUnconnected(SCIP *scip, GRAPH *propgraph, SCIP_Bool *probisinfeas, SCIP_Real *offset)
Definition: prop_stp.c:1276
PATH * redcosts_getNodeToTermsPathsTop(const REDCOST *redcostdata)
Definition: redcosts.c:253
static SCIP_DECL_PROPFREE(propFreeStp)
Definition: prop_stp.c:2220
SCIP_RETCODE reduce_stp(SCIP *, GRAPH *, REDSOL *, int, SCIP_Bool, SCIP_Bool, SCIP_Bool, SCIP_Bool)
Definition: reduce_base.c:1181
#define BRANCH_STP_VERTEX_TERM
Definition: branch_stp.h:39
int reduce_extendedEdge(SCIP *, GRAPH *, const PATH *, const SCIP_Real *, const SCIP_Real *, const int *, SCIP_Real, int, STP_Bool *, SCIP_Bool)
Definition: reduce_ext.c:1155
#define flipedge(edge)
Definition: graphdefs.h:84
#define STP_TERM
Definition: graphdefs.h:61
#define PROP_PRIORITY
Definition: prop_stp.c:49
#define PROP_FREQ
Definition: prop_stp.c:50
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:142
IDX * graph_getFixedges(const GRAPH *)
int *RESTRICT term
Definition: graphdefs.h:196
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
void graph_edge_printInfo(const GRAPH *, int)
Definition: graph_stats.c:133
SCIP_RETCODE graph_copyPseudoAncestors(SCIP *, const GRAPH *, GRAPH *)
Definition: graph_base.c:1088
SCIP_Bool graph_pc_knotIsNonLeafTerm(const GRAPH *, int)
int redcosts_getLevel(const REDCOST *redcostdata)
Definition: redcosts.c:358
void redcosts_setRoot(int root, int level, REDCOST *redcostdata)
Definition: redcosts.c:433
const int * SCIPStpGetPcImplVerts(SCIP *scip)
Definition: cons_stp.c:1269
void graph_path_exit(SCIP *, GRAPH *)
Definition: graph_path.c:515
SCIP_Bool graph_pc_isPc(const GRAPH *)
#define BRANCH_STP_VERTEX_KILLED
Definition: branch_stp.h:37
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip_prop.c:222
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:932
Portable definitions.
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
#define PROP_STP_REDCOST_LEVELS
Definition: prop_stp.c:58
void redcosts_setCutoffFromBound(SCIP_Real upperbound, int level, REDCOST *redcostdata)
Definition: redcosts.c:645
void graph_pc_enforceNode(SCIP *, GRAPH *, int, SCIP_Real *)
Steiner vertex branching rule.
void redcosts_unifyBlockedEdgeCosts(const GRAPH *graph, int level, REDCOST *redcostdata)
Definition: redcosts.c:705
#define Is_pseudoTerm(a)
Definition: graphdefs.h:103
void graph_freeHistory(SCIP *, GRAPH *)
Definition: graph_base.c:868
SCIP_Bool redcosts_forLPareAvailable(SCIP *scip)
Definition: redcosts.c:767
Reduced cost based routines for Steiner problems.
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:238
#define REDUCTION_WAIT_RATIO_INITIAL
Definition: prop_stp.c:68
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE extreduce_distDataInit(SCIP *, GRAPH *, int, SCIP_Bool, SCIP_Bool, DISTDATA **)
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
static void propgraphFixNode(SCIP *scip, int node, GRAPH *propgraph, SCIP_Real *offset)
Definition: prop_stp.c:914
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:963
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
SCIP_Real * cost
Definition: graphdefs.h:221
SCIP_Bool redcosts_forLPareReliable(SCIP *scip, SCIP_VAR **vars, const GRAPH *graph)
Definition: redcosts.c:814
int graph_pc_deleteTerm(SCIP *, GRAPH *, int, SCIP_Real *)
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
const int * SCIPStpGetPcImplStarts(SCIP *scip)
Definition: cons_stp.c:1231
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITSOL((*propinitsol)))
Definition: scip_prop.c:206
#define DEFAULT_MAXNWAITINGROUNDS
Definition: prop_stp.c:67
#define SCIP_Real
Definition: def.h:177
static SCIP_Bool useRedcostdata(const GRAPH *graph)
Definition: prop_stp.c:1394
#define BLOCKED
Definition: graphdefs.h:90
static SCIP_RETCODE applyLastVertexBranch(SCIP *scip, const GRAPH *graph, SCIP_VAR **vars, SCIP_PROPDATA *propdata)
Definition: prop_stp.c:2167
static SCIP_RETCODE getBoundchanges(SCIP *scip, SCIP_VAR **vars, const GRAPH *propgraph, int *nodestate, int *edgestate, SCIP_Bool *probisinfeas)
Definition: prop_stp.c:281
void redcosts_setCutoff(SCIP_Real cutoff, int level, REDCOST *redcostdata)
Definition: redcosts.c:380
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:43
#define StpVecFree(scip, vec)
Definition: stpvector.h:153
#define PROP_DESC
Definition: prop_stp.c:47
static SCIP_RETCODE fixEdgeVar(SCIP *scip, int edge, SCIP_VAR **vars, SCIP_PROPDATA *propdata)
Definition: prop_stp.c:147
int *RESTRICT outbeg
Definition: graphdefs.h:204
SCIP_Real * redcosts_getRootToNodeDistTop(const REDCOST *redcostdata)
Definition: redcosts.c:228
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:158
SCIP_RETCODE graph_copy(SCIP *, const GRAPH *, GRAPH **)
Definition: graph_base.c:939
SCIP_RETCODE reduce_pc(SCIP *, REDSOL *, GRAPH *, int, SCIP_Bool, SCIP_Bool, SCIP_Bool, SCIP_Bool)
Definition: reduce_base.c:1260
#define STP_BRMWCSP
Definition: graphdefs.h:55
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:780
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
Definition: prop.c:790
static SCIP_RETCODE initPropAtFirstCall(SCIP *scip, const GRAPH *graph, SCIP_VAR **vars, SCIP_PROPDATA *propdata)
Definition: prop_stp.c:2105
#define SCIP_Longint
Definition: def.h:162
int edges
Definition: graphdefs.h:219
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
void graph_pc_knotToFixedTerm(SCIP *, GRAPH *, int, SCIP_Real *)
int graph_pc_nNonFixedTerms(const GRAPH *)
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
#define nnodes
Definition: gastrans.c:65
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
#define StpVecPushBack(scip, vec, value)
Definition: stpvector.h:167
static void mark0FixedArcs(const GRAPH *graph, SCIP_VAR **vars, STP_Bool *arcIs0Fixed)
Definition: prop_stp.c:544
static SCIP_DECL_PROPEXEC(propExecStp)
Definition: prop_stp.c:2240
static void updateDeg2LurkingBounds(const GRAPH *graph, const SCIP_Real *pathdist, const PATH *vnoi, SCIP_Real lpobjal, SCIP_Real *deg2bounds)
Definition: prop_stp.c:890
struct Int_List_Node * parent
Definition: misc_stp.h:91
int SCIPStpGetPcImplNstarts(SCIP *scip)
Definition: cons_stp.c:1250
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
#define Is_anyTerm(a)
Definition: graphdefs.h:105
SCIP_Bool graph_typeIsSpgLike(const GRAPH *)
Definition: graph_stats.c:57
includes various reduction methods for Steiner tree problems
SCIP_RETCODE reduce_mw(SCIP *, REDSOL *, GRAPH *, int, SCIP_Bool, SCIP_Bool, SCIP_Bool)
Definition: reduce_base.c:1344
static void validateEdgestate(const GRAPH *graph, const GRAPH *propgraph, SCIP_VAR **vars, const int *edgestate, SCIP_Bool *error)
Definition: prop_stp.c:570
#define PROP_TIMING
Definition: prop_stp.c:48
#define STP_MWCSP
Definition: graphdefs.h:51
GRAPH * SCIPprobdataGetGraph2(SCIP *scip)
static void propgraphFixEdge(SCIP *scip, int e, GRAPH *propgraph)
Definition: prop_stp.c:1012
static SCIP_Bool fixVarsRedbasedIsPromising(SCIP *scip, const GRAPH *graph, SCIP_VAR **vars, SCIP_PROPDATA *propdata)
Definition: prop_stp.c:2012
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
SCIP_RETCODE redcosts_initFromParams(SCIP *scip, const RCPARAMS *parameters, REDCOST **redcostdata)
Definition: redcosts.c:590
int graph_pc_getTwinTerm(const GRAPH *, int)
int norgmodelknots
Definition: graphdefs.h:187
SCIP_RETCODE extreduce_pseudoDeleteNodes(SCIP *, const SCIP_Bool *, EXTPERMA *, GRAPH *, SCIP_Real *, int *)
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
void redcosts_forLPget(SCIP *scip, SCIP_VAR **vars, const GRAPH *graph, SCIP_Real *redcosts)
Definition: redcosts.c:861