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