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