Scippy

SCIP

Solving Constraint Integer Programs

branch_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 /**@file branch_stp.c
16  * @brief Steiner vertex branching rule
17  * @author Daniel Rehfeldt
18  *
19  * The Steiner branching rule implemented in this file is described in
20  * "SCIP-Jack - A solver for STP and variants with parallelization extensions" by
21  * Gamrath, Koch, Maher, Rehfeldt and Shinano
22  * It includes and excludes Steiner vertices during branching.
23  *
24 */
25 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
26 //#define SCIP_DEBUG
27 #include <assert.h>
28 #include <string.h>
29 #include "scip/cons_linear.h"
30 #include "scip/cons_setppc.h"
31 #include "scip/var.h"
32 #include "scip/set.h"
33 #include "scip/struct_scip.h"
34 #include "graph.h"
35 #include "heur_tm.h"
36 #include "solstp.h"
37 #include "heur_local.h"
38 #include "branch_stp.h"
39 #include "prop_stp.h"
40 #include "probdata_stp.h"
41 #include "scip/pub_tree.h"
42 
43 #define BRANCHRULE_NAME "stp"
44 #define BRANCHRULE_DESC "stp branching on vertices"
45 #define BRANCHRULE_PRIORITY 10000000
46 #define BRANCHRULE_MAXDEPTH -1
47 #define BRANCHRULE_MAXBOUNDDIST 1.0
48 #define BRANCHRULE_TMRUNS 20
49 #define BRANCHRULE_TMRUNS_SPG 8
50 #define BRANCH_STP_ON_LP 0
51 #define BRANCH_STP_ON_LP2 1
52 #define BRANCH_STP_ON_SOL 2
53 #define BRANCH_STP_ON_DEGREE 3
54 
55 
56 
57 /*
58  * Data structures
59  */
60 
61 
62 
63 /** branching rule data */
64 struct SCIP_BranchruleData
65 {
66  SCIP_Bool branchtypeIsFixed; /**< branching type fixed? */
67  int branchtype; /**< type of branching */
68  SCIP_Bool active; /**< is branch-rule being used? */
69 };
70 
71 
72 /*
73  * Local methods
74  */
75 
76 
77 /** check whether branching-rule is compatible with given problem type */
78 static inline
80  const GRAPH* graph /**< graph */
81 )
82 {
83  return (graph->stp_type != STP_DCSTP);
84 }
85 
86 
87 /** check whether given problem type allows for solution based branching */
88 static inline
90  const GRAPH* graph /**< graph */
91 )
92 {
93  return (graph_typeIsSpgLike(graph) || (graph_pc_isPcMw(graph) && graph->stp_type != STP_BRMWCSP));
94 }
95 
96 
97 /** check whether branching-rule is compatible with given problem type */
98 static inline
100  SCIP* scip, /**< SCIP data structure */
101  const GRAPH* g, /**< graph */
102  SCIP_BRANCHRULEDATA* branchruledata /**< data */
103 )
104 {
105  int branchtype;
106 
107  if( !branchruledata->branchtypeIsFixed )
108  {
109  // todo add a user parameter "automatic"
111  {
112  branchruledata->branchtype = BRANCH_STP_ON_SOL;
113  }
114  }
115 
116  branchtype = branchruledata->branchtype;
117 
118  // todo at least add a warning
119  if( !probAllowsSolBranching(g) )
120  {
121  branchtype = BRANCH_STP_ON_LP;
122  }
123 
124  if( graph_pc_isPcMw(g) && (branchtype == BRANCH_STP_ON_LP || branchtype == BRANCH_STP_ON_LP2) )
125  {
126  branchtype = BRANCH_STP_ON_SOL; // todo do this properly
127  }
128 
129 #ifndef WITH_UG
130  if( !branchruledata->branchtypeIsFixed )
131  printf("using branching type %d \n", branchtype);
132 #endif
133 
134  branchruledata->branchtypeIsFixed = TRUE;
135 
136  return branchtype;
137 }
138 
139 
140 /** gets vertex with highest degree in solution */
141 static
143  const int* nodestatenew, /**< node state derived from branching history */
144  const int* soledges, /**< solution edges mark */
145  const GRAPH* graph /**< graph */
146 )
147 {
148  const int nnodes = graph->knots;
149  int maxdeg = -1;
150  int vertex = -1;
151  SCIP_Bool ptermselected = FALSE;
152 
153  assert(soledges && nodestatenew);
154 
155  for( int i = 0; i < nnodes; i++ )
156  {
157  if( nodestatenew[i] == BRANCH_STP_VERTEX_NONTERM && graph->grad[i] != 0 )
158  {
159  int soldeg = 0;
160  assert(!Is_term(graph->term[i]));
161  assert(!ptermselected || graph_pc_isPcMw(graph));
162 
163  for( int e = graph->outbeg[i]; e != EAT_LAST; e = graph->oeat[e] )
164  if( soledges[e] == CONNECT || soledges[flipedge(e)] == CONNECT )
165  soldeg++;
166 
167  /* first pterm? Then update */
168  if( !ptermselected && Is_pseudoTerm(graph->term[i]) )
169  {
170  assert(graph_pc_isPcMw(graph));
171  maxdeg = soldeg;
172  vertex = i;
173  ptermselected = TRUE;
174  }
175  else if( soldeg > maxdeg && (!ptermselected || Is_pseudoTerm(graph->term[i])) )
176  {
177  maxdeg = soldeg;
178  vertex = i;
179  }
180  }
181  }
182 
183  assert(maxdeg >= 0);
184 
185  return vertex;
186 }
187 
188 
189 /** applies branching-changes to graph */
190 static
192  SCIP* scip, /**< SCIP data structure */
193  const int* nodestatenew, /**< node state derived from branching history */
194  GRAPH* graph /**< graph */
195  )
196 {
197  const int nnodes = graph->knots;
198  const SCIP_Bool mw = graph_pc_isMw(graph);
199  const SCIP_Bool pcmw = graph_pc_isPcMw(graph);
200  const SCIP_Bool rpcmw = graph_pc_isRootedPcMw(graph);
201 
202  assert(!pcmw || graph->extended);
203 
204  for( int k = 0; k < nnodes; k++ )
205  {
206  if( Is_term(graph->term[k]) )
207  {
208  assert(nodestatenew[k] != BRANCH_STP_VERTEX_KILLED );
209  continue;
210  }
211 
212  if( nodestatenew[k] == BRANCH_STP_VERTEX_TERM )
213  {
214  assert(graph->grad[k] > 0);
215 
216  if( !pcmw )
217  {
218  graph_knot_chg(graph, k, STP_TERM);
219  continue;
220  }
221 
222  if( Is_nonleafTerm(graph->term[k]) )
223  {
224  graph_pc_enforceNonLeafTerm(scip, graph, k);
225  }
226  else if( Is_pseudoTerm(graph->term[k]) )
227  {
228  graph_pc_enforcePseudoTerm(scip, graph, k);
229  }
230  else if( graph_pc_isRootedPcMw(graph) )
231  {
233  }
234  }
235  else if( nodestatenew[k] == BRANCH_STP_VERTEX_KILLED )
236  {
237  assert(!pcmw || !graph_pc_knotIsFixedTerm(graph, k));
238 
239  if( mw )
240  {
241  if( Is_anyTerm(graph->term[k]) )
242  continue;
243 
244  graph->prize[k] = -BLOCKED;
245  }
246 
247  for( int e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
248  {
249  if( pcmw )
250  {
251  if( graph->term2edge[k] == e ) /* do not change edge going to pseudo-terminal */
252  {
253  assert(Is_pseudoTerm(graph->term[k]));
254  assert(Is_term(graph->term[graph->head[e]]));
255  continue;
256  }
257  else if( !rpcmw && graph->head[e] == graph->source ) /* do not change edge going to pseudo-root */
258  {
259  assert(Is_pseudoTerm(graph->term[k]));
260  assert(SCIPisEQ(scip, graph->cost[e], FARAWAY));
261  continue;
262  }
263  }
264 
265  assert(SCIPisLT(scip, graph->cost[e], FARAWAY) && SCIPisLT(scip, graph->cost[flipedge(e)], FARAWAY));
266 
267  if( !mw && graph->cost[e] < BLOCKED )
268  graph->cost[e] = BLOCKED;
269 
270  if( graph->cost[flipedge(e)] < BLOCKED )
271  graph->cost[flipedge(e)] = BLOCKED;
272  }
273  }
274  }
275 }
276 
277 
278 /** select vertex to branch on by choosing vertex of highest degree */
279 static
281  SCIP* scip, /**< SCIP data structure */
282  int* vertex, /**< the vertex to branch on */
283  const GRAPH* g /**< graph */
284  )
285 {
286  int* nodestate;
287  int maxdegree = 0;
288  const int nnodes = g->knots;
289  SCIP_Bool ptermselected;
290 
291  assert(g != NULL && scip != NULL && vertex != NULL);
292  assert(!graph_pc_isPcMw(g) || g->extended);
293 
294  SCIP_CALL( SCIPallocBufferArray(scip, &nodestate, nnodes) );
295 
296  *vertex = UNKNOWN;
297 
298  SCIPStpBranchruleInitNodeState(g, nodestate);
299 
300  /* get vertex changes from branch-and-bound */
301  if( SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) != 0 )
302  {
303  SCIP_Bool conflict = FALSE;
304 
305  SCIP_CALL( SCIPStpBranchruleGetVertexChgs(scip, nodestate, &conflict) );
306 
307  assert(!conflict);
308  }
309 
310  ptermselected = FALSE;
311  for( int k = 0; k < nnodes; k++ )
312  {
313  if( nodestate[k] == BRANCH_STP_VERTEX_NONTERM )
314  {
315  assert(!Is_term(g->term[k]));
316  assert(!ptermselected || graph_pc_isPcMw(g));
317 
318  /* first pterm? Then update */
319  if( !ptermselected && Is_pseudoTerm(g->term[k]) )
320  {
321  assert(graph_pc_isPcMw(g));
322  maxdegree = g->grad[k];
323  *vertex = k;
324  ptermselected = TRUE;
325  }
326  else if( g->grad[k] > maxdegree && (!ptermselected || Is_pseudoTerm(g->term[k])) )
327  {
328  maxdegree = g->grad[k];
329  *vertex = k;
330  }
331  }
332  }
333 
334  assert(maxdegree > 0);
335 
336  SCIPfreeBufferArray(scip, &nodestate);
337 
338  return SCIP_OKAY;
339 }
340 
341 
342 /** select vertex to branch on by using primal solution */
343 static
345  SCIP* scip, /**< original SCIP data structure */
346  int* vertex, /**< the vertex to branch on */
347  SCIP_Bool addsol /**< add new solution to pool? */
348  )
349 {
350  GRAPH* graph = SCIPprobdataGetGraph2(scip);
351  SCIP_Real* costorg = NULL;
352  SCIP_Real* costorg_pc = NULL;
353  SCIP_Real* prizeorg = NULL;
354  int* soledges = NULL;
355  int* nodestatenew = NULL;
356  int* termorg = NULL;
357  int* term2edgeorg = NULL;
358  const int nnodes = graph_get_nNodes(graph);
359  const int nedges = graph_get_nEdges(graph);
360 #ifndef NDEBUG
361  const int ntermsorg = graph->terms;
362 #endif
363  SCIP_Bool success;
364  const SCIP_Bool pcmw = graph_pc_isPcMw(graph);
365  const int ntmruns = graph_typeIsSpgLike(graph) ? BRANCHRULE_TMRUNS_SPG : BRANCHRULE_TMRUNS;
366 
367  assert(scip && vertex);
368  assert(!pcmw || graph->extended);
369  assert(graph_valid(scip, graph));
370  assert(probAllowsSolBranching(graph));
371 
372 
373  *vertex = UNKNOWN;
374 
375  SCIP_CALL( SCIPallocBufferArray(scip, &costorg, nedges) );
376  SCIP_CALL( SCIPallocBufferArray(scip, &soledges, nedges) );
377  SCIP_CALL( SCIPallocBufferArray(scip, &nodestatenew, nnodes) );
378  SCIP_CALL( SCIPallocBufferArray(scip, &termorg, nnodes) );
379 
380  BMScopyMemoryArray(costorg, graph->cost, nedges);
381  BMScopyMemoryArray(termorg, graph->term, nnodes);
382 
383  if( pcmw )
384  {
385  assert(graph->prize && graph->term2edge);
386 
387  if( graph_pc_isPc(graph) )
388  {
389  assert(graph->cost_org_pc);
390 
391  SCIP_CALL( SCIPallocBufferArray(scip, &costorg_pc, nedges) );
392  BMScopyMemoryArray(costorg_pc, graph->cost_org_pc, nedges);
393  }
394  else
395  {
396  assert(!graph->cost_org_pc);
397  }
398 
399  SCIP_CALL( SCIPallocBufferArray(scip, &prizeorg, nnodes) );
400  SCIP_CALL( SCIPallocBufferArray(scip, &term2edgeorg, nnodes) );
401 
402  BMScopyMemoryArray(prizeorg, graph->prize, nnodes);
403  BMScopyMemoryArray(term2edgeorg, graph->term2edge, nnodes);
404  }
405 
406  SCIPStpBranchruleInitNodeState(graph, nodestatenew);
407 
408  /* get vertex changes from branch-and-bound and apply them to graph */
409  if( SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) != 0 )
410  {
411  SCIP_Bool conflict = FALSE;
412 
413  SCIP_CALL( SCIPStpBranchruleGetVertexChgs(scip, nodestatenew, &conflict) );
414 
415  assert(!conflict);
416  }
417 
418  applyBranchHistoryToGraph(scip, nodestatenew, graph);
419 
420  /* compute locally feasible solution (SPH + local) */
421  SCIP_CALL( SCIPStpHeurTMRunLP(scip, graph, NULL, soledges, ntmruns, &success) );
422  assert(success);
423 
424  if( !graph_typeIsSpgLike(graph) )
425  SCIP_CALL( SCIPStpHeurLocalRun(scip, graph, soledges) );
426 
427  assert(solstp_isValid(scip, graph, soledges));
428 
429  /* restore the graph */
430  for( int k = 0; k < nnodes; k++ )
431  {
432  if( graph->term[k] != termorg[k] )
433  graph_knot_chg(graph, k, termorg[k]);
434  }
435 
436  BMScopyMemoryArray(graph->cost, costorg, nedges);
437 
438  if( pcmw )
439  {
440  BMScopyMemoryArray(graph->prize, prizeorg, nnodes);
441  BMScopyMemoryArray(graph->term2edge, term2edgeorg, nnodes);
442 
443  if( graph_pc_isPc(graph) )
444  BMScopyMemoryArray(graph->cost_org_pc, costorg_pc, nedges);
445  }
446 
447  assert(solstp_isValid(scip, graph, soledges));
448 
449  if( addsol )
450  {
451  const int nvars = SCIPprobdataGetNVars(scip);
452  assert(nvars == graph->edges);
453 
454  /* use cost array to store solution */
455  for( int e = 0; e < nvars; e++ )
456  costorg[e] = (CONNECT == soledges[e]) ? 1.0 : 0.0;
457 
458  SCIP_CALL( SCIPprobdataAddNewSol(scip, costorg, NULL, &success) );
459  SCIPdebugMessage("solution added? %d \n", success);
460  }
461 
462  *vertex = getHighSolDegVertex(nodestatenew, soledges, graph);
463 
464  SCIPfreeBufferArrayNull(scip, &term2edgeorg);
465  SCIPfreeBufferArrayNull(scip, &prizeorg);
466  SCIPfreeBufferArrayNull(scip, &costorg_pc);
467  SCIPfreeBufferArray(scip, &termorg);
468  SCIPfreeBufferArray(scip, &nodestatenew);
469  SCIPfreeBufferArray(scip, &soledges);
470  SCIPfreeBufferArray(scip, &costorg);
471 
472  assert(graph->terms == ntermsorg);
473  assert(graph_valid(scip, graph));
474 
475  return SCIP_OKAY;
476 }
477 
478 /** select vertex to branch on by using LP */
479 static
481  SCIP* scip, /**< original SCIP data structure */
482  int* vertex, /**< the vertex to branch on */
483  const GRAPH* g /**< graph */
484  )
485 {
486  SCIP_VAR** edgevars;
487  SCIP_Real bestflow;
488  const int nnodes = g->knots;
489 
490  assert(g != NULL && vertex != NULL);
491 
492  *vertex = UNKNOWN;
493 
494  /* LP has not been solved */
496  return SCIP_OKAY;
497 
498  edgevars = SCIPprobdataGetEdgeVars(scip);
499  assert(edgevars != NULL);
500 
501  bestflow = 1.0;
502  for( int k = 0; k < nnodes; k++ )
503  {
504  SCIP_Real inflow = 0.0;
505 
506  if( Is_term(g->term[k]) )
507  continue;
508 
509  for( int a = g->inpbeg[k]; a != EAT_LAST; a = g->ieat[a] )
510  inflow += SCIPvarGetLPSol(edgevars[a]);
511 
512  if( SCIPisLT(scip, inflow, 1.0) && SCIPisPositive(scip, inflow) && fabs(inflow - 0.5) < bestflow )
513  {
514  *vertex = k;
515  bestflow = fabs(inflow - 0.5);
516  SCIPdebugMessage("new maxflow %f on vertex %d \n", inflow, k );
517  }
518  }
519 
520  if( *vertex == UNKNOWN && SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) != 0 )
521  {
522  SCIP_Bool conflict = FALSE;
523  int* nodestate;
524 
525  SCIP_CALL( SCIPallocBufferArray(scip, &nodestate, nnodes) );
526  SCIPStpBranchruleInitNodeState(g, nodestate);
527  SCIP_CALL( SCIPStpBranchruleGetVertexChgs(scip, nodestate, &conflict) );
528  assert(!conflict);
529 
530  for( int k = 0; k < nnodes; k++ )
531  {
532  SCIP_Real inflow = 0.0;
533 
534  if( Is_term(g->term[k]) || nodestate[k] != BRANCH_STP_VERTEX_NONTERM )
535  continue;
536 
537  for( int a = g->inpbeg[k]; a != EAT_LAST; a = g->ieat[a] )
538  inflow += SCIPvarGetLPSol(edgevars[a]);
539 
540  if( SCIPisPositive(scip, inflow) )
541  {
542  *vertex = k;
543  break;
544  }
545  }
546 
547  SCIPfreeBufferArray(scip, &nodestate);
548  }
549 
550  SCIPdebugMessage("maxflow %f on vertex %d, term? %d \n", bestflow, *vertex, Is_term(g->term[*vertex]) );
551 
552  return SCIP_OKAY;
553 }
554 
555 /** select vertices with flow on at least two incoming arcs */
556 static
558  SCIP* scip, /**< original SCIP data structure */
559  int* vertex, /**< the vertex to branch on */
560  const GRAPH* g /**< graph */
561  )
562 {
563  SCIP_VAR** edgevars;
564  int* nodestate;
565  SCIP_Real bestflow;
566  const int nnodes = g->knots;
567 
568  assert(g != NULL && vertex != NULL);
569 
570  *vertex = UNKNOWN;
571 
572  /* has LP not been solved? */
574  return SCIP_OKAY;
575 
576  SCIP_CALL( SCIPallocBufferArray(scip, &nodestate, nnodes) );
577 
578  SCIPStpBranchruleInitNodeState(g, nodestate);
579 
580  /* get vertex changes from branch-and-bound */
581  if( SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) != 0 )
582  {
583  SCIP_Bool conflict = FALSE;
584 
585  SCIP_CALL( SCIPStpBranchruleGetVertexChgs(scip, nodestate, &conflict) );
586 
587  assert(!conflict);
588  }
589 
590  edgevars = SCIPprobdataGetEdgeVars(scip);
591  assert(edgevars != NULL);
592 
593  bestflow = 1.0;
594  for( int k = 0; k < nnodes; k++ )
595  {
596  if( nodestate[k] == BRANCH_STP_VERTEX_NONTERM )
597  {
598  int ninarcs = 0;
599  assert(g->grad[k] > 0);
600  assert(!Is_term(g->term[k]));
601 
602  for( int a = g->inpbeg[k]; a != EAT_LAST; a = g->ieat[a] )
603  if( SCIPisPositive(scip, SCIPvarGetLPSol(edgevars[a])) )
604  ninarcs++;
605 
606  if( ninarcs > 1 )
607  {
608  SCIP_Real inflow = 0.0;
609  for( int a = g->inpbeg[k]; a != EAT_LAST; a = g->ieat[a] )
610  inflow += SCIPvarGetLPSol(edgevars[a]);
611 
612  if( fabs(inflow - 0.5) < bestflow )
613  {
614  *vertex = k;
615  bestflow = fabs(inflow - 0.5);
616  SCIPdebugMessage("new maxflow %f on vertex %d \n", inflow, k );
617  }
618  }
619  }
620  }
621 
622  SCIPfreeBufferArray(scip, &nodestate);
623 
624  SCIPdebugMessage("LP2: branch on vertex %d with abs(flow - 0.5): %f \n", *vertex, bestflow);
625 
626  return SCIP_OKAY;
627 }
628 
629 
630 /** branch on specified (Steiner) vertex */
631 static
633  SCIP* scip, /**< SCIP data structure */
634  const GRAPH* g, /**< graph data structure */
635  int branchvertex /**< the vertex to branch on */
636  )
637 {
638  char consnamein[SCIP_MAXSTRLEN];
639  char consnameout[SCIP_MAXSTRLEN];
640  SCIP_CONS* consin = NULL;
641  SCIP_CONS* consout = NULL;
642  SCIP_NODE* vertexin = NULL;
643  SCIP_NODE* vertexout = NULL;
644  SCIP_VAR** const edgevars = SCIPprobdataGetEdgeVars(scip);
645  const SCIP_Real estimatein = SCIPgetUpperbound(scip);
646  const SCIP_Real estimateout = SCIPgetUpperbound(scip);
647 
648  assert(scip != NULL);
649  assert(g != NULL);
650  assert(branchvertex >= 0 && branchvertex < g->knots);
651  assert(!Is_term(g->term[branchvertex]));
652 
653  (void) SCIPsnprintf(consnamein, SCIP_MAXSTRLEN, "consin%d", branchvertex);
654  (void) SCIPsnprintf(consnameout, SCIP_MAXSTRLEN, "consout%d", branchvertex);
655 
656  /* create constraints */
657  // SCIP_CALL( SCIPcreateConsSetpart(scip, &consin,
658  // consnamein, 0, NULL, TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE) );
659 
660  SCIP_CALL( SCIPcreateConsLinear(scip, &consin,
661  consnamein, 0, NULL, NULL, 1.0, 1.0, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE) );
662 
663  SCIP_CALL( SCIPcreateConsLinear(scip, &consout,
664  consnameout, 0, NULL, NULL, 0.0, 0.0, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE) );
665 //+ consnameout, 0, NULL, NULL, 0.0, 0.0, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE) );
666 
667  for( int e = g->inpbeg[branchvertex]; e != EAT_LAST; e = g->ieat[e] )
668  {
669  //SCIP_CALL(SCIPaddCoefSetppc(scip, consin, edgevars[e]));
670  SCIP_CALL(SCIPaddCoefLinear(scip, consin, edgevars[e], 1.0));
671 
672  SCIP_CALL(SCIPaddCoefLinear(scip, consout, edgevars[e], 1.0));
673  SCIP_CALL(SCIPaddCoefLinear(scip, consout, edgevars[flipedge(e)], 1.0));
674  }
675 
676  /* create the child nodes */
677  SCIP_CALL(SCIPcreateChild(scip, &vertexin, 1.0, estimatein));
678  SCIP_CALL(SCIPcreateChild(scip, &vertexout, 1.0, estimateout));
679 
680  assert(vertexin != NULL);
681  assert(vertexout != NULL);
682 
683  SCIP_CALL(SCIPaddConsNode(scip, vertexin, consin, NULL));
684  SCIP_CALL(SCIPaddConsNode(scip, vertexout, consout, NULL));
685 
686  SCIP_CALL(SCIPreleaseCons(scip, &consin));
687  SCIP_CALL(SCIPreleaseCons(scip, &consout));
688 
689  return SCIP_OKAY;
690 }
691 
692 
693 /*
694  * Callback methods of branching rule
695  */
696 
697 /** copy method for branchrule plugins (called when SCIP copies plugins) */
698 static
699 SCIP_DECL_BRANCHCOPY(branchCopyStp)
700 { /*lint --e{715}*/
701  assert(scip != NULL);
702  assert(branchrule != NULL);
703  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
704 
705  /* call inclusion method of branchrule */
707 
708  return SCIP_OKAY;
709 }
710 
711 /** destructor of branching rule to free user data (called when SCIP is exiting) */
712 static
713 SCIP_DECL_BRANCHFREE(branchFreeStp)
714 { /*lint --e{715}*/
715  SCIP_BRANCHRULEDATA* branchruledata;
716 
717  /* free branching rule data */
718  branchruledata = SCIPbranchruleGetData(branchrule);
719  assert(branchruledata != NULL);
720 
721  SCIPfreeMemory(scip, &branchruledata);
722  SCIPbranchruleSetData(branchrule, NULL);
723 
724  return SCIP_OKAY;
725 }
726 
727 /** initialization method of branching rule (called after problem was transformed) */
728 static
729 SCIP_DECL_BRANCHINIT(branchInitStp)
730 { /*lint --e{715}*/
731  SCIP_BRANCHRULEDATA* branchruledata;
732 
733  branchruledata = SCIPbranchruleGetData(branchrule);
734  assert(branchruledata != NULL);
735 
736  branchruledata->branchtypeIsFixed = FALSE;
737 
738  return SCIP_OKAY;
739 }
740 
741 /** deinitialization method of branching rule (called before transformed problem is freed) */
742 static
743 SCIP_DECL_BRANCHEXIT(branchExitStp)
744 { /*lint --e{715}*/
745  SCIPstatistic(int j = 0);
746 
747  return SCIP_OKAY;
748 }
749 
750 /** branching execution method for fractional LP solutions */
751 static
752 SCIP_DECL_BRANCHEXECLP(branchExeclpStp)
753 { /*lint --e{715}*/
754  SCIP_PROBDATA* probdata;
755  SCIP_BRANCHRULEDATA* branchruledata;
756  GRAPH* g;
757  int branchruletype;
758  int branchvertex = UNKNOWN;
759 
760  assert(branchrule != NULL);
761  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
762  assert(scip != NULL);
763  assert(result != NULL);
764 
765  SCIPdebugMessage("Execlp method of STP branching\n ");
766  *result = SCIP_DIDNOTRUN;
767 
768  /* get branching rule data */
769  branchruledata = SCIPbranchruleGetData(branchrule);
770  assert(branchruledata != NULL);
771 
772  if( !branchruledata->active )
773  return SCIP_OKAY;
774 
775  /* get problem data */
776  probdata = SCIPgetProbData(scip);
777  assert(probdata != NULL);
778 
779  /* get graph */
780  g = SCIPprobdataGetGraph(probdata);
781  assert(g != NULL);
782 
783  if( !probIsCompatible(g) )
784  {
785  branchruledata->active = FALSE;
786 
787 #ifndef WITH_UG
788  printf("\n ---branching-rule data cannot be used for this problem class!--- \n \n");
789 #endif
790 
791  return SCIP_OKAY;
792  }
793 
794  branchruletype = branchruleGetType(scip, g, branchruledata);
795 
796  /* get vertex to branch on */
797  if( branchruletype == BRANCH_STP_ON_LP )
798  {
799  SCIP_CALL( selectBranchingVertexByLp(scip, &branchvertex, g) );
800  }
801  else if( branchruletype == BRANCH_STP_ON_LP2 )
802  {
803  SCIP_CALL( selectBranchingVertexByLp2Flow(scip, &branchvertex, g) );
804  }
805  else if( branchruletype == BRANCH_STP_ON_SOL )
806  {
807  SCIP_CALL( selectBranchingVertexBySol(scip, &branchvertex, TRUE) );
808  }
809 
810  /* fall-back strategy */
811  if( branchvertex == UNKNOWN )
812  {
813  SCIP_CALL( selectBranchingVertexByDegree(scip, &branchvertex, g) );
814  }
815 
816  /* we should only have terminals in this case */
817  if( branchvertex == UNKNOWN )
818  {
819  printf("Stp branching could not run \n");
820  return SCIP_ERROR;
821  }
822 
823  SCIP_CALL( branchOnVertex(scip, g, branchvertex) );
824 
825  SCIPdebugMessage("Branched on stp vertex %d \n", branchvertex);
826 
827  *result = SCIP_BRANCHED;
828 
829  return SCIP_OKAY;
830 }
831 
832 
833 /** branching execution method for not completely fixed pseudo solutions */
834 static
835 SCIP_DECL_BRANCHEXECPS(branchExecpsStp)
836 { /*lint --e{715}*/
837  SCIP_PROBDATA* probdata;
838  SCIP_BRANCHRULEDATA* branchruledata;
839  GRAPH* g;
840  int branchvertex;
841 
842  assert(branchrule != NULL);
843  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
844  assert(scip != NULL);
845  assert(result != NULL);
846 
847  branchruledata = SCIPbranchruleGetData(branchrule);
848  assert(branchruledata != NULL);
849 
850  SCIPdebugMessage("Execps method of STP branching\n");
851  *result = SCIP_DIDNOTRUN;
852 
853  if( !branchruledata->active )
854  return SCIP_OKAY;
855 
856  probdata = SCIPgetProbData(scip);
857  assert(probdata != NULL);
858 
859  g = SCIPprobdataGetGraph(probdata);
860  assert(g != NULL);
861 
862  if( !probIsCompatible(g) )
863  {
864  branchruledata->active = FALSE;
865 
866 #ifndef WITH_UG
867  printf("\n ---branching-rule data cannot be used for this problem class!--- \n \n");
868 #endif
869 
870  return SCIP_OKAY;
871  }
872 
873  branchvertex = UNKNOWN;
874 
875  if( probAllowsSolBranching(g) && branchruleGetType(scip, g, branchruledata) != BRANCH_STP_ON_DEGREE )
876  SCIP_CALL( selectBranchingVertexBySol(scip, &branchvertex, TRUE) );
877 
878  /* fall-back strategy */
879  if( branchvertex == UNKNOWN )
880  SCIP_CALL( selectBranchingVertexByDegree(scip, &branchvertex, g) );
881 
882  if( branchvertex == UNKNOWN )
883  {
884  SCIPdebugMessage("Stp branching did not run \n");
885  return SCIP_OKAY;
886  }
887 
888  branchruledata->active = TRUE;
889  SCIP_CALL( branchOnVertex(scip, g, branchvertex) );
890 
891  *result = SCIP_BRANCHED;
892 
893  return SCIP_OKAY;
894 }
895 
896 
897 /*
898  * branching rule specific interface methods
899  */
900 
901 /** parse constraint name and apply changes to graph or array */
903  int* vertexchgs, /**< array to store changes */
904  const char* consname, /**< constraint name */
905  SCIP_Bool* conflictFound /**< conflict with existing vertex changes found? */
906 )
907 {
908  assert(vertexchgs && consname && conflictFound);
909 
910  *conflictFound = FALSE;
911 
912  /* terminal inclusion constraint? */
913  if( strncmp(consname, "consin", 6) == 0 )
914  {
915  char* tailptr;
916  const int term = (int) strtol(consname + 6, &tailptr, 10);
917 
918  SCIPdebugMessage("mark terminal %d \n", term);
919 
920  if( BRANCH_STP_VERTEX_KILLED == vertexchgs[term] )
921  {
922  SCIPdebugMessage("conflict found for vertex %d: try to fix deleted vertex \n", term);
923  *conflictFound = TRUE;
924  }
925 
926  vertexchgs[term] = BRANCH_STP_VERTEX_TERM;
927  }
928  /* node removal constraint? */
929  else if( strncmp(consname, "consout", 7) == 0 )
930  {
931  char* tailptr;
932  const int vert = (int) strtol(consname + 7, &tailptr, 10);
933 
934  SCIPdebugMessage("mark deleted node %d \n", vert);
935 
936  if( BRANCH_STP_VERTEX_TERM == vertexchgs[vert] )
937  {
938  SCIPdebugMessage("conflict found for vertex %d: try to delete terminal \n", vert);
939  *conflictFound = TRUE;
940  }
941 
942  vertexchgs[vert] = BRANCH_STP_VERTEX_KILLED;
943  }
944  else
945  {
946  printf("found unknown constraint at b&b node \n");
947  return SCIP_ERROR;
948  }
949 
950  return SCIP_OKAY;
951 }
952 
953 /** applies vertex changes caused by this branching rule, either on a graph or on an array */
955  const GRAPH* g, /**< graph data structure */
956  int* nodestate /**< node state array */
957  )
958 {
959  const int nnodes = g->knots;
960 
961  assert(g != NULL);
962  assert(nodestate != NULL);
963 
964  assert(nnodes > 0);
965 
966  for( int k = 0; k < nnodes; k++ )
967  {
968  if( Is_term(g->term[k]) )
969  nodestate[k] = BRANCH_STP_VERTEX_TERM;
970  else
971  nodestate[k] = BRANCH_STP_VERTEX_NONTERM;
972  }
973 }
974 
975 
976 /** applies vertex changes caused by this branching rule, either on a graph or on an array */
978  SCIP* scip, /**< SCIP data structure */
979  int* vertexchgs, /**< array to store changes */
980  SCIP_Bool* conflictFound /**< conflict with existing vertex changes found? */
981  )
982 {
983  SCIP_CONS* parentcons;
984  SCIP_BRANCHRULE* branchrule = NULL;
985  SCIP_BRANCHRULEDATA* branchruledata;
986  int naddedconss;
987 
988  assert(scip && vertexchgs && conflictFound);
989 
990  *conflictFound = FALSE;
991  branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
992  assert(branchrule != NULL);
993  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
994 
995  branchruledata = SCIPbranchruleGetData(branchrule);
996  assert(branchruledata != NULL);
997 
998  if( !(branchruledata->active) )
999  {
1000  SCIPerrorMessage("STP branchrule not active! \n");
1001  return SCIP_ERROR;
1002  }
1003 
1004  assert(SCIPnodeGetNAddedConss(SCIPgetCurrentNode(scip)) == 1);
1005 
1006  /* not very clean, but this should only happen when the whole b&b tree is explored */
1007  if( SCIPnodeGetNAddedConss(SCIPgetCurrentNode(scip)) != 1 )
1008  return SCIP_OKAY;
1009 
1010  /* move up branch-and-bound path and check constraints */
1011  for( SCIP_NODE* node = SCIPgetCurrentNode(scip); SCIPnodeGetDepth(node) > 0; node = SCIPnodeGetParent(node) )
1012  {
1013  SCIP_Bool localconflict = FALSE;
1014  char* consname;
1015 
1016  assert(SCIPnodeGetNAddedConss(node) == 1);
1017 
1018  if( SCIPnodeGetNAddedConss(node) != 1 )
1019  break;
1020 
1021  /* get constraints */
1022  SCIPnodeGetAddedConss(node, &parentcons, &naddedconss, 1);
1023  consname = (char*) SCIPconsGetName(parentcons);
1024 
1025  SCIP_CALL( STPStpBranchruleParseConsname(vertexchgs, consname, &localconflict) );
1026 
1027  if( localconflict )
1028  *conflictFound = TRUE;
1029  }
1030 
1031  return SCIP_OKAY;
1032 }
1033 
1034 
1035 /** get last change */
1037  SCIP* scip, /**< SCIP data structure */
1038  int* vertex, /**< changed vertex */
1039  SCIP_Bool* isDeleted /**< deleted? (otherwise terminal) */
1040  )
1041 {
1042  char* consname;
1043  SCIP_CONS* cons;
1044  SCIP_BRANCHRULE* branchrule = NULL;
1045  SCIP_BRANCHRULEDATA* branchruledata;
1046  int naddedconss;
1047 
1048  branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
1049  assert(branchrule != NULL);
1050  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
1051 
1052  branchruledata = SCIPbranchruleGetData(branchrule);
1053  assert(branchruledata != NULL);
1054 
1055  *vertex = -1;
1056 
1057  if( !(branchruledata->active) )
1058  {
1059  SCIPerrorMessage("STP branchrule not active! \n");
1060  return SCIP_ERROR;
1061  }
1062 
1063  assert(SCIPnodeGetNAddedConss(SCIPgetCurrentNode(scip)) == 1);
1064 
1065  SCIPnodeGetAddedConss(SCIPgetCurrentNode(scip), &cons, &naddedconss, 1);
1066  consname = (char*) SCIPconsGetName(cons);
1067 
1068  if( strncmp(consname, "consin", 6) == 0 )
1069  {
1070  char *tailptr;
1071  const int term = (int) strtol(consname + 6, &tailptr, 10);
1072 
1073  SCIPdebugMessage("mark terminal %d \n", term);
1074  *vertex = term;
1075  *isDeleted = FALSE;
1076  }
1077  /* node removal constraint? */
1078  else if( strncmp(consname, "consout", 7) == 0 )
1079  {
1080  char *tailptr;
1081  const int vert = (int) strtol(consname + 7, &tailptr, 10);
1082 
1083  SCIPdebugMessage("mark deleted node %d \n", vert);
1084 
1085  *vertex = vert;
1086  *isDeleted = TRUE;
1087  }
1088  else
1089  {
1090  printf("found unknown constraint at b&b node \n");
1091  return SCIP_ERROR;
1092  }
1093 
1094  return SCIP_OKAY;
1095 }
1096 
1097 
1098 /** is the branching rule active? */
1100  SCIP* scip /**< SCIP data structure */
1101  )
1102 {
1103  SCIP_BRANCHRULE* branchrule = NULL;
1104  SCIP_BRANCHRULEDATA* branchruledata;
1105 
1106  branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
1107  assert(branchrule != NULL);
1108  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
1109 
1110  branchruledata = SCIPbranchruleGetData(branchrule);
1111  assert(branchruledata != NULL);
1112 
1113  return branchruledata->active;
1114 }
1115 
1116 
1117 
1118 /** returns whether branching-rule is compatible with given graph problem type */
1120  const GRAPH* graph /**< graph */
1121 )
1122 {
1123  assert(graph);
1124 
1125  return probIsCompatible(graph);
1126 }
1127 
1128 /** creates the stp branching rule and includes it in SCIP */
1130  SCIP* scip /**< SCIP data structure */
1131  )
1132 {
1133  SCIP_BRANCHRULEDATA* branchruledata;
1134  SCIP_BRANCHRULE* branchrule;
1135 
1136  /* create stp branching rule data */
1137  SCIP_CALL( SCIPallocMemory(scip, &branchruledata) );
1138  branchruledata->branchtypeIsFixed = FALSE;
1139 
1140  /* include branching rule */
1142  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
1143 
1144  assert(branchrule != NULL);
1145 
1146  /* set non fundamental callbacks via setter functions */
1147  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyStp) );
1148  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeStp) );
1149  SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitStp) );
1150  SCIP_CALL( SCIPsetBranchruleExit(scip, branchrule, branchExitStp) );
1151  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpStp) );
1152  SCIP_CALL( SCIPsetBranchruleExecPs(scip, branchrule, branchExecpsStp) );
1153 
1154  SCIP_CALL( SCIPaddIntParam(scip, "branching/stp/type",
1155  "Branching: 0 based on LP, 1 based on LP and with indegree > 1, 2 based on best solution,"
1156  "3 based on degree",
1157  &(branchruledata->branchtype), FALSE, BRANCH_STP_ON_LP, 0, 3, NULL, NULL) );
1158 
1159  SCIP_CALL( SCIPaddBoolParam(scip, "branching/stp/vertexbranching",
1160  "use branching on vertices?",
1161  &(branchruledata->active), FALSE, TRUE, NULL, NULL) );
1162 
1163  return SCIP_OKAY;
1164 }
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
void graph_knot_chg(GRAPH *, int, int)
Definition: graph_node.c:86
static SCIP_RETCODE selectBranchingVertexByLp2Flow(SCIP *scip, int *vertex, const GRAPH *g)
Definition: branch_stp.c:557
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1840
SCIP_Bool graph_pc_isMw(const GRAPH *)
int *RESTRICT head
Definition: graphdefs.h:224
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:82
#define BRANCHRULE_PRIORITY
Definition: branch_stp.c:45
public methods for branch and bound tree
int source
Definition: graphdefs.h:195
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:272
SCIP_RETCODE SCIPStpBranchruleGetVertexChgs(SCIP *scip, int *vertexchgs, SCIP_Bool *conflictFound)
Definition: branch_stp.c:977
SCIP_Bool graph_pc_isRootedPcMw(const GRAPH *)
static void applyBranchHistoryToGraph(SCIP *scip, const int *nodestatenew, GRAPH *graph)
Definition: branch_stp.c:191
#define Is_term(a)
Definition: graphdefs.h:102
static SCIP_DECL_BRANCHEXECLP(branchExeclpStp)
Definition: branch_stp.c:752
SCIP_Bool graph_valid(SCIP *, const GRAPH *)
Definition: graph_base.c:1480
#define SCIP_MAXSTRLEN
Definition: def.h:293
int terms
Definition: graphdefs.h:192
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:48
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7712
includes methods for Steiner tree problem solutions
SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: scip_branch.c:192
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:160
SCIP_RETCODE SCIPincludeBranchruleStp(SCIP *scip)
Definition: branch_stp.c:1129
SCIP_RETCODE SCIPStpBranchruleGetVertexChgLast(SCIP *scip, int *vertex, SCIP_Bool *isDeleted)
Definition: branch_stp.c:1036
SCIP_RETCODE SCIPStpHeurTMRunLP(SCIP *scip, GRAPH *graph, SCIP_HEUR *heur, int *result, int runs, SCIP_Bool *success)
Definition: heur_tm.c:3509
#define FALSE
Definition: def.h:87
int *RESTRICT inpbeg
Definition: graphdefs.h:202
static SCIP_Bool probAllowsSolBranching(const GRAPH *graph)
Definition: branch_stp.c:89
void SCIPStpBranchruleInitNodeState(const GRAPH *g, int *nodestate)
Definition: branch_stp.c:954
#define BRANCHRULE_DESC
Definition: branch_stp.c:44
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
Problem data for stp problem.
#define TRUE
Definition: def.h:86
static SCIP_DECL_BRANCHEXIT(branchExitStp)
Definition: branch_stp.c:743
void graph_pc_enforceNonLeafTerm(SCIP *, GRAPH *, int)
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:144
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:288
#define STP_DCSTP
Definition: graphdefs.h:47
int SCIPprobdataGetNVars(SCIP *scip)
static int branchruleGetType(SCIP *scip, const GRAPH *g, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch_stp.c:99
static GRAPHNODE ** active
#define EAT_LAST
Definition: graphdefs.h:58
#define SCIPdebugMessage
Definition: pub_message.h:87
#define FARAWAY
Definition: graphdefs.h:89
SCIP_RETCODE SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
Definition: scip_branch.c:107
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7442
static SCIP_Bool probIsCompatible(const GRAPH *graph)
Definition: branch_stp.c:79
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
#define Is_nonleafTerm(a)
Definition: graphdefs.h:104
Constraint handler for the set partitioning / packing / covering constraints .
SCIP_Real * cost_org_pc
Definition: graphdefs.h:222
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 SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:240
SCIP_RETCODE STPStpBranchruleParseConsname(int *vertexchgs, const char *consname, SCIP_Bool *conflictFound)
Definition: branch_stp.c:902
#define BRANCHRULE_NAME
Definition: branch_stp.c:43
int *RESTRICT oeat
Definition: graphdefs.h:231
static SCIP_DECL_BRANCHCOPY(branchCopyStp)
Definition: branch_stp.c:699
#define BRANCH_STP_VERTEX_NONTERM
Definition: branch_stp.h:38
SCIP_Bool extended
Definition: graphdefs.h:267
int stp_type
Definition: graphdefs.h:264
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPprobdataProbIsAdversarial(SCIP *scip)
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:128
SCIP_Real * prize
Definition: graphdefs.h:210
SCIP_RETCODE SCIPprobdataAddNewSol(SCIP *scip, SCIP_Real *nval, SCIP_HEUR *heur, SCIP_Bool *success)
#define BRANCH_STP_ON_LP2
Definition: branch_stp.c:51
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8085
int *RESTRICT grad
Definition: graphdefs.h:201
#define BRANCHRULE_TMRUNS_SPG
Definition: branch_stp.c:49
#define BRANCHRULE_TMRUNS
Definition: branch_stp.c:48
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_RETCODE SCIPStpHeurLocalRun(SCIP *scip, GRAPH *graph, int *solEdges)
Definition: heur_local.c:3899
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18284
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1008
SCIP_Bool SCIPStpBranchruleIsActive(SCIP *scip)
Definition: branch_stp.c:1099
int knots
Definition: graphdefs.h:190
static int getHighSolDegVertex(const int *nodestatenew, const int *soledges, const GRAPH *graph)
Definition: branch_stp.c:142
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:384
#define BRANCHRULE_MAXBOUNDDIST
Definition: branch_stp.c:47
SCIP main data structure.
int * term2edge
Definition: graphdefs.h:208
Improvement heuristic for Steiner problems.
static SCIP_DECL_BRANCHINIT(branchInitStp)
Definition: branch_stp.c:729
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:74
void graph_pc_enforcePseudoTerm(SCIP *, GRAPH *, int)
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip_prob.c:3322
internal methods for problem variables
propagator for Steiner tree problems, using the LP reduced costs
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define SCIP_Bool
Definition: def.h:84
int *RESTRICT ieat
Definition: graphdefs.h:230
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
#define BRANCH_STP_ON_LP
Definition: branch_stp.c:50
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1850
#define BRANCH_STP_VERTEX_TERM
Definition: branch_stp.h:39
SCIP_VAR ** SCIPprobdataGetEdgeVars(SCIP *scip)
#define flipedge(edge)
Definition: graphdefs.h:84
#define STP_TERM
Definition: graphdefs.h:61
int *RESTRICT term
Definition: graphdefs.h:196
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
SCIP_Bool SCIPStpBranchruleProbIsCompatible(const GRAPH *graph)
Definition: branch_stp.c:1119
static SCIP_DECL_BRANCHFREE(branchFreeStp)
Definition: branch_stp.c:713
Constraint handler for linear constraints in their most general form, .
SCIP_Bool graph_pc_isPc(const GRAPH *)
#define BRANCH_STP_VERTEX_KILLED
Definition: branch_stp.h:37
#define CONNECT
Definition: graphdefs.h:87
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
#define BRANCHRULE_MAXDEPTH
Definition: branch_stp.c:46
Steiner vertex branching rule.
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
#define BRANCH_STP_ON_DEGREE
Definition: branch_stp.c:53
#define Is_pseudoTerm(a)
Definition: graphdefs.h:103
#define BRANCH_STP_ON_SOL
Definition: branch_stp.c:52
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:963
static SCIP_RETCODE selectBranchingVertexBySol(SCIP *scip, int *vertex, SCIP_Bool addsol)
Definition: branch_stp.c:344
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
SCIP_Real * cost
Definition: graphdefs.h:221
static SCIP_RETCODE selectBranchingVertexByDegree(SCIP *scip, int *vertex, const GRAPH *g)
Definition: branch_stp.c:280
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
static SCIP_DECL_BRANCHEXECPS(branchExecpsStp)
Definition: branch_stp.c:835
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
SCIP_VAR * a
Definition: circlepacking.c:57
#define SCIPstatistic(x)
Definition: pub_message.h:111
#define SCIP_Real
Definition: def.h:177
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1962
#define BLOCKED
Definition: graphdefs.h:90
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip_branch.c:176
int *RESTRICT outbeg
Definition: graphdefs.h:204
#define STP_BRMWCSP
Definition: graphdefs.h:55
shortest paths based primal heuristics for Steiner problems
int edges
Definition: graphdefs.h:219
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
static SCIP_RETCODE selectBranchingVertexByLp(SCIP *scip, int *vertex, const GRAPH *g)
Definition: branch_stp.c:480
int SCIPnodeGetNAddedConss(SCIP_NODE *node)
Definition: tree.c:1702
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
#define UNKNOWN
Definition: sepa_mcf.c:4095
#define nnodes
Definition: gastrans.c:65
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
#define Is_anyTerm(a)
Definition: graphdefs.h:105
SCIP_Bool graph_typeIsSpgLike(const GRAPH *)
Definition: graph_stats.c:57
void SCIPnodeGetAddedConss(SCIP_NODE *node, SCIP_CONS **addedconss, int *naddedconss, int addedconsssize)
Definition: tree.c:1672
void graph_pc_nonTermToFixedTerm(GRAPH *, int, SCIP_Real *)
GRAPH * SCIPprobdataGetGraph2(SCIP *scip)
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
static SCIP_RETCODE branchOnVertex(SCIP *scip, const GRAPH *g, int branchvertex)
Definition: branch_stp.c:632