Scippy

SCIP

Solving Constraint Integer Programs

branch_leastinf.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_leastinf.c
17  * @brief least infeasible LP branching rule
18  * @author Tobias Achterberg
19  * @author Stefan Vigerske
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include <assert.h>
25 #include <string.h>
26 
27 #include "scip/branch_leastinf.h"
28 
29 #define BRANCHRULE_NAME "leastinf"
30 #define BRANCHRULE_DESC "least infeasible branching"
31 #define BRANCHRULE_PRIORITY 50
32 #define BRANCHRULE_MAXDEPTH -1
33 #define BRANCHRULE_MAXBOUNDDIST 1.0
34 
35 /*
36  * Local methods
37  */
38 
39 /** compares the so far best branching candidate with a new candidate and updates best candidate, if new candidate is better */
40 static
42  SCIP* scip, /**< SCIP data structure */
43  SCIP_VAR** bestvar, /**< best branching candidate */
44  SCIP_Real* bestscore, /**< score of best branching candidate */
45  SCIP_Real* bestobj, /**< absolute objective value of best branching candidate */
46  SCIP_Real* bestsol, /**< proposed branching point of best branching candidate */
47  SCIP_VAR* cand, /**< branching candidate to consider */
48  SCIP_Real candscore, /**< scoring of branching candidate */
49  SCIP_Real candsol /**< proposed branching point of branching candidate */
50  )
51 {
52  SCIP_Real obj;
53 
54  assert(scip != NULL);
55  assert(bestvar != NULL);
56  assert(bestscore != NULL);
57  assert(bestobj != NULL);
58  assert(*bestobj >= 0.0);
59  assert(cand != NULL);
60 
61  /* a branching variable candidate should either be an active problem variable or a multi-aggregated variable */
62  assert(SCIPvarIsActive(SCIPvarGetProbvar(cand)) ||
64 
66  {
67  /* for a multi-aggregated variable, we call updateBestCandidate function recursively with all variables in the multi-aggregation */
68  SCIP_VAR** multvars;
69  int nmultvars;
70  int i;
71  SCIP_Bool success;
72  SCIP_Real multvarlb;
73  SCIP_Real multvarub;
74 
75  cand = SCIPvarGetProbvar(cand);
76  multvars = SCIPvarGetMultaggrVars(cand);
77  nmultvars = SCIPvarGetMultaggrNVars(cand);
78 
79  /* if we have a candidate branching point, then first register only aggregation variables
80  * for which we can compute a corresponding branching point too (see also comments below)
81  * if this fails, then register all (unfixed) aggregation variables, thereby forgetting about candsol
82  */
83  success = FALSE;
84  if( candsol != SCIP_INVALID ) /*lint !e777*/
85  {
86  SCIP_Real* multscalars;
87  SCIP_Real minact;
88  SCIP_Real maxact;
89  SCIP_Real aggrvarsol;
90  SCIP_Real aggrvarsol1;
91  SCIP_Real aggrvarsol2;
92 
93  multscalars = SCIPvarGetMultaggrScalars(cand);
94 
95  /* for computing the branching point, we need the current bounds of the multi-aggregated variable */
96  minact = SCIPcomputeVarLbLocal(scip, cand);
97  maxact = SCIPcomputeVarUbLocal(scip, cand);
98 
99  for( i = 0; i < nmultvars; ++i )
100  {
101  /* skip fixed variables */
102  multvarlb = SCIPcomputeVarLbLocal(scip, multvars[i]);
103  multvarub = SCIPcomputeVarUbLocal(scip, multvars[i]);
104  if( SCIPisEQ(scip, multvarlb, multvarub) )
105  continue;
106 
107  assert(multscalars != NULL);
108  assert(multscalars[i] != 0.0);
109 
110  /* we cannot ensure that both the upper bound in the left node and the lower bound in the right node
111  * will be candsol by a clever choice for the branching point of multvars[i],
112  * but we can try to ensure that at least one of them will be at candsol
113  */
114  if( multscalars[i] > 0.0 )
115  {
116  /* cand >= candsol
117  * if multvars[i] >= (candsol - (maxact - multscalars[i] * ub(multvars[i]))) / multscalars[i]
118  * = (candsol - maxact) / multscalars[i] + ub(multvars[i])
119  */
120  aggrvarsol1 = (candsol - maxact) / multscalars[i] + multvarub;
121 
122  /* cand <= candsol
123  * if multvars[i] <= (candsol - (minact - multscalar[i] * lb(multvars[i]))) / multscalars[i]
124  * = (candsol - minact) / multscalars[i] + lb(multvars[i])
125  */
126  aggrvarsol2 = (candsol - minact) / multscalars[i] + multvarlb;
127  }
128  else
129  {
130  /* cand >= candsol
131  * if multvars[i] <= (candsol - (maxact - multscalars[i] * lb(multvars[i]))) / multscalars[i]
132  * = (candsol - maxact) / multscalars[i] + lb(multvars[i])
133  */
134  aggrvarsol2 = (candsol - maxact) / multscalars[i] + multvarlb;
135 
136  /* cand <= candsol
137  * if multvars[i] >= (candsol - (minact - multscalar[i] * ub(multvars[i]))) / multscalars[i]
138  * = (candsol - minact) / multscalars[i] + ub(multvars[i])
139  */
140  aggrvarsol1 = (candsol - minact) / multscalars[i] + multvarub;
141  }
142 
143  /* by the above choice, aggrvarsol1 <= ub(multvars[i]) and aggrvarsol2 >= lb(multvars[i])
144  * if aggrvarsol1 <= lb(multvars[i]) or aggrvarsol2 >= ub(multvars[i]), then choose the other one
145  * if both are out of bounds, then give up
146  * if both are inside bounds, then choose the one closer to 0.0 (someone has better idea???)
147  */
148  if( SCIPisFeasLE(scip, aggrvarsol1, multvarlb) )
149  {
150  if( SCIPisFeasGE(scip, aggrvarsol2, multvarub) )
151  continue;
152  else
153  aggrvarsol = aggrvarsol2;
154  }
155  else
156  {
157  if( SCIPisFeasGE(scip, aggrvarsol2, multvarub) )
158  aggrvarsol = aggrvarsol1;
159  else
160  aggrvarsol = REALABS(aggrvarsol1) < REALABS(aggrvarsol2) ? aggrvarsol1 : aggrvarsol2;
161  }
162  success = TRUE;
163 
164  updateBestCandidate(scip, bestvar, bestscore, bestobj, bestsol,
165  multvars[i], candscore, aggrvarsol);
166  }
167  }
168 
169  if( !success )
170  for( i = 0; i < nmultvars; ++i )
171  {
172  /* skip fixed variables */
173  multvarlb = SCIPcomputeVarLbLocal(scip, multvars[i]);
174  multvarub = SCIPcomputeVarUbLocal(scip, multvars[i]);
175  if( SCIPisEQ(scip, multvarlb, multvarub) )
176  continue;
177 
178  updateBestCandidate(scip, bestvar, bestscore, bestobj, bestsol,
179  multvars[i], candscore, SCIP_INVALID);
180  }
181 
182  assert(*bestvar != NULL); /* if all variables were fixed, something is strange */
183 
184  return;
185  }
186 
187  candscore *= SCIPvarGetBranchFactor(cand);
188  obj = SCIPvarGetObj(cand);
189  obj = REALABS(obj);
190  if( SCIPisInfinity(scip, *bestscore)
191  || (!SCIPisInfinity(scip, candscore) &&
192  (SCIPisLT(scip, candscore, *bestscore) || (SCIPisLE(scip, candscore, *bestscore) && obj > *bestobj))) )
193  {
194  *bestvar = cand;
195  *bestscore = candscore;
196  *bestobj = obj;
197  *bestsol = candsol;
198  }
199 }
200 
201 /*
202  * Callback methods
203  */
204 
205 /** copy method for branchrule plugins (called when SCIP copies plugins) */
206 static
207 SCIP_DECL_BRANCHCOPY(branchCopyLeastinf)
208 { /*lint --e{715}*/
209  assert(scip != NULL);
210  assert(branchrule != NULL);
211  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
212 
213  /* call inclusion method of branchrule */
215 
216  return SCIP_OKAY;
217 }
218 
219 
220 /** branching execution method for fractional LP solutions */
221 static
222 SCIP_DECL_BRANCHEXECLP(branchExeclpLeastinf)
223 { /*lint --e{715}*/
224  SCIP_VAR** lpcands;
225  SCIP_Real* lpcandsfrac;
226  int nlpcands;
227  SCIP_Real infeasibility;
228  SCIP_Real score;
229  SCIP_Real obj;
230  SCIP_Real bestscore;
231  SCIP_Real bestobj;
232  int bestcand;
233  int i;
234 
235  assert(branchrule != NULL);
236  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
237  assert(scip != NULL);
238  assert(result != NULL);
239 
240  SCIPdebugMsg(scip, "Execlp method of leastinf branching\n");
241 
242  /* get branching candidates */
243  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, NULL, &lpcandsfrac, NULL, &nlpcands, NULL) );
244  assert(nlpcands > 0);
245 
246  /* search the least infeasible candidate */
247  bestscore = SCIP_REAL_MIN;
248  bestobj = 0.0;
249  bestcand = -1;
250  for( i = 0; i < nlpcands; ++i )
251  {
252  assert(lpcands[i] != NULL);
253 
254  infeasibility = lpcandsfrac[i];
255  infeasibility = MIN(infeasibility, 1.0-infeasibility);
256  score = 1.0 - infeasibility;
257  score *= SCIPvarGetBranchFactor(lpcands[i]);
258  obj = SCIPvarGetObj(lpcands[i]);
259  obj = REALABS(obj);
260  if( SCIPisGT(scip, score, bestscore)
261  || (SCIPisGE(scip, score, bestscore) && obj > bestobj) )
262  {
263  bestscore = score;
264  bestobj = obj;
265  bestcand = i;
266  }
267  }
268  assert(bestcand >= 0);
269 
270  SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s> (frac=%g, obj=%g, factor=%g, score=%g)\n",
271  nlpcands, bestcand, SCIPvarGetName(lpcands[bestcand]), lpcandsfrac[bestcand], bestobj,
272  SCIPvarGetBranchFactor(lpcands[bestcand]), bestscore);
273 
274  /* perform the branching */
275  SCIP_CALL( SCIPbranchVar(scip, lpcands[bestcand], NULL, NULL, NULL) );
276  *result = SCIP_BRANCHED;
277 
278  return SCIP_OKAY;
279 }
280 
281 
282 /** branching execution method for external candidates */
283 static
284 SCIP_DECL_BRANCHEXECEXT(branchExecextLeastinf)
285 { /*lint --e{715}*/
286  SCIP_VAR** externcands;
287  SCIP_Real* externcandssol;
288  SCIP_Real* externcandsscore;
289  int nexterncands;
290  SCIP_VAR* bestcand;
291  SCIP_Real bestscore;
292  SCIP_Real bestobj;
293  SCIP_Real bestsol;
294  SCIP_Real brpoint;
295  int i;
296  SCIP_NODE* downchild;
297  SCIP_NODE* eqchild;
298  SCIP_NODE* upchild;
299 
300  assert(branchrule != NULL);
301  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
302  assert(scip != NULL);
303  assert(result != NULL);
304 
305  SCIPdebugMsg(scip, "Execext method of leastinf branching\n");
306 
307  /* get branching candidates */
308  SCIP_CALL( SCIPgetExternBranchCands(scip, &externcands, &externcandssol, &externcandsscore, NULL, &nexterncands, NULL, NULL, NULL) );
309  assert(nexterncands > 0);
310 
311  /* search the least infeasible candidate */
312  bestscore = SCIPinfinity(scip);
313  bestobj = 0.0;
314  bestcand = NULL;
315  bestsol = SCIP_INVALID;
316  for( i = 0; i < nexterncands; ++i )
317  {
318  updateBestCandidate(scip, &bestcand, &bestscore, &bestobj, &bestsol, externcands[i], externcandsscore[i], externcandssol[i]);
319  }
320 
321  if( bestcand == NULL )
322  {
323  SCIPerrorMessage("branchExecextLeastinf failed to select a branching variable from %d candidates\n", nexterncands);
324  *result = SCIP_DIDNOTRUN;
325  return SCIP_OKAY;
326  }
327 
328  brpoint = SCIPgetBranchingPoint(scip, bestcand, bestsol);
329 
330  SCIPdebugMsg(scip, " -> %d candidates, selected variable <%s> (infeas=%g, obj=%g, factor=%g, score=%g), branching point=%g\n",
331  nexterncands, SCIPvarGetName(bestcand), bestsol, bestobj,
332  SCIPvarGetBranchFactor(bestcand), bestscore, brpoint);
333 
334  /* perform the branching */
335  SCIP_CALL( SCIPbranchVarVal(scip, bestcand, brpoint, &downchild, &eqchild, &upchild) );
336 
337  if( downchild != NULL || eqchild != NULL || upchild != NULL )
338  {
339  *result = SCIP_BRANCHED;
340  }
341  else
342  {
343  /* if there are no children, then variable should have been fixed by SCIPbranchVarVal */
344  assert(SCIPisEQ(scip, SCIPvarGetLbLocal(bestcand), SCIPvarGetUbLocal(bestcand)));
345  *result = SCIP_REDUCEDDOM;
346  }
347 
348  return SCIP_OKAY;
349 }
350 
351 
352 /*
353  * branching specific interface methods
354  */
355 
356 /** creates the least infeasible LP branching rule and includes it in SCIP */
358  SCIP* scip /**< SCIP data structure */
359  )
360 {
361  SCIP_BRANCHRULE* branchrule;
362 
363  /* include branching rule */
364  branchrule = NULL;
367  assert(branchrule != NULL);
368 
369  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyLeastinf) );
370  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpLeastinf) );
371  SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextLeastinf) );
372 
373  return SCIP_OKAY;
374 }
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip.c:36128
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
Definition: var.c:16958
SCIP_Real SCIPvarGetBranchFactor(SCIP_VAR *var)
Definition: var.c:17326
#define BRANCHRULE_DESC
SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
Definition: var.c:16946
static SCIP_DECL_BRANCHCOPY(branchCopyLeastinf)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17222
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45803
#define BRANCHRULE_PRIORITY
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
Definition: scip.c:36631
#define BRANCHRULE_MAXBOUNDDIST
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46138
#define FALSE
Definition: def.h:64
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:45816
#define TRUE
Definition: def.h:63
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip.c:9038
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
least infeasible LP branching rule
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
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45751
SCIP_RETCODE SCIPgetExternBranchCands(SCIP *scip, SCIP_VAR ***externcands, SCIP_Real **externcandssol, SCIP_Real **externcandsscore, int *nexterncands, int *nprioexterncands, int *nprioexternbins, int *nprioexternints, int *nprioexternimpls)
Definition: scip.c:36244
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_Real SCIPcomputeVarLbLocal(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:23412
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip.c:9136
static SCIP_DECL_BRANCHEXECEXT(branchExecextLeastinf)
#define BRANCHRULE_NAME
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:11524
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip.c:36737
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45764
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
#define NULL
Definition: lpi_spx1.cpp:137
#define REALABS(x)
Definition: def.h:159
#define SCIP_CALL(x)
Definition: def.h:306
SCIP_Real SCIPcomputeVarUbLocal(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:23433
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip.c:36813
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46112
static void updateBestCandidate(SCIP *scip, SCIP_VAR **bestvar, SCIP_Real *bestscore, SCIP_Real *bestobj, SCIP_Real *bestsol, SCIP_VAR *cand, SCIP_Real candscore, SCIP_Real candsol)
#define SCIP_Bool
Definition: def.h:61
SCIP_RETCODE SCIPincludeBranchruleLeastinf(SCIP *scip)
static SCIP_DECL_BRANCHEXECLP(branchExeclpLeastinf)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17014
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip.c:9152
int SCIPvarGetMultaggrNVars(SCIP_VAR *var)
Definition: var.c:16934
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:45827
#define SCIP_REAL_MIN
Definition: def.h:137
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45790
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16671
#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
#define SCIP_INVALID
Definition: def.h:155
#define BRANCHRULE_MAXDEPTH
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45777
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17232
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16839