Scippy

SCIP

Solving Constraint Integer Programs

branch_ryanfoster.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-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_ryanfoster.c
17  * @ingroup BRANCHINGRULES
18  * @brief Ryan/Foster branching rule
19  * @author Timo Berthold
20  * @author Stefan Heinz
21  *
22  * This file implements the Ryan/Foster branching rule. For more details see \ref BINPACKING_BRANCHING page.
23  *
24  * @page BINPACKING_BRANCHING Ryan/Foster branching
25  *
26  * Ryan/Foster branching is a very useful branching rule for the integer program model in use. A
27  * standard variable branching has the disadvantage that the zero branch is more or less useless because
28  * we only forbid one packing out of exponential many. On the other hand, the branch fixing a packing reduces the problem since
29  * certain items are packed. This leads to a very unbalanced search tree.
30  *
31  * The branching rule of Ryan/Foster was itroduced in@n
32  * D. M. Ryan and B. A. Foster: An Integer Programming Approach to Scheduling,
33  * In Computer scheduling of public transport: Urban passenger vehicle and crew scheduling, A. Wren editor, North-Holland 1981, 269-280.
34  *
35  * The idea is to select a pair of items which is either a) forced to be packed together or b)
36  * not allowed to be packed together. Note that in both cases, it is allowed to use packings
37  * which contain none of the two items.
38  *
39  * There are two issues to be taken care off:
40  * -# How do we select the pair of items?
41  * -# How do we realize such a branching within \SCIP?
42  *
43  * @section BINPACKING_SELECTION How do we select the pair of items?
44  *
45  * To select a pair of items, we have to know for each packing the items which are contained. Since every packing is a
46  * variable and each item is a set covering constraint, we have to know for each variable in which set covering
47  * constraints it appears (this means, has a coefficient of 1.0). Since \SCIP is constraint based, it is in general
48  * not possible to get this information directly. To overcome this issue, we use the functionality to add
49  * \ref vardata_binpacking.c "variable data" to every
50  * variable. This variable data contains the constraints in which this variable appears (see vardata_binpacking.c for more details).
51  * With the help of the variable data, it is now possible to get the
52  * information which items belong to which packing. Therefore, we can use the Ryan/Foster idea to select a pair of
53  * items.
54  *
55  * @section BINPACKING_SAMEDIFFBRANCHING How do we realize such a branching within SCIP?
56  *
57  * After having selected a pair of items to branch on, the question now is how to realize such a branching with \SCIP.
58  * Since \SCIP is
59  * constraint based, it is really easy to do that. We implement a constraint handler which handles the
60  * information, see cons_samediff.c. This constraint handler does not only store the branching
61  * decisions. Furthermore, it also ensures that all packing which are not feasible at a particular node are
62  * locally fixed to zero. For more details, we refer to the \ref cons_samediff.c "source code of the constraint handler".
63  *
64  */
65 
66 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
67 
68 #include <assert.h>
69 #include <string.h>
70 
71 #include "branch_ryanfoster.h"
72 #include "cons_samediff.h"
73 #include "probdata_binpacking.h"
74 #include "vardata_binpacking.h"
75 
76 /**@name Branching rule properties
77  *
78  * @{
79  */
80 
81 #define BRANCHRULE_NAME "RyanFoster"
82 #define BRANCHRULE_DESC "Ryan/Foster branching rule"
83 #define BRANCHRULE_PRIORITY 50000
84 #define BRANCHRULE_MAXDEPTH -1
85 #define BRANCHRULE_MAXBOUNDDIST 1.0
86 
87 /**@} */
88 
89 /**@name Callback methods
90  *
91  * @{
92  */
93 
94 /** branching execution method for fractional LP solutions */
95 static
96 SCIP_DECL_BRANCHEXECLP(branchExeclpRyanFoster)
97 { /*lint --e{715}*/
98  SCIP_PROBDATA* probdata;
99  SCIP_Real** pairweights;
100  SCIP_VAR** lpcands;
101  SCIP_Real* lpcandsfrac;
102  int nlpcands;
103  SCIP_Real bestvalue;
104  SCIP_Real value;
105 
106  SCIP_NODE* childsame;
107  SCIP_NODE* childdiffer;
108  SCIP_CONS* conssame;
109  SCIP_CONS* consdiffer;
110 
111  SCIP_VARDATA* vardata;
112  int* consids;
113  int nconsids;
114  int nitems;
115 
116  int id1;
117  int id2;
118 
119  int i;
120  int j;
121  int v;
122 
123  assert(scip != NULL);
124  assert(branchrule != NULL);
125  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
126  assert(result != NULL);
127 
128  SCIPdebugMsg(scip, "start branching at node %"SCIP_LONGINT_FORMAT", depth %d\n", SCIPgetNNodes(scip), SCIPgetDepth(scip));
129 
130  *result = SCIP_DIDNOTRUN;
131 
132  probdata = SCIPgetProbData(scip);
133  assert(probdata != NULL);
134 
135  nitems = SCIPprobdataGetNItems(probdata);
136 
137  /* allocate memory for triangle matrix */
138  SCIP_CALL( SCIPallocBufferArray(scip, &pairweights, nitems) );
139  for( i = 0; i < nitems; ++i )
140  {
141  SCIP_CALL( SCIPallocClearBufferArray(scip, &pairweights[i], i+1) ); /*lint !e866 */
142  }
143 
144  /* get fractional LP candidates */
145  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, NULL, &lpcandsfrac, NULL, &nlpcands, NULL) );
146  assert(nlpcands > 0);
147 
148  /* compute weights for each order pair */
149  for( v = 0; v < nlpcands; ++v )
150  {
151  SCIP_Real solval;
152 
153  assert(lpcands[v] != NULL);
154 
155  solval = lpcandsfrac[v];
156 
157  /* get variable data which contains the information to which constraints/items the variable belongs */
158  vardata = SCIPvarGetData(lpcands[v]);
159 
160  consids = SCIPvardataGetConsids(vardata);
161  nconsids = SCIPvardataGetNConsids(vardata);
162  assert(nconsids > 0);
163 
164  /* loop over all constraints/items the variable belongs to */
165  for( i = 0; i < nconsids; ++i )
166  {
167  id1 = consids[i];
168 
169  /* store the LP sum for single items in the diagonal */
170  pairweights[id1][id1] += solval;
171 
172  /* update LP sums for all pairs of items */
173  for( j = i+1; j < nconsids; ++j )
174  {
175  id2 = consids[j];
176  assert(id1 < id2);
177 
178  pairweights[id2][id1] += solval;
179 
180  assert( SCIPisFeasGE(scip, pairweights[id2][id1], 0.0) );
181  }
182  }
183  }
184 
185  /* select branching */
186  bestvalue = 0.0;
187  id1 = -1;
188  id2 = -1;
189 
190  for( i = 0; i < nitems; ++i )
191  {
192  for( j = 0; j < i; ++j )
193  {
194  value = MIN(pairweights[i][j], 1-pairweights[i][j]);
195 
196  if( bestvalue < value )
197  {
198  /* there is no variable with (fractional) LP value > 0 that contains exactly one of the items */
199  if( SCIPisEQ(scip, pairweights[i][j], pairweights[i][i])
200  && SCIPisEQ(scip, pairweights[i][j], pairweights[j][j]) )
201  continue;
202 
203  bestvalue = value;
204  id1 = j;
205  id2 = i;
206  }
207  }
208  }
209 
210  assert( bestvalue > 0.0 );
211  assert( id1 >= 0 && id1 < nitems);
212  assert( id2 >= 0 && id2 < nitems);
213 
214  /* free memory for triangle matrix */
215  for( i = 0; i < nitems; ++i )
216  {
217  SCIPfreeBufferArray(scip, &pairweights[i]);
218  }
219  SCIPfreeBufferArray(scip, &pairweights);
220 
221  SCIPdebugMsg(scip, "branch on order pair <%d,%d> with weight <%g>\n",
222  SCIPprobdataGetIds(probdata)[id1], SCIPprobdataGetIds(probdata)[id2], bestvalue);
223 
224  /* create the branch-and-bound tree child nodes of the current node */
227 
228  /* create corresponding constraints */
229  SCIP_CALL( SCIPcreateConsSamediff(scip, &conssame, "same", id1, id2, SAME, childsame, TRUE) );
230  SCIP_CALL( SCIPcreateConsSamediff(scip, &consdiffer, "differ", id1, id2, DIFFER, childdiffer, TRUE) );
231 
232  /* add constraints to nodes */
233  SCIP_CALL( SCIPaddConsNode(scip, childsame, conssame, NULL) );
234  SCIP_CALL( SCIPaddConsNode(scip, childdiffer, consdiffer, NULL) );
235 
236  /* release constraints */
237  SCIP_CALL( SCIPreleaseCons(scip, &conssame) );
238  SCIP_CALL( SCIPreleaseCons(scip, &consdiffer) );
239 
240  *result = SCIP_BRANCHED;
241 
242  return SCIP_OKAY;
243 }
244 
245 /**@} */
246 
247 /**@name Interface methods
248  *
249  * @{
250  */
251 
252 /** creates the ryan foster branching rule and includes it in SCIP */
254  SCIP* scip /**< SCIP data structure */
255  )
256 {
257  SCIP_BRANCHRULEDATA* branchruledata;
258  SCIP_BRANCHRULE* branchrule;
259 
260  /* create ryan foster branching rule data */
261  branchruledata = NULL;
262  branchrule = NULL;
263  /* include branching rule */
265  BRANCHRULE_MAXBOUNDDIST, branchruledata) );
266  assert(branchrule != NULL);
267 
268  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpRyanFoster) );
269 
270  return SCIP_OKAY;
271 }
272 
273 /**@} */
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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
Ryan/Foster branching rule.
#define BRANCHRULE_DESC
#define BRANCHRULE_MAXDEPTH
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:113
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:48
SCIP_RETCODE SCIPincludeBranchruleRyanFoster(SCIP *scip)
Constraint handler stores the local branching decision data.
SCIP_RETCODE SCIPcreateConsSamediff(SCIP *scip, SCIP_CONS **cons, const char *name, int itemid1, int itemid2, CONSTYPE type, SCIP_NODE *node, SCIP_Bool local)
struct SCIP_VarData SCIP_VARDATA
Definition: type_var.h:107
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:962
Variable data containing the ids of constraints in which the variable appears.
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
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
int * SCIPvardataGetConsids(SCIP_VARDATA *vardata)
#define SCIPdebugMsg
Definition: scip_message.h:69
#define BRANCHRULE_PRIORITY
SCIP_Longint SCIPgetNNodes(SCIP *scip)
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:370
int * SCIPprobdataGetIds(SCIP_PROBDATA *probdata)
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip_prob.c:3317
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:638
Problem data for binpacking problem.
int SCIPprobdataGetNItems(SCIP_PROBDATA *probdata)
#define BRANCHRULE_NAME
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
#define BRANCHRULE_MAXBOUNDDIST
int SCIPvardataGetNConsids(SCIP_VARDATA *vardata)
#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
SCIP_EXPORT SCIP_VARDATA * SCIPvarGetData(SCIP_VAR *var)
Definition: var.c:17037
static SCIP_DECL_BRANCHEXECLP(branchExeclpRyanFoster)
SCIP_Real SCIPgetLocalTransEstimate(SCIP *scip)
Definition: scip_prob.c:3540
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110