Scippy

SCIP

Solving Constraint Integer Programs

branch_vanillafullstrong.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_vanillafullstrong.c
26 * @ingroup DEFPLUGINS_BRANCH
27 * @brief vanilla full strong LP branching rule
28 * @author Tobias Achterberg
29 * @author Maxime Gasse
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 "vanillafullstrong"
55#define BRANCHRULE_DESC "vanilla full strong branching"
56#define BRANCHRULE_PRIORITY -2000
57#define BRANCHRULE_MAXDEPTH -1
58#define BRANCHRULE_MAXBOUNDDIST 1.0
59
60#define DEFAULT_INTEGRALCANDS FALSE /**< should integral variables in the current LP solution be considered as
61 * branching candidates ? */
62#define DEFAULT_SCOREALL FALSE /**< should strong branching scores be computed for all candidates, or can
63 * we early stop when a variable has infinite score ? */
64#define DEFAULT_IDEMPOTENT FALSE /**< should strong branching side-effects be prevented (e.g., domain
65 * changes, stat updates etc.) ? */
66#define DEFAULT_COLLECTSCORES FALSE /**< should strong branching scores be collected ? */
67#define DEFAULT_DONOTBRANCH FALSE /**< should branching be done ? */
68
69
70/** branching rule data */
71struct SCIP_BranchruleData
72{
73 SCIP_Bool integralcands; /**< should integral variables in the current LP solution be considered
74 * as branching candidates ? */
75 SCIP_Bool scoreall; /**< should strong branching scores be computed for all candidates, or
76 * can we early stop when a node is detected infeasible ? */
77 SCIP_Bool idempotent; /**< should strong branching side-effects be prevented (e.g., domain
78 * changes, stat updates etc.) ? */
79 SCIP_Bool collectscores; /**< should strong branching scores be collected ? */
80 SCIP_Bool donotbranch; /**< should branching be done ? */
81 SCIP_VAR** cands; /**< candidate variables */
82 SCIP_Real* candscores; /**< candidate scores */
83 int ncands; /**< number of candidates */
84 int npriocands; /**< number of priority candidates */
85 int bestcand; /**< best branching candidate */
86 int candcapacity; /**< capacity of candidate arrays */
87};
88
89
90/*
91 * local methods
92 */
93
94
95/** selects a variable from a set of candidates by strong branching */
96static
98 SCIP* scip, /**< SCIP data structure */
99 SCIP_VAR** cands, /**< branching candidates */
100 int ncands, /**< number of branching candidates */
101 int npriocands, /**< number of branching candidates with highest priority */
102 SCIP_Bool scoreall, /**< should strong branching scores be computed for all candidates, or can
103 * we early stop when a node is detected infeasible ? */
104 SCIP_Bool idempotent, /**< should strong branching side-effects be prevented (e.g., domain
105 * changes, stat updates etc.) ? */
106 SCIP_Real* scores, /**< candidate scores */
107 int* bestcand, /**< best candidate for branching */
108 SCIP_Real* bestdown, /**< objective value of the down branch for bestcand */
109 SCIP_Real* bestup, /**< objective value of the up branch for bestcand */
110 SCIP_Real* bestscore, /**< score for bestcand */
111 SCIP_Bool* bestdownvalid, /**< is bestdown a valid dual bound for the down branch? */
112 SCIP_Bool* bestupvalid, /**< is bestup a valid dual bound for the up branch? */
113 SCIP_Real* provedbound /**< proved dual bound for current subtree */
114 )
115{ /*lint --e{715}*/
116 SCIP_Real lpobjval;
117 int nsbcalls;
118 int c;
119
120 assert(scip != NULL);
121 assert(cands != NULL);
122 assert(bestcand != NULL);
123 assert(bestdown != NULL);
124 assert(bestup != NULL);
125 assert(bestscore != NULL);
126 assert(bestdownvalid != NULL);
127 assert(bestupvalid != NULL);
128 assert(provedbound != NULL);
129 assert(ncands > 0);
130
131 /* get current LP objective bound of the local sub problem and global cutoff bound */
132 lpobjval = SCIPgetLPObjval(scip);
133 *provedbound = lpobjval;
134
135 *bestcand = 0;
136 *bestdown = lpobjval;
137 *bestup = lpobjval;
138 *bestdownvalid = TRUE;
139 *bestupvalid = TRUE;
140 *bestscore = -SCIPinfinity(scip);
141
142 if( scores != NULL )
143 for( c = 0; c < ncands; ++c )
144 scores[c] = -SCIPinfinity(scip);
145
146 /* if only one candidate exists, choose this one without applying strong branching; also, when SCIP is about to be
147 * stopped, all strongbranching evaluations will be aborted anyway, thus we can return immediately
148 */
149 if( (!scoreall && ncands == 1) || SCIPisStopped(scip) )
150 return SCIP_OKAY;
151
152 /* this assert may not hold if SCIP is stopped, thus we only check it here */
154
155 /* initialize strong branching without propagation */
157
158 /* compute strong branching scores */
159 nsbcalls = 0;
160 for( c = 0; c < ncands ; ++c )
161 {
162 SCIP_VAR* var;
163 SCIP_Real val;
164 SCIP_Bool integral;
165 SCIP_Real down, up;
166 SCIP_Real downgain, upgain;
167 SCIP_Bool downvalid, upvalid;
168 SCIP_Bool downinf, upinf;
169 SCIP_Bool downconflict, upconflict;
170 SCIP_Bool lperror;
171 SCIP_Real gains[3];
172 SCIP_Real score;
173
174 var = cands[c];
175 assert(var != NULL);
176
177 val = SCIPvarGetLPSol(var);
178 integral = SCIPisFeasIntegral(scip, val);
179
180 up = -SCIPinfinity(scip);
181 down = -SCIPinfinity(scip);
182
183 SCIPdebugMsg(scip, "applying vanilla strong branching on variable <%s> with solution %g\n",
184 SCIPvarGetName(var), val);
185
186 /* apply strong branching */
187 if( integral )
188 {
189 SCIP_CALL( SCIPgetVarStrongbranchInt(scip, cands[c], INT_MAX, idempotent,
190 &down, &up, &downvalid, &upvalid, &downinf, &upinf, &downconflict, &upconflict, &lperror) );
191 }
192 else
193 {
194 SCIP_CALL( SCIPgetVarStrongbranchFrac(scip, cands[c], INT_MAX, idempotent,
195 &down, &up, &downvalid, &upvalid, &downinf, &upinf, &downconflict, &upconflict, &lperror) );
196 }
197 nsbcalls++;
198
199 /* check for an error in strong branching */
200 if( lperror )
201 {
203 "(node %" SCIP_LONGINT_FORMAT ") error in strong branching call for variable <%s> with solution %g\n",
204 SCIPgetNNodes(scip), SCIPvarGetName(var), val);
205 break;
206 }
207
208 /* evaluate strong branching */
209 down = MAX(down, lpobjval);
210 up = MAX(up, lpobjval);
211 downgain = down - lpobjval;
212 upgain = up - lpobjval;
213
214 assert(!SCIPallColsInLP(scip) || SCIPisExactSolve(scip) || !downvalid || downinf == SCIPisGE(scip, down, SCIPgetCutoffbound(scip)));
215 assert(!SCIPallColsInLP(scip) || SCIPisExactSolve(scip) || !upvalid || upinf == SCIPisGE(scip, up, SCIPgetCutoffbound(scip)));
216 assert(downinf || !downconflict);
217 assert(upinf || !upconflict);
218
219 if( !idempotent )
220 {
221 /* display node information line */
222 if( SCIPgetDepth(scip) == 0 && nsbcalls % 100 == 0 )
223 {
225 }
226 /* update variable pseudo cost values */
227 if( !downinf && downvalid )
228 {
229 SCIP_CALL( SCIPupdateVarPseudocost(scip, var, integral ? -1.0 : 0.0 - SCIPfrac(scip, val), downgain, 1.0) );
230 }
231 if( !upinf && upvalid )
232 {
233 SCIP_CALL( SCIPupdateVarPseudocost(scip, var, integral ? +1.0 : 1.0 - SCIPfrac(scip, val), upgain, 1.0) );
234 }
235 }
236
237 /* compute strong branching score */
238 gains[0] = downgain;
239 gains[1] = upgain;
240 gains[2] = 0.0;
241 score = SCIPgetBranchScoreMultiple(scip, var, integral ? 3 : 2, gains);
242
243 /* collect scores if requested */
244 if( scores != NULL )
245 scores[c] = score;
246
247 /* check for a better score */
248 if( score > *bestscore )
249 {
250 *bestcand = c;
251 *bestdown = down;
252 *bestup = up;
253 *bestdownvalid = downvalid;
254 *bestupvalid = upvalid;
255 *bestscore = score;
256 }
257
258 SCIPdebugMsg(scip, " -> cand %d/%d (prio:%d) var <%s> (solval=%g, downgain=%g, upgain=%g, score=%g) -- best: <%s> (%g)\n",
259 c, ncands, npriocands, SCIPvarGetName(var), val, downgain, upgain, score,
260 SCIPvarGetName(cands[*bestcand]), *bestscore);
261
262 /* node is infeasible -> early stopping (highest score) */
263 if( !integral && !scoreall && downinf && upinf )
264 {
265 /* we should only detect infeasibility if the LP is a valid relaxation */
266 assert(SCIPallColsInLP(scip));
267 assert(!SCIPisExactSolve(scip));
268
269 SCIPdebugMsg(scip, " -> variable <%s> is infeasible in both directions\n", SCIPvarGetName(var));
270 break;
271 }
272 }
273
274 /* end strong branching */
276
277 return SCIP_OKAY;
278}
279
280/*
281 * Callback methods
282 */
283
284/** copy method for branchrule plugins (called when SCIP copies plugins) */
285static
286SCIP_DECL_BRANCHCOPY(branchCopyVanillafullstrong)
287{ /*lint --e{715}*/
288 assert(scip != NULL);
289 assert(branchrule != NULL);
290 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
291
292 /* call inclusion method of branchrule */
294
295 return SCIP_OKAY;
296}
297
298/** destructor of branching rule to free user data (called when SCIP is exiting) */
299static
300SCIP_DECL_BRANCHFREE(branchFreeVanillafullstrong)
301{ /*lint --e{715}*/
302 SCIP_BRANCHRULEDATA* branchruledata;
303
304 /* free branching rule data */
305 branchruledata = SCIPbranchruleGetData(branchrule);
306 assert(branchruledata != NULL);
307
308 SCIPfreeBlockMemoryNull(scip, &branchruledata);
309
310 return SCIP_OKAY;
311}
312
313/** initialization method of branching rule (called after problem was transformed) */
314static
315SCIP_DECL_BRANCHINIT(branchInitVanillafullstrong)
316{ /*lint --e{715}*/
317#ifndef NDEBUG
318 SCIP_BRANCHRULEDATA* branchruledata;
319
320 /* initialize branching rule data */
321 branchruledata = SCIPbranchruleGetData(branchrule);
322#endif
323 assert(branchruledata != NULL);
324 assert(branchruledata->candscores == NULL);
325 assert(branchruledata->cands == NULL);
326
327 return SCIP_OKAY;
328}
329
330/** deinitialization method of branching rule (called before transformed problem is freed) */
331static
332SCIP_DECL_BRANCHEXIT(branchExitVanillafullstrong)
333{ /*lint --e{715}*/
334 SCIP_BRANCHRULEDATA* branchruledata;
335
336 /* initialize branching rule data */
337 branchruledata = SCIPbranchruleGetData(branchrule);
338 assert(branchruledata != NULL);
339
340 /* free candidate arrays if any */
341 if( branchruledata->candscores != NULL )
342 {
343 SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->candscores, branchruledata->candcapacity);
344 }
345 if( branchruledata->cands != NULL )
346 {
347 SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->cands, branchruledata->candcapacity);
348 }
349
350 branchruledata->candcapacity = -1;
351 branchruledata->ncands = -1;
352 branchruledata->npriocands = -1;
353 branchruledata->bestcand = -1;
354
355 return SCIP_OKAY;
356}
357
358/** branching execution method */
359static
360SCIP_DECL_BRANCHEXECLP(branchExeclpVanillafullstrong)
361{ /*lint --e{715}*/
362 SCIP_BRANCHRULEDATA* branchruledata;
363 SCIP_Real bestdown;
364 SCIP_Real bestup;
365 SCIP_Real bestscore;
366 SCIP_Real provedbound;
367 SCIP_Bool bestdownvalid;
368 SCIP_Bool bestupvalid;
369 SCIP_VAR** cands;
370 int ncands;
371 int npriocands;
372 int i;
373
374 assert(branchrule != NULL);
375 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
376 assert(scip != NULL);
377 assert(result != NULL);
378
379 SCIPdebugMsg(scip, "Execlp method of vanilla fullstrong branching\n");
380
381 *result = SCIP_DIDNOTRUN;
382
383 /* get branching rule data */
384 branchruledata = SCIPbranchruleGetData(branchrule);
385 assert(branchruledata != NULL);
386
387 /* get branching candidates, either all non-fixed variables or only the
388 * fractional ones */
389 if( branchruledata->integralcands )
390 {
391 SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, &ncands, &npriocands) );
392 }
393 else
394 {
395 SCIP_CALL( SCIPgetLPBranchCands(scip, &cands, NULL, NULL, &ncands, &npriocands, NULL) );
396 }
397
398 assert(ncands > 0);
399 assert(npriocands > 0);
400
401 /* increase candidate arrays capacity if needed */
402 if( ncands > branchruledata->candcapacity )
403 {
404 /* free previously allocated arrays if any */
405 if( branchruledata->candscores != NULL)
406 {
407 SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->candscores, branchruledata->candcapacity);
408 branchruledata->candscores = NULL;
409 }
410 if( branchruledata->cands != NULL)
411 {
412 SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->cands, branchruledata->candcapacity);
413 branchruledata->cands = NULL;
414 }
415
416 /* update capacity */
417 branchruledata->candcapacity = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) + SCIPgetNImplVars(scip);
418 }
419 assert(branchruledata->candcapacity >= ncands);
420
421 /* allocate new candidate arrays if needed */
422 if( branchruledata->cands == NULL )
423 {
424 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->cands, branchruledata->candcapacity) );
425 }
426 if( branchruledata->candscores == NULL && branchruledata->collectscores )
427 {
428 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->candscores, branchruledata->candcapacity) );
429 }
430
431 /* copy candidates */
432 branchruledata->ncands = ncands;
433 branchruledata->npriocands = npriocands;
434
435 for( i = 0; i < ncands; i++ )
436 branchruledata->cands[i] = cands[i];
437
438 SCIP_CALL( runVanillaStrongBranching(scip, branchruledata->cands, branchruledata->ncands, branchruledata->npriocands,
439 branchruledata->scoreall, branchruledata->idempotent, branchruledata->candscores,
440 &branchruledata->bestcand, &bestdown, &bestup, &bestscore, &bestdownvalid,
441 &bestupvalid, &provedbound) );
442
443 if( !branchruledata->donotbranch )
444 {
445 SCIP_VAR* var;
446 SCIP_Real val;
447 SCIP_NODE* downchild;
448 SCIP_NODE* eqchild;
449 SCIP_NODE* upchild;
450 SCIP_Bool allcolsinlp;
451 SCIP_Bool exactsolve;
452
453 assert(0 <= branchruledata->bestcand && branchruledata->bestcand < branchruledata->ncands);
454 assert(SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
455
456 var = branchruledata->cands[branchruledata->bestcand];
457 val = SCIPvarGetLPSol(var);
458
459 /* perform the branching */
460 SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s>[%g,%g] (solval=%g, down=%g, up=%g, score=%g)\n",
461 branchruledata->ncands, branchruledata->bestcand, SCIPvarGetName(var), SCIPvarGetLbLocal(var),
462 SCIPvarGetUbLocal(var), val, bestdown, bestup, bestscore);
463 SCIP_CALL( SCIPbranchVarVal(scip, var, val, &downchild, &eqchild, &upchild) );
464
465 /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
466 * for cutting off sub problems and improving lower bounds of children
467 */
468 exactsolve = SCIPisExactSolve(scip);
469
470 /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
471 allcolsinlp = SCIPallColsInLP(scip);
472
473 /* update the lower bounds in the children */
474 if( !branchruledata->idempotent && allcolsinlp && !exactsolve )
475 {
476 if( downchild != NULL )
477 {
478 SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestdownvalid ? MAX(bestdown, provedbound) : provedbound) );
479 SCIPdebugMsg(scip, " -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild));
480 }
481 if( eqchild != NULL )
482 {
483 SCIP_CALL( SCIPupdateNodeLowerbound(scip, eqchild, provedbound) );
484 SCIPdebugMsg(scip, " -> eq child's lowerbound: %g\n", SCIPnodeGetLowerbound(eqchild));
485 }
486 if( upchild != NULL )
487 {
488 SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestupvalid ? MAX(bestup, provedbound) : provedbound) );
489 SCIPdebugMsg(scip, " -> up child's lowerbound: %g\n", SCIPnodeGetLowerbound(upchild));
490 }
491 }
492
493 *result = SCIP_BRANCHED;
494 }
495
496 return SCIP_OKAY;
497}
498
499
500/*
501 * branching specific interface methods
502 */
503
504/** creates the vanilla full strong LP branching rule and includes it in SCIP */
506 SCIP* scip /**< SCIP data structure */
507 )
508{
509 SCIP_BRANCHRULEDATA* branchruledata;
510 SCIP_BRANCHRULE* branchrule;
511
512 /* create fullstrong branching rule data */
513 SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
514 branchruledata->cands = NULL;
515 branchruledata->candscores = NULL;
516 branchruledata->candcapacity = -1;
517 branchruledata->ncands = -1;
518 branchruledata->npriocands = -1;
519 branchruledata->bestcand = -1;
520
521 /* include branching rule */
524
525 assert(branchrule != NULL);
526
527 /* set non-fundamental callbacks via specific setter functions*/
528 SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyVanillafullstrong) );
529 SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeVanillafullstrong) );
530 SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitVanillafullstrong) );
531 SCIP_CALL( SCIPsetBranchruleExit(scip, branchrule, branchExitVanillafullstrong) );
532 SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpVanillafullstrong) );
533
534 /* fullstrong branching rule parameters */
536 "branching/vanillafullstrong/integralcands",
537 "should integral variables in the current LP solution be considered as branching candidates?",
538 &branchruledata->integralcands, FALSE, DEFAULT_INTEGRALCANDS, NULL, NULL) );
540 "branching/vanillafullstrong/idempotent",
541 "should strong branching side-effects be prevented (e.g., domain changes, stat updates etc.)?",
542 &branchruledata->idempotent, FALSE, DEFAULT_IDEMPOTENT, NULL, NULL) );
544 "branching/vanillafullstrong/scoreall",
545 "should strong branching scores be computed for all candidates, or can we early stop when a variable has infinite score?",
546 &branchruledata->scoreall, TRUE, DEFAULT_SCOREALL, NULL, NULL) );
548 "branching/vanillafullstrong/collectscores",
549 "should strong branching scores be collected?",
550 &branchruledata->collectscores, TRUE, DEFAULT_COLLECTSCORES, NULL, NULL) );
552 "branching/vanillafullstrong/donotbranch",
553 "should candidates only be scored, but no branching be performed?",
554 &branchruledata->donotbranch, TRUE, DEFAULT_DONOTBRANCH, NULL, NULL) );
555
556 return SCIP_OKAY;
557}
558
559
560/** recovers candidate variables and their scores from last vanilla full strong branching call */
562 SCIP* scip, /**< SCIP data structure */
563 SCIP_VAR*** cands, /**< pointer to store candidate variables; or NULL */
564 SCIP_Real** candscores, /**< pointer to store candidate scores; or NULL */
565 int* ncands, /**< pointer to store number of candidates; or NULL */
566 int* npriocands, /**< pointer to store number of priority candidates; or NULL */
567 int* bestcand /**< pointer to store best branching candidate; or NULL */
568 )
569{
570 SCIP_BRANCHRULEDATA* branchruledata;
571 SCIP_BRANCHRULE* branchrule;
572
573 assert(scip != NULL);
574
576 assert( branchrule != NULL );
577 branchruledata = SCIPbranchruleGetData(branchrule);
578 assert( branchruledata != NULL );
579
580 if( cands )
581 {
582 *cands = branchruledata->cands;
583 }
584 if( candscores && branchruledata->collectscores )
585 {
586 *candscores = branchruledata->candscores;
587 }
588 if( ncands )
589 {
590 *ncands = branchruledata->ncands;
591 }
592 if( npriocands )
593 {
594 *npriocands = branchruledata->npriocands;
595 }
596 if( bestcand )
597 {
598 *bestcand = branchruledata->bestcand;
599 }
600
601 return SCIP_OKAY;
602}
#define BRANCHRULE_DESC
#define DEFAULT_IDEMPOTENT
#define BRANCHRULE_PRIORITY
SCIP_RETCODE SCIPgetVanillafullstrongData(SCIP *scip, SCIP_VAR ***cands, SCIP_Real **candscores, int *ncands, int *npriocands, int *bestcand)
#define DEFAULT_SCOREALL
#define BRANCHRULE_NAME
static SCIP_DECL_BRANCHCOPY(branchCopyVanillafullstrong)
static SCIP_RETCODE runVanillaStrongBranching(SCIP *scip, SCIP_VAR **cands, int ncands, int npriocands, SCIP_Bool scoreall, SCIP_Bool idempotent, SCIP_Real *scores, int *bestcand, SCIP_Real *bestdown, SCIP_Real *bestup, SCIP_Real *bestscore, SCIP_Bool *bestdownvalid, SCIP_Bool *bestupvalid, SCIP_Real *provedbound)
#define DEFAULT_INTEGRALCANDS
#define DEFAULT_DONOTBRANCH
static SCIP_DECL_BRANCHFREE(branchFreeVanillafullstrong)
static SCIP_DECL_BRANCHEXIT(branchExitVanillafullstrong)
static SCIP_DECL_BRANCHEXECLP(branchExeclpVanillafullstrong)
static SCIP_DECL_BRANCHINIT(branchInitVanillafullstrong)
#define BRANCHRULE_MAXDEPTH
#define DEFAULT_COLLECTSCORES
#define BRANCHRULE_MAXBOUNDDIST
vanilla full strong LP branching rule
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#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_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPincludeBranchruleVanillafullstrong(SCIP *scip)
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
SCIP_Bool SCIPisExactSolve(SCIP *scip)
Definition: scip_general.c:611
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2127
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
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 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
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_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:733
SCIP_Real SCIPgetBranchScoreMultiple(SCIP *scip, SCIP_VAR *var, int nchildren, SCIP_Real *gains)
Definition: scip_branch.c:872
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 SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
#define SCIPfreeBlockMemoryNull(scip, ptr)
Definition: scip_mem.h:109
#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_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
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 SCIPgetVarStrongbranchInt(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:3662
SCIP_RETCODE SCIPendStrongbranch(SCIP *scip)
Definition: scip_var.c:2744
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18452
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 SCIPstartStrongbranch(SCIP *scip, SCIP_Bool enablepropagation)
Definition: scip_var.c:2686
memory allocation routines
public methods for branching rules
public methods for message output
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_BRANCHED
Definition: type_result.h:54
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63