Scippy

SCIP

Solving Constraint Integer Programs

branch_coloring.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-2020 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_coloring.c
17  * @brief default branching rule for the vertex coloring problem
18  * @author Gerald Gamrath
19  *
20  * This file implements the standard branching rule for the coloring algorithm.
21  *
22  * As we use column generation, we may not branch on the variables themselves,
23  * but on some sort of constraints that we introduce in the pricing problem.
24  *
25  * In our case, we choose two nodes v and w, which are not adjacent in the current graph, and
26  * consider the following two constraints: SAME(v,w) and DIFFER(v,w). SAME(v,w) requires that both
27  * nodes v and w get the same color, whereas DIFFER(v,w) forbids this. For each pair of nodes, each
28  * feasible solution fulfills exactly one of these constraints. Hence, splitting the solution space
29  * into two parts, one fulfilling SAME(v,w) and the other DIFFER(v,w), does not cut off any feasible
30  * solution and can therefore be used as the branching rule.
31  *
32  * The branching is done as follows: Given the optimal (fractional) solution of the current
33  * branch-and-bound node, choose the most fractional variable and the corresponding stable set
34  * s1. Now choose two nodes v, w and another stable set s2, such that v is part of both stable sets,
35  * whereas w is part of exactly one of the stable sets. Create two children of the current node,
36  * one with the restriction SAME(v,w), the other one with restriction DIFFER(v,w). Therefore, each
37  * node gets a constraint of type @c cons_storeGraph, which enforces the branching decision and
38  * assures that each coloring of the nodes in the respective subgraph assigns to both nodes the same
39  * color/different colors by fixing stable sets to 0 that violate this constraint.
40  */
41 
42 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
43 #include <assert.h>
44 #include <string.h>
45 
46 #include "branch_coloring.h"
47 
48 #define BRANCHRULE_NAME "coloring"
49 #define BRANCHRULE_DESC "branching rule template"
50 #define BRANCHRULE_PRIORITY 50000
51 #define BRANCHRULE_MAXDEPTH -1
52 #define BRANCHRULE_MAXBOUNDDIST 1.0
53 
54 /*
55  * Callback methods of branching rule
56  */
57 
58 /** copy method for branchrule plugins (called when SCIP copies plugins) */
59 static
60 SCIP_DECL_BRANCHCOPY(branchCopyColoring)
61 { /*lint --e{715}*/
62  assert(scip != NULL);
63  assert(branchrule != NULL);
64  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
65 
66  return SCIP_OKAY;
67 }
68 
69 /** branching execution method for fractional LP solutions */
70 static
71 SCIP_DECL_BRANCHEXECLP(branchExeclpColoring)
72 {
73  /* array of candidates for branching + fractionalities of candidates + length of array */
74  SCIP_VAR** lpcands;
75  SCIP_Real* lpcandsfrac;
76  int nlpcands;
77  /* variables for finding the most fractional column */
78  SCIP_Real fractionality;
79  SCIP_Real bestfractionality;
80  int bestcand;
81  /* array of variables in a constraint + length of array */
82  SCIP_VAR** vars;
83  int nvars;
84  /* the variables for 2 stable sets, needed to find the two nodes for branching */
85  SCIP_VAR* s1;
86  SCIP_VAR* s2;
87  /* the 2 stable sets: array with all nodes and arraylength for each of them */
88  int* set1;
89  int setlength1;
90  int* set2;
91  int setlength2;
92  /* the 2 nodes, for which the branching is done by DIFFER and SAME */
93  int node1;
94  int node2;
95  /* the constraint belonging to node1 */
96  SCIP_CONS* cons1;
97  /* the nodes in the branch&bound-tree which are created */
98  SCIP_NODE* childsame;
99  SCIP_NODE* childdiffer;
100  /* the constraints for the created b&b-nodes */
101  SCIP_CONS* conssame;
102  SCIP_CONS* consdiffer;
103  /* the constraint of the processed b&b-node */
104  SCIP_CONS* currentcons;
105 
106  int i;
107  int j;
108  int k;
109  int l;
110  int setindex;
111 
112  assert(scip != NULL);
113  assert(branchrule != NULL);
114  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
115  assert(result != NULL);
116 
117  *result = SCIP_DIDNOTRUN;
118 
119  /* get branching candidates */
120  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, NULL, &lpcandsfrac, NULL, &nlpcands, NULL) );
121  assert(nlpcands > 0);
122 
123  bestcand = -1;
124 
125  /* search the least fractional candidate */
126  bestfractionality = 1;
127  for( i = 0; i < nlpcands; ++i )
128  {
129  assert(lpcands[i] != NULL);
130  fractionality = lpcandsfrac[i];
131  fractionality = MIN( fractionality, 1.0-fractionality );
132  if ( fractionality < bestfractionality )
133  {
134  bestfractionality = fractionality;
135  bestcand = i;
136  }
137  }
138 
139  assert(bestcand >= 0);
140  assert(SCIPisFeasPositive(scip, bestfractionality));
141 
142  /* s1 = column belonging to bestcand */
143  s1 = lpcands[bestcand];
144  setindex = (int)(size_t) SCIPvarGetData(s1);
145 
146  /* get stable set corresponding to variable s1 */
147  COLORprobGetStableSet(scip, setindex, &set1, &setlength1);
148 
149  node1 = -1;
150  node2 = -1;
151  s2 = NULL;
152  /* search for two nodes node1, node2 and column s2 (s2 != s1) such that:
153  the node1-constraint is covered by s1 and s2
154  the node2-constraint is covered by exactly one of the columns s1,s2 */
155  for ( i = 0; ((i < setlength1) && (node2 == -1)); i++ )
156  {
157  node1 = COLORconsGetRepresentative(scip, set1[i]);
158  /* search for other set containing the node */
159  cons1 = COLORprobGetConstraint(scip, node1);
160  vars = SCIPgetVarsSetppc(scip, cons1);
161  nvars = SCIPgetNVarsSetppc(scip, cons1);
162  for ( j = 0; j < nvars; j++ )
163  {
164  if ( vars[j] != s1 && !SCIPisFeasZero(scip, SCIPvarGetUbLocal(vars[j])) )
165  {
166  s2 = vars[j];
167  setindex = (int)(size_t) SCIPvarGetData(s2);
168  /* get Stable Set corresponding to Variable s2 */
169  COLORprobGetStableSet(scip, setindex, &set2, &setlength2);
170  /* for all nodes in set1 */
171  for ( k = 0; k < setlength1; k++ )
172  {
173  /* set node2 = current node in set1 */
174  node2 = COLORconsGetRepresentative(scip, set1[k]);
175  if ( node2 == node1)
176  {
177  node2 = -1;
178  }
179  else
180  {
181  /* check whether node2 is in set2 */
182  for ( l = 0; l < setlength2; l++ )
183  {
184  if ( COLORconsGetRepresentative(scip, set2[l]) == node2 )
185  {
186  /* node2 is in both sets -> no branching-candidate */
187  node2 = -1;
188  break; /* for l */
189  }
190  }
191  /* if node2 found, get out of for-loops */
192  if ( node2 != -1 )
193  {
194  break; /* for k */
195  }
196  }
197  }
198  if ( node2 != -1 )
199  {
200  break; /* for j */
201  }
202  for ( k = 0; k < setlength2; k++ )
203  {
204  /* set node2 = current node in set1 */
205  node2 = COLORconsGetRepresentative(scip, set2[k]);
206  if ( node2 == node1)
207  {
208  node2 = -1;
209  }
210  else
211  {
212  /* check whether node2 is in set2 */
213  for ( l = 0; l < setlength1; l++ )
214  {
215  if ( COLORconsGetRepresentative(scip, set1[l]) == node2 )
216  {
217  /* node2 is in both sets -> no branching-candidate */
218  node2 = -1;
219  break; /* for l */
220  }
221  }
222  /* if node2 found, get out of for-loops */
223  if ( node2 != -1 )
224  {
225  break; /* for k */
226  }
227  }
228  }
229  if ( node2 != -1 )
230  {
231  break; /* for j */
232  }
233  }
234  }
235  }
236 
237  assert(node2 != -1);
238  assert(node1 != -1);
239  assert(node1 == COLORconsGetRepresentative(scip, node1));
240  assert(node2 == COLORconsGetRepresentative(scip, node2));
241  assert(!tcliqueIsEdge(COLORconsGetCurrentGraph(scip), node1, node2));
242 
243  /* create the b&b-tree child-nodes of the current node */
246 
247  /* create corresponding constraints */
248  currentcons = COLORconsGetActiveStoreGraphCons(scip);
249  SCIP_CALL( COLORcreateConsStoreGraph(scip, &conssame, "same", currentcons, COLOR_CONSTYPE_SAME, node1, node2, childsame) );
250  SCIP_CALL( COLORcreateConsStoreGraph(scip, &consdiffer, "differ", currentcons, COLOR_CONSTYPE_DIFFER, node1, node2, childdiffer) );
251 
252  /* add constraints to nodes */
253  SCIP_CALL( SCIPaddConsNode(scip, childsame, conssame, NULL) );
254  SCIP_CALL( SCIPaddConsNode(scip, childdiffer, consdiffer, NULL) );
255 
256  /* release constraints */
257  SCIP_CALL( SCIPreleaseCons(scip, &conssame) );
258  SCIP_CALL( SCIPreleaseCons(scip, &consdiffer) );
259 
260  *result = SCIP_BRANCHED;
261 
262  return SCIP_OKAY;
263 }/*lint !e715*/
264 
265 
266 /** branching execution method for not completely fixed pseudo solutions */
267 static
268 SCIP_DECL_BRANCHEXECPS(branchExecpsColoring)
269 {
270  /* the 2 nodes, for which the branching is done by DIFFER and SAME */
271  int node1;
272  int node2;
273  /* the nodes in the branch&bound-tree which are created */
274  SCIP_NODE* childsame;
275  SCIP_NODE* childdiffer;
276  /* the constraints for the created b&b-nodes */
277  SCIP_CONS* conssame;
278  SCIP_CONS* consdiffer;
279  /* the constraint of the processed b&b-node */
280  SCIP_CONS* currentcons;
281 
282  assert(scip != NULL);
283  assert(branchrule != NULL);
284  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
285  assert(result != NULL);
286 
287  *result = SCIP_DIDNOTRUN;
288 
289  /* search for two nodes node1, node2 such that:
290  node1 and node2 are neither in the same union nor adjacent */
291  for ( node1 = 0; node1 < COLORprobGetNNodes(scip); ++node1 )
292  {
293  if ( node1 != COLORconsGetRepresentative(scip, node1) )
294  {
295  continue;
296  }
297  for ( node2 = node1+1; node2 < COLORprobGetNNodes(scip); ++node2 )
298  {
299  if ( node2 != COLORconsGetRepresentative(scip, node2) )
300  {
301  continue;
302  }
303  if ( (node2 != node1) && !tcliqueIsEdge(COLORconsGetCurrentGraph(scip), node1, node2))
304  {
305  /* create the b&b-tree child-nodes of the current node */
308 
309  /* create corresponding constraints */
310  currentcons = COLORconsGetActiveStoreGraphCons(scip);
311  SCIP_CALL( COLORcreateConsStoreGraph(scip, &conssame, "same", currentcons, COLOR_CONSTYPE_SAME, node1, node2, childsame) );
312  SCIP_CALL( COLORcreateConsStoreGraph(scip, &consdiffer, "differ", currentcons, COLOR_CONSTYPE_DIFFER, node1, node2, childdiffer) );
313 
314  /* add constraints to nodes */
315  SCIP_CALL( SCIPaddConsNode(scip, childsame, conssame, NULL) );
316  SCIP_CALL( SCIPaddConsNode(scip, childdiffer, consdiffer, NULL) );
317 
318  /* release constraints */
319  SCIP_CALL( SCIPreleaseCons(scip, &conssame) );
320  SCIP_CALL( SCIPreleaseCons(scip, &consdiffer) );
321 
322  *result = SCIP_BRANCHED;
323 
324  return SCIP_OKAY;
325  }
326  }
327  }
328 
330  *result = SCIP_BRANCHED;
331 
332  return SCIP_OKAY;
333 }/*lint !e715*/
334 
335 /*
336  * branching rule specific interface methods
337  */
338 
339 /** creates the coloring branching rule and includes it in SCIP */
341  SCIP* scip /**< SCIP data structure */
342  )
343 {
344  SCIP_BRANCHRULEDATA* branchruledata;
345  SCIP_BRANCHRULE* branchrule;
346 
347  assert(scip != NULL);
348 
349  /* create branching rule data */
350  branchruledata = NULL;
351  branchrule = NULL;
352  /* include branching rule */
354  BRANCHRULE_MAXBOUNDDIST, branchruledata) );
355 
356  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpColoring) );
357  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyColoring) );
358  SCIP_CALL( SCIPsetBranchruleExecPs(scip, branchrule, branchExecpsColoring) );
359 
360  return SCIP_OKAY;
361 
362 }
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:240
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1008
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
SCIP_CONS * COLORconsGetActiveStoreGraphCons(SCIP *scip)
SCIP_RETCODE SCIPincludeBranchruleColoring(SCIP *scip)
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:48
static SCIP_DECL_BRANCHCOPY(branchCopyColoring)
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
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9272
#define BRANCHRULE_DESC
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 SCIP_DECL_BRANCHEXECLP(branchExeclpColoring)
#define BRANCHRULE_MAXDEPTH
SCIP_CONS * COLORprobGetConstraint(SCIP *scip, int node)
int COLORconsGetRepresentative(SCIP *scip, int node)
#define BRANCHRULE_NAME
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:272
void COLORprobGetStableSet(SCIP *scip, int setindex, int **stableset, int *nelements)
default branching rule for the vertex coloring problem
int COLORprobGetNNodes(SCIP *scip)
#define NULL
Definition: lpi_spx1.cpp:155
#define BRANCHRULE_PRIORITY
#define SCIP_CALL(x)
Definition: def.h:364
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip_prob.c:3317
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17733
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9249
#define BRANCHRULE_MAXBOUNDDIST
#define SCIP_Real
Definition: def.h:163
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
static SCIP_DECL_BRANCHEXECPS(branchExecpsColoring)
SCIP_RETCODE COLORcreateConsStoreGraph(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONS *fatherconstraint, COLOR_CONSTYPE type, int node1, int node2, SCIP_NODE *stickingnode)
SCIP_EXPORT SCIP_VARDATA * SCIPvarGetData(SCIP_VAR *var)
Definition: var.c:17037
TCLIQUE_GRAPH * COLORconsGetCurrentGraph(SCIP *scip)
SCIP_Real SCIPgetLocalTransEstimate(SCIP *scip)
Definition: scip_prob.c:3540
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)