Scippy

SCIP

Solving Constraint Integer Programs

branch_allfullstrong.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_allfullstrong.c
26 * @ingroup DEFPLUGINS_BRANCH
27 * @brief all variables full strong LP branching rule
28 * @author Tobias Achterberg
29 *
30 * The all variables full strong branching rule applies strong branching to every non-fixed variable
31 * at the current node of the branch-and-bound search. The rule selects the candidate
32 * which will cause the highest gain of the dual bound in the created sub-tree among all branching variables.
33 *
34 * For calculating the gain, a look-ahead is performed by solving the child node LPs which will result
35 * from branching on a variable.
36 *
37 * For a more mathematical description and a comparison between the strong branching rule and other branching rules
38 * in SCIP, we refer to
39 *
40 * @par
41 * Tobias Achterberg@n
42 * Constraint Integer Programming@n
43 * PhD Thesis, Technische Universität Berlin, 2007@n
44 *
45 */
46
47/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
48
51#include "scip/pub_branch.h"
52#include "scip/pub_message.h"
53#include "scip/pub_tree.h"
54#include "scip/pub_var.h"
55#include "scip/scip_branch.h"
56#include "scip/scip_general.h"
57#include "scip/scip_lp.h"
58#include "scip/scip_mem.h"
59#include "scip/scip_message.h"
60#include "scip/scip_numerics.h"
61#include "scip/scip_prob.h"
63#include "scip/scip_tree.h"
64#include "scip/scip_var.h"
65#include <string.h>
66
67
68#define BRANCHRULE_NAME "allfullstrong"
69#define BRANCHRULE_DESC "all variables full strong branching"
70#define BRANCHRULE_PRIORITY -1000
71#define BRANCHRULE_MAXDEPTH -1
72#define BRANCHRULE_MAXBOUNDDIST 1.0
73
74
75/** branching rule data */
76struct SCIP_BranchruleData
77{
78 int lastcand; /**< last evaluated candidate of last branching rule execution */
79 int skipsize; /**< size of skipdown and skipup array */
80 SCIP_Bool* skipdown; /**< should down branch be skiped? */
81 SCIP_Bool* skipup; /**< should up branch be skiped? */
82};
83
84
85/** performs the all fullstrong branching */
86static
88 SCIP* scip, /**< SCIP data structure */
89 SCIP_BRANCHRULE* branchrule, /**< branching rule */
90 SCIP_RESULT* result /**< pointer to store the result of the callback method */
91 )
92{
93 SCIP_BRANCHRULEDATA* branchruledata;
94 SCIP_VAR** pseudocands;
95 SCIP_VAR** pseudocandscopy;
96 SCIP_Real bestdown;
97 SCIP_Real bestup;
98 SCIP_Real bestscore;
99 SCIP_Real provedbound;
100 SCIP_Bool exactsolve;
101 SCIP_Bool allcolsinlp;
102 SCIP_Bool bestdownvalid;
103 SCIP_Bool bestupvalid;
104 int npseudocands;
105 int npriopseudocands;
106 int bestpseudocand;
107#ifndef NDEBUG
108 SCIP_Real cutoffbound;
109 cutoffbound = SCIPgetCutoffbound(scip);
110#endif
111
112 assert(branchrule != NULL);
113 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
114 assert(scip != NULL);
115 assert(result != NULL);
116
117 /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
118 allcolsinlp = SCIPallColsInLP(scip);
119
120 /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
121 * for cutting off sub problems and improving lower bounds of children
122 */
123 exactsolve = SCIPisExactSolve(scip);
124
125 /* get branching rule data */
126 branchruledata = SCIPbranchruleGetData(branchrule);
127 assert(branchruledata != NULL);
128
129 if( branchruledata->skipdown == NULL )
130 {
131 assert(branchruledata->skipup == NULL);
132
133 branchruledata->skipsize = SCIPgetNVars(scip);
134 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize) );
135 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize) );
136 BMSclearMemoryArray(branchruledata->skipdown, branchruledata->skipsize);
137 BMSclearMemoryArray(branchruledata->skipup, branchruledata->skipsize);
138 }
139
140 /* get all non-fixed variables (not only the fractional ones) */
141 SCIP_CALL( SCIPgetPseudoBranchCands(scip, &pseudocands, &npseudocands, &npriopseudocands) );
142 assert(npseudocands > 0);
143 assert(npriopseudocands > 0);
144
145 SCIP_CALL( SCIPduplicateBufferArray(scip, &pseudocandscopy, pseudocands, npseudocands) );
146
147 SCIP_CALL( SCIPselectVarPseudoStrongBranching(scip, pseudocandscopy, branchruledata->skipdown, branchruledata->skipup, npseudocands,
148 npriopseudocands, &bestpseudocand, &bestdown, &bestup, &bestscore, &bestdownvalid, &bestupvalid, &provedbound, result) );
149
150 if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED )
151 {
152 SCIP_NODE* downchild;
153 SCIP_NODE* eqchild;
154 SCIP_NODE* upchild;
155 SCIP_VAR* var;
156
157 assert(*result == SCIP_DIDNOTRUN);
158 assert(0 <= bestpseudocand && bestpseudocand < npseudocands);
159 assert(SCIPisLT(scip, provedbound, cutoffbound));
160
161 var = pseudocandscopy[bestpseudocand];
162
163 /* perform the branching */
164 SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s>[%g,%g] (solval=%g, down=%g, up=%g, score=%g)\n",
165 npseudocands, bestpseudocand, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPvarGetLPSol(var),
166 bestdown, bestup, bestscore);
167 SCIP_CALL( SCIPbranchVarVal(scip, var, SCIPvarGetLPSol(var), &downchild, &eqchild, &upchild) );
168
169 /* update the lower bounds in the children */
170 if( allcolsinlp && !exactsolve )
171 {
172 if( downchild != NULL )
173 {
174 SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestdownvalid ? MAX(bestdown, provedbound) : provedbound) );
175 SCIPdebugMsg(scip, " -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild));
176 }
177 if( eqchild != NULL )
178 {
179 SCIP_CALL( SCIPupdateNodeLowerbound(scip, eqchild, provedbound) );
180 SCIPdebugMsg(scip, " -> eq child's lowerbound: %g\n", SCIPnodeGetLowerbound(eqchild));
181 }
182 if( upchild != NULL )
183 {
184 SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestupvalid ? MAX(bestup, provedbound) : provedbound) );
185 SCIPdebugMsg(scip, " -> up child's lowerbound: %g\n", SCIPnodeGetLowerbound(upchild));
186 }
187 }
188
189 *result = SCIP_BRANCHED;
190 }
191
192 SCIPfreeBufferArray(scip, &pseudocandscopy);
193
194 return SCIP_OKAY;
195}
196
197
198/*
199 * Callback methods
200 */
201
202/** copy method for branchrule plugins (called when SCIP copies plugins) */
203static
204SCIP_DECL_BRANCHCOPY(branchCopyAllfullstrong)
205{ /*lint --e{715}*/
206 assert(scip != NULL);
207 assert(branchrule != NULL);
208 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
209
210 /* call inclusion method of branchrule */
212
213 return SCIP_OKAY;
214}
215
216/** destructor of branching rule to free user data (called when SCIP is exiting) */
217static
218SCIP_DECL_BRANCHFREE(branchFreeAllfullstrong)
219{ /*lint --e{715}*/
220 SCIP_BRANCHRULEDATA* branchruledata;
221
222 /* free branching rule data */
223 branchruledata = SCIPbranchruleGetData(branchrule);
224 SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipdown, branchruledata->skipsize);
225 SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipup, branchruledata->skipsize);
226
227 SCIPfreeBlockMemory(scip, &branchruledata);
228 SCIPbranchruleSetData(branchrule, NULL);
229
230 return SCIP_OKAY;
231}
232
233
234/** initialization method of branching rule (called after problem was transformed) */
235static
236SCIP_DECL_BRANCHINIT(branchInitAllfullstrong)
237{ /*lint --e{715}*/
238 SCIP_BRANCHRULEDATA* branchruledata;
239
240 /* initialize branching rule data */
241 branchruledata = SCIPbranchruleGetData(branchrule);
242 branchruledata->lastcand = 0;
243
244 return SCIP_OKAY;
245}
246
247
248/** branching execution method for fractional LP solutions */
249static
250SCIP_DECL_BRANCHEXECLP(branchExeclpAllfullstrong)
251{ /*lint --e{715}*/
252 assert(result != NULL);
253
254 SCIPdebugMsg(scip, "Execlp method of allfullstrong branching\n");
255
256 *result = SCIP_DIDNOTRUN;
257
258 SCIP_CALL( branch(scip, branchrule, result) );
259
260 return SCIP_OKAY;
261}
262
263
264/** branching execution method for not completely fixed pseudo solutions */
265static
266SCIP_DECL_BRANCHEXECPS(branchExecpsAllfullstrong)
267{ /*lint --e{715}*/
268 assert(result != NULL);
269
270 SCIPdebugMsg(scip, "Execps method of allfullstrong branching\n");
271
272 *result = SCIP_DIDNOTRUN;
273
275 {
276 SCIP_CALL( branch(scip, branchrule, result) );
277 }
278
279 return SCIP_OKAY;
280}
281
282
283/*
284 * branching specific interface methods
285 */
286/**
287 * Selects a variable from a set of candidates by strong branching
288 *
289 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
290 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
291 *
292 * @note The variables in the lpcands array must have a fractional value in the current LP solution
293 */
295 SCIP* scip, /**< original SCIP data structure */
296 SCIP_VAR** pseudocands, /**< branching candidates */
297 SCIP_Bool* skipdown, /**< should down branchings be skipped? */
298 SCIP_Bool* skipup, /**< should up branchings be skipped? */
299 int npseudocands, /**< number of branching candidates */
300 int npriopseudocands, /**< number of priority branching candidates */
301 int* bestpseudocand, /**< best candidate for branching */
302 SCIP_Real* bestdown, /**< objective value of the down branch for bestcand */
303 SCIP_Real* bestup, /**< objective value of the up branch for bestcand */
304 SCIP_Real* bestscore, /**< score for bestcand */
305 SCIP_Bool* bestdownvalid, /**< is bestdown a valid dual bound for the down branch? */
306 SCIP_Bool* bestupvalid, /**< is bestup a valid dual bound for the up branch? */
307 SCIP_Real* provedbound, /**< proved dual bound for current subtree */
308 SCIP_RESULT* result /**< result pointer */
309 )
310{ /*lint --e{715}*/
311 SCIP_Real lpobjval;
312 SCIP_Bool allcolsinlp;
313 SCIP_Bool exactsolve;
314#ifndef NDEBUG
315 SCIP_Real cutoffbound;
316 cutoffbound = SCIPgetCutoffbound(scip);
317#endif
318
319 assert(scip != NULL);
320 assert(pseudocands != NULL);
321 assert(bestpseudocand != NULL);
322 assert(skipdown != NULL);
323 assert(skipup != NULL);
324 assert(bestdown != NULL);
325 assert(bestup != NULL);
326 assert(bestscore != NULL);
327 assert(bestdownvalid != NULL);
328 assert(bestupvalid != NULL);
329 assert(provedbound != NULL);
330 assert(result != NULL);
332
333 /* get current LP objective bound of the local sub problem and global cutoff bound */
334 lpobjval = SCIPgetLPObjval(scip);
335
336 /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
337 * for cutting off sub problems and improving lower bounds of children
338 */
339 exactsolve = SCIPisExactSolve(scip);
340
341 /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
342 allcolsinlp = SCIPallColsInLP(scip);
343
344 /* if only one candidate exists, choose this one without applying strong branching */
345 *bestpseudocand = 0;
346 *bestdown = lpobjval;
347 *bestup = lpobjval;
348 *bestdownvalid = TRUE;
349 *bestupvalid = TRUE;
350 *bestscore = -SCIPinfinity(scip);
351 *provedbound = lpobjval;
352 if( npseudocands > 1 )
353 {
354 SCIP_BRANCHRULE* branchrule;
355 SCIP_BRANCHRULEDATA* branchruledata;
356
357 SCIP_Real solval;
358 SCIP_Real down;
359 SCIP_Real up;
360 SCIP_Real downgain;
361 SCIP_Real upgain;
362 SCIP_Real score;
363 SCIP_Bool integral;
364 SCIP_Bool lperror;
365 SCIP_Bool downvalid;
366 SCIP_Bool upvalid;
367 SCIP_Bool downinf;
368 SCIP_Bool upinf;
369 SCIP_Bool downconflict;
370 SCIP_Bool upconflict;
371 int nsbcalls;
372 int i;
373 int c;
374
376 assert(branchrule != NULL);
377
378 /* get branching rule data */
379 branchruledata = SCIPbranchruleGetData(branchrule);
380 assert(branchruledata != NULL);
381
382 /* initialize strong branching */
384
385 /* search the full strong candidate:
386 * cycle through the candidates, starting with the position evaluated in the last run
387 */
388 nsbcalls = 0;
389 for( i = 0, c = branchruledata->lastcand; i < npseudocands; ++i, ++c )
390 {
391 c = c % npseudocands;
392 assert(pseudocands[c] != NULL);
393
394 /* we can only apply strong branching on COLUMN variables that are in the current LP */
395 if( !SCIPvarIsInLP(pseudocands[c]) )
396 continue;
397
398 solval = SCIPvarGetLPSol(pseudocands[c]);
399 integral = SCIPisFeasIntegral(scip, solval);
400
401 SCIPdebugMsg(scip, "applying strong branching on %s variable <%s>[%g,%g] with solution %g\n",
402 integral ? "integral" : "fractional", SCIPvarGetName(pseudocands[c]), SCIPvarGetLbLocal(pseudocands[c]),
403 SCIPvarGetUbLocal(pseudocands[c]), solval);
404
405 up = -SCIPinfinity(scip);
406 down = -SCIPinfinity(scip);
407
408 if( integral )
409 {
410 SCIP_CALL( SCIPgetVarStrongbranchInt(scip, pseudocands[c], INT_MAX, FALSE,
411 skipdown[c] ? NULL : &down, skipup[c] ? NULL : &up, &downvalid, &upvalid, &downinf, &upinf, &downconflict, &upconflict, &lperror) );
412 }
413 else
414 {
415 SCIP_CALL( SCIPgetVarStrongbranchFrac(scip, pseudocands[c], INT_MAX, FALSE,
416 skipdown[c] ? NULL : &down, skipup[c] ? NULL : &up, &downvalid, &upvalid, &downinf, &upinf, &downconflict, &upconflict, &lperror) );
417 }
418 nsbcalls++;
419
420 /* display node information line in root node */
421 if( SCIPgetDepth(scip) == 0 && nsbcalls % 100 == 0 )
422 {
424 }
425
426 /* check for an error in strong branching */
427 if( lperror )
428 {
430 "(node %" SCIP_LONGINT_FORMAT ") error in strong branching call for variable <%s> with solution %g\n",
431 SCIPgetNNodes(scip), SCIPvarGetName(pseudocands[c]), solval);
432 break;
433 }
434
435 /* evaluate strong branching */
436 down = MAX(down, lpobjval);
437 up = MAX(up, lpobjval);
438 downgain = down - lpobjval;
439 upgain = up - lpobjval;
440 assert(!allcolsinlp || exactsolve || !downvalid || downinf == SCIPisGE(scip, down, cutoffbound));
441 assert(!allcolsinlp || exactsolve || !upvalid || upinf == SCIPisGE(scip, up, cutoffbound));
442 assert(downinf || !downconflict);
443 assert(upinf || !upconflict);
444
445 /* check if there are infeasible roundings */
446 if( downinf || upinf )
447 {
448 assert(allcolsinlp);
449 assert(!exactsolve);
450
451 if( downinf && upinf )
452 {
453 if( integral )
454 {
455 SCIP_Bool infeasible;
456 SCIP_Bool fixed;
457
458 /* both bound changes are infeasible: variable can be fixed to its current value */
459 SCIP_CALL( SCIPfixVar(scip, pseudocands[c], solval, &infeasible, &fixed) );
460 assert(!infeasible);
461 assert(fixed);
462 *result = SCIP_REDUCEDDOM;
463 SCIPdebugMsg(scip, " -> integral variable <%s> is infeasible in both directions\n",
464 SCIPvarGetName(pseudocands[c]));
465 break; /* terminate initialization loop, because LP was changed */
466 }
467 else
468 {
469 /* both roundings are infeasible: the node is infeasible */
470 *result = SCIP_CUTOFF;
471 SCIPdebugMsg(scip, " -> fractional variable <%s> is infeasible in both directions\n",
472 SCIPvarGetName(pseudocands[c]));
473 break; /* terminate initialization loop, because node is infeasible */
474 }
475 }
476 else if( downinf )
477 {
478 SCIP_Real newlb;
479
480 /* downwards rounding is infeasible -> change lower bound of variable to upward rounding */
481 newlb = SCIPfeasCeil(scip, solval);
482 if( SCIPvarGetLbLocal(pseudocands[c]) < newlb - 0.5 )
483 {
484 SCIP_CALL( SCIPchgVarLb(scip, pseudocands[c], newlb) );
485 *result = SCIP_REDUCEDDOM;
486 SCIPdebugMsg(scip, " -> variable <%s> is infeasible in downward branch\n", SCIPvarGetName(pseudocands[c]));
487 break; /* terminate initialization loop, because LP was changed */
488 }
489 }
490 else
491 {
492 SCIP_Real newub;
493
494 /* upwards rounding is infeasible -> change upper bound of variable to downward rounding */
495 assert(upinf);
496 newub = SCIPfeasFloor(scip, solval);
497 if( SCIPvarGetUbLocal(pseudocands[c]) > newub + 0.5 )
498 {
499 SCIP_CALL( SCIPchgVarUb(scip, pseudocands[c], newub) );
500 *result = SCIP_REDUCEDDOM;
501 SCIPdebugMsg(scip, " -> variable <%s> is infeasible in upward branch\n", SCIPvarGetName(pseudocands[c]));
502 break; /* terminate initialization loop, because LP was changed */
503 }
504 }
505 }
506 else if( allcolsinlp && !exactsolve && downvalid && upvalid )
507 {
508 SCIP_Real minbound;
509
510 /* the minimal lower bound of both children is a proved lower bound of the current subtree */
511 minbound = MIN(down, up);
512 *provedbound = MAX(*provedbound, minbound);
513 }
514
515 /* check for a better score, if we are within the maximum priority candidates */
516 if( c < npriopseudocands )
517 {
518 if( integral )
519 {
520 if( skipdown[c] )
521 {
522 downgain = 0.0;
523 score = SCIPgetBranchScore(scip, pseudocands[c], downgain, upgain);
524 }
525 else if( skipup[c] )
526 {
527 upgain = 0.0;
528 score = SCIPgetBranchScore(scip, pseudocands[c], downgain, upgain);
529 }
530 else
531 {
532 SCIP_Real gains[3];
533
534 gains[0] = downgain;
535 gains[1] = 0.0;
536 gains[2] = upgain;
537 score = SCIPgetBranchScoreMultiple(scip, pseudocands[c], 3, gains);
538 }
539 }
540 else
541 score = SCIPgetBranchScore(scip, pseudocands[c], downgain, upgain);
542
543 if( score > *bestscore )
544 {
545 *bestpseudocand = c;
546 *bestdown = down;
547 *bestup = up;
548 *bestdownvalid = downvalid;
549 *bestupvalid = upvalid;
550 *bestscore = score;
551 }
552 }
553 else
554 {
555 SCIPdebug( score = 0.0; )
556 }
557
558 /* update pseudo cost values */
559 if( !downinf )
560 {
561 SCIP_CALL( SCIPupdateVarPseudocost(scip, pseudocands[c],
562 solval-SCIPfeasCeil(scip, solval-1.0), downgain, 1.0) );
563 }
564 if( !upinf )
565 {
566 SCIP_CALL( SCIPupdateVarPseudocost(scip, pseudocands[c],
567 solval-SCIPfeasFloor(scip, solval+1.0), upgain, 1.0) );
568 }
569
570 SCIPdebugMsg(scip, " -> var <%s> (solval=%g, downgain=%g, upgain=%g, score=%g) -- best: <%s> (%g)\n",
571 SCIPvarGetName(pseudocands[c]), solval, downgain, upgain, score,
572 SCIPvarGetName(pseudocands[*bestpseudocand]), *bestscore);
573 }
574
575 /* remember last evaluated candidate */
576 branchruledata->lastcand = c;
577
578 /* end strong branching */
580 }
581
582 return SCIP_OKAY;
583}
584
585/** creates the all variables full strong LP branching rule and includes it in SCIP */
587 SCIP* scip /**< SCIP data structure */
588 )
589{
590 SCIP_BRANCHRULEDATA* branchruledata;
591 SCIP_BRANCHRULE* branchrule;
592
593 /* create allfullstrong branching rule data */
594 SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
595 branchruledata->lastcand = 0;
596 branchruledata->skipsize = 0;
597 branchruledata->skipup = NULL;
598 branchruledata->skipdown = NULL;
599
600 /* include allfullstrong branching rule */
603
604 assert(branchrule != NULL);
605
606 /* set non-fundamental callbacks via specific setter functions*/
607 SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyAllfullstrong) );
608 SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeAllfullstrong) );
609 SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitAllfullstrong) );
610 SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpAllfullstrong) );
611 SCIP_CALL( SCIPsetBranchruleExecPs(scip, branchrule, branchExecpsAllfullstrong) );
612
613 return SCIP_OKAY;
614}
#define BRANCHRULE_DESC
static SCIP_RETCODE branch(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_RESULT *result)
SCIP_RETCODE SCIPselectVarPseudoStrongBranching(SCIP *scip, SCIP_VAR **pseudocands, SCIP_Bool *skipdown, SCIP_Bool *skipup, int npseudocands, int npriopseudocands, int *bestpseudocand, SCIP_Real *bestdown, SCIP_Real *bestup, SCIP_Real *bestscore, SCIP_Bool *bestdownvalid, SCIP_Bool *bestupvalid, SCIP_Real *provedbound, SCIP_RESULT *result)
static SCIP_DECL_BRANCHCOPY(branchCopyAllfullstrong)
#define BRANCHRULE_PRIORITY
#define BRANCHRULE_NAME
SCIP_RETCODE SCIPincludeBranchruleAllfullstrong(SCIP *scip)
static SCIP_DECL_BRANCHFREE(branchFreeAllfullstrong)
static SCIP_DECL_BRANCHEXECLP(branchExeclpAllfullstrong)
static SCIP_DECL_BRANCHINIT(branchInitAllfullstrong)
#define BRANCHRULE_MAXDEPTH
#define BRANCHRULE_MAXBOUNDDIST
static SCIP_DECL_BRANCHEXECPS(branchExecpsAllfullstrong)
all variables full strong LP branching rule
#define NULL
Definition: def.h:267
#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_CALL(x)
Definition: def.h:374
SCIP_Bool SCIPisExactSolve(SCIP *scip)
Definition: scip_general.c:611
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
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 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
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:281
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 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_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip_branch.c:849
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:83
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 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_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasIntegral(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_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
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 SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8276
SCIP_RETCODE SCIPstartStrongbranch(SCIP *scip, SCIP_Bool enablepropagation)
Definition: scip_var.c:2686
SCIP_Bool SCIPvarIsInLP(SCIP_VAR *var)
Definition: var.c:17800
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 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