Scippy

SCIP

Solving Constraint Integer Programs

branch_mostinf.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-2016 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_mostinf.c
17  * @brief most infeasible LP branching rule
18  * @author Tobias Achterberg
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #include <string.h>
25 
26 #include "scip/branch_mostinf.h"
27 
28 
29 #define BRANCHRULE_NAME "mostinf"
30 #define BRANCHRULE_DESC "most infeasible branching"
31 #define BRANCHRULE_PRIORITY 100
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, candscore)
191  || (!SCIPisInfinity(scip, *bestscore) &&
192  (SCIPisGT(scip, candscore, *bestscore) || (SCIPisGE(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(branchCopyMostinf)
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(branchExeclpMostinf)
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  SCIPdebugMessage("Execlp method of mostinf 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 most 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 = 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  SCIPdebugMessage(" -> %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 /** branching execution method for external candidates */
282 static
283 SCIP_DECL_BRANCHEXECEXT(branchExecextMostinf)
284 { /*lint --e{715}*/
285  SCIP_VAR** externcands;
286  SCIP_Real* externcandssol;
287  SCIP_Real* externcandsscore;
288  int nexterncands;
289  SCIP_VAR* bestcand;
290  SCIP_Real bestscore;
291  SCIP_Real bestobj;
292  SCIP_Real bestsol;
293  SCIP_Real brpoint;
294  int i;
295  SCIP_NODE* downchild;
296  SCIP_NODE* eqchild;
297  SCIP_NODE* upchild;
298 
299  assert(branchrule != NULL);
300  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
301  assert(scip != NULL);
302  assert(result != NULL);
303 
304  SCIPdebugMessage("Execext method of mostinf branching\n");
305 
306  /* get branching candidates */
307  SCIP_CALL( SCIPgetExternBranchCands(scip, &externcands, &externcandssol, &externcandsscore, NULL, &nexterncands, NULL, NULL, NULL) );
308  assert(nexterncands > 0);
309 
310  /* search the most infeasible candidate */
311  bestscore = SCIP_REAL_MIN;
312  bestobj = 0.0;
313  bestcand = NULL;
314  bestsol = SCIP_INVALID;
315  for( i = 0; i < nexterncands; ++i )
316  {
317  updateBestCandidate(scip, &bestcand, &bestscore, &bestobj, &bestsol, externcands[i], externcandsscore[i], externcandssol[i]);
318  }
319 
320  if( bestcand == NULL )
321  {
322  SCIPerrorMessage("branchExecextMostinf failed to select a branching variable from %d candidates\n", nexterncands);
323  *result = SCIP_DIDNOTRUN;
324  return SCIP_OKAY;
325  }
326 
327  brpoint = SCIPgetBranchingPoint(scip, bestcand, bestsol);
328 
329  SCIPdebugMessage(" -> %d candidates, selected variable <%s> (infeas=%g, obj=%g, factor=%g, score=%g), branching point=%g\n",
330  nexterncands, SCIPvarGetName(bestcand), bestsol, bestobj,
331  SCIPvarGetBranchFactor(bestcand), bestscore, brpoint);
332 
333  /* perform the branching */
334  SCIP_CALL( SCIPbranchVarVal(scip, bestcand, brpoint, &downchild, &eqchild, &upchild) );
335 
336  if( downchild != NULL || eqchild != NULL || upchild != NULL )
337  {
338  *result = SCIP_BRANCHED;
339  }
340  else
341  {
342  /* if there are no children, then variable should have been fixed by SCIPbranchVarVal */
343  assert(SCIPisEQ(scip, SCIPvarGetLbLocal(bestcand), SCIPvarGetUbLocal(bestcand)));
344  *result = SCIP_REDUCEDDOM;
345  }
346 
347  return SCIP_OKAY;
348 }
349 
350 
351 /*
352  * branching specific interface methods
353  */
354 
355 /** creates the most infeasible LP branching rule and includes it in SCIP */
357  SCIP* scip /**< SCIP data structure */
358  )
359 {
360  SCIP_BRANCHRULE* branchrule;
361 
362  /* include branching rule */
365 
366  assert(branchrule != NULL);
367 
368  /* set non-fundamental callbacks via specific setter functions*/
369  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyMostinf) );
370  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpMostinf) );
371  SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextMostinf) );
372 
373  return SCIP_OKAY;
374 }
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41572
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip.c:33125
#define BRANCHRULE_DESC
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:33241
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16443
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip.c:33734
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:41648
#define NULL
Definition: lpi_spx.cpp:130
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17113
SCIP_Real SCIPcomputeVarLbLocal(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:21407
#define FALSE
Definition: def.h:56
#define TRUE
Definition: def.h:55
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIP_CALL(x)
Definition: def.h:266
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1877
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip.c:8290
#define SCIPdebugMessage
Definition: pub_message.h:77
#define BRANCHRULE_MAXDEPTH
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:16905
SCIP_Real SCIPvarGetBranchFactor(SCIP_VAR *var)
Definition: var.c:17217
SCIP_RETCODE SCIPincludeBranchruleMostinf(SCIP *scip)
#define BRANCHRULE_PRIORITY
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16562
static SCIP_DECL_BRANCHCOPY(branchCopyMostinf)
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip.c:8388
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:8253
#define SCIPerrorMessage
Definition: pub_message.h:45
static SCIP_DECL_BRANCHEXECLP(branchExeclpMostinf)
SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
Definition: var.c:16837
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41611
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17123
#define SCIP_Bool
Definition: def.h:53
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip.c:8404
SCIP_Real SCIPcomputeVarUbLocal(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:21428
int SCIPvarGetMultaggrNVars(SCIP_VAR *var)
Definition: var.c:16825
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
Definition: var.c:16849
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
Definition: scip.c:33628
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41624
#define BRANCHRULE_MAXBOUNDDIST
#define SCIP_REAL_MIN
Definition: def.h:129
most infeasible LP branching rule
#define REALABS(x)
Definition: def.h:151
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41933
#define SCIP_Real
Definition: def.h:127
#define MIN(x, y)
Definition: memory.c:67
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41959
#define SCIP_INVALID
Definition: def.h:147
#define BRANCHRULE_NAME
static SCIP_DECL_BRANCHEXECEXT(branchExecextMostinf)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16730
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:11481
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)
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip.c:33810