Scippy

SCIP

Solving Constraint Integer Programs

branch_fullstrong.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-2024 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_fullstrong.c
26 * @ingroup DEFPLUGINS_BRANCH
27 * @brief full strong LP branching rule
28 * @author Tobias Achterberg
29 * @author Gerald Gamrath
30 */
31
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
36#include "scip/pub_branch.h"
37#include "scip/pub_message.h"
38#include "scip/pub_tree.h"
39#include "scip/pub_var.h"
40#include "scip/scip_branch.h"
41#include "scip/scip_general.h"
42#include "scip/scip_lp.h"
43#include "scip/scip_mem.h"
44#include "scip/scip_message.h"
45#include "scip/scip_numerics.h"
46#include "scip/scip_param.h"
47#include "scip/scip_prob.h"
49#include "scip/scip_tree.h"
50#include "scip/scip_var.h"
51#include <string.h>
52
53
54#define BRANCHRULE_NAME "fullstrong"
55#define BRANCHRULE_DESC "full strong branching"
56#define BRANCHRULE_PRIORITY 0
57#define BRANCHRULE_MAXDEPTH -1
58#define BRANCHRULE_MAXBOUNDDIST 1.0
59
60#define DEFAULT_REEVALAGE 10LL /**< number of intermediate LPs solved to trigger reevaluation of strong branching
61 * value for a variable that was already evaluated at the current node */
62#define DEFAULT_MAXPROPROUNDS -2 /**< maximum number of propagation rounds to be performed during strong branching
63 * before solving the LP (-1: no limit, -2: parameter settings) */
64#define DEFAULT_PROBINGBOUNDS TRUE /**< should valid bounds be identified in a probing-like fashion during strong
65 * branching (only with propagation)? */
66#define DEFAULT_FORCESTRONGBRANCH FALSE /**< should strong branching be applied even if there is just a single candidate? */
67
68
69/** branching rule data */
70struct SCIP_BranchruleData
71{
72 SCIP_Longint reevalage; /**< number of intermediate LPs solved to trigger reevaluation of strong branching
73 * value for a variable that was already evaluated at the current node */
74 int maxproprounds; /**< maximum number of propagation rounds to be performed during strong branching
75 * before solving the LP (-1: no limit, -2: parameter settings) */
76 SCIP_Bool probingbounds; /**< should valid bounds be identified in a probing-like fashion during strong
77 * branching (only with propagation)? */
78 SCIP_Bool forcestrongbranch; /**< should strong branching be applied even if there is just a single candidate? */
79 int lastcand; /**< last evaluated candidate of last branching rule execution */
80 int skipsize; /**< size of skipdown and skipup array */
81 SCIP_Bool* skipdown; /**< should be branching on down child be skipped? */
82 SCIP_Bool* skipup; /**< should be branching on up child be skipped? */
83};
84
85
86/*
87 * Callback methods
88 */
89
90/** copy method for branchrule plugins (called when SCIP copies plugins) */
91static
92SCIP_DECL_BRANCHCOPY(branchCopyFullstrong)
93{ /*lint --e{715}*/
94 assert(scip != NULL);
95 assert(branchrule != NULL);
96 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
97
98 /* call inclusion method of branchrule */
100
101 return SCIP_OKAY;
102}
103
104/** destructor of branching rule to free user data (called when SCIP is exiting) */
105static
106SCIP_DECL_BRANCHFREE(branchFreeFullstrong)
107{ /*lint --e{715}*/
108 SCIP_BRANCHRULEDATA* branchruledata;
109
110 /* free branching rule data */
111 branchruledata = SCIPbranchruleGetData(branchrule);
112 assert(branchruledata != NULL);
113
114 SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipdown, branchruledata->skipsize);
115 SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipup, branchruledata->skipsize);
116
117 SCIPfreeBlockMemory(scip, &branchruledata);
118 SCIPbranchruleSetData(branchrule, NULL);
119
120 return SCIP_OKAY;
121}
122
123
124/** initialization method of branching rule (called after problem was transformed) */
125static
126SCIP_DECL_BRANCHINIT(branchInitFullstrong)
127{ /*lint --e{715}*/
128 SCIP_BRANCHRULEDATA* branchruledata;
129
130 /* initialize branching rule data */
131 branchruledata = SCIPbranchruleGetData(branchrule);
132 assert(branchruledata != NULL);
133
134 branchruledata->lastcand = 0;
135
136 return SCIP_OKAY;
137}
138
139/** deinitialization method of branching rule (called before transformed problem is freed) */
140static
141SCIP_DECL_BRANCHEXIT(branchExitFullstrong)
142{ /*lint --e{715}*/
143 SCIP_BRANCHRULEDATA* branchruledata;
144
145 /* initialize branching rule data */
146 branchruledata = SCIPbranchruleGetData(branchrule);
147 assert(branchruledata != NULL);
148 assert((branchruledata->skipdown != NULL) == (branchruledata->skipup != NULL));
149
150 if( branchruledata->skipdown != NULL )
151 {
152 SCIPfreeBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize);
153 SCIPfreeBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize);
154 branchruledata->skipdown = NULL;
155 branchruledata->skipup = NULL;
156 branchruledata->skipsize = 0;
157 }
158
159 return SCIP_OKAY;
160}
161
162/**
163 * Selects a variable from a set of candidates by strong branching
164 *
165 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
166 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
167 *
168 * @note The variables in the lpcands array must have a fractional value in the current LP solution
169 */
171 SCIP* scip, /**< original SCIP data structure */
172 SCIP_VAR** lpcands, /**< branching candidates */
173 SCIP_Real* lpcandssol, /**< solution values of the branching candidates */
174 SCIP_Real* lpcandsfrac, /**< fractional values of the branching candidates */
175 SCIP_Bool* skipdown, /**< should down branchings be skipped? */
176 SCIP_Bool* skipup, /**< should up branchings be skipped? */
177 int nlpcands, /**< number of branching candidates */
178 int npriolpcands, /**< number of priority branching candidates */
179 int ncomplete, /**< number of branching candidates without skip */
180 int* start, /**< starting index in lpcands */
181 int maxproprounds, /**< maximum number of propagation rounds to be performed during strong
182 * branching before solving the LP (-1: no limit, -2: parameter settings) */
183 SCIP_Bool probingbounds, /**< should valid bounds be identified in a probing-like fashion during
184 * strong branching (only with propagation)? */
185 SCIP_Bool forcestrongbranch, /**< should strong branching be applied even if there is just a single candidate? */
186 int* bestcand, /**< best candidate for branching */
187 SCIP_Real* bestdown, /**< objective value of the down branch for bestcand */
188 SCIP_Real* bestup, /**< objective value of the up branch for bestcand */
189 SCIP_Real* bestscore, /**< score for bestcand */
190 SCIP_Bool* bestdownvalid, /**< is bestdown a valid dual bound for the down branch? */
191 SCIP_Bool* bestupvalid, /**< is bestup a valid dual bound for the up branch? */
192 SCIP_Real* provedbound, /**< proved dual bound for current subtree */
193 SCIP_RESULT* result /**< result pointer */
194 )
195{ /*lint --e{715}*/
196 SCIP_VAR** vars = NULL;
197 SCIP_Real* newlbs = NULL;
198 SCIP_Real* newubs = NULL;
199 SCIP_BRANCHRULE* branchrule;
200 SCIP_BRANCHRULEDATA* branchruledata;
201 SCIP_Longint reevalage;
202 SCIP_Longint nodenum;
203 SCIP_Real down;
204 SCIP_Real up;
205 SCIP_Real downgain;
206 SCIP_Real upgain;
207 SCIP_Real score;
208 SCIP_Real lpobjval;
209 SCIP_Bool exactsolve;
210 SCIP_Bool lperror;
211 SCIP_Bool allcolsinlp;
212 SCIP_Bool downvalid;
213 SCIP_Bool upvalid;
214 SCIP_Bool downinf;
215 SCIP_Bool upinf;
216 SCIP_Bool downconflict;
217 SCIP_Bool upconflict;
218 SCIP_Bool bothgains;
219 SCIP_Bool propagate;
220 int nvars = 0;
221 int nsbcalls;
222 int i;
223 int c;
224
225 assert(scip != NULL);
226 assert(lpcands != NULL);
227 assert(lpcandssol != NULL);
228 assert(lpcandsfrac != NULL);
229 assert(bestcand != NULL);
230 assert(skipdown != NULL);
231 assert(skipup != NULL);
232 assert(bestdown != NULL);
233 assert(bestup != NULL);
234 assert(bestscore != NULL);
235 assert(bestdownvalid != NULL);
236 assert(bestupvalid != NULL);
237 assert(provedbound != NULL);
238 assert(result != NULL);
239 assert(nlpcands > 0);
240
241 /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
242 * for cutting off sub problems and improving lower bounds of children
243 */
244 exactsolve = SCIPisExactSolve(scip);
245
246 /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
247 allcolsinlp = SCIPallColsInLP(scip);
248
249 /* get current node number */
250 nodenum = SCIPgetNNodes(scip);
251
252 /* get current LP objective bound of the local sub problem and global cutoff bound */
253 lpobjval = SCIPgetLPObjval(scip);
254 *provedbound = lpobjval;
255
256 *bestcand = 0;
257 *bestdown = lpobjval;
258 *bestup = lpobjval;
259 *bestdownvalid = TRUE;
260 *bestupvalid = TRUE;
261 *bestscore = -SCIPinfinity(scip);
262
263 /* if only one candidate exists, choose this one without applying strong branching; also, when SCIP is about to be
264 * stopped, all strongbranching evaluations will be aborted anyway, thus we can return immediately
265 */
266 if( (!forcestrongbranch && nlpcands == 1) || SCIPisStopped(scip) )
267 return SCIP_OKAY;
268
269 /* this assert may not hold if SCIP is stopped, thus we only check it here */
271
272 /* get branching rule */
274 assert(branchrule != NULL);
275
276 /* get branching rule data */
277 branchruledata = SCIPbranchruleGetData(branchrule);
278 assert(branchruledata != NULL);
279
280 /* auto-setting for reevalage */
281 reevalage = branchruledata->reevalage;
282
283 /* check whether propagation should be performed */
284 propagate = (maxproprounds != 0);
285
286 /* if we don't do propagation, we cannot identify valid bounds in a probing-like fashion */
287 if( !propagate && maxproprounds > -3 )
288 probingbounds = FALSE;
289
290 /* create arrays for probing-like bound tightening */
291 if( probingbounds )
292 {
293 vars = SCIPgetVars(scip);
294 nvars = SCIPgetNVars(scip);
295
296 SCIP_CALL( SCIPallocBufferArray(scip, &newlbs, nvars) );
297 SCIP_CALL( SCIPallocBufferArray(scip, &newubs, nvars) );
298 }
299
300 /* initialize strong branching */
301 SCIP_CALL( SCIPstartStrongbranch(scip, propagate) );
302
303 /* search the full strong candidate
304 * cycle through the candidates, starting with the position evaluated in the last run
305 */
306 nsbcalls = 0;
307 bothgains = TRUE;
308 for( i = 0, c = *start; i < nlpcands && (!bothgains || i < ncomplete); ++i, ++c )
309 {
310 c = c % nlpcands;
311 assert(lpcands[c] != NULL);
312
313 /* don't use strong branching on variables that have already been initialized at the current node,
314 * and that were evaluated not too long ago
315 */
316 if( SCIPgetVarStrongbranchNode(scip, lpcands[c]) == nodenum
317 && SCIPgetVarStrongbranchLPAge(scip, lpcands[c]) < reevalage )
318 {
319 SCIP_Real lastlpobjval;
320
321 /* use the score of the strong branching call at the current node */
322 SCIP_CALL( SCIPgetVarStrongbranchLast(scip, lpcands[c], &down, &up, NULL, NULL, NULL, &lastlpobjval) );
323 downgain = MAX(down - lastlpobjval, 0.0);
324 upgain = MAX(up - lastlpobjval, 0.0);
325 downvalid = FALSE;
326 upvalid = FALSE;
327 downinf = FALSE;
328 upinf = FALSE;
329 downconflict = FALSE;
330 upconflict = FALSE;
331 lperror = FALSE;
332 SCIPdebugMsg(scip, "strong branching on variable <%s> already performed (lpage=%" SCIP_LONGINT_FORMAT ", down=%g (%+g), up=%g (%+g))\n",
333 SCIPvarGetName(lpcands[c]), SCIPgetVarStrongbranchLPAge(scip, lpcands[c]), down, downgain, up, upgain);
334 }
335 else
336 {
337 SCIPdebugMsg(scip, "applying strong branching%s on variable <%s> with solution %g\n",
338 propagate ? "with propagation" : "", SCIPvarGetName(lpcands[c]), lpcandssol[c]);
339 assert(i >= ncomplete || (!skipdown[i] && !skipup[i]));
340
341 /* apply strong branching */
342 up = -SCIPinfinity(scip);
343 down = -SCIPinfinity(scip);
344
345 if( propagate )
346 {
347 SCIP_CALL( SCIPgetVarStrongbranchWithPropagation(scip, lpcands[c], lpcandssol[c], lpobjval, INT_MAX,
348 maxproprounds, skipdown[i] ? NULL : &down, skipup[i] ? NULL : &up, &downvalid,
349 &upvalid, NULL, NULL, &downinf, &upinf, &downconflict, &upconflict, &lperror, newlbs, newubs) );
350
351 SCIPdebugMsg(scip, "-> down=%.9g (gain=%.9g, valid=%u, inf=%u, conflict=%u), up=%.9g (gain=%.9g, valid=%u, inf=%u, conflict=%u)\n",
352 down, down - lpobjval, downvalid, downinf, downconflict, up, up - lpobjval, upvalid, upinf, upconflict);
353 }
354 else
355 {
356 SCIP_CALL( SCIPgetVarStrongbranchFrac(scip, lpcands[c], INT_MAX, FALSE,
357 skipdown[i] ? NULL : &down, skipup[i] ? NULL : &up, &downvalid, &upvalid, &downinf, &upinf,
358 &downconflict, &upconflict, &lperror) );
359 }
360 nsbcalls++;
361
362 /* display node information line */
363 if( SCIPgetDepth(scip) == 0 && nsbcalls % 100 == 0 )
364 {
366 }
367
368 /* check for an error in strong branching */
369 if( lperror )
370 {
372 "(node %" SCIP_LONGINT_FORMAT ") error in strong branching call%s for variable <%s> with solution %g\n",
373 SCIPgetNNodes(scip), propagate ? " with propagation" : "", SCIPvarGetName(lpcands[c]), lpcandssol[c]);
374 break;
375 }
376
377 /* evaluate strong branching */
378 down = MAX(down, lpobjval);
379 up = MAX(up, lpobjval);
380 downgain = down - lpobjval;
381 upgain = up - lpobjval;
382 if( !SCIPisFeasZero(scip,downgain) && !SCIPisFeasZero(scip,upgain) )
383 bothgains = TRUE;
384
385 assert(!allcolsinlp || exactsolve || !downvalid || downinf == SCIPisGE(scip, down, SCIPgetCutoffbound(scip)));
386 assert(!allcolsinlp || exactsolve || !upvalid || upinf == SCIPisGE(scip, up, SCIPgetCutoffbound(scip)));
387 assert(downinf || !downconflict);
388 assert(upinf || !upconflict);
389
390 /* update pseudo cost values */
391 if( !downinf && downvalid )
392 {
393 SCIP_CALL( SCIPupdateVarPseudocost(scip, lpcands[c], 0.0-lpcandsfrac[c], downgain, 1.0) );
394 }
395 if( !upinf && upvalid )
396 {
397 SCIP_CALL( SCIPupdateVarPseudocost(scip, lpcands[c], 1.0-lpcandsfrac[c], upgain, 1.0) );
398 }
399
400 /* check if there are infeasible roundings */
401 if( downinf || upinf )
402 {
403 /* if we didn't do propagation, we can only detect infeasibility if the LP is a valid relaxation */
404 assert(allcolsinlp || propagate);
405 assert(!exactsolve);
406
407 if( downinf && upinf )
408 {
409 /* both roundings are infeasible -> node is infeasible */
410 *result = SCIP_CUTOFF;
411 SCIPdebugMsg(scip, " -> variable <%s> is infeasible in both directions\n", SCIPvarGetName(lpcands[c]));
412 break; /* terminate initialization loop, because node is infeasible */
413 }
414 else if( downinf )
415 {
416 SCIP_Bool infeasible;
417 SCIP_Bool tightened;
418
419 /* downwards rounding is infeasible -> change lower bound of variable to upward rounding */
420 SCIP_CALL( SCIPtightenVarLb(scip, lpcands[c], SCIPfeasCeil(scip, lpcandssol[c]), TRUE, &infeasible, &tightened) );
421 assert(!infeasible);
422
423 /* if we did propagation, the bound change might already have been added */
424 assert(tightened || propagate);
425
426 *result = SCIP_REDUCEDDOM;
427 SCIPdebugMsg(scip, " -> variable <%s> is infeasible in downward branch\n", SCIPvarGetName(lpcands[c]));
428 break; /* terminate initialization loop, because LP was changed */
429 }
430 else
431 {
432 SCIP_Bool infeasible;
433 SCIP_Bool tightened;
434
435 /* upwards rounding is infeasible -> change upper bound of variable to downward rounding */
436 assert(upinf);
437 SCIP_CALL( SCIPtightenVarUb(scip, lpcands[c], SCIPfeasFloor(scip, lpcandssol[c]), TRUE, &infeasible, &tightened) );
438 assert(!infeasible);
439
440 /* if we did propagation, the bound change might already have been added */
441 assert(tightened || propagate);
442
443 *result = SCIP_REDUCEDDOM;
444 SCIPdebugMsg(scip, " -> variable <%s> is infeasible in upward branch\n", SCIPvarGetName(lpcands[c]));
445 break; /* terminate initialization loop, because LP was changed */
446 }
447 }
448 else if( allcolsinlp && !exactsolve && downvalid && upvalid )
449 {
450 SCIP_Real minbound;
451
452 /* the minimal lower bound of both children is a proved lower bound of the current subtree */
453 minbound = MIN(down, up);
454 *provedbound = MAX(*provedbound, minbound);
455
456 /* apply probing-like bounds detected during strong branching */
457 if( probingbounds )
458 {
459 int nboundchgs;
460 int v;
461
462 assert(vars != NULL);
463 assert(nvars > 0);
464 assert(newlbs != NULL);
465 assert(newubs != NULL);
466
467 nboundchgs = 0;
468
469 for( v = 0; v < nvars; ++v )
470 {
471 if( SCIPisGT(scip, newlbs[v], SCIPvarGetLbLocal(vars[v])) )
472 {
473 SCIPdebugMsg(scip, "better lower bound for variable <%s>: %.9g -> %.9g (strongbranching on var <%s>\n",
474 SCIPvarGetName(vars[v]), SCIPvarGetLbLocal(vars[v]), newlbs[v], SCIPvarGetName(lpcands[c]));
475
476 SCIP_CALL( SCIPchgVarLb(scip, vars[v], newlbs[v]) );
477 ++nboundchgs;
478 }
479 if( SCIPisLT(scip, newubs[v], SCIPvarGetUbLocal(vars[v])) )
480 {
481 SCIPdebugMsg(scip, "better upper bound for variable <%s>: %.9g -> %.9g (strongbranching on var <%s>\n",
482 SCIPvarGetName(vars[v]), SCIPvarGetUbLocal(vars[v]), newubs[v], SCIPvarGetName(lpcands[c]));
483
484 SCIP_CALL( SCIPchgVarUb(scip, vars[v], newubs[v]) );
485 ++nboundchgs;
486 }
487 }
488
489 if( nboundchgs > 0 )
490 {
491 *result = SCIP_REDUCEDDOM;
492 SCIPdebugMsg(scip, " -> strong branching with propagation on variable <%s> led to %d bound changes\n",
493 SCIPvarGetName(lpcands[c]), nboundchgs);
494 break; /* terminate initialization loop, because LP was changed */
495 }
496 }
497 }
498 }
499
500 /* check for a better score, if we are within the maximum priority candidates */
501 if( c < npriolpcands )
502 {
503 score = SCIPgetBranchScore(scip, lpcands[c], downgain, upgain);
504 if( score > *bestscore )
505 {
506 *bestcand = c;
507 *bestdown = down;
508 *bestup = up;
509 *bestdownvalid = downvalid;
510 *bestupvalid = upvalid;
511 *bestscore = score;
512 }
513 }
514 else
515 {
516 SCIPdebug(score = 0.0;)
517 }
518
519 SCIPdebugMsg(scip, " -> cand %d/%d (prio:%d) var <%s> (solval=%g, downgain=%g, upgain=%g, score=%g) -- best: <%s> (%g)\n",
520 c, nlpcands, npriolpcands, SCIPvarGetName(lpcands[c]), lpcandssol[c], downgain, upgain, score,
521 SCIPvarGetName(lpcands[*bestcand]), *bestscore);
522 }
523
524 /* end strong branching */
526
527 *start = c;
528
529 if( probingbounds )
530 {
531 assert(newlbs != NULL);
532 assert(newubs != NULL);
533
534 SCIPfreeBufferArray(scip, &newlbs);
535 SCIPfreeBufferArray(scip, &newubs);
536 }
537
538 return SCIP_OKAY;
539}
540
541/** branching execution method for fractional LP solutions */
542static
543SCIP_DECL_BRANCHEXECLP(branchExeclpFullstrong)
544{ /*lint --e{715}*/
545 SCIP_BRANCHRULEDATA* branchruledata;
546 SCIP_VAR** tmplpcands;
547 SCIP_VAR** lpcands;
548 SCIP_Real* tmplpcandssol;
549 SCIP_Real* lpcandssol;
550 SCIP_Real* tmplpcandsfrac;
551 SCIP_Real* lpcandsfrac;
552 SCIP_Real bestdown;
553 SCIP_Real bestup;
554 SCIP_Real bestscore;
555 SCIP_Real provedbound;
556 SCIP_Bool bestdownvalid;
557 SCIP_Bool bestupvalid;
558 int nlpcands;
559 int npriolpcands;
560 int bestcand;
561
562 assert(branchrule != NULL);
563 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
564 assert(scip != NULL);
565 assert(result != NULL);
566
567 SCIPdebugMsg(scip, "Execlp method of fullstrong branching\n");
568
569 *result = SCIP_DIDNOTRUN;
570
571 /* get branching rule data */
572 branchruledata = SCIPbranchruleGetData(branchrule);
573 assert(branchruledata != NULL);
574
575 /* get branching candidates */
576 SCIP_CALL( SCIPgetLPBranchCands(scip, &tmplpcands, &tmplpcandssol, &tmplpcandsfrac, &nlpcands, &npriolpcands, NULL) );
577 assert(nlpcands > 0);
578 assert(npriolpcands > 0);
579
580 /* copy LP banching candidates and solution values, because they will be updated w.r.t. the strong branching LP
581 * solution
582 */
583 SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcands, tmplpcands, nlpcands) );
584 SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandssol, tmplpcandssol, nlpcands) );
585 SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandsfrac, tmplpcandsfrac, nlpcands) );
586
587 if( branchruledata->skipdown == NULL )
588 {
589 assert(branchruledata->skipup == NULL);
590
591 branchruledata->skipsize = SCIPgetNVars(scip);
592 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize) );
593 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize) );
594 BMSclearMemoryArray(branchruledata->skipdown, branchruledata->skipsize);
595 BMSclearMemoryArray(branchruledata->skipup, branchruledata->skipsize);
596 }
597
598 SCIP_CALL( SCIPselectVarStrongBranching(scip, lpcands, lpcandssol, lpcandsfrac, branchruledata->skipdown,
599 branchruledata->skipup, nlpcands, npriolpcands, nlpcands, &branchruledata->lastcand,
600 branchruledata->maxproprounds, branchruledata->probingbounds, branchruledata->forcestrongbranch, &bestcand,
601 &bestdown, &bestup, &bestscore, &bestdownvalid, &bestupvalid, &provedbound, result) );
602
603 if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED )
604 {
605 SCIP_NODE* downchild;
606 SCIP_NODE* upchild;
607 SCIP_VAR* var;
608 SCIP_Real val;
609 SCIP_Bool allcolsinlp;
610 SCIP_Bool exactsolve;
611
612 assert(*result == SCIP_DIDNOTRUN);
613 assert(0 <= bestcand && bestcand < nlpcands);
614 assert(SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
615
616 var = lpcands[bestcand];
617 val = lpcandssol[bestcand];
618
619 /* perform the branching */
620 SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s> (solval=%g, down=%g, up=%g, score=%g)\n",
621 nlpcands, bestcand, SCIPvarGetName(var), lpcandssol[bestcand], bestdown, bestup, bestscore);
622 SCIP_CALL( SCIPbranchVarVal(scip, var, val, &downchild, NULL, &upchild) );
623 assert(downchild != NULL);
624 assert(upchild != NULL);
625
626 /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
627 * for cutting off sub problems and improving lower bounds of children
628 */
629 exactsolve = SCIPisExactSolve(scip);
630
631 /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
632 allcolsinlp = SCIPallColsInLP(scip);
633
634 /* update the lower bounds in the children */
635 if( allcolsinlp && !exactsolve )
636 {
637 SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestdownvalid ? MAX(bestdown, provedbound) : provedbound) );
638 SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestupvalid ? MAX(bestup, provedbound) : provedbound) );
639 }
640 SCIPdebugMsg(scip, " -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild));
641 SCIPdebugMsg(scip, " -> up child's lowerbound: %g\n", SCIPnodeGetLowerbound(upchild));
642
643 *result = SCIP_BRANCHED;
644 }
645
646 SCIPfreeBufferArray(scip, &lpcandsfrac);
647 SCIPfreeBufferArray(scip, &lpcandssol);
648 SCIPfreeBufferArray(scip, &lpcands);
649
650 return SCIP_OKAY;
651}
652
653
654/*
655 * branching specific interface methods
656 */
657
658/** creates the full strong LP branching rule and includes it in SCIP */
660 SCIP* scip /**< SCIP data structure */
661 )
662{
663 SCIP_BRANCHRULEDATA* branchruledata;
664 SCIP_BRANCHRULE* branchrule;
665
666 /* create fullstrong branching rule data */
667 SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
668 branchruledata->lastcand = 0;
669 branchruledata->skipsize = 0;
670 branchruledata->skipup = NULL;
671 branchruledata->skipdown = NULL;
672
673 /* include branching rule */
676
677 assert(branchrule != NULL);
678
679 /* set non-fundamental callbacks via specific setter functions*/
680 SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyFullstrong) );
681 SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeFullstrong) );
682 SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitFullstrong) );
683 SCIP_CALL( SCIPsetBranchruleExit(scip, branchrule, branchExitFullstrong) );
684 SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpFullstrong) );
685
686 /* fullstrong branching rule parameters */
688 "branching/fullstrong/reevalage",
689 "number of intermediate LPs solved to trigger reevaluation of strong branching value for a variable that was already evaluated at the current node",
690 &branchruledata->reevalage, TRUE, DEFAULT_REEVALAGE, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
692 "branching/fullstrong/maxproprounds",
693 "maximum number of propagation rounds to be performed during strong branching before solving the LP (-1: no limit, -2: parameter settings)",
694 &branchruledata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -3, INT_MAX, NULL, NULL) );
696 "branching/fullstrong/probingbounds",
697 "should valid bounds be identified in a probing-like fashion during strong branching (only with propagation)?",
698 &branchruledata->probingbounds, TRUE, DEFAULT_PROBINGBOUNDS, NULL, NULL) );
700 "branching/fullstrong/forcestrongbranch",
701 "should strong branching be applied even if there is just a single candidate?",
702 &branchruledata->forcestrongbranch, TRUE, DEFAULT_FORCESTRONGBRANCH, NULL, NULL) );
703
704 return SCIP_OKAY;
705}
#define BRANCHRULE_DESC
#define BRANCHRULE_PRIORITY
#define DEFAULT_PROBINGBOUNDS
static SCIP_DECL_BRANCHEXIT(branchExitFullstrong)
#define DEFAULT_REEVALAGE
static SCIP_DECL_BRANCHINIT(branchInitFullstrong)
#define BRANCHRULE_NAME
static SCIP_DECL_BRANCHFREE(branchFreeFullstrong)
#define DEFAULT_FORCESTRONGBRANCH
#define DEFAULT_MAXPROPROUNDS
#define BRANCHRULE_MAXDEPTH
static SCIP_DECL_BRANCHCOPY(branchCopyFullstrong)
#define BRANCHRULE_MAXBOUNDDIST
static SCIP_DECL_BRANCHEXECLP(branchExeclpFullstrong)
full strong LP branching rule
#define NULL
Definition: def.h:267
#define SCIP_Longint
Definition: def.h:158
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define SCIP_LONGINT_MAX
Definition: def.h:159
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPselectVarStrongBranching(SCIP *scip, SCIP_VAR **lpcands, SCIP_Real *lpcandssol, SCIP_Real *lpcandsfrac, SCIP_Bool *skipdown, SCIP_Bool *skipup, int nlpcands, int npriolpcands, int ncomplete, int *start, int maxproprounds, SCIP_Bool probingbounds, SCIP_Bool forcestrongbranch, int *bestcand, SCIP_Real *bestdown, SCIP_Real *bestup, SCIP_Real *bestscore, SCIP_Bool *bestdownvalid, SCIP_Bool *bestupvalid, SCIP_Real *provedbound, SCIP_RESULT *result)
SCIP_RETCODE SCIPincludeBranchruleFullstrong(SCIP *scip)
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
SCIP_Bool SCIPisExactSolve(SCIP *scip)
Definition: scip_general.c:611
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
SCIP_RETCODE SCIPupdateNodeLowerbound(SCIP *scip, SCIP_NODE *node, SCIP_Real newbound)
Definition: scip_prob.c:3757
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:111
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: scip_branch.c:201
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:249
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:297
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:153
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
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1849
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:169
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip_branch.c:185
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1859
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_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 SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip_branch.c:849
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip_lp.c:649
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:247
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7513
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_RETCODE SCIPprintDisplayLine(SCIP *scip, FILE *file, SCIP_VERBLEVEL verblevel, SCIP_Bool endline)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_RETCODE SCIPgetVarStrongbranchFrac(SCIP *scip, SCIP_VAR *var, int itlim, SCIP_Bool idempotent, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, SCIP_Bool *downinf, SCIP_Bool *upinf, SCIP_Bool *downconflict, SCIP_Bool *upconflict, SCIP_Bool *lperror)
Definition: scip_var.c:2919
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5203
SCIP_RETCODE SCIPendStrongbranch(SCIP *scip)
Definition: scip_var.c:2744
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4676
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4766
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5320
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Longint SCIPgetVarStrongbranchNode(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:4160
SCIP_Longint SCIPgetVarStrongbranchLPAge(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:4194
SCIP_RETCODE SCIPgetVarStrongbranchWithPropagation(SCIP *scip, SCIP_VAR *var, SCIP_Real solval, SCIP_Real lpobjval, int itlim, int maxproprounds, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, SCIP_Longint *ndomredsdown, SCIP_Longint *ndomredsup, SCIP_Bool *downinf, SCIP_Bool *upinf, SCIP_Bool *downconflict, SCIP_Bool *upconflict, SCIP_Bool *lperror, SCIP_Real *newlbs, SCIP_Real *newubs)
Definition: scip_var.c:3352
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
SCIP_RETCODE SCIPupdateVarPseudocost(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: scip_var.c:8780
SCIP_RETCODE SCIPgetVarStrongbranchLast(SCIP *scip, SCIP_VAR *var, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, SCIP_Real *solval, SCIP_Real *lpobjval)
Definition: scip_var.c:4010
SCIP_RETCODE SCIPstartStrongbranch(SCIP *scip, SCIP_Bool enablepropagation)
Definition: scip_var.c:2686
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
public methods for branching rules
public methods for message output
#define SCIPdebug(x)
Definition: pub_message.h:93
public methods for branch and bound tree
public methods for problem variables
public methods for branching rule plugins and branching
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:57
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
@ SCIP_VERBLEVEL_HIGH
Definition: type_message.h:56
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_REDUCEDDOM
Definition: type_result.h:51
@ SCIP_CONSADDED
Definition: type_result.h:52
@ SCIP_BRANCHED
Definition: type_result.h:54
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63