SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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
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 */
55static
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);
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 */
79
81 {
82 /* for a multi-aggregated variable, we call updateBestCandidate function recursively with all variables in the multi-aggregation */
84 int nmultvars;
85 int i;
86 SCIP_Bool success;
87 SCIP_Real multvarlb;
88 SCIP_Real multvarub;
89
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
109
110 /* for computing the branching point, we need the current bounds of the multi-aggregated variable */
113
114 for( i = 0; i < nmultvars; ++i )
115 {
116 /* skip fixed variables */
120 continue;
121
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 */
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 */
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 */
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 */
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 */
164 {
166 continue;
167 else
169 }
170 else
171 {
174 else
176 }
177 success = TRUE;
178
181 }
182 }
183
184 if( !success )
185 for( i = 0; i < nmultvars; ++i )
186 {
187 /* skip fixed variables */
191 continue;
192
195 }
196
197 assert(*bestvar != NULL); /* if all variables were fixed, something is strange */
198
199 return;
200 }
201
204 obj = REALABS(obj);
206 || (!SCIPisInfinity(scip, candscore) &&
208 {
209 *bestvar = cand;
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) */
221static
223{ /*lint --e{715}*/
224 assert(scip != NULL);
227
228 /* call inclusion method of branchrule */
230
231 return SCIP_OKAY;
232}
233
234
235/** branching execution method for fractional LP solutions */
236static
238{ /*lint --e{715}*/
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
252 assert(scip != NULL);
253 assert(result != NULL);
254
255 SCIPdebugMsg(scip, "Execlp method of leastinf branching\n");
256
257 /* get branching candidates */
259 assert(nlpcands > 0);
260
261 /* search the least infeasible candidate */
263 bestobj = 0.0;
264 bestcand = -1;
265 for( i = 0; i < nlpcands; ++i )
266 {
267 assert(lpcands[i] != NULL);
268
271 score = 1.0 - infeasibility;
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",
288
289 /* perform the branching */
292
293 return SCIP_OKAY;
294}
295
296
297/** branching execution method for external candidates */
298static
300{ /*lint --e{715}*/
301 SCIP_VAR** externcands;
302 SCIP_Real* externcandssol;
303 SCIP_Real* externcandsscore;
304 int nexterncands;
306 SCIP_Real bestscore;
307 SCIP_Real bestobj;
308 SCIP_Real bestsol;
309 SCIP_Real brpoint;
310 int i;
314
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 */
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);
340 return SCIP_OKAY;
341 }
342
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,
348
349 /* perform the branching */
351
352 if( downchild != NULL || eqchild != NULL || upchild != NULL )
353 {
355 }
356 else
357 {
358 /* if there are no children, then variable should have been fixed by SCIPbranchVarVal */
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 */
#define BRANCHRULE_DESC
#define BRANCHRULE_PRIORITY
#define BRANCHRULE_NAME
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 BRANCHRULE_MAXDEPTH
#define BRANCHRULE_MAXBOUNDDIST
least infeasible LP branching rule
#define SCIP_INVALID
Definition def.h:206
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIP_REAL_MIN
Definition def.h:188
#define REALABS(x)
Definition def.h:210
#define SCIP_CALL(x)
Definition def.h:388
SCIP_RETCODE SCIPincludeBranchruleLeastinf(SCIP *scip)
#define SCIPdebugMsg
SCIP_RETCODE SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition branch.c:1971
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPgetExternBranchCands(SCIP *scip, SCIP_VAR ***externcands, SCIP_Real **externcandssol, SCIP_Real **externcandsscore, int *nexterncands, int *nprioexterncands, int *nprioexternbins, int *nprioexternints, int *nprioexternimpls)
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition var.c:17570
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17360
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:17966
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17748
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition var.c:12207
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17241
SCIP_Real SCIPvarGetBranchFactor(SCIP_VAR *var)
Definition var.c:18060
SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
Definition var.c:17680
int SCIPvarGetMultaggrNVars(SCIP_VAR *var)
Definition var.c:17668
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:17956
SCIP_Real SCIPcomputeVarLbLocal(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:6505
SCIP_Real SCIPcomputeVarUbLocal(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:6526
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
Definition var.c:17692
return SCIP_OKAY
int nlpcands
SCIP_Real obj
SCIP_VAR ** lpcands
assert(minobj< SCIPgetCutoffbound(scip))
int bestcand
SCIP_Real * lpcandsfrac
#define NULL
Definition lpi_spx1.cpp:161
public methods for branching rules
public methods for message output
#define SCIPerrorMessage
Definition pub_message.h:64
public methods for problem variables
public methods for branching rule plugins and branching
public methods for message handling
public methods for numerical tolerances
public methods for SCIP variables
#define SCIP_DECL_BRANCHEXECLP(x)
#define SCIP_DECL_BRANCHEXECEXT(x)
#define SCIP_DECL_BRANCHCOPY(x)
Definition type_branch.h:67
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_REDUCEDDOM
Definition type_result.h:51
@ SCIP_BRANCHED
Definition type_result.h:54
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARSTATUS_MULTAGGR
Definition type_var.h:54