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-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_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 "scip/branch_mostinf.h"
24 #include "scip/pub_branch.h"
25 #include "scip/pub_message.h"
26 #include "scip/pub_var.h"
27 #include "scip/scip_branch.h"
28 #include "scip/scip_message.h"
29 #include "scip/scip_numerics.h"
30 #include "scip/scip_var.h"
31 #include <string.h>
32 
33 
34 #define BRANCHRULE_NAME "mostinf"
35 #define BRANCHRULE_DESC "most infeasible branching"
36 #define BRANCHRULE_PRIORITY 100
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, candscore)
196  || (!SCIPisInfinity(scip, *bestscore) &&
197  (SCIPisGT(scip, candscore, *bestscore) || (SCIPisGE(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(branchCopyMostinf)
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(branchExeclpMostinf)
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 mostinf 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 most 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 = 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 /** branching execution method for external candidates */
287 static
288 SCIP_DECL_BRANCHEXECEXT(branchExecextMostinf)
289 { /*lint --e{715}*/
290  SCIP_VAR** externcands;
291  SCIP_Real* externcandssol;
292  SCIP_Real* externcandsscore;
293  int nexterncands;
294  SCIP_VAR* bestcand;
295  SCIP_Real bestscore;
296  SCIP_Real bestobj;
297  SCIP_Real bestsol;
298  SCIP_Real brpoint;
299  int i;
300  SCIP_NODE* downchild;
301  SCIP_NODE* eqchild;
302  SCIP_NODE* upchild;
303 
304  assert(branchrule != NULL);
305  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
306  assert(scip != NULL);
307  assert(result != NULL);
308 
309  SCIPdebugMsg(scip, "Execext method of mostinf branching\n");
310 
311  /* get branching candidates */
312  SCIP_CALL( SCIPgetExternBranchCands(scip, &externcands, &externcandssol, &externcandsscore, NULL, &nexterncands, NULL, NULL, NULL) );
313  assert(nexterncands > 0);
314 
315  /* search the most infeasible candidate */
316  bestscore = SCIP_REAL_MIN;
317  bestobj = 0.0;
318  bestcand = NULL;
319  bestsol = SCIP_INVALID;
320  for( i = 0; i < nexterncands; ++i )
321  {
322  updateBestCandidate(scip, &bestcand, &bestscore, &bestobj, &bestsol, externcands[i], externcandsscore[i], externcandssol[i]);
323  }
324 
325  if( bestcand == NULL )
326  {
327  SCIPerrorMessage("branchExecextMostinf failed to select a branching variable from %d candidates\n", nexterncands);
328  *result = SCIP_DIDNOTRUN;
329  return SCIP_OKAY;
330  }
331 
332  brpoint = SCIPgetBranchingPoint(scip, bestcand, bestsol);
333 
334  SCIPdebugMsg(scip, " -> %d candidates, selected variable <%s> (infeas=%g, obj=%g, factor=%g, score=%g), branching point=%g\n",
335  nexterncands, SCIPvarGetName(bestcand), bestsol, bestobj,
336  SCIPvarGetBranchFactor(bestcand), bestscore, brpoint);
337 
338  /* perform the branching */
339  SCIP_CALL( SCIPbranchVarVal(scip, bestcand, brpoint, &downchild, &eqchild, &upchild) );
340 
341  if( downchild != NULL || eqchild != NULL || upchild != NULL )
342  {
343  *result = SCIP_BRANCHED;
344  }
345  else
346  {
347  /* if there are no children, then variable should have been fixed by SCIPbranchVarVal */
348  assert(SCIPisEQ(scip, SCIPvarGetLbLocal(bestcand), SCIPvarGetUbLocal(bestcand)));
349  *result = SCIP_REDUCEDDOM;
350  }
351 
352  return SCIP_OKAY;
353 }
354 
355 
356 /*
357  * branching specific interface methods
358  */
359 
360 /** creates the most infeasible LP branching rule and includes it in SCIP */
362  SCIP* scip /**< SCIP data structure */
363  )
364 {
365  SCIP_BRANCHRULE* branchrule;
366 
367  /* include branching rule */
370 
371  assert(branchrule != NULL);
372 
373  /* set non-fundamental callbacks via specific setter functions*/
374  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyMostinf) );
375  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpMostinf) );
376  SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextMostinf) );
377 
378  return SCIP_OKAY;
379 }
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:238
#define NULL
Definition: def.h:253
#define BRANCHRULE_DESC
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPcomputeVarLbLocal(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:6417
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
Definition: scip_branch.c:886
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1970
SCIP_EXPORT SCIP_Real SCIPvarGetBranchFactor(SCIP_VAR *var)
Definition: var.c:17512
SCIP_RETCODE SCIPincludeBranchruleMostinf(SCIP *scip)
#define FALSE
Definition: def.h:73
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17200
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:142
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_EXPORT SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17025
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:1068
#define BRANCHRULE_MAXDEPTH
public methods for branching rules
SCIP_EXPORT SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16857
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
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:17144
#define BRANCHRULE_PRIORITY
static SCIP_DECL_BRANCHCOPY(branchCopyMostinf)
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16738
#define SCIPerrorMessage
Definition: pub_message.h:45
static SCIP_DECL_BRANCHEXECLP(branchExeclpMostinf)
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
SCIP_Real SCIPcomputeVarUbLocal(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:6438
#define REALABS(x)
Definition: def.h:188
#define SCIP_CALL(x)
Definition: def.h:365
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:992
#define SCIP_Bool
Definition: def.h:70
SCIP_EXPORT SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:11712
#define MIN(x, y)
Definition: def.h:223
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip_branch.c:254
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17408
#define BRANCHRULE_MAXBOUNDDIST
#define SCIP_REAL_MIN
Definition: def.h:166
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17418
most infeasible LP branching rule
public methods for branching rule plugins and branching
SCIP_EXPORT int SCIPvarGetMultaggrNVars(SCIP_VAR *var)
Definition: var.c:17120
public methods for message output
#define SCIP_Real
Definition: def.h:164
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:384
#define SCIP_INVALID
Definition: def.h:184
#define BRANCHRULE_NAME
static SCIP_DECL_BRANCHEXECEXT(branchExecextMostinf)
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_EXPORT SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
Definition: var.c:17132