Scippy

SCIP

Solving Constraint Integer Programs

branch_strongcoloring.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 branch_strongcoloring.c
17  * @brief branching rule performing strong branching for the vertex coloring problem
18  * @author Gerald Gamrath
19  *
20  * This file implements an additional branching rule for the coloring algorithm.
21  *
22  * We are looking for two nodes v and w, which are not adjacent in the current graph, and consider
23  * the following two constraints: SAME(v,w) and DIFFER(v,w). More information about the meaning of
24  * these constraints can be found in the documentation of the branching rule in branch_coloring.c.
25  *
26  * This branching rule puts some more effort into the choice of the two nodes and performs a
27  * strongbranching. This means that for every possible choice of two nodes, it solves the LPs of the
28  * created children and computes a score with respect to the increase of the lower bound in both
29  * nodes. After that, it takes the combination of nodes yielding the best score. The interesting
30  * point is that the strongbranching is not performed for each variable, as it is done in some
31  * default branching rules of SCIP and supported by the LP-solver, but is done for a constraint,
32  * since we are branching on constraints. Look at executeStrongBranching() to see how it is
33  * done. There are also some improvements, since testing all possible combination of nodes is very
34  * expensive. The first possibility to avoid this is to stop the computation of scores once a
35  * possible branching is found that has only one feasible child. This results in more restrictions
36  * in this child without increasing the number of unprocessed nodes.
37  *
38  * The second improvement is to compute a priority for all possible combinations, w.r.t. the
39  * fractional values of the variables. Then, only the first best k combinations are investigated by
40  * strongbranching.
41  *
42  * This code is not optimized and in most cases inferior to the standard branching rule. It is only
43  * a demonstration of how to perform strongbranching on constraints!
44  */
45 
46 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
47 #include <assert.h>
48 #include <string.h>
49 
50 #include "branch_strongcoloring.h"
51 #include "pricer_coloring.h"
52 
53 #define BRANCHRULE_NAME "strongcoloring"
54 #define BRANCHRULE_DESC "branching rule template"
55 #define BRANCHRULE_PRIORITY 15000
56 #define BRANCHRULE_MAXDEPTH -1
57 #define BRANCHRULE_MAXBOUNDDIST 1.0
58 
59 /* default values for parameters */
60 #define DEFAULT_BRANCHINGMODE 2
61 #define DEFAULT_FIXINGSSCOREMODE 3
62 #define DEFAULT_MAXPRICINGROUNDS -1
63 #define DEFAULT_USETCLIQUE TRUE
64 #define DEFAULT_LOOKAHEAD 10
65 
66 
67 
68 /*
69  * Data structures
70  */
71 
72 /** branching rule data */
73 struct SCIP_BranchruleData
74 {
75  int branchingmode; /* determines the branchingmode, 0: for fullstrong branching,
76  1: strong branching, take first possible branching with only one child-node
77  2: strong branching with prior sorting of candidates w.r.t. the fractional value of concerned sets */
78  int length; /* length of the arrays samevalue and differvalue, length = n*(n-1)/2 with n = NNodes*/
79  SCIP_Real* samevalue; /* value of variables, that would be fixed to 0 for same(i,j), index = nodes2index(i,j) */
80  SCIP_Real* differvalue; /* value of variables, that would be fixed to 0 for differ(i,j), index = nodes2index(i,j) */
81  SCIP_Real* combinedvalue; /* combination of samevalue and differvalue, computed by computeScore*/
82  int* permutation; /* permutation of the indexes of the array combinedvalue, s.t. it is sorted */
83  SCIP_Bool usetclique; /* should the exact pricing with the tclique-algorithm be used for the strongbranchings? */
84  int maxpricingrounds; /* maximal number of pricing rounds used for each probing node in the strongbranching */
85  int lookahead; /* number of candidates to be considered in branchingmode 2 */
86  int fixingsscoremode; /* determines the weightings of the two factors for prior sorting by fractional LP value */
87 
88 };
89 
90 
91 
92 
93 /*
94  * Local methods
95  */
96 
97 /** computes a score for the two improvements that are achieved in the two sons for a branching decision */
98 static
99 double computeScore(
100  SCIP_Real val1, /**< the first value */
101  SCIP_Real val2 /**< the second value */
102  )
103 {
104  return 0.2 * MAX( val1, val2 ) + 0.8 * MIN( val1, val2 );
105 }
106 
107 /** computes a score for the fractional values of the variables that would be fixed to zero for a same- or differ-branching */
108 static
110  SCIP_Real samevalue, /**< value of the fractional variables fixed to 0 for a same-branching*/
111  SCIP_Real differvalue, /**< value of the fractional variables fixed to 0 for a differ-branching*/
112  SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */
113  )
114 {
115  if ( branchruledata->fixingsscoremode == 1 )
116  {
117  return 3*samevalue+differvalue;
118  }
119  if ( branchruledata->fixingsscoremode == 2 )
120  {
121  return 2*samevalue+differvalue;
122  }
123  if ( branchruledata->fixingsscoremode == 3 )
124  {
125  return samevalue+10*differvalue;
126  }
127  if ( branchruledata->fixingsscoremode == 4 )
128  {
129  if ( samevalue == -1 && differvalue == -1 )
130  return -1;
131  return samevalue*differvalue;
132  }
133  return samevalue*differvalue;
134 }
135 
136 /** for given nodes node1, node2, compute the corresponding index in the arrays branchruledata->same-/differvalue */
137 static
139  SCIP* scip, /**< SCIP data structure */
140  int node1, /**< the first node */
141  int node2 /**< the second node */
142  )
143 {
144  int ind;
145  int nnodes;
146  int i;
147 
148  assert(scip != NULL);
149  assert(node1 >= 0 && node2 >= 0);
150 
151  /* node 1 has to be smaller than node 2 */
152  if ( node1 > node2 )
153  {
154  ind = node1;
155  node1 = node2;
156  node2 = ind;
157  }
158  nnodes = COLORprobGetNNodes(scip);
159  assert(node1 < nnodes && node2 < nnodes);
160  ind = 0;
161  for ( i = 0; i < node1; i++ )
162  ind += (nnodes - i - 1);
163  ind += ( node2-node1-1);
164  return ind;
165 }
166 
167 /** for given index of the arrays branchruledata->same-/differvalue, compute the two nodes, the index represents */
168 static
170  SCIP* scip, /**< SCIP data structure */
171  int ind, /**< the given index in the arrays */
172  int* node1, /**< return value: the first node */
173  int* node2 /**< return value: the second node */
174  )
175 {
176  int nnodes;
177  int value;
178 
179  assert(scip != NULL);
180  assert(node2 != NULL && node1 != NULL);
181 
182  nnodes = COLORprobGetNNodes(scip);
183  *node1 = 0;
184  value = 0;
185  while ( value + nnodes - 1 - *node1 <= ind )
186  {
187  value += (nnodes - 1 - *node1);
188  *node1 = *node1 + 1;
189  }
190  *node2 = *node1 + 1 + (ind - value);
191 }
192 
193 /** computes for each pair of nodes (i,j) two values, one for same (i,j), the other for differ(i,j) which are the sum of
194  the values of variables with fractional parts, that would be fixed for this decision
195  asd */
196 static
198  SCIP* scip, /**< SCIP data structure */
199  SCIP_BRANCHRULEDATA* branchruledata /**< the data of the branching rule */
200  )
201 {
202  SCIP_VAR** lpcands;
203  SCIP_Real* lpcandsfrac;
204  TCLIQUE_GRAPH* graph;
205  int nlpcands;
206  int i;
207  int j;
208  int k;
209  int node1;
210  int node2;
211  SCIP_VAR* var;
212  int setindex;
213  int* set;
214  int setlength;
215  int nnodes;
216 
217  assert(scip != NULL);
218  assert(branchruledata != NULL);
219 
220  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, NULL, &lpcandsfrac, &nlpcands, NULL, NULL) );
221  nnodes = COLORprobGetNNodes(scip);
222  graph = COLORconsGetCurrentGraph(scip);
223 
224  assert(graph != NULL);
225  assert(nnodes >= 0);
226 
227  /* fill array samevalue, differvalue with zeroes, or -1 for impossible branchings */
228  for ( i = 0; i < branchruledata->length; i++ )
229  {
230  index2nodes(scip, i, &node1, &node2);
231  /* there is an edge between node1 and node2 --> no branching possible --> set value to -1 */
232  if ( tcliqueIsEdge(graph, node1, node2) )
233  {
234  branchruledata->samevalue[i] = -1;
235  branchruledata->differvalue[i] = -1;
236  continue;
237  }
238  branchruledata->samevalue[i] = 0;
239  branchruledata->differvalue[i] = 0;
240  }
241 
242  /* for all branching candidates (variables with fractional value) check for which branching decisions they would be
243  fixed to 0 and add the fractional part to the related entry in the array samevalue or differvalue */
244  for ( i = 0; i < nlpcands; i++ )
245  {
246  assert(SCIPisFeasPositive(scip, lpcandsfrac[i]));
247  var = lpcands[i];
248  setindex = (int)(size_t) SCIPvarGetData(var);
249  COLORprobGetStableSet(scip, setindex, &set, &setlength);
250  for ( j = 0; j < setlength; j++ )
251  {
252  node1 = set[j];
253  /* if node1 is part of a union and not its representant, continue */
254  if ( COLORconsGetRepresentative(scip, node1) != node1 )
255  {
256  continue;
257  }
258  k = 0;
259  for ( node2 = nnodes-1; node2 >= 0; node2-- )
260  {
261  /* if k is a node, which is part of, but not representant of a union, increment k */
262  while ( k < setlength && COLORconsGetRepresentative(scip, set[k]) != set[k] )
263  {
264  k++;
265  }
266  /* node1 is equal to node2 -> increment k and continue */
267  if ( node2 == node1 )
268  {
269  assert(k == j);
270  k++;
271  continue;
272  }
273  /* if node2 is part of a union and not its representant, continue */
274  if ( COLORconsGetRepresentative(scip, node2) != node2 )
275  continue;
276  /* if there is an edge between node1 and node2 in the current graph, continue */
277  if ( branchruledata->differvalue[nodes2index(scip, node1, node2)] == -1 )
278  {
279  continue;
280  }
281  /* node2 is also in the set --> the variable would be fixed to 0 for differ(node1, node2) */
282  if ( k < setlength && node2 == set[k] )
283  {
284  branchruledata->differvalue[nodes2index(scip, node1, node2)] += lpcandsfrac[i];
285  assert(COLORprobIsNodeInStableSet(scip, setindex, node1) && COLORprobIsNodeInStableSet(scip, setindex, node2));
286  k++;
287  }
288  /* node2 is not in the set --> the variable would be fixed to 0 for same(node1, node2) */
289  else
290  {
291  branchruledata->samevalue[nodes2index(scip, node1, node2)] += lpcandsfrac[i];
292  assert(COLORprobIsNodeInStableSet(scip, setindex, node1) && !COLORprobIsNodeInStableSet(scip, setindex, node2));
293  }
294  }
295  assert(k == setlength);
296  }
297  }
298 
299  return SCIP_OKAY;
300 
301 }
302 
303 
304 
305 /** computes the lower bound that would a child node with the given branching decision would have */
306 static
308  SCIP* scip, /**< SCIP data structure */
309  COLOR_CONSTYPE constype, /**< the type of the contraint: SAME or DIFFER */
310  int node1, /**< the first node for the branching constraint */
311  int node2, /**< the second node for the branching constraint */
312  SCIP_BRANCHRULEDATA* branchruledata, /**< the data of the branching rule */
313  SCIP_Real* newlb /**< pointer to store the resulting value */
314  )
315 {
316  SCIP_NODE* newnode;
317  SCIP_CONS* currentcons;
318  SCIP_CONS* cons;
319  SCIP_Bool cutoff;
320  SCIP_Bool lperror;
321 
322  assert(scip != NULL);
323  assert(newlb != NULL);
324 
325  /* get the constraint of the current Node in the B&B-Tree */
326  currentcons = COLORconsGetActiveStoreGraphCons(scip);
327 
328  /* start Probing */
329  SCIP_CALL( SCIPstartProbing(scip) );
330 
331  /* create new probing node and add store graph cons to it with same(node1, node2) */
332  SCIP_CALL( SCIPnewProbingNode(scip) );
333  newnode = SCIPgetCurrentNode(scip);
334  SCIP_CALL( COLORcreateConsStoreGraph(scip, &cons, "probingcons", currentcons, constype, node1, node2, newnode) );
335  SCIP_CALL( SCIPaddConsNode(scip, newnode, cons, NULL) );
336  /* propagate the new b&b-node, i.e. fix vars to 0 that don't contain both node1 and node2 */
337  SCIP_CALL( SCIPpropagateProbing(scip, -1, &cutoff, NULL) );
338  /* solve the LP using pricing */
339  SCIP_CALL( SCIPsolveProbingLPWithPricing(scip, FALSE, FALSE, branchruledata->maxpricingrounds, &lperror, &cutoff) );
340  assert(!lperror);
341  assert(!cutoff);
342  /* get the changed objective value */
343  *newlb = SCIPgetLPObjval(scip);
344 
345  SCIP_CALL( SCIPdelCons(scip, cons) );
346  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
347  SCIP_CALL( SCIPendProbing(scip) );
348 
349  return SCIP_OKAY;
350 }
351 
352 
353 /** index comparison method two values in a real array */
354 static
355 SCIP_DECL_SORTINDCOMP(consdataCompValues)
356 {
357  SCIP_Real* values;
358 
359  values = (SCIP_Real*)dataptr;
360 
361  assert(values != NULL);
362 
363  if ( values[ind1] > values[ind2] )
364  {
365  return -1;
366  }
367  if ( values[ind1] < values[ind2] )
368  {
369  return 1;
370  }
371  return 0;
372 }
373 
374 
375 /*
376  * Callback methods of branching rule
377  */
378 
379 /** copy method for branchrule plugins (called when SCIP copies plugins) */
380 static
381 SCIP_DECL_BRANCHCOPY(branchCopyStrongcoloring)
382 { /*lint --e{715}*/
383  assert(scip != NULL);
384  assert(branchrule != NULL);
385  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
386 
387  return SCIP_OKAY;
388 }
389 
390 
391 /** branching execution method for fractional LP solutions */
392 static
393 SCIP_DECL_BRANCHEXECLP(branchExeclpStrongcoloring)
394 {
395  /* the 2 nodes, for which the branching is done by DIFFER and SAME */
396  int node1;
397  int node2;
398  /* the nodes in the branch&bound-tree which are created */
399  SCIP_NODE* childsame;
400  SCIP_NODE* childdiffer;
401  /* the constraints for the created b&b-nodes */
402  SCIP_CONS* conssame;
403  SCIP_CONS* consdiffer;
404  /* the constraint of the processed b&b-node */
405  SCIP_CONS* currentcons;
406 
407  int i;
408  int j;
409  int nnodes;
410 
411  SCIP_Bool* wasnode1;
412  SCIP_Bool* wasnode2;
413  SCIP_Bool start;
414  TCLIQUE_GRAPH* graph;
415  SCIP_Real currLb;
416  SCIP_Real sameLb;
417  SCIP_Real differLb;
418 
419  SCIP_Real bestscore;
420  SCIP_Real bestdiffer;
421  SCIP_Real bestsame;
422  SCIP_Real score;
423  int bestnode2;
424  int bestnode1;
425 
426  SCIP_BRANCHRULEDATA* branchruledata;
427 
428 #ifndef NDEBUG
429  SCIP_NODE* node;
430 #endif
431 
432  assert(scip != NULL);
433  assert(branchrule != NULL);
434  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
435  assert(result != NULL);
436 
437  *result = SCIP_DIDNOTRUN;
438 
439  /* get branching rule data */
440  branchruledata = SCIPbranchruleGetData(branchrule);
441  nnodes = COLORprobGetNNodes(scip);
443 
444  if ( branchruledata->branchingmode == 2 )
445  {
446  SCIP_CALL( computeBranchingPriorities(scip, branchruledata) );
447 
448  for ( i = 0; i < branchruledata->length; i++ )
449  {
450  branchruledata->combinedvalue[i] = computeFixingsScore(branchruledata->samevalue[i], branchruledata->differvalue[i], branchruledata);
451  }
452  /* get permutation of indexes, so that the array is sorted */
453  /** @todo could be improved by only getting the k best indexes */
454  SCIPsort(branchruledata->permutation, consdataCompValues, branchruledata->combinedvalue, branchruledata->length);
455 
456  bestscore = -1;
457  bestnode1 = -1;
458  bestnode2 = -1;
459  bestdiffer = -1;
460  bestsame = -1;
461 
462  for ( i = 0; i < branchruledata->lookahead && i < branchruledata->length; i++ )
463  {
464  index2nodes(scip, branchruledata->permutation[i], &node1, &node2);
465  currLb = SCIPgetLPObjval(scip);
466 
467  /* SAME */
468  SCIP_CALL( executeStrongBranching(scip, COLOR_CONSTYPE_SAME, node1, node2, branchruledata, &sameLb) );
469  if ( sameLb-currLb > 1000 )
470  {
471  sameLb = currLb + 1000;
472  }
473 
474  /* DIFFER */
475  SCIP_CALL( executeStrongBranching(scip, COLOR_CONSTYPE_DIFFER, node1, node2, branchruledata, &differLb) );
476  if ( differLb-currLb > 1000 )
477  {
478  differLb = currLb + 1000;
479  }
480 
481  score = computeScore( sameLb - currLb, differLb-currLb );
482  assert( !SCIPisFeasZero(scip, score) || (SCIPisFeasZero(scip, 0.2 * (sameLb-currLb)) && SCIPisFeasZero(scip, 0.2 * (differLb-currLb))
483  && (SCIPisFeasZero(scip, sameLb-currLb) || SCIPisFeasZero(scip, differLb-currLb))) );
484 
485  if ( score > bestscore )
486  {
487  bestscore = score;
488  bestnode1 = node1;
489  bestnode2 = node2;
490  bestdiffer = differLb-currLb;
491  bestsame = sameLb-currLb;
492  }
493  if ( bestdiffer > 999 || bestsame > 999 )
494  {
495  break;
496  }
497  }
498 
499  }
500  else
501  {
502  assert(branchruledata->branchingmode == 0 || branchruledata->branchingmode == 1);
503  /* create array wasnode1 and wasnode2 and fill them with FALSE */
504  SCIP_CALL( SCIPallocBufferArray(scip, &wasnode1, nnodes) );
505  BMSclearMemoryArray(wasnode1, nnodes);
506  SCIP_CALL( SCIPallocBufferArray(scip, &wasnode2, nnodes) );
507 
508  bestscore = -1;
509  bestnode1 = -1;
510  bestnode2 = -1;
511  bestdiffer = -1;
512  bestsame = -1;
513 
514  SCIP_CALL( SCIPsetBoolParam(scip, "pricers/coloring/usetclique", branchruledata->usetclique) );
515 #ifndef NDEBUG
516  node = SCIPgetCurrentNode(scip);
517 #endif
518  currentcons = COLORconsGetActiveStoreGraphCons(scip);
519 
520  start = TRUE;
521  for ( i = SCIPgetDepth(scip)%nnodes; (start || (i != SCIPgetDepth(scip)%nnodes)); i=((i+1)%nnodes) )
522  {
523  start = FALSE;
524  node1 = COLORconsGetRepresentative(scip, i);
525  /* check whether node1 was already tested */
526  if ( wasnode1[node1] == TRUE )
527  {
528  continue;
529  }
530  else
531  {
532  wasnode1[node1] = TRUE;
533  }
534  BMSclearMemoryArray(wasnode2, nnodes);
535 
536  for ( j = i+1; j < nnodes; j++ )
537  {
538  node2 = COLORconsGetRepresentative(scip, j);
539  if ( node2 == node1 || tcliqueIsEdge(graph, node1, node2) || node2 < i )
540  {
541  continue;
542  }
543  else
544  {
545  /* check whether node2 was already tested */
546  if ( wasnode2[node2] == TRUE ) continue;
547  else wasnode2[node2] = TRUE;
548 
549  currLb = SCIPgetLPObjval(scip);
550 
551  assert(currentcons == COLORconsGetActiveStoreGraphCons(scip));
552  assert(node == SCIPgetCurrentNode(scip));
553 
554  /* compute lower bounds for possible branchings */
555 
556  /* SAME */
557  SCIP_CALL( executeStrongBranching(scip, COLOR_CONSTYPE_SAME, node1, node2, branchruledata, &sameLb) );
558  if ( sameLb-currLb > 1000 )
559  {
560  sameLb = currLb + 1000;
561  }
562 
563  /* DIFFER */
564  SCIP_CALL( executeStrongBranching(scip, COLOR_CONSTYPE_DIFFER, node1, node2, branchruledata, &differLb) );
565  if ( differLb-currLb > 1000 )
566  {
567  differLb = currLb + 1000;
568  }
569 
570  score = computeScore( sameLb-currLb, differLb-currLb );
571  if ( score > bestscore )
572  {
573  bestscore = score;
574  bestnode1 = node1;
575  bestnode2 = node2;
576  bestdiffer = differLb-currLb;
577  bestsame = sameLb-currLb;
578  }
579  if ( (branchruledata->branchingmode == 1) && (bestdiffer > 999 || bestsame > 999) )
580  {
581  break;
582  }
583 
584  }
585  }
586  if ( (branchruledata->branchingmode == 1) && (bestdiffer > 999 || bestsame > 999) )
587  {
588  break;
589  }
590  }
591 
592  SCIP_CALL( SCIPsetBoolParam(scip, "pricers/coloring/usetclique", TRUE) );
593  assert(node == SCIPgetCurrentNode(scip));
594  assert(currentcons == COLORconsGetActiveStoreGraphCons(scip));
595 
596  SCIPfreeBufferArray(scip, &wasnode2);
597  SCIPfreeBufferArray(scip, &wasnode1);
598 
599  }
600 
601  assert(!SCIPisSumNegative(scip, bestscore));
602 
603  node1 = bestnode1;
604  node2 = bestnode2;
605 
606  /* branchingmode >= 1 --> only create nodes, that do not have a LP solution that is much bigger than the lower bound */
607  if ( branchruledata->branchingmode >= 1 && branchruledata->usetclique == TRUE )
608  {
609  *result = SCIP_CUTOFF;
610  currentcons = COLORconsGetActiveStoreGraphCons(scip);
611 
612  if ( bestdiffer <= 999 )
613  {
614  /* create the b&b-tree child-nodes of the current node */
616 
617  /* create corresponding constraints */
618  SCIP_CALL( COLORcreateConsStoreGraph(scip, &consdiffer, "differ", currentcons, COLOR_CONSTYPE_DIFFER, node1, node2, childdiffer) );
619 
620  /* add constraints to nodes */
621  SCIP_CALL( SCIPaddConsNode(scip, childdiffer, consdiffer, NULL) );
622 
623  /* release constraints */
624  SCIP_CALL( SCIPreleaseCons(scip, &consdiffer) );
625 
626  *result = SCIP_BRANCHED;
627  }
628 
629  if ( bestsame <= 999 )
630  {
631  /* create the b&b-tree child-nodes of the current node */
633 
634  /* create corresponding constraints */
635  SCIP_CALL( COLORcreateConsStoreGraph(scip, &conssame, "same", currentcons, COLOR_CONSTYPE_SAME, node1, node2, childsame) );
636 
637  /* add constraints to nodes */
638  SCIP_CALL( SCIPaddConsNode(scip, childsame, conssame, NULL) );
639 
640  /* release constraints */
641  SCIP_CALL( SCIPreleaseCons(scip, &conssame) );
642 
643  *result = SCIP_BRANCHED;
644  }
645  }
646  /* create both children */
647  else
648  {
651 
652  /* create the b&b-tree child-nodes of the current node */
655 
656  /* create corresponding constraints */
657  currentcons = COLORconsGetActiveStoreGraphCons(scip);
658  SCIP_CALL( COLORcreateConsStoreGraph(scip, &conssame, "same", currentcons, COLOR_CONSTYPE_SAME, node1, node2, childsame) );
659  SCIP_CALL( COLORcreateConsStoreGraph(scip, &consdiffer, "differ", currentcons, COLOR_CONSTYPE_DIFFER, node1, node2, childdiffer) );
660 
661  /* add constraints to nodes */
662  SCIP_CALL( SCIPaddConsNode(scip, childsame, conssame, NULL) );
663  SCIP_CALL( SCIPaddConsNode(scip, childdiffer, consdiffer, NULL) );
664 
665  /* release constraints */
666  SCIP_CALL( SCIPreleaseCons(scip, &conssame) );
667  SCIP_CALL( SCIPreleaseCons(scip, &consdiffer) );
668 
669  *result = SCIP_BRANCHED;
670  }
671 
672  return SCIP_OKAY;
673 }/*lint !e715*/
674 
675 
676 /** destructor of branching rule to free user data (called when SCIP is exiting) */
677 static
678 SCIP_DECL_BRANCHFREE(branchFreeStrongcoloring)
679 {
680  SCIP_BRANCHRULEDATA* branchruledata;
681 
682  /* free branching rule data */
683  branchruledata = SCIPbranchruleGetData(branchrule);
684  SCIPfreeBlockMemory(scip, &branchruledata);
685  SCIPbranchruleSetData(branchrule, NULL);
686 
687  return SCIP_OKAY;
688 }
689 
690 /** initialization method of branching rule (called after problem was transformed) */
691 static
692 SCIP_DECL_BRANCHINIT(branchInitStrongcoloring)
693 {
694  SCIP_BRANCHRULEDATA* branchruledata;
695 
696  /* get branching rule data */
697  branchruledata = SCIPbranchruleGetData(branchrule);
698  assert(branchruledata != NULL);
699 
700  /* get memory for the arrays */
701  branchruledata->length = (COLORprobGetNNodes(scip)*(COLORprobGetNNodes(scip)-1))/2;
702  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(branchruledata->samevalue), branchruledata->length) );
703  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(branchruledata->differvalue), branchruledata->length) );
704  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(branchruledata->combinedvalue), branchruledata->length) );
705  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(branchruledata->permutation), branchruledata->length) );
706 
707  return SCIP_OKAY;
708 }
709 
710 /** deinitialization method of branching rule (called before transformed problem is freed) */
711 static
712 SCIP_DECL_BRANCHEXIT(branchExitStrongcoloring)
713 {
714  SCIP_BRANCHRULEDATA* branchruledata;
715 
716  /* get branching rule data */
717  branchruledata = SCIPbranchruleGetData(branchrule);
718  assert(branchruledata != NULL);
719 
720  /* free arrays */
721  SCIPfreeBlockMemoryArray(scip, &(branchruledata->samevalue), branchruledata->length);
722  SCIPfreeBlockMemoryArray(scip, &(branchruledata->differvalue), branchruledata->length);
723  SCIPfreeBlockMemoryArray(scip, &(branchruledata->combinedvalue), branchruledata->length);
724  SCIPfreeBlockMemoryArray(scip, &(branchruledata->permutation), branchruledata->length);
725 
726  return SCIP_OKAY;
727 }
728 
729 /*
730  * branching rule specific interface methods
731  */
732 
733 /** creates the coloring branching rule and includes it in SCIP */
735  SCIP* scip /**< SCIP data structure */
736  )
737 {
738  SCIP_BRANCHRULEDATA* branchruledata;
739  SCIP_BRANCHRULE* branchrule;
740 
741  assert(scip != NULL);
742 
743  /* create branching rule data */
744  SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
745 
746  branchrule = NULL;
747  /* include branching rule */
749  BRANCHRULE_MAXBOUNDDIST, branchruledata) );
750  assert(branchrule != NULL);
751 
752  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyStrongcoloring) );
753  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeStrongcoloring) );
754  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpStrongcoloring) );
755  SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitStrongcoloring) );
756  SCIP_CALL( SCIPsetBranchruleExit(scip, branchrule, branchExitStrongcoloring) );
757 
758 
760  "branching/strongcoloring/lookahead",
761  "number of candidates to be considered in branchingmode 2",
762  &branchruledata->lookahead, TRUE, DEFAULT_LOOKAHEAD, 0, INT_MAX, NULL, NULL) );
763 
765  "branching/strongcoloring/usetclique",
766  "should the exact pricing with the tclique-algorithm be used for the strongbranchings?",
767  &branchruledata->usetclique, FALSE, DEFAULT_USETCLIQUE, NULL, NULL) );
768 
770  "branching/strongcoloring/maxpricingrounds",
771  "maximal number of pricing rounds used for each probing node in the strongbranching",
772  &branchruledata->maxpricingrounds, TRUE, DEFAULT_MAXPRICINGROUNDS, -1, INT_MAX, NULL, NULL) );
773 
775  "branching/strongcoloring/branchingmode",
776  "determines the branchingmode, 0: fullstrong branching, 1: strong branching, take first possible branching with only one child-node, 2: strong branching with prior sorting of candidates w.r.t. the fractional value of concerned sets */",
777  &branchruledata->branchingmode, FALSE, DEFAULT_BRANCHINGMODE, 0, 2, NULL, NULL) );
778 
780  "branching/strongcoloring/fixingsscoremode",
781  "determines the weightings of the two factors for prior sorting by fractional LP value",
782  &branchruledata->fixingsscoremode, TRUE, DEFAULT_FIXINGSSCOREMODE, 0, 4, NULL, NULL) );
783 
784  return SCIP_OKAY;
785 }
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:386
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1840
SCIP_Bool SCIPconsIsEnabled(SCIP_CONS *cons)
Definition: cons.c:8182
#define BRANCHRULE_PRIORITY
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:82
#define BRANCHRULE_DESC
#define DEFAULT_MAXPRICINGROUNDS
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:40
SCIP_RETCODE SCIPincludeBranchruleStrongcoloring(SCIP *scip)
static SCIP_DECL_SORTINDCOMP(consdataCompValues)
SCIP_Real SCIPgetLocalTransEstimate(SCIP *scip)
Definition: scip_prob.c:3545
static SCIP_DECL_BRANCHCOPY(branchCopyStrongcoloring)
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2842
SCIP_CONS * COLORconsGetActiveStoreGraphCons(SCIP *scip)
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:48
SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: scip_branch.c:192
static SCIP_RETCODE computeBranchingPriorities(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata)
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:160
SCIP_Bool SCIPisSumNegative(SCIP *scip, SCIP_Real val)
#define FALSE
Definition: def.h:87
#define TRUE
Definition: def.h:86
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
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
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
static int nodes2index(SCIP *scip, int node1, int node2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
static SCIP_Real computeFixingsScore(SCIP_Real samevalue, SCIP_Real differvalue, SCIP_BRANCHRULEDATA *branchruledata)
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
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:240
SCIP_CONS * COLORprobGetConstraint(SCIP *scip, int node)
#define DEFAULT_LOOKAHEAD
#define BRANCHRULE_MAXBOUNDDIST
int COLORconsGetRepresentative(SCIP *scip, int node)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:571
void COLORprobGetStableSet(SCIP *scip, int setindex, int **stableset, int *nelements)
static void index2nodes(SCIP *scip, int ind, int *node1, int *node2)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:420
int COLORprobGetNNodes(SCIP *scip)
variable pricer for the vertex coloring problem
static SCIP_DECL_BRANCHINIT(branchInitStrongcoloring)
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:251
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1008
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip_prob.c:3322
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define SCIP_Bool
Definition: def.h:84
static SCIP_DECL_BRANCHFREE(branchFreeStrongcoloring)
static double computeScore(SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:661
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1850
SCIP_Bool COLORprobIsNodeInStableSet(SCIP *scip, int setindex, int node)
#define DEFAULT_USETCLIQUE
SCIP_VARDATA * SCIPvarGetData(SCIP_VAR *var)
Definition: var.c:17271
#define MAX(x, y)
Definition: tclique_def.h:83
static SCIP_RETCODE executeStrongBranching(SCIP *scip, COLOR_CONSTYPE constype, int node1, int node2, SCIP_BRANCHRULEDATA *branchruledata, SCIP_Real *newlb)
static SCIP_DECL_BRANCHEXIT(branchExitStrongcoloring)
static SCIP_DECL_BRANCHEXECLP(branchExeclpStrongcoloring)
#define BRANCHRULE_NAME
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:238
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
Definition: misc.c:5440
SCIP_RETCODE SCIPsolveProbingLPWithPricing(SCIP *scip, SCIP_Bool pretendroot, SCIP_Bool displayinfo, int maxpricerounds, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:834
#define DEFAULT_FIXINGSSCOREMODE
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
enum COLOR_ConsType COLOR_CONSTYPE
#define SCIP_Real
Definition: def.h:177
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1962
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip_branch.c:176
#define BRANCHRULE_MAXDEPTH
branching rule performing strong branching for the vertex coloring problem
SCIP_RETCODE COLORcreateConsStoreGraph(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONS *fatherconstraint, COLOR_CONSTYPE type, int node1, int node2, SCIP_NODE *stickingnode)
#define nnodes
Definition: gastrans.c:65
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:156
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:110
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:123
TCLIQUE_GRAPH * COLORconsGetCurrentGraph(SCIP *scip)
SCIPallocBlockMemory(scip, subsol))
#define DEFAULT_BRANCHINGMODE
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