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