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