1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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
computeScore(SCIP_Real val1,SCIP_Real val2)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
computeFixingsScore(SCIP_Real samevalue,SCIP_Real differvalue,SCIP_BRANCHRULEDATA * branchruledata)109 SCIP_Real computeFixingsScore(
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
nodes2index(SCIP * scip,int node1,int node2)138 int nodes2index(
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
index2nodes(SCIP * scip,int ind,int * node1,int * node2)169 void index2nodes(
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
computeBranchingPriorities(SCIP * scip,SCIP_BRANCHRULEDATA * branchruledata)197 SCIP_RETCODE computeBranchingPriorities(
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
executeStrongBranching(SCIP * scip,COLOR_CONSTYPE constype,int node1,int node2,SCIP_BRANCHRULEDATA * branchruledata,SCIP_Real * newlb)307 SCIP_RETCODE executeStrongBranching(
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
SCIP_DECL_SORTINDCOMP(consdataCompValues)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
SCIP_DECL_BRANCHCOPY(branchCopyStrongcoloring)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
SCIP_DECL_BRANCHEXECLP(branchExeclpStrongcoloring)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);
442 graph = COLORconsGetCurrentGraph(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 */
615 SCIP_CALL( SCIPcreateChild(scip, &childdiffer, 0.0, SCIPgetLocalTransEstimate(scip)) );
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 */
632 SCIP_CALL( SCIPcreateChild(scip, &childsame, 0.0, SCIPgetLocalTransEstimate(scip)) );
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 {
649 /* create the b&b-tree child-nodes of the current node */
650 SCIP_CALL( SCIPcreateChild(scip, &childsame, 0.0, SCIPgetLocalTransEstimate(scip)) );
651 SCIP_CALL( SCIPcreateChild(scip, &childdiffer, 0.0, SCIPgetLocalTransEstimate(scip)) );
652
653 /* create corresponding constraints */
654 currentcons = COLORconsGetActiveStoreGraphCons(scip);
655 SCIP_CALL( COLORcreateConsStoreGraph(scip, &conssame, "same", currentcons, COLOR_CONSTYPE_SAME, node1, node2, childsame) );
656 SCIP_CALL( COLORcreateConsStoreGraph(scip, &consdiffer, "differ", currentcons, COLOR_CONSTYPE_DIFFER, node1, node2, childdiffer) );
657
658 /* add constraints to nodes */
659 SCIP_CALL( SCIPaddConsNode(scip, childsame, conssame, NULL) );
660 SCIP_CALL( SCIPaddConsNode(scip, childdiffer, consdiffer, NULL) );
661
662 /* release constraints */
663 SCIP_CALL( SCIPreleaseCons(scip, &conssame) );
664 SCIP_CALL( SCIPreleaseCons(scip, &consdiffer) );
665
666 *result = SCIP_BRANCHED;
667 }
668
669 return SCIP_OKAY;
670 }/*lint !e715*/
671
672
673 /** destructor of branching rule to free user data (called when SCIP is exiting) */
674 static
SCIP_DECL_BRANCHFREE(branchFreeStrongcoloring)675 SCIP_DECL_BRANCHFREE(branchFreeStrongcoloring)
676 {
677 SCIP_BRANCHRULEDATA* branchruledata;
678
679 /* free branching rule data */
680 branchruledata = SCIPbranchruleGetData(branchrule);
681 SCIPfreeBlockMemory(scip, &branchruledata);
682 SCIPbranchruleSetData(branchrule, NULL);
683
684 return SCIP_OKAY;
685 }
686
687 /** initialization method of branching rule (called after problem was transformed) */
688 static
SCIP_DECL_BRANCHINIT(branchInitStrongcoloring)689 SCIP_DECL_BRANCHINIT(branchInitStrongcoloring)
690 {
691 SCIP_BRANCHRULEDATA* branchruledata;
692
693 /* get branching rule data */
694 branchruledata = SCIPbranchruleGetData(branchrule);
695 assert(branchruledata != NULL);
696
697 /* get memory for the arrays */
698 branchruledata->length = (COLORprobGetNNodes(scip)*(COLORprobGetNNodes(scip)-1))/2;
699 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(branchruledata->samevalue), branchruledata->length) );
700 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(branchruledata->differvalue), branchruledata->length) );
701 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(branchruledata->combinedvalue), branchruledata->length) );
702 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(branchruledata->permutation), branchruledata->length) );
703
704 return SCIP_OKAY;
705 }
706
707 /** deinitialization method of branching rule (called before transformed problem is freed) */
708 static
SCIP_DECL_BRANCHEXIT(branchExitStrongcoloring)709 SCIP_DECL_BRANCHEXIT(branchExitStrongcoloring)
710 {
711 SCIP_BRANCHRULEDATA* branchruledata;
712
713 /* get branching rule data */
714 branchruledata = SCIPbranchruleGetData(branchrule);
715 assert(branchruledata != NULL);
716
717 /* free arrays */
718 SCIPfreeBlockMemoryArray(scip, &(branchruledata->samevalue), branchruledata->length);
719 SCIPfreeBlockMemoryArray(scip, &(branchruledata->differvalue), branchruledata->length);
720 SCIPfreeBlockMemoryArray(scip, &(branchruledata->combinedvalue), branchruledata->length);
721 SCIPfreeBlockMemoryArray(scip, &(branchruledata->permutation), branchruledata->length);
722
723 return SCIP_OKAY;
724 }
725
726 /*
727 * branching rule specific interface methods
728 */
729
730 /** creates the coloring branching rule and includes it in SCIP */
SCIPincludeBranchruleStrongcoloring(SCIP * scip)731 SCIP_RETCODE SCIPincludeBranchruleStrongcoloring(
732 SCIP* scip /**< SCIP data structure */
733 )
734 {
735 SCIP_BRANCHRULEDATA* branchruledata;
736 SCIP_BRANCHRULE* branchrule;
737
738 assert(scip != NULL);
739
740 /* create branching rule data */
741 SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
742
743 branchrule = NULL;
744 /* include branching rule */
745 SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY, BRANCHRULE_MAXDEPTH,
746 BRANCHRULE_MAXBOUNDDIST, branchruledata) );
747 assert(branchrule != NULL);
748
749 SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyStrongcoloring) );
750 SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeStrongcoloring) );
751 SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpStrongcoloring) );
752 SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitStrongcoloring) );
753 SCIP_CALL( SCIPsetBranchruleExit(scip, branchrule, branchExitStrongcoloring) );
754
755
756 SCIP_CALL( SCIPaddIntParam(scip,
757 "branching/strongcoloring/lookahead",
758 "number of candidates to be considered in branchingmode 2",
759 &branchruledata->lookahead, TRUE, DEFAULT_LOOKAHEAD, 0, INT_MAX, NULL, NULL) );
760
761 SCIP_CALL( SCIPaddBoolParam(scip,
762 "branching/strongcoloring/usetclique",
763 "should the exact pricing with the tclique-algorithm be used for the strongbranchings?",
764 &branchruledata->usetclique, FALSE, DEFAULT_USETCLIQUE, NULL, NULL) );
765
766 SCIP_CALL( SCIPaddIntParam(scip,
767 "branching/strongcoloring/maxpricingrounds",
768 "maximal number of pricing rounds used for each probing node in the strongbranching",
769 &branchruledata->maxpricingrounds, TRUE, DEFAULT_MAXPRICINGROUNDS, -1, INT_MAX, NULL, NULL) );
770
771 SCIP_CALL( SCIPaddIntParam(scip,
772 "branching/strongcoloring/branchingmode",
773 "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 */",
774 &branchruledata->branchingmode, FALSE, DEFAULT_BRANCHINGMODE, 0, 2, NULL, NULL) );
775
776 SCIP_CALL( SCIPaddIntParam(scip,
777 "branching/strongcoloring/fixingsscoremode",
778 "determines the weightings of the two factors for prior sorting by fractional LP value",
779 &branchruledata->fixingsscoremode, TRUE, DEFAULT_FIXINGSSCOREMODE, 0, 4, NULL, NULL) );
780
781 return SCIP_OKAY;
782 }
783