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-2024 Zuse Institute Berlin (ZIB) */
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) */
68static
69SCIP_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 */
79static
80SCIP_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 */
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 */
278static
279SCIP_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 */
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}
#define BRANCHRULE_DESC
#define BRANCHRULE_PRIORITY
static SCIP_DECL_BRANCHEXECLP(branchExeclpColoring)
#define BRANCHRULE_NAME
static SCIP_DECL_BRANCHCOPY(branchCopyColoring)
SCIP_RETCODE SCIPincludeBranchruleColoring(SCIP *scip)
static SCIP_DECL_BRANCHEXECPS(branchExecpsColoring)
#define BRANCHRULE_MAXDEPTH
#define BRANCHRULE_MAXBOUNDDIST
default branching rule for the vertex coloring problem
TCLIQUE_GRAPH * COLORconsGetCurrentGraph(SCIP *scip)
SCIP_RETCODE COLORcreateConsStoreGraph(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONS *fatherconstraint, COLOR_CONSTYPE type, int node1, int node2, SCIP_NODE *stickingnode)
int COLORconsGetRepresentative(SCIP *scip, int node)
SCIP_CONS * COLORconsGetActiveStoreGraphCons(SCIP *scip)
@ COLOR_CONSTYPE_DIFFER
@ COLOR_CONSTYPE_SAME
#define NULL
Definition: def.h:267
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define SCIP_CALL(x)
Definition: def.h:374
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9545
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9568
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip_prob.c:3323
SCIP_Real SCIPgetLocalTransEstimate(SCIP *scip)
Definition: scip_prob.c:3546
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:249
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:153
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
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:281
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
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_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1017
SCIP_Bool SCIPconsIsEnabled(SCIP_CONS *cons)
Definition: cons.c:8311
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_VARDATA * SCIPvarGetData(SCIP_VAR *var)
Definition: var.c:17439
void COLORprobGetStableSet(SCIP *scip, int setindex, int **stableset, int *nelements)
int COLORprobGetNNodes(SCIP *scip)
SCIP_CONS * COLORprobGetConstraint(SCIP *scip, int node)
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:57
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_BRANCHED
Definition: type_result.h:54
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63