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