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-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_leastinf.c
26  * @ingroup DEFPLUGINS_BRANCH
27  * @brief least infeasible LP branching rule
28  * @author Tobias Achterberg
29  * @author Stefan Vigerske
30  */
31 
32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33 
34 #include "scip/branch_leastinf.h"
35 #include "scip/pub_branch.h"
36 #include "scip/pub_message.h"
37 #include "scip/pub_var.h"
38 #include "scip/scip_branch.h"
39 #include "scip/scip_message.h"
40 #include "scip/scip_numerics.h"
41 #include "scip/scip_var.h"
42 #include <string.h>
43 
44 #define BRANCHRULE_NAME "leastinf"
45 #define BRANCHRULE_DESC "least infeasible branching"
46 #define BRANCHRULE_PRIORITY 50
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, *bestscore)
206  || (!SCIPisInfinity(scip, candscore) &&
207  (SCIPisLT(scip, candscore, *bestscore) || (SCIPisLE(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(branchCopyLeastinf)
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(branchExeclpLeastinf)
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 leastinf 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 least 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 = 1.0 - 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 
297 /** branching execution method for external candidates */
298 static
299 SCIP_DECL_BRANCHEXECEXT(branchExecextLeastinf)
300 { /*lint --e{715}*/
301  SCIP_VAR** externcands;
302  SCIP_Real* externcandssol;
303  SCIP_Real* externcandsscore;
304  int nexterncands;
305  SCIP_VAR* bestcand;
306  SCIP_Real bestscore;
307  SCIP_Real bestobj;
308  SCIP_Real bestsol;
309  SCIP_Real brpoint;
310  int i;
311  SCIP_NODE* downchild;
312  SCIP_NODE* eqchild;
313  SCIP_NODE* upchild;
314 
315  assert(branchrule != NULL);
316  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
317  assert(scip != NULL);
318  assert(result != NULL);
319 
320  SCIPdebugMsg(scip, "Execext method of leastinf branching\n");
321 
322  /* get branching candidates */
323  SCIP_CALL( SCIPgetExternBranchCands(scip, &externcands, &externcandssol, &externcandsscore, NULL, &nexterncands, NULL, NULL, NULL) );
324  assert(nexterncands > 0);
325 
326  /* search the least infeasible candidate */
327  bestscore = SCIPinfinity(scip);
328  bestobj = 0.0;
329  bestcand = NULL;
330  bestsol = SCIP_INVALID;
331  for( i = 0; i < nexterncands; ++i )
332  {
333  updateBestCandidate(scip, &bestcand, &bestscore, &bestobj, &bestsol, externcands[i], externcandsscore[i], externcandssol[i]);
334  }
335 
336  if( bestcand == NULL )
337  {
338  SCIPerrorMessage("branchExecextLeastinf failed to select a branching variable from %d candidates\n", nexterncands);
339  *result = SCIP_DIDNOTRUN;
340  return SCIP_OKAY;
341  }
342 
343  brpoint = SCIPgetBranchingPoint(scip, bestcand, bestsol);
344 
345  SCIPdebugMsg(scip, " -> %d candidates, selected variable <%s> (infeas=%g, obj=%g, factor=%g, score=%g), branching point=%g\n",
346  nexterncands, SCIPvarGetName(bestcand), bestsol, bestobj,
347  SCIPvarGetBranchFactor(bestcand), bestscore, brpoint);
348 
349  /* perform the branching */
350  SCIP_CALL( SCIPbranchVarVal(scip, bestcand, brpoint, &downchild, &eqchild, &upchild) );
351 
352  if( downchild != NULL || eqchild != NULL || upchild != NULL )
353  {
354  *result = SCIP_BRANCHED;
355  }
356  else
357  {
358  /* if there are no children, then variable should have been fixed by SCIPbranchVarVal */
359  assert(SCIPisEQ(scip, SCIPvarGetLbLocal(bestcand), SCIPvarGetUbLocal(bestcand)));
360  *result = SCIP_REDUCEDDOM;
361  }
362 
363  return SCIP_OKAY;
364 }
365 
366 
367 /*
368  * branching specific interface methods
369  */
370 
371 /** creates the least infeasible LP branching rule and includes it in SCIP */
373  SCIP* scip /**< SCIP data structure */
374  )
375 {
376  SCIP_BRANCHRULE* branchrule;
377 
378  /* include branching rule */
379  branchrule = NULL;
382  assert(branchrule != NULL);
383 
384  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyLeastinf) );
385  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpLeastinf) );
386  SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextLeastinf) );
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
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
Definition: var.c:17693
SCIP_Real SCIPvarGetBranchFactor(SCIP_VAR *var)
Definition: var.c:18061
#define BRANCHRULE_DESC
SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
Definition: var.c:17681
static SCIP_DECL_BRANCHCOPY(branchCopyLeastinf)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17957
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:897
#define BRANCHRULE_MAXBOUNDDIST
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define FALSE
Definition: def.h:96
SCIP_Real SCIPinfinity(SCIP *scip)
#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
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: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
static SCIP_DECL_BRANCHEXECEXT(branchExecextLeastinf)
#define BRANCHRULE_NAME
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:12208
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
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17242
#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)
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:93
SCIP_RETCODE SCIPincludeBranchruleLeastinf(SCIP *scip)
static SCIP_DECL_BRANCHEXECLP(branchExeclpLeastinf)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17749
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:17669
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define SCIP_REAL_MIN
Definition: def.h:188
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:17361
#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_MAXDEPTH
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17967
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17571