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-2017 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 email to scip@zib.de. */
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 
100  SCIP_Real** pairweights;
101 
102  SCIP_VAR** lpcands;
103  SCIP_Real* lpcandsfrac;
104  int nlpcands;
105  SCIP_Real bestvalue;
106  SCIP_Real value;
107 
108  SCIP_NODE* childsame;
109  SCIP_NODE* childdiffer;
110  SCIP_CONS* conssame;
111  SCIP_CONS* consdiffer;
112 
113  SCIP_VARDATA* vardata;
114  int* consids;
115  int nconsids;
116  int nitems;
117 
118  int id1;
119  int id2;
120 
121  int i;
122  int j;
123  int v;
124 
125  assert(scip != NULL);
126  assert(branchrule != NULL);
127  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
128  assert(result != NULL);
129 
130  SCIPdebugMsg(scip, "start branching at node %"SCIP_LONGINT_FORMAT", depth %d\n", SCIPgetNNodes(scip), SCIPgetDepth(scip));
131 
132  *result = SCIP_DIDNOTRUN;
133 
134  probdata = SCIPgetProbData(scip);
135  assert(probdata != NULL);
136 
137  nitems = SCIPprobdataGetNItems(probdata);
138 
139  /* allocate memory for triangle matrix */
140  SCIP_CALL( SCIPallocBufferArray(scip, &pairweights, nitems) );
141  for( i = 0; i < nitems; ++i )
142  {
143  SCIP_CALL( SCIPallocBufferArray(scip, &pairweights[i], nitems) ); /*lint !e866 */
144 
145  for( j = 0; j < nitems; ++j )
146  pairweights[i][j] = 0.0;
147  }
148 
149  /* get fractional LP candidates */
150  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, NULL, &lpcandsfrac, NULL, &nlpcands, NULL) );
151  assert(nlpcands > 0);
152 
153  /* compute weigthts for each order pair */
154  for( v = 0; v < nlpcands; ++v )
155  {
156  assert(lpcands[v] != NULL);
157 
158  /* get variable data which contains the information to which constraints/items the variable belongs */
159  vardata = SCIPvarGetData(lpcands[v]);
160 
161  consids = SCIPvardataGetConsids(vardata);
162  nconsids = SCIPvardataGetNConsids(vardata);
163  assert(nconsids > 0);
164 
165  /* loop over all constraints/items the variable belongs to */
166  for( i = 0; i < nconsids; ++i )
167  {
168  id1 = consids[i];
169  for( j = i+1; j < nconsids; ++j )
170  {
171  id2 = consids[j];
172  assert(id1 < id2);
173 
174  pairweights[id2][id1] += lpcandsfrac[v];
175 
176  assert( SCIPisFeasLE(scip, pairweights[id2][id1], 1.0) );
177  assert( SCIPisFeasGE(scip, pairweights[id2][id1], 0.0) );
178  }
179  }
180  }
181 
182  /* select branching */
183  bestvalue = 0.0;
184  id1 = -1;
185  id2 = -1;
186 
187  for( i = 0; i < nitems; ++i )
188  {
189  for( j = 0; j < i+1; ++j )
190  {
191  value = MIN(pairweights[i][j], 1-pairweights[i][j]);
192 
193  if( bestvalue < value )
194  {
195  bestvalue = value;
196  id1 = j;
197  id2 = i;
198  }
199  }
200  }
201 
202  assert( bestvalue > 0.0 );
203  assert( id1 >= 0 && id1 < nitems);
204  assert( id2 >= 0 && id2 < nitems);
205 
206  /* free memory for triangle matrix */
207  for( i = 0; i < nitems; ++i )
208  {
209  SCIPfreeBufferArray(scip, &pairweights[i]);
210  }
211  SCIPfreeBufferArray(scip, &pairweights);
212 
213  SCIPdebugMsg(scip, "branch on order pair <%d,%d> with weight <%g>\n",
214  SCIPprobdataGetIds(probdata)[id1], SCIPprobdataGetIds(probdata)[id2], bestvalue);
215 
216  /* create the branch-and-bound tree child nodes of the current node */
219 
220  /* create corresponding constraints */
221  SCIP_CALL( SCIPcreateConsSamediff(scip, &conssame, "same", id1, id2, SAME, childsame, TRUE) );
222  SCIP_CALL( SCIPcreateConsSamediff(scip, &consdiffer, "differ", id1, id2, DIFFER, childdiffer, TRUE) );
223 
224  /* add constraints to nodes */
225  SCIP_CALL( SCIPaddConsNode(scip, childsame, conssame, NULL) );
226  SCIP_CALL( SCIPaddConsNode(scip, childdiffer, consdiffer, NULL) );
227 
228  /* release constraints */
229  SCIP_CALL( SCIPreleaseCons(scip, &conssame) );
230  SCIP_CALL( SCIPreleaseCons(scip, &consdiffer) );
231 
232  *result = SCIP_BRANCHED;
233 
234  return SCIP_OKAY;
235 }
236 
237 /**@} */
238 
239 /**@name Interface methods
240  *
241  * @{
242  */
243 
244 /** creates the ryan foster branching rule and includes it in SCIP */
246  SCIP* scip /**< SCIP data structure */
247  )
248 {
249  SCIP_BRANCHRULEDATA* branchruledata;
250  SCIP_BRANCHRULE* branchrule;
251 
252  /* create ryan foster branching rule data */
253  branchruledata = NULL;
254  branchrule = NULL;
255  /* include branching rule */
257  BRANCHRULE_MAXBOUNDDIST, branchruledata) );
258  assert(branchrule != NULL);
259 
260  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpRyanFoster) );
261 
262  return SCIP_OKAY;
263 }
264 
265 /**@} */
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip.c:36128
Ryan/Foster branching rule.
#define BRANCHRULE_DESC
#define BRANCHRULE_MAXDEPTH
SCIP_Real SCIPgetLocalTransEstimate(SCIP *scip)
Definition: scip.c:13183
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:43
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)
Definition: scip.c:46138
struct SCIP_VarData SCIP_VARDATA
Definition: type_var.h:98
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
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.c:9001
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
int * SCIPvardataGetConsids(SCIP_VARDATA *vardata)
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip.c:9136
#define BRANCHRULE_PRIORITY
#define NULL
Definition: lpi_spx1.cpp:137
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip.c:36704
#define SCIP_CALL(x)
Definition: def.h:306
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46112
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip.c:12960
int * SCIPprobdataGetIds(SCIP_PROBDATA *probdata)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
Problem data for binpacking problem.
int SCIPprobdataGetNItems(SCIP_PROBDATA *probdata)
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:42094
SCIP_VARDATA * SCIPvarGetData(SCIP_VAR *var)
Definition: var.c:16572
#define BRANCHRULE_NAME
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip.c:10621
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip.c:27323
#define BRANCHRULE_MAXBOUNDDIST
int SCIPvardataGetNConsids(SCIP_VARDATA *vardata)
#define SCIP_Real
Definition: def.h:135
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1896
#define MIN(x, y)
Definition: memory.c:75
static SCIP_DECL_BRANCHEXECLP(branchExeclpRyanFoster)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:41182