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