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-2019 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 /**@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 
27 #include <assert.h>
28 #include <string.h>
29 #include "scip/branch_fullstrong.h"
30 #include "scip/cons_linear.h"
31 #include "scip/cons_setppc.h"
32 #include "scip/var.h"
33 #include "scip/set.h"
34 #include "scip/pub_tree.h"
35 #include "scip/struct_scip.h"
36 #include "scip/clock.h"
37 #include "grph.h"
38 #include "heur_tm.h"
39 #include "heur_local.h"
40 #include "branch_stp.h"
41 #include "prop_stp.h"
42 #include "probdata_stp.h"
43 #include "scip/pub_tree.h"
44 
45 #define BRANCHRULE_NAME "stp"
46 #define BRANCHRULE_DESC "stp branching on vertices"
47 #define BRANCHRULE_PRIORITY 10000000
48 #define BRANCHRULE_MAXDEPTH -1
49 #define BRANCHRULE_MAXBOUNDDIST 1.0
50 #define BRANCHRULE_TMRUNS 20
51 
52 #define BRANCH_STP_ON_LP 0
53 #define BRANCH_STP_ON_LP2 1
54 #define BRANCH_STP_ON_SOL 2
55 
56 
57 /*
58  * Data structures
59  */
60 
61 /** branching rule data */
62 struct SCIP_BranchruleData
63 {
64  int lastcand; /**< last evaluated candidate of last branching rule execution */
65  int branchtype; /**< type of branching */
66 };
67 
68 
69 /*
70  * Local methods
71  */
72 
73 
74 /** check whether branching-rule is compatible with given problem type */
75 static
77  int probtype /**< the problem type */
78 )
79 {
80  return (probtype == STP_SPG || probtype == STP_RSMT || probtype == STP_OARSMT
81  || probtype == STP_PCSPG || probtype == STP_RPCSPG);
82 }
83 
84 /** select vertex to branch on by choosing vertex of highest degree */
85 static
87  SCIP* scip, /**< original SCIP data structure */
88  int* vertex, /**< the vertex to branch on */
89  const GRAPH* g /**< graph */
90  )
91 {
92  int* nodestate;
93  int maxdegree = 0;
94  const int nnodes = g->knots;
95  const SCIP_Bool pcmw = graph_pc_isPcMw(g);
96 
97  SCIP_CALL( SCIPallocBufferArray(scip, &nodestate, nnodes) );
98 
99  *vertex = UNKNOWN;
100 
101  SCIPStpBranchruleInitNodeState(g, nodestate);
102 
103  SCIP_CALL( SCIPStpBranchruleApplyVertexChgs(scip, nodestate, NULL) );
104 
105  for( int k = 0; k < nnodes; k++ )
106  {
107  if( nodestate[k] == BRANCH_STP_VERTEX_NONTERM && (g->grad[k] > maxdegree
108  || (pcmw && Is_pterm(g->term[k]))) )
109  {
110  assert(!Is_term(g->term[k]));
111 
112  maxdegree = g->grad[k];
113  *vertex = k;
114 
115  if( pcmw && Is_pterm(g->term[k]) )
116  maxdegree = nnodes;
117  }
118  }
119 
120  SCIPdebugMessage("vertex selected by degree branching rule: %d \n\n", *vertex);
121 
122  SCIPfreeBufferArray(scip, &nodestate);
123 
124  return SCIP_OKAY;
125 }
126 
127 /** select vertex to branch on by using primal solution */
128 static
130  SCIP* scip, /**< original SCIP data structure */
131  int* vertex, /**< the vertex to branch on */
132  SCIP_Bool addsol /**< add new solution to pool? */
133  )
134 {
135  GRAPH* graph;
136  SCIP_Real* cost;
137  SCIP_Real* costrev;
138  int* soledges;
139  int* nodestatenew;
140  int* termorg;
141 
142  SCIP_Bool success;
143  int nedges;
144  int nnodes;
145  int maxdeg;
146 
147  assert(vertex != NULL);
148  *vertex = UNKNOWN;
149 
150  /* check whether LP solution is available */
152  return SCIP_OKAY;
153 
154  graph = SCIPprobdataGetGraph2(scip);
155  assert(graph != NULL);
156 
157  nedges = graph->edges;
158  nnodes = graph->knots;
159 
160  /*
161  * compute locally feasible solution (SPH + local)
162  */
163 
164  SCIP_CALL( SCIPallocBufferArray(scip, &cost, nedges) );
165  SCIP_CALL( SCIPallocBufferArray(scip, &costrev, nedges) );
166  SCIP_CALL( SCIPallocBufferArray(scip, &soledges, nedges) );
167  SCIP_CALL( SCIPallocBufferArray(scip, &nodestatenew, nnodes) );
168  SCIP_CALL( SCIPallocBufferArray(scip, &termorg, nnodes) );
169 
170  for( int k = 0; k < nnodes; k++ )
171  {
172  if( Is_term(graph->term[k]) )
173  nodestatenew[k] = BRANCH_STP_VERTEX_TERM;
174  else
175  nodestatenew[k] = BRANCH_STP_VERTEX_NONTERM;
176  }
177 
178  BMScopyMemoryArray(termorg, graph->term, nnodes);
179 
180  /* get vertex changes from branch-and-bound */
181  if( SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) != 0 )
182  SCIP_CALL( SCIPStpBranchruleApplyVertexChgs(scip, nodestatenew, NULL) );
183 
184  /* currently not supported because of next loop */
185  assert(!graph_pc_isPcMw(graph));
186 
187  for( int k = 0; k < nnodes; k++ )
188  if( !Is_term(graph->term[k]) && nodestatenew[k] == BRANCH_STP_VERTEX_TERM )
189  {
190  assert(graph->grad[k] > 0);
191  graph_knot_chg(graph, k, 0);
192  }
193 
194  SCIP_CALL( SCIPStpHeurTMRunLP(scip, graph, NULL, soledges, BRANCHRULE_TMRUNS, cost, costrev, &success) );
195  assert(success);
196  SCIP_CALL( SCIPStpHeurLocalRun(scip, graph, graph->cost, soledges) );
197 
198  assert(graph_sol_valid(scip, graph, soledges));
199 
200  for( int k = 0; k < nnodes; k++ )
201  if( graph->term[k] != termorg[k] )
202  graph_knot_chg(graph, k, termorg[k]);
203 
204  assert(graph_sol_valid(scip, graph, soledges));
205 
206  if( addsol )
207  {
208  SCIP_SOL* sol = NULL;
209 
210  const int nvars = SCIPprobdataGetNVars(scip);
211 
212  assert(graph->edges == nvars);
213 
214  /* use cost array to store solution */
215  for( int e = 0; e < nvars; e++ )
216  if( soledges[e] == CONNECT )
217  cost[e] = 1.0;
218  else
219  cost[e] = 0.0;
220 
221  SCIP_CALL( SCIPprobdataAddNewSol(scip, cost, sol, NULL, &success) );
222  SCIPdebugMessage("solution added? %d \n", success);
223  }
224 
225  /* get vertex with highest degree in solution */
226  maxdeg = -1;
227  for( int i = 0; i < nnodes; i++ )
228  {
229  if( nodestatenew[i] == BRANCH_STP_VERTEX_NONTERM && graph->grad[i] != 0 )
230  {
231  int soldeg = 0;
232  for( int e = graph->outbeg[i]; e != EAT_LAST; e = graph->oeat[e] )
233  if( soledges[e] == CONNECT || soledges[flipedge(e)] == CONNECT )
234  soldeg++;
235  if( soldeg > maxdeg )
236  {
237  maxdeg = soldeg;
238  *vertex = i;
239  }
240  }
241  }
242 
243  SCIPfreeBufferArray(scip, &termorg);
244  SCIPfreeBufferArray(scip, &nodestatenew);
245  SCIPfreeBufferArray(scip, &soledges);
246  SCIPfreeBufferArray(scip, &costrev);
247  SCIPfreeBufferArray(scip, &cost);
248 
249  return SCIP_OKAY;
250 }
251 
252 /** select vertex to branch on by using LP */
253 static
255  SCIP* scip, /**< original SCIP data structure */
256  int* vertex, /**< the vertex to branch on */
257  const GRAPH* g /**< graph */
258  )
259 {
260  SCIP_VAR** edgevars;
261  SCIP_Real bestflow;
262  const int nnodes = g->knots;
263 
264  assert(g != NULL && vertex != NULL);
265 
266  *vertex = UNKNOWN;
267 
268  /* LP has not been solved */
270  return SCIP_OKAY;
271 
272  edgevars = SCIPprobdataGetEdgeVars(scip);
273  assert(edgevars != NULL);
274 
275  bestflow = 1.0;
276  for( int k = 0; k < nnodes; k++ )
277  {
278  SCIP_Real inflow = 0.0;
279  for( int a = g->inpbeg[k]; a != EAT_LAST; a = g->ieat[a] )
280  inflow += SCIPvarGetLPSol(edgevars[a]);
281 
282  if( !Is_term(g->term[k]) && SCIPisLT(scip, inflow, 1.0) && fabs(inflow - 0.5) < bestflow && SCIPisPositive(scip, inflow) )
283  {
284  *vertex = k;
285  bestflow = fabs(inflow - 0.5);
286  SCIPdebugMessage("new maxflow %f on vertex %d \n", inflow, k );
287  }
288  }
289 
290  SCIPdebugMessage("maxflow %f on vertex %d, term? %d \n", bestflow, *vertex, Is_term(g->term[*vertex]) );
291 
292  return SCIP_OKAY;
293 }
294 
295 /** select vertices with flow on at least two incoming arcs */
296 static
298  SCIP* scip, /**< original SCIP data structure */
299  int* vertex, /**< the vertex to branch on */
300  const GRAPH* g /**< graph */
301  )
302 {
303  SCIP_VAR** edgevars;
304  int* nodestate;
305  SCIP_Real bestflow;
306  const int nnodes = g->knots;
307 
308  assert(g != NULL && vertex != NULL);
309 
310  *vertex = UNKNOWN;
311 
312  /* has LP not been solved? */
314  return SCIP_OKAY;
315 
316  SCIP_CALL( SCIPallocBufferArray(scip, &nodestate, nnodes) );
317 
318  for( int k = 0; k < nnodes; k++ )
319  {
320  if( Is_term(g->term[k]) )
321  nodestate[k] = BRANCH_STP_VERTEX_TERM;
322  else
323  nodestate[k] = BRANCH_STP_VERTEX_NONTERM;
324  }
325 
326  /* get vertex changes from branch-and-bound */
327  if( SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) != 0 )
328  SCIP_CALL( SCIPStpBranchruleApplyVertexChgs(scip, nodestate, NULL) );
329 
330  edgevars = SCIPprobdataGetEdgeVars(scip);
331  assert(edgevars != NULL);
332 
333  bestflow = 1.0;
334  for( int k = 0; k < nnodes; k++ )
335  {
336  if( nodestate[k] == BRANCH_STP_VERTEX_NONTERM )
337  {
338  int ninarcs = 0;
339  assert(g->grad[k] > 0);
340  assert(!Is_term(g->term[k]));
341 
342  for( int a = g->inpbeg[k]; a != EAT_LAST; a = g->ieat[a] )
343  if( SCIPisPositive(scip, SCIPvarGetLPSol(edgevars[a])) )
344  ninarcs++;
345 
346  if( ninarcs > 1 )
347  {
348  SCIP_Real inflow = 0.0;
349  for( int a = g->inpbeg[k]; a != EAT_LAST; a = g->ieat[a] )
350  inflow += SCIPvarGetLPSol(edgevars[a]);
351 
352  if( fabs(inflow - 0.5) < bestflow )
353  {
354  *vertex = k;
355  bestflow = fabs(inflow - 0.5);
356  SCIPdebugMessage("new maxflow %f on vertex %d \n", inflow, k );
357  }
358  }
359  }
360  }
361 
362  SCIPfreeBufferArray(scip, &nodestate);
363 
364  SCIPdebugMessage("LP2: branch on vertex %d with abs(flow - 0.5): %f \n", *vertex, bestflow);
365 
366  return SCIP_OKAY;
367 }
368 
369 
370 /** branch on specified (Steiner) vertex */
371 static
373  SCIP* scip, /**< SCIP data structure */
374  const GRAPH* g, /**< graph data structure */
375  int branchvertex /**< the vertex to branch on */
376  )
377 {
378  char consnamein[SCIP_MAXSTRLEN];
379  char consnameout[SCIP_MAXSTRLEN];
380  SCIP_CONS* consin = NULL;
381  SCIP_CONS* consout = NULL;
382  SCIP_NODE* vertexin = NULL;
383  SCIP_NODE* vertexout = NULL;
384  SCIP_VAR** const edgevars = SCIPprobdataGetEdgeVars(scip);
385  const SCIP_Real estimatein = SCIPgetUpperbound(scip);
386  const SCIP_Real estimateout = SCIPgetUpperbound(scip);
387 
388  assert(scip != NULL);
389  assert(g != NULL);
390  assert(branchvertex >= 0 && branchvertex < g->knots);
391  assert(!Is_term(g->term[branchvertex]));
392 
393  (void) SCIPsnprintf(consnamein, SCIP_MAXSTRLEN, "consin%d", branchvertex);
394  (void) SCIPsnprintf(consnameout, SCIP_MAXSTRLEN, "consout%d", branchvertex);
395 
396  /* create constraints */
397  SCIP_CALL( SCIPcreateConsSetpart(scip, &consin,
398  consnamein, 0, NULL, TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE) );
399 
400  SCIP_CALL( SCIPcreateConsLinear(scip, &consout,
401  consnameout, 0, NULL, NULL, 0.0, 0.0, TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE) );
402 
403  for( int e = g->inpbeg[branchvertex]; e != EAT_LAST; e = g->ieat[e] )
404  {
405  SCIP_CALL(SCIPaddCoefSetppc(scip, consin, edgevars[e]));
406  SCIP_CALL(SCIPaddCoefLinear(scip, consout, edgevars[e], 1.0));
407  SCIP_CALL(SCIPaddCoefLinear(scip, consout, edgevars[flipedge(e)], 1.0));
408  }
409 
410  /* create the child nodes */
411  SCIP_CALL(SCIPcreateChild(scip, &vertexin, 1.0, estimatein));
412  SCIP_CALL(SCIPcreateChild(scip, &vertexout, 1.0, estimateout));
413 
414  assert(vertexin != NULL);
415  assert(vertexout != NULL);
416 
417  SCIP_CALL(SCIPaddConsNode(scip, vertexin, consin, NULL));
418  SCIP_CALL(SCIPaddConsNode(scip, vertexout, consout, NULL));
419 
420  /* release constraints */
421  SCIP_CALL(SCIPreleaseCons(scip, &consin));
422  SCIP_CALL(SCIPreleaseCons(scip, &consout));
423 
424  return SCIP_OKAY;
425 }
426 
427 
428 /*
429  * Callback methods of branching rule
430  */
431 
432 /** copy method for branchrule plugins (called when SCIP copies plugins) */
433 static
434 SCIP_DECL_BRANCHCOPY(branchCopyStp)
435 { /*lint --e{715}*/
436  assert(scip != NULL);
437  assert(branchrule != NULL);
438  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
439 
440  /* call inclusion method of branchrule */
442 
443  return SCIP_OKAY;
444 }
445 
446 /** destructor of branching rule to free user data (called when SCIP is exiting) */
447 static
448 SCIP_DECL_BRANCHFREE(branchFreeStp)
449 { /*lint --e{715}*/
450  SCIP_BRANCHRULEDATA* branchruledata;
451 
452  /* free branching rule data */
453  branchruledata = SCIPbranchruleGetData(branchrule);
454  assert(branchruledata != NULL);
455 
456  SCIPfreeMemory(scip, &branchruledata);
457  SCIPbranchruleSetData(branchrule, NULL);
458 
459  return SCIP_OKAY;
460 }
461 
462 /** initialization method of branching rule (called after problem was transformed) */
463 static
464 SCIP_DECL_BRANCHINIT(branchInitStp)
465 { /*lint --e{715}*/
466  SCIP_BRANCHRULEDATA* branchruledata;
467 
468  branchruledata = SCIPbranchruleGetData(branchrule);
469  assert(branchruledata != NULL);
470 
471  branchruledata->lastcand = 0;
472 
473  return SCIP_OKAY;
474 }
475 
476 /** deinitialization method of branching rule (called before transformed problem is freed) */
477 static
478 SCIP_DECL_BRANCHEXIT(branchExitStp)
479 { /*lint --e{715}*/
480 #if 0
481  SCIP_BRANCHRULEDATA* branchruledata;
482 #endif
483  SCIPstatistic(int j = 0);
484 
485 #if 0
486  /* initialize branching rule data */
487  branchruledata = SCIPbranchruleGetData(branchrule);
488  assert(branchruledata != NULL);
489 #endif
490  return SCIP_OKAY;
491 }
492 
493 /** branching execution method for fractional LP solutions */
494 static
495 SCIP_DECL_BRANCHEXECLP(branchExeclpStp)
496 { /*lint --e{715}*/
497  SCIP_PROBDATA* probdata;
498  SCIP_BRANCHRULEDATA* branchruledata;
499  GRAPH* g;
500  int branchvertex;
501 
502  assert(branchrule != NULL);
503  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
504  assert(scip != NULL);
505  assert(result != NULL);
506 
507  SCIPdebugMessage("Execlp method of STP branching\n ");
508  *result = SCIP_DIDNOTRUN;
509 
510  /* get branching rule data */
511  branchruledata = SCIPbranchruleGetData(branchrule);
512  assert(branchruledata != NULL);
513 
514  /* get problem data */
515  probdata = SCIPgetProbData(scip);
516  assert(probdata != NULL);
517 
518  /* get graph */
519  g = SCIPprobdataGetGraph(probdata);
520  assert(g != NULL);
521 
522  if( !isProbCompatible(g->stp_type) )
523  return SCIP_OKAY;
524 
525  /* get vertex to branch on */
526  if( branchruledata->branchtype == BRANCH_STP_ON_LP )
527  SCIP_CALL( selectBranchingVertexByLp(scip, &branchvertex, g) );
528  else if( branchruledata->branchtype == BRANCH_STP_ON_LP2 )
529  SCIP_CALL( selectBranchingVertexByLp2Flow(scip, &branchvertex, g) );
530  else
531  {
532  assert(branchruledata->branchtype == BRANCH_STP_ON_SOL);
533  SCIP_CALL( selectBranchingVertexBySol(scip, &branchvertex, TRUE) );
534  }
535 
536  /* fall-back strategy */
537  if( branchvertex == UNKNOWN )
538  SCIP_CALL( selectBranchingVertexByDegree(scip, &branchvertex, g) );
539 
540  /* we should only have terminals in this case */
541  if( branchvertex == UNKNOWN )
542  {
543  SCIPdebugMessage("Stp branching did not run \n");
544  return SCIP_OKAY;
545  }
546 
547  SCIP_CALL( branchOnVertex(scip, g, branchvertex) );
548 
549  SCIPdebugMessage("Branched on stp vertex %d \n", branchvertex);
550 
551  *result = SCIP_BRANCHED;
552 
553  return SCIP_OKAY;
554 }
555 
556 
557 /** branching execution method for not completely fixed pseudo solutions */
558 static
559 SCIP_DECL_BRANCHEXECPS(branchExecpsStp)
560 { /*lint --e{715}*/
561  SCIP_PROBDATA* probdata;
562  GRAPH* g;
563  int branchvertex;
564 
565  assert(branchrule != NULL);
566  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
567  assert(scip != NULL);
568  assert(result != NULL);
569 
570  SCIPdebugMsg(scip, "Execps method of STP branching\n");
571  *result = SCIP_DIDNOTRUN;
572 
573  probdata = SCIPgetProbData(scip);
574  assert(probdata != NULL);
575 
576  g = SCIPprobdataGetGraph(probdata);
577  assert(g != NULL);
578 
579  if( !isProbCompatible(g->stp_type) )
580  return SCIP_OKAY;
581 
582  /* select vertex to branch on */
583  SCIP_CALL( selectBranchingVertexByDegree(scip, &branchvertex, g) );
584 
585  if( branchvertex == UNKNOWN )
586  {
587  SCIPdebugMessage("Stp branching did not run \n");
588  return SCIP_OKAY;
589  }
590 
591  SCIP_CALL( branchOnVertex(scip, g, branchvertex) );
592 
593  *result = SCIP_BRANCHED;
594 
595  return SCIP_OKAY;
596 }
597 
598 
599 /*
600  * branching rule specific interface methods
601  */
602 
603 /** parse constraint name and apply changes to graph or array */
605  SCIP* scip, /**< SCIP data structure */
606  int* vertexchgs, /**< array to store changes or NULL */
607  GRAPH* graph, /**< graph to modify or NULL */
608  const char* consname, /**< constraint name */
609  SCIP_Bool deletehistory /**< delete history of graph? */
610 )
611 {
612  /* terminal inclusion constraint? */
613  if( strncmp(consname, "consin", 6) == 0 )
614  {
615  char* tailptr;
616  const int term = (int) strtol(consname + 6, &tailptr, 10);
617 
618  SCIPdebugMessage("make terminal %d \n", term);
619 
620  if( graph != NULL && !Is_term(graph->term[term]) )
621  {
622  if( graph->stp_type == STP_PCSPG )
623  {
624  if( Is_pterm(graph->term[term]) )
625  graph_pc_chgPrize(scip, graph, FARAWAY, term);
626  }
627  else if( graph->stp_type == STP_RPCSPG )
628  {
629  assert(0 && "not implemented");
630  }
631  else
632  {
633  graph_knot_chg(graph, term, 0);
634  }
635  }
636 
637  if( vertexchgs != NULL )
638  vertexchgs[term] = BRANCH_STP_VERTEX_TERM;
639  }
640  /* node removal constraint? */
641  else if( strncmp(consname, "consout", 7) == 0 )
642  {
643  char* tailptr;
644  const int vert = (int) strtol(consname + 7, &tailptr, 10);
645 
646  SCIPdebugMessage("delete vertex %d \n", vert);
647 
648  if( graph != NULL )
649  {
650  assert(!Is_term(graph->term[vert]));
651 
652  if( graph->stp_type == STP_PCSPG )
653  {
654  if( Is_pterm(graph->term[vert]) )
655  {
656  // todo fix arc vars
657  graph_pc_deleteTerm(scip, graph, vert);
658  }
659  graph_knot_del(scip, graph, vert, deletehistory);
660  }
661  else if( graph->stp_type == STP_RPCSPG )
662  {
663  assert(0 && "not implemented");
664  }
665  else
666  {
667  graph_knot_del(scip, graph, vert, deletehistory);
668  }
669  }
670 
671  if( vertexchgs != NULL )
672  vertexchgs[vert] = BRANCH_STP_VERTEX_KILLED;
673  }
674  else
675  {
676  printf("found unknown constraint at b&b node \n");
677  return SCIP_ERROR;
678  }
679  return SCIP_OKAY;
680 }
681 
682 /** applies vertex changes caused by this branching rule, either on a graph or on an array */
684  const GRAPH* g, /**< graph data structure */
685  int* nodestate /**< node state array */
686  )
687 {
688  const int nnodes = g->knots;
689 
690  assert(g != NULL);
691  assert(nodestate != NULL);
692 
693  assert(nnodes > 0);
694 
695  for( int k = 0; k < nnodes; k++ )
696  {
697  if( g->grad[k] == 0 )
698  nodestate[k] = BRANCH_STP_VERTEX_KILLED;
699  else if( Is_term(g->term[k]) )
700  nodestate[k] = BRANCH_STP_VERTEX_TERM;
701  else
702  nodestate[k] = BRANCH_STP_VERTEX_NONTERM;
703  }
704 }
705 
706 
707 /** applies vertex changes caused by this branching rule, either on a graph or on an array */
709  SCIP* scip, /**< SCIP data structure */
710  int* vertexchgs, /**< array to store changes or NULL */
711  GRAPH* graph /**< graph to apply changes on or NULL */
712  )
713 {
714  SCIP_CONS* parentcons;
715  int naddedconss;
716 
717  assert(scip != NULL);
718  assert(graph != NULL || vertexchgs != NULL);
719 
720  assert(SCIPnodeGetNAddedConss(SCIPgetCurrentNode(scip)) == 1);
721 
722  /* not very clean, but this should only happen when the whole b&b tree is explored */
724  return SCIP_OKAY;
725 
726  /* move up branch-and-bound path and check constraints */
727  for( SCIP_NODE* node = SCIPgetCurrentNode(scip); SCIPnodeGetDepth(node) > 0; node = SCIPnodeGetParent(node) )
728  {
729  char* consname;
730 
731  assert(SCIPnodeGetNAddedConss(node) == 1);
732 
733  if( SCIPnodeGetNAddedConss(node) != 1 )
734  break;
735 
736  /* get constraints */
737  SCIPnodeGetAddedConss(node, &parentcons, &naddedconss, 1);
738  consname = (char*) SCIPconsGetName(parentcons);
739 
740  SCIP_CALL( STPStpBranchruleParseConsname(scip, vertexchgs, graph, consname, TRUE) );
741  }
742 
743  return SCIP_OKAY;
744 }
745 
746 /** creates the multi-aggregated branching rule and includes it in SCIP */
748  SCIP* scip /**< SCIP data structure */
749  )
750 {
751  SCIP_BRANCHRULEDATA* branchruledata;
752  SCIP_BRANCHRULE* branchrule;
753 
754  /* create stp branching rule data */
755  SCIP_CALL( SCIPallocMemory(scip, &branchruledata) );
756  branchruledata->lastcand = 0;
757 
758  /* include branching rule */
760  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
761 
762  assert(branchrule != NULL);
763 
764  /* set non fundamental callbacks via setter functions */
765  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyStp) );
766  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeStp) );
767  SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitStp) );
768  SCIP_CALL( SCIPsetBranchruleExit(scip, branchrule, branchExitStp) );
769  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpStp) );
770  SCIP_CALL( SCIPsetBranchruleExecPs(scip, branchrule, branchExecpsStp) );
771 
772  SCIP_CALL( SCIPaddIntParam(scip, "branching/stp/type",
773  "Branching: 0 based on LP, 1 based on LP and with indegree > 1, 2 based on best solution",
774  &(branchruledata->branchtype), FALSE, BRANCH_STP_ON_LP, 0, 2, NULL, NULL) );
775 
776  return SCIP_OKAY;
777 }
static SCIP_RETCODE selectBranchingVertexByLp2Flow(SCIP *scip, int *vertex, const GRAPH *g)
Definition: branch_stp.c:297
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1848
#define NULL
Definition: def.h:246
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:158
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9229
#define BRANCHRULE_PRIORITY
Definition: branch_stp.c:47
Definition: grph.h:57
public methods for branch and bound tree
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:270
static SCIP_DECL_BRANCHEXECLP(branchExeclpStp)
Definition: branch_stp.c:495
#define SCIP_MAXSTRLEN
Definition: def.h:267
internal methods for clocks and timing issues
void graph_knot_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: grphbase.c:2242
int graph_pc_deleteTerm(SCIP *, GRAPH *, int)
Definition: grphbase.c:1941
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:43
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7627
#define EAT_LAST
Definition: grph.h:31
SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: scip_branch.c:190
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:158
SCIP_RETCODE SCIPincludeBranchruleStp(SCIP *scip)
Definition: branch_stp.c:747
#define FALSE
Definition: def.h:72
int *RESTRICT inpbeg
Definition: grph.h:74
void SCIPStpBranchruleInitNodeState(const GRAPH *g, int *nodestate)
Definition: branch_stp.c:683
#define BRANCHRULE_DESC
Definition: branch_stp.c:46
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10253
Problem data for stp problem.
#define TRUE
Definition: def.h:71
static SCIP_DECL_BRANCHEXIT(branchExitStp)
Definition: branch_stp.c:478
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:142
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
int SCIPprobdataGetNVars(SCIP *scip)
#define STP_PCSPG
Definition: grph.h:40
#define SCIPdebugMessage
Definition: pub_message.h:77
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:105
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7357
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIPdebugMsg
Definition: scip_message.h:88
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:155
void graph_knot_chg(GRAPH *, int, int)
Definition: grphbase.c:2218
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:238
#define BRANCHRULE_NAME
Definition: branch_stp.c:45
int *RESTRICT oeat
Definition: grph.h:103
#define CONNECT
Definition: grph.h:154
static SCIP_DECL_BRANCHCOPY(branchCopyStp)
Definition: branch_stp.c:434
#define BRANCH_STP_VERTEX_NONTERM
Definition: branch_stp.h:37
int stp_type
Definition: grph.h:127
SCIP_RETCODE STPStpBranchruleParseConsname(SCIP *scip, int *vertexchgs, GRAPH *graph, const char *consname, SCIP_Bool deletehistory)
Definition: branch_stp.c:604
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define Is_pterm(a)
Definition: grph.h:169
SCIP_RETCODE SCIPprobdataAddNewSol(SCIP *scip, SCIP_Real *nval, SCIP_SOL *sol, SCIP_HEUR *heur, SCIP_Bool *success)
#define BRANCH_STP_ON_LP2
Definition: branch_stp.c:53
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8076
int *RESTRICT grad
Definition: grph.h:73
SCIP_RETCODE SCIPcreateConsSetpart(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, 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)
Definition: cons_setppc.c:9058
#define BRANCHRULE_TMRUNS
Definition: branch_stp.c:50
SCIP_Bool graph_sol_valid(SCIP *, const GRAPH *, const int *)
Definition: grphbase.c:3066
SCIPInterval fabs(const SCIPInterval &x)
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:17718
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:959
int knots
Definition: grph.h:62
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:358
#define BRANCHRULE_MAXBOUNDDIST
Definition: branch_stp.c:49
SCIP main data structure.
Improvement heuristic for Steiner problems.
static SCIP_DECL_BRANCHINIT(branchInitStp)
Definition: branch_stp.c:464
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:141
#define FARAWAY
Definition: grph.h:156
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip_prob.c:3376
#define STP_SPG
Definition: grph.h:38
internal methods for problem variables
propagator for Steiner tree problems, using the LP reduced costs
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
full strong LP branching rule
static SCIP_Bool isProbCompatible(int probtype)
Definition: branch_stp.c:76
#define SCIP_Bool
Definition: def.h:69
int *RESTRICT ieat
Definition: grph.h:102
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:226
#define BRANCH_STP_ON_LP
Definition: branch_stp.c:52
void graph_pc_chgPrize(SCIP *, GRAPH *, SCIP_Real, int)
Definition: grphbase.c:2031
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1858
#define BRANCH_STP_VERTEX_TERM
Definition: branch_stp.h:38
SCIP_VAR ** SCIPprobdataGetEdgeVars(SCIP *scip)
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
Definition: grphbase.c:2184
int *RESTRICT term
Definition: grph.h:68
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:123
static SCIP_DECL_BRANCHFREE(branchFreeStp)
Definition: branch_stp.c:448
Constraint handler for linear constraints in their most general form, .
includes various files containing graph methods used for Steiner tree problems
#define BRANCH_STP_VERTEX_KILLED
Definition: branch_stp.h:36
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:86
#define BRANCHRULE_MAXDEPTH
Definition: branch_stp.c:48
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_SOL
Definition: branch_stp.c:54
#define Is_term(a)
Definition: grph.h:168
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
SCIP_RETCODE SCIPStpBranchruleApplyVertexChgs(SCIP *scip, int *vertexchgs, GRAPH *graph)
Definition: branch_stp.c:708
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:1020
static SCIP_RETCODE selectBranchingVertexBySol(SCIP *scip, int *vertex, SCIP_Bool addsol)
Definition: branch_stp.c:129
SCIP_Real * cost
Definition: grph.h:94
static SCIP_RETCODE selectBranchingVertexByDegree(SCIP *scip, int *vertex, const GRAPH *g)
Definition: branch_stp.c:86
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1187
static SCIP_DECL_BRANCHEXECPS(branchExecpsStp)
Definition: branch_stp.c:559
SCIP_VAR * a
Definition: circlepacking.c:57
#define SCIPstatistic(x)
Definition: pub_message.h:101
#define SCIP_Real
Definition: def.h:157
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1970
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip_branch.c:174
int *RESTRICT outbeg
Definition: grph.h:76
SCIP_RETCODE SCIPStpHeurLocalRun(SCIP *scip, GRAPH *graph, const SCIP_Real *cost, int *best_result)
Definition: heur_local.c:208
shortest paths based primal heuristics for Steiner problems
int edges
Definition: grph.h:92
#define flipedge(edge)
Definition: grph.h:150
SCIP_RETCODE SCIPStpHeurTMRunLP(SCIP *scip, GRAPH *graph, SCIP_HEUR *heur, int *result, int runs, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Bool *success)
Definition: heur_tm.c:2353
static SCIP_RETCODE selectBranchingVertexByLp(SCIP *scip, int *vertex, const GRAPH *g)
Definition: branch_stp.c:254
int SCIPnodeGetNAddedConss(SCIP_NODE *node)
Definition: tree.c:1668
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:70
#define UNKNOWN
Definition: sepa_mcf.c:4081
#define STP_RSMT
Definition: grph.h:45
#define nnodes
Definition: gastrans.c:65
#define STP_OARSMT
Definition: grph.h:46
SCIP_Real SCIPgetUpperbound(SCIP *scip)
void SCIPnodeGetAddedConss(SCIP_NODE *node, SCIP_CONS **addedconss, int *naddedconss, int addedconsssize)
Definition: tree.c:1638
#define STP_RPCSPG
Definition: grph.h:41
GRAPH * SCIPprobdataGetGraph2(SCIP *scip)
static SCIP_RETCODE branchOnVertex(SCIP *scip, const GRAPH *g, int branchvertex)
Definition: branch_stp.c:372