Scippy

SCIP

Solving Constraint Integer Programs

treemodel.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 treemodel.c
26 * @brief Branching rules based on the Single-Variable-Branching (SVB) model
27 * @author Daniel Anderson
28 * @author Pierre Le Bodic
29 *
30 * The Single-Variable-Branching (SVB) model is a simplified model of
31 * Branch & Bound trees, from which several nontrivial variable selection
32 * rules arise. The Treemodel branching rule complements SCIP's hybrid
33 * branching by suggesting improved branching variables given the current
34 * pseudocosts and the current dual gap.
35 *
36 * Given a variable with dual bound changes (l, r) (both positive)
37 * and an absolute gap G, the SVB model describes the tree that needs to be
38 * built by branching on that same variable at every node until the value G
39 * is reached at every leaf, starting from 0 at the root node.
40 * If we do so for every variable, we can select the variable that produces
41 * the smallest tree.
42 * In the case where the gap is not known, then we can compute the growth rate
43 * of the tree, which we call the ratio.
44 * The ratio of a variable (l, r) is the factor by which the size of the tree
45 * built using (l, r) that closes a gap G must be multiplied by to close a gap
46 * G+1. This ratio is not constant for all gaps, but when G tends to infinity,
47 * it converges to a fixed value we can compute numerically using a root finding
48 * algorithm (e.g. Laguerre).
49 * The ratio is used when the gap is too large (e.g. no primal bound known) or
50 * to help approximate the size of the SVB tree for that variable.
51 *
52 * See the following publication for more detail:
53 *
54 * @par
55 * Pierre Le Bodic and George Nemhauser@n
56 * An abstract model for branching and its application to mixed integer programming@n
57 * Mathematical Programming, 2017@n
58 */
59
60/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
61
62#include "scip/treemodel.h"
63
64#include "scip/history.h"
65#include "scip/var.h"
66
67#include <limits.h>
68
69#define LAGUERRE_THRESHOLD 100 /**< Maximum value of r/l at which Laguerre is the prefered FP method */
70
71/* Default parameters for the Treemodel branching rules */
72#define DEFAULT_ENABLE FALSE /**< should candidate branching variables be scored using the Treemodel rule? */
73#define DEFAULT_HIGHRULE 'r' /**< scoring function to use at nodes predicted to be high in the tree.
74 * ('d'efault, 's'vts, 'r'atio, 't'ree sample) */
75#define DEFAULT_LOWRULE 'r' /**< scoring function to use at nodes predicted to be low in the tree
76 * ('d'efault, 's'vts, 'r'atio, 't'ree sample) */
77#define DEFAULT_HEIGHT 10 /**< estimated tree height at which we switch from using the low rule to
78 * the high rule */
79#define DEFAULT_FILTERHIGH 'a' /**< should dominated candidates be filtered before using the high scoring
80 * function? ('a'uto, 't'rue, 'f'alse) */
81#define DEFAULT_FILTERLOW 'a' /**< should dominated candidates be filtered before using the low scoring
82 * function? ('a'uto, 't'rue, 'f'alse) */
83#define DEFAULT_MAXFPITER 24 /**< maximum number of fixed-point iterations when computing the ratio */
84#define DEFAULT_MAXSVTSHEIGHT 100 /**< maximum height to compute the SVTS score exactly before approximating */
85#define DEFAULT_FALLBACKINF 'r' /**< which method should be used as a fallback if the tree size estimates are
86 * infinite? ('d'efault, 'r'atio) */
87#define DEFAULT_FALLBACKNOPRIM 'r' /**< which method should be used as a fallback if there is no primal bound
88 * available? ('d'efault, 'r'atio) */
89#define DEFAULT_SMALLPSCOST 0.1 /**< threshold at which pseudocosts are considered small, making hybrid scores
90 * more likely to be the deciding factor in branching */
91
92/** parameters required by the Treemodel branching rules */
94{
95 SCIP_Bool enabled; /**< should candidate branching variables be scored using the Treemodel
96 * rule? */
97 char highrule; /**< scoring function to use at nodes predicted to be high in the tree.
98 * ('d'efault, 's'vts, 'r'atio, 't'ree sample) */
99 char lowrule; /**< scoring function to use at nodes predicted to be low in the tree
100 * ('d'efault, 's'vts, 'r'atio, 't'ree sample) */
101 int height; /**< estimated tree height at which we switch from using the low rule to
102 * the high rule */
103 char filterhigh; /**< should dominated candidates be filtered before using the high
104 * scoring function? ('a'uto, 't'rue, 'f'alse) [ADVANCED] */
105 char filterlow; /**< should dominated candidates be filtered before using the low
106 * scoring function? ('a'uto, 't'rue, 'f'alse) [ADVANCED] */
107 int maxfpiter; /**< maximum number of fixed-point iterations when computing the ratio
108 * [ADVANCED] */
109 int maxsvtsheight; /**< maximum height to compute the SVTS score exactly before approximating
110 * [ADVANCED] */
111 char fallbackinf; /**< which method should be used as a fallback if the tree size estimates
112 * are infinite? ('d'efault, 'r'atio) [ADVANCED] */
113 char fallbacknoprim; /**< which method should be used as a fallback if there is no primal bound
114 * available? ('d'efault, 'r'atio) [ADVANCED] */
115 SCIP_Real smallpscost; /**< threshold at which pseudocosts are considered small, making hybrid
116 * scores more likely to be the deciding factor in branching [ADVANCED] */
117};
118
119/** branching encoding of a variable's ratio
120 * A variable's ratio is defined based upon its left and right LP gains, as the unique root > 1 of
121 * the polynomial x^r - x^(r-l) -1, where l and r are the left and right LP gains.
122 * We store the root as upratio^(invleft), with invleft = 1/l. The value upratio is thus
123 * the ratio of the variable (1, r/l).
124 * An extra boolean stores whether the encoded ratio is valid,
125 * i.e. there were no numerical problems when computing it */
127{
128 SCIP_Real upratio; /**< "UnPowered" ratio, i.e. the ratio of the characteristic polynomial
129 * with gains (1, rightgain/leftgain) */
130 SCIP_Real invleft; /**< "INVerse left gain, i.e. 1/leftgain */
131 SCIP_Bool valid; /**< True iff the ratio computed is valid */
132};
133typedef struct SCIP_Ratio SCIP_RATIO;
134
135/** a comparison method for the next method. It simply compares two SCIP_Real */
136static
138{
139 SCIP_Real* value = (SCIP_Real*) dataptr;
140 SCIP_Real diffval;
141
142 assert(value != NULL);
143 assert(ind1 >= 0 && ind2 >= 0);
144
145 diffval = value[ind1] - value[ind2];
146 if( diffval < 0.0 )
147 return -1;
148 else if( diffval > 0.0)
149 return 1;
150 else
151 return 0;
152}
153
154/** given a pair of arrays of real non-negative values (a,b), with a <= b, computes
155 * the pairs that belong to the pareto front (with a tolerance).
156 * In other words, we are looking for non-dominated pairs of values.
157 * One value and one array are computed after this method.
158 * The value is the number of non-dominated elements.
159 * The array is a boolean array that indicates if an element is dominated.
160 * In case of a draw, only one variable is considered as non-dominated.
161 */
162static
164 SCIP* scip, /**< SCIP data structure */
165 SCIP_Real* a, /**< the first set of values */
166 SCIP_Real* b, /**< the second set of values */
167 int size, /**< the size of array a (and b) */
168 int* ndominated, /**< returns the number of dominated elements */
169 SCIP_Bool* dominated /**< returns the array of booleans that determine if an element is
170 * dominated */
171 )
172{
173 SCIP_Real bestcurrenta;
174 SCIP_Real besta;
175 SCIP_Real currentb;
176 int* permb;
177 int* bestcurrents;
178 int nbestcurrent;
179 int indexinpermb;
180 int origindex;
181 int iterbestcurrent;
182
183 assert(scip != NULL);
184 assert(a != NULL);
185 assert(b != NULL);
186 assert(ndominated != NULL);
187 assert(dominated != NULL);
188 assert(size > 0);
189
190 SCIP_CALL( SCIPallocBufferArray(scip, &bestcurrents, size) );
191
192 /* we first find the permutation of indices of array b that corresponds to
193 * the array of a non-increasing sort of its values */
194 SCIP_CALL( SCIPallocBufferArray(scip, &permb, size) );
195 for( origindex=0; origindex<size; ++origindex )
196 permb[origindex] = origindex;
197
198 SCIPsortDownInd(permb, sciprealcomp, (void*)b, size);
199
200 *ndominated = 0;
201 /* Now we will traverse the pair of arrays a and b by non-decreasing order of values of b
202 * and mark the (non) dominated pairs */
203
204 /* The current max value of a for all pairs that (almost) have the same value b */
205 bestcurrenta = a[permb[0]];
206
207 /* the current value b */
208 currentb = b[permb[0]];
209 /* the best pair(s) for the current value b */
210 bestcurrents[0] = permb[0];
211 nbestcurrent = 1;
212 /* the value a to "beat" to be non-dominated */
213 besta = -1;
214 for( indexinpermb = 1; indexinpermb < size; ++indexinpermb )
215 {
216 origindex = permb[indexinpermb];
217 assert(b[origindex] <= currentb);
218 if( SCIPisLT(scip, b[origindex], currentb) )
219 {
220 /* If the above is true, then we went through all the previous elements that had value currentb */
221 /* Thus the best element for value currentb is non-dominated if its value bestcurrenta is better
222 * than the previous best besta */
223 if( bestcurrenta > besta )
224 {
225 for( iterbestcurrent=0; iterbestcurrent < nbestcurrent; ++iterbestcurrent )
226 dominated[bestcurrents[iterbestcurrent]] = FALSE;
227
228 besta = bestcurrenta;
229 }
230 else
231 {
232 for( iterbestcurrent = 0; iterbestcurrent < nbestcurrent; ++iterbestcurrent )
233 {
234 dominated[bestcurrents[iterbestcurrent]] = TRUE;
235 ++(*ndominated);
236 }
237 }
238 bestcurrenta = a[origindex];
239 currentb = b[origindex];
240 bestcurrents[0] = origindex;
241 nbestcurrent = 1;
242 }
243 else
244 {
245 /* Then the b values are (almost) equal and we need to compare values a */
246 if( SCIPisGT(scip, a[origindex], bestcurrenta) )
247 {
248 /* Then the new value is better than the old one(s) */
249 for( iterbestcurrent = 0; iterbestcurrent < nbestcurrent; ++iterbestcurrent )
250 {
251 dominated[bestcurrents[iterbestcurrent]] = TRUE;
252 ++(*ndominated);
253 }
254
255 bestcurrenta = a[origindex];
256 bestcurrents[0] = origindex;
257 nbestcurrent = 1;
258 }
259 else
260 {
261 /* Then the new value is equal or dominated */
262 if( SCIPisEQ(scip, a[origindex], bestcurrenta) )
263 {
264 bestcurrents[nbestcurrent] = origindex;
265 ++nbestcurrent;
266 }
267 else
268 {
269 dominated[origindex] = TRUE;
270 ++(*ndominated);
271 }
272 }
273 }
274 }
275 /* Finally, we have to look at the last best variable */
276 if( bestcurrenta > besta )
277 {
278 for( iterbestcurrent = 0; iterbestcurrent < nbestcurrent; ++iterbestcurrent )
279 dominated[bestcurrents[iterbestcurrent]] = FALSE;
280 }
281 else
282 {
283 for( iterbestcurrent = 0; iterbestcurrent < nbestcurrent; ++iterbestcurrent )
284 {
285 dominated[bestcurrents[iterbestcurrent]] = TRUE;
286 ++(*ndominated);
287 }
288 }
289
290 SCIPfreeBufferArray(scip, &permb);
291 SCIPfreeBufferArray(scip, &bestcurrents);
292 return SCIP_OKAY;
293}
294
295/** returns true iff the variable with given gains has a ratio better (i.e smaller) than the given one */
296static
298 SCIP* scip, /**< SCIP data structure */
299 SCIP_RATIO* branchratio, /**< The variable's ratio to compare against */
300 SCIP_Real leftgain, /**< the left gain of a variable */
301 SCIP_Real rightgain /**< the right gain of a variable */
302 )
303{
304 SCIP_Real result;
305
306 assert(branchratio != NULL);
307 assert(branchratio->valid);
308 assert(SCIPisLE(scip, leftgain, rightgain));
309
310 /* We evaluate the characteristic polynomial of the variable on the given ratio. */
311 result = -1;
312 if( leftgain > 0.0 && rightgain > 0.0 )
313 {
314 result = pow(branchratio->upratio, rightgain * branchratio->invleft) - pow(branchratio->upratio, (rightgain - leftgain) * branchratio->invleft) - 1; /*lint !e644*/
315 }
316
317 /* If the result is positive, then it has a better ratio. */
318 return (result > 0.0);
319}
320
321/** computes the variable ratio corresponding to the left and right gains */
322static
324 SCIP* scip, /**< SCIP data structure */
325 SCIP_TREEMODEL* treemodel, /**< Treemodel parameter data structure */
326 SCIP_VAR* var, /**< the candidate branching variable */
327 SCIP_Real leftgain, /**< the left gain of the variable */
328 SCIP_Real rightgain, /**< the right gain of the variable */
329 SCIP_RATIO* branchratio /**< storage for the computed ratio */
330 )
331{
332 SCIP_Real ratio;
333 SCIP_Real newratio;
334 SCIP_Real r;
335 int iters;
336
337 assert(SCIPisGE(scip, leftgain, 0.0));
338 assert(SCIPisGE(scip, rightgain, leftgain));
339
340 if( SCIPisZero(scip, leftgain) || SCIPisZero(scip, rightgain) )
341 {
342 branchratio->valid = FALSE;
343 return;
344 }
345
346 /* We scale left and right gains by dividing both by left */
347 r = rightgain / leftgain;
348
349 /* In the case where l and r are very close r may become < 1 */
350 if( r <= 1 )
351 {
352 branchratio->valid = TRUE;
353 branchratio->upratio = 2.0;
354 branchratio->invleft = 1.0 / leftgain;
355 return;
356 }
357
358 /* Check if this ratio has already been computed */
360 {
361 branchratio->valid = TRUE;
362 branchratio->upratio = SCIPhistoryGetLastRatio(var->history);
363 branchratio->invleft = 1.0 / leftgain;
364 return;
365 }
366
367 /* Initialise the ratio at the previously computed ratio (if applicable) otherwise
368 * use the lower bound 2^(1/r) <= phi <= 2^(1/l).
369 * Note that we only use the previous ratio if the previous value of r/l was larger,
370 * ie. the previous ratio was smaller since we want to initialise at a lower bound.
371 */
372 ratio = 1.0;
373 newratio = pow(2.0, 1.0/r);
375 && SCIPhistoryGetLastRatio(var->history) > newratio )
376 newratio = SCIPhistoryGetLastRatio(var->history);
377
378 /* Depending on the value of rightgain/leftgain, we have two different methods to compute the ratio
379 * If this value is bigger than 100, we use a fixed-point method. Otherwise, we use Laguerre's method
380 * This is strictly for numerical efficiency and based on experiments.
381 */
382
383 /* Use Laguerre's method */
384 if( r <= LAGUERRE_THRESHOLD )
385 {
386 /* We relax the epsilon after 5 iterations since we may not have enough precision to achieve any better
387 * convergence */
388 for( iters = 0; ((iters <= 5 && !SCIPisEQ(scip, ratio, newratio)) ||
389 (iters > 5 && !SCIPisSumEQ(scip, ratio, newratio)))
390 && iters < treemodel->maxfpiter && newratio > 1.0; iters++ )
391 {
392 double G, H, a, p, p1, p2, phi_r;
393
394 ratio = newratio;
395 phi_r = pow(ratio, r);
396 p = phi_r - phi_r / ratio - 1.0;
397 if( p != 0 )
398 {
399 p1 = (r * phi_r - (r - 1.0) * phi_r / ratio) / ratio;
400 p2 = (r * (r - 1.0) * phi_r - (r - 1.0) * (r - 2.0) * phi_r / ratio) / ratio / ratio;
401 G = p1 / p;
402 H = G * G - (p2 / p);
403 a = r / (G + (G >= 0 ? 1.0 : -1.0) * sqrt((r - 1.0) * (r * H - G * G)));
404 newratio = ratio - a;
405 }
406 }
407 }
408 /* Use fixed point method */
409 else
410 {
411 /* We relax the epsilon after 10 iterations since we may not have enough precision to achieve any better
412 * convergence */
413 for( iters = 0; ((iters <= 10 && !SCIPisEQ(scip, ratio, newratio)) ||
414 (iters > 10 && !SCIPisSumEQ(scip, ratio, newratio)))
415 && iters < treemodel->maxfpiter && newratio > 1; iters++ )
416 {
417 ratio = newratio;
418 newratio = pow(1.0-1.0/ratio, -1.0/r);
419 }
420 }
421
422 /* We think that everything worked.
423 * Note that the fixed point method is not guaranteed to converge due to numerical precision issues.
424 * In the case that the method fails to converge, a fallback strategy must be used.
425 * For instance, if this method is used for branching, then this variable can be ignored,
426 * or the scores of all variables could be recomputed using a different method. */
427 if( iters < treemodel->maxfpiter && newratio > 1.0 )
428 {
429 branchratio->valid = TRUE;
430 branchratio->upratio = (ratio + newratio) / 2.0;
431 branchratio->invleft = 1.0 / leftgain;
432 }
433 /* We (hopefully) make finding bugs easier by setting these values */
434 else
435 {
436 branchratio->valid = FALSE;
437 branchratio->upratio = -1.0;
438 branchratio->invleft = -1.0;
439 }
440
441 /* Update the history */
442 SCIPhistorySetRatioHistory(var->history, branchratio->valid, branchratio->upratio, r);
443}
444
445/** use the Ratio scoring function to select a branching candidate */
446static
448 SCIP* scip, /**< SCIP data structure */
449 SCIP_TREEMODEL* treemodel, /**< Treemodel parameter data structure */
450 SCIP_VAR** branchcands, /**< branching candidate storage */
451 SCIP_Real* mingains, /**< minimum gain of rounding downwards or upwards */
452 SCIP_Real* maxgains, /**< maximum gain of rounding downwards or upwards */
453 SCIP_Bool filterdominated, /**< whether dominated variables have been filtered */
454 SCIP_Bool* dominated, /**< whether each variable is dominated or not */
455 int nbranchcands, /**< the number of branching candidates */
456 int* bestcand /**< the best branching candidate found before the call,
457 and the best candidate after the call (possibly the same) */
458 )
459{
460 SCIP_RATIO branchratio;
461 SCIP_RATIO bestbranchratio;
462 int c;
463
464 /* We initialize bestbranchratio at the default bestcand ratio, since it is likely to have
465 * a very good ratio and save evaluations of the ratio for many variables */
466 int referencevar = *bestcand;
467 computeVarRatio(scip, treemodel, branchcands[referencevar], mingains[referencevar], maxgains[referencevar], &bestbranchratio);
468
469 for( c = 0; c < nbranchcands; ++c )
470 {
471 if( (!filterdominated || !dominated[c]) && c != referencevar )
472 {
473 if( !bestbranchratio.valid || hasBetterRatio(scip, &bestbranchratio, mingains[c], maxgains[c]) ) /*lint !e644*/
474 {
475 computeVarRatio(scip, treemodel, branchcands[c], mingains[c], maxgains[c], &branchratio);
476 if( branchratio.valid ) /*lint !e644*/
477 {
478 *bestcand = c;
479 bestbranchratio = branchratio;
480 }
481 }
482 }
483 }
484
485 return SCIP_OKAY;
486}
487
488/** Returns the predicted treesize for the gap and given up and down gains */
489static
491 SCIP* scip, /**< SCIP data structure */
492 SCIP_TREEMODEL* treemodel, /**< Treemodel parameter data structure */
493 SCIP_VAR* var, /**< the candidate branching variable */
494 SCIP_Real absgap, /**< the absolute gap to close (typically the local gap at the current node) */
495 SCIP_Real mingain, /**< prediction of smaller objective gain of downwards/upwards */
496 SCIP_Real maxgain /**< prediction of larger objective gain of downwards/upwards */
497 )
498{
499 SCIP_Real prediction = SCIP_REAL_MAX;
500
501 if( SCIPisGT(scip, mingain, 0.0) && !SCIPisInfinity(scip, absgap) )
502 {
503 SCIP_Real treesize;
504 SCIP_Real gaptoreach;
505 SCIP_Real scaledgap;
506 SCIP_Real scaledgain;
507 int mindepth;
508 int nr;
509 int ir;
510
511 /* We implicitly set the minimum gain to 1, and the maximum gain and gap accordingly,
512 * as the treesize does not change if we scale the gains and gap by a scalar */
513 scaledgain = maxgain / mingain;
514 scaledgap = absgap / mingain;
515
516 mindepth = (int) SCIPceil(scip, scaledgap / scaledgain);
517
518 /* In the following case we compute the treesize for a smaller gap
519 * and we will deduce the treesize of the scaledgap using the ratio */
520 if( mindepth > treemodel->maxsvtsheight )
521 {
522 gaptoreach = scaledgap * (treemodel->maxsvtsheight - 1) / mindepth;
523
524 assert(!SCIPisInfinity(scip, gaptoreach));
525 assert(gaptoreach > scaledgain);
526 }
527 else
528 {
529 gaptoreach = scaledgap;
530 }
531
532 mindepth = (int) ceil(gaptoreach / scaledgain);
533 assert(mindepth <= treemodel->maxsvtsheight);
534 treesize = 1;
535
536 /* nr is the number of times we turn right to reach a leaf */
537 for( nr = 1; nr <= mindepth; ++nr )
538 {
539 SCIP_Real binomcoeff = 1.0;
540 for( ir = 1; ir <= nr; ++ir )
541 {
542 binomcoeff *= (nr + ceil((gaptoreach - (nr - 1) * scaledgain)) - ir) / ir;
543 }
544 treesize += binomcoeff;
545 }
546
547 treesize = 2.0 * treesize - 1.0;
548
549 assert(SCIPisGE(scip, treesize, 3.0));
550
551 if( !SCIPisEQ(scip, scaledgap, gaptoreach) )
552 {
553 /* If we have not computed the treesize for the scaled gap but for max gap instead,
554 * we use the ratio between two iterations to come up with an estimate of the treesize
555 * for the scaled gap */
556 if( !SCIPisInfinity(scip,treesize) )
557 {
558 SCIP_RATIO branchratio;
559 computeVarRatio(scip, treemodel, var, mingain, maxgain, &branchratio);
560
561 if( branchratio.valid ) /*lint !e644*/
562 prediction = treesize * pow(branchratio.upratio, (scaledgap - gaptoreach) * branchratio.invleft); /*lint !e644*/
563 }
564 }
565 else
566 {
567 prediction = treesize;
568 }
569 }
570
571 return prediction;
572}
573
574/** use the SVTS scoring function to select a branching candidate */
575static
577 SCIP* scip, /**< SCIP data structure */
578 SCIP_TREEMODEL* treemodel, /**< Treemodel parameter data structure */
579 SCIP_VAR** branchcands, /**< branching candidate storage */
580 SCIP_Real* mingains, /**< minimum gain of rounding downwards or upwards */
581 SCIP_Real* maxgains, /**< maximum gain of rounding downwards or upwards */
582 SCIP_Real* tiebreakerscore, /**< scores to use for tie breaking */
583 SCIP_Real localabsgap, /**< The dual gap at the current node */
584 SCIP_Bool filterdominated, /**< whether dominated variables have been filtered */
585 SCIP_Bool* dominated, /**< whether each variable is dominated or not */
586 int nbranchcands, /**< the number of branching candidates */
587 int ndominated, /**< the number of dominated candidates */
588 int* bestcand /**< the best branching candidate found before the call,
589 and the best candidate after the call (possibly the same) */
590 )
591{
592 SCIP_Real* treesizes;
593 SCIP_Real referencetreesize;
594 SCIP_Real score;
595 SCIP_Real bestscore;
596 SCIP_Real avgtreesize;
597 int besttscand;
598 int referencevar;
599 int c;
600
601 /* We will first measure the treesize for scip's default variable. If it is infinite then we don't compute
602 * the treesize for other variables (even though it might be finite) and go directly to the fallback strategy */
603 besttscand = *bestcand;
604 referencevar = *bestcand;
605
606 treesizes = NULL;
607 bestscore = 0.0;
608 avgtreesize = 0.0;
609 if( !SCIPisInfinity(scip, localabsgap) )
610 {
611 referencetreesize = computeSVTS(scip, treemodel, branchcands[referencevar], localabsgap, mingains[referencevar],
612 maxgains[referencevar]);
613 if( !SCIPisInfinity(scip, referencetreesize) )
614 {
615 SCIP_CALL( SCIPallocBufferArray(scip, &treesizes, nbranchcands) );
616 treesizes[referencevar] = referencetreesize;
617
618 for( c = 0; c < nbranchcands; ++c )
619 {
620 if( !filterdominated || !dominated[c] )
621 {
622 if( c != referencevar )
623 treesizes[c] = computeSVTS(scip, treemodel, branchcands[c], localabsgap, mingains[c], maxgains[c]);
624 else
625 treesizes[c] = referencetreesize;
626
627 avgtreesize += treesizes[c];
628 }
629 else
630 treesizes[c] = SCIP_REAL_MAX;
631 }
632 avgtreesize = avgtreesize / (nbranchcands - ndominated);
633
634 for( c = 0; c < nbranchcands; ++c )
635 {
636 score = (1.0 - 1.0 / (1.0 + avgtreesize / treesizes[c])) + 0.01 * tiebreakerscore[c];
637 if(score > bestscore)
638 {
639 bestscore = score;
640 besttscand = c;
641 }
642 }
643
644 *bestcand = besttscand;
645
646 SCIPfreeBufferArray(scip, &treesizes);
647 }
648 /* Apply infinite treesize fallback strategy */
649 else if( treemodel->fallbackinf == 'r' )
650 {
651 SCIP_CALL( selectCandidateUsingRatio(scip, treemodel, branchcands, mingains, maxgains, filterdominated, dominated,
652 nbranchcands, bestcand) );
653 }
654 }
655 /* Apply no primal bound fallback strategy */
656 else if( treemodel->fallbacknoprim == 'r' )
657 {
658 SCIP_CALL( selectCandidateUsingRatio(scip, treemodel, branchcands, mingains, maxgains, filterdominated, dominated,
659 nbranchcands, bestcand) );
660 }
661
662 return SCIP_OKAY;
663}
664
665/** computes a^b for integer b */
666static
668 SCIP_Real a, /**< the base */
669 int b /**< the integer exponent */
670 )
671{ /*lint --e{644}*/
672 SCIP_Real ans;
673
674 ans = 1.0;
675 for( ; b; b /= 2 )
676 {
677 if( b & 1 )
678 ans *= a;
679 a *= a;
680 }
681 return ans;
682}
683
684/** returns the sampled tree size for the given lp gains and dual gap */
685static
687 SCIP* scip, /**< SCIP data structure */
688 SCIP_TREEMODEL* treemodel, /**< Treemodel parameter data structure */
689 SCIP_VAR* var, /**< the candidate branching variable */
690 SCIP_Real absgap, /**< the absolute gap to close (typically the local at the current node) */
691 SCIP_Real leftgain, /**< The minimum gain from branching on this variable */
692 SCIP_Real rightgain /**< The maximum gain from branching on this variable */
693 )
694{
695 SCIP_RATIO branchratio;
696 SCIP_Real prediction;
697 SCIP_Real leftsize;
698 SCIP_Real rightsize;
699 SCIP_Real midsize;
700
701 computeVarRatio(scip, treemodel, var, leftgain, rightgain, &branchratio);
702
703 if( branchratio.valid ) /*lint !e644*/
704 { /*lint --e{644}*/
705 SCIP_Real phi_l = branchratio.upratio;
706 SCIP_Real phi_r = pow(branchratio.upratio, rightgain * branchratio.invleft);
707 int kl = (int)ceil(absgap / leftgain);
708 int kr = (int)ceil(absgap / rightgain);
709 int k = (int)ceil(absgap / (leftgain + rightgain));
710 SCIP_Real phi_lr = phi_l * phi_r;
711 SCIP_Real phi_klr = integerpow(phi_lr, k);
712
713 /* We compute an estimate of the size of the tree using the left-most leaf,
714 * right-most leaf, and the leaf obtained from alternating left and right. */
715 leftsize = (integerpow(phi_l, kl + 1) - 1.0) / (phi_l - 1.0);
716 rightsize = (integerpow(phi_r, kr + 1) - 1.0) / (phi_r - 1.0);
717
718 if( k * (leftgain + rightgain) < absgap + rightgain )
719 midsize = (1.0 + phi_l) * (phi_klr * phi_lr - 1.0) / (phi_lr - 1.0) - phi_klr * phi_l;
720 else
721 midsize = (1.0 + phi_l) * (phi_klr - 1.0) / (phi_lr - 1.0);
722
723 prediction = (leftsize + rightsize + midsize) / 3.0;
724 }
725 else
726 {
727 prediction = SCIP_REAL_MAX;
728 }
729
730 return prediction;
731}
732
733/** use the Tree Sampling scoring function to select a branching candidate */
734static
736 SCIP* scip, /**< SCIP data structure */
737 SCIP_TREEMODEL* treemodel, /**< Treemodel parameter data structure */
738 SCIP_VAR** branchcands, /**< branching candidate storage */
739 SCIP_Real* mingains, /**< minimum gain of rounding downwards or upwards */
740 SCIP_Real* maxgains, /**< maximum gain of rounding downwards or upwards */
741 SCIP_Real* tiebreakerscore, /**< scores to use for tie breaking */
742 SCIP_Real localabsgap, /**< The dual gap at the current node */
743 SCIP_Bool filterdominated, /**< whether dominated variables have been filtered */
744 SCIP_Bool* dominated, /**< whether each variable is dominated or not */
745 int nbranchcands, /**< the number of branching candidates */
746 int ndominated, /**< the number of dominated candidates */
747 int* bestcand /**< the best branching candidate found before the call,
748 and the best candidate after the call (possibly the same) */
749 )
750{
751 SCIP_Real* treesizes;
752 SCIP_Real referencetreesize;
753 SCIP_Real score;
754 SCIP_Real bestscore;
755 SCIP_Real avgtreesize;
756 int besttscand;
757 int referencevar;
758 int c;
759
760 /* We will first measure the treesize for scip's default variable. If it is infinite then we don't compute
761 * the treesize for other variables (even though it might be finite) and go directly to the fallback strategy */
762 besttscand = *bestcand;
763 referencevar = *bestcand;
764
765 treesizes = NULL;
766 bestscore = 0.0;
767 avgtreesize = 0.0;
768 if( !SCIPisInfinity(scip, localabsgap) )
769 {
770 referencetreesize = computeSampleTreesize(scip, treemodel, branchcands[referencevar], localabsgap, mingains[referencevar],
771 maxgains[referencevar]);
772
773 if( !SCIPisInfinity(scip, referencetreesize) )
774 {
775 SCIP_CALL( SCIPallocBufferArray(scip, &treesizes, nbranchcands) );
776 treesizes[referencevar] = referencetreesize;
777
778 for( c = 0; c < nbranchcands; ++c )
779 {
780 if( !filterdominated || !dominated[c] )
781 {
782 if( c != referencevar )
783 treesizes[c] = computeSampleTreesize(scip, treemodel, branchcands[c], localabsgap, mingains[c], maxgains[c]);
784 else
785 treesizes[c] = referencetreesize;
786
787 avgtreesize += treesizes[c];
788 }
789 else
790 treesizes[c] = SCIP_REAL_MAX;
791 }
792 avgtreesize = avgtreesize / (nbranchcands - ndominated);
793
794 for( c = 0; c < nbranchcands; ++c )
795 {
796 score = (1.0 - 1.0 / (1.0 + avgtreesize / treesizes[c])) + 0.01 * tiebreakerscore[c];
797 if( score > bestscore )
798 {
799 bestscore = score;
800 besttscand = c;
801 }
802 }
803
804 *bestcand = besttscand;
805
806 SCIPfreeBufferArray(scip, &treesizes);
807 }
808 /* Apply infinite treesize fallback strategy */
809 else if( treemodel->fallbackinf == 'r' )
810 {
811 SCIP_CALL( selectCandidateUsingRatio(scip, treemodel, branchcands, mingains, maxgains, filterdominated, dominated,
812 nbranchcands, bestcand) );
813 }
814 }
815 /* Apply no primal bound fallback strategy */
816 else if( treemodel->fallbacknoprim == 'r' )
817 {
818 SCIP_CALL( selectCandidateUsingRatio(scip, treemodel, branchcands, mingains, maxgains, filterdominated, dominated,
819 nbranchcands, bestcand) );
820 }
821
822 return SCIP_OKAY;
823}
824
825/** initialises the Treemodel parameter data structure */
827 SCIP* scip, /**< SCIP data structure */
828 SCIP_TREEMODEL** treemodel /**< Treemodel parameter data structure */
829 )
830{
831 assert(treemodel != NULL);
832 SCIP_CALL( SCIPallocBlockMemory(scip, treemodel) );
833 assert(*treemodel != NULL);
834
835 SCIP_CALL( SCIPaddBoolParam(scip, "branching/treemodel/enable",
836 "should candidate branching variables be scored using the Treemodel branching rules?",
837 &(*treemodel)->enabled, FALSE, DEFAULT_ENABLE,
838 NULL, NULL) );
839 SCIP_CALL( SCIPaddCharParam(scip, "branching/treemodel/highrule",
840 "scoring function to use at nodes predicted to be high in the tree ('d'efault, 's'vts, 'r'atio, 't'ree sample)",
841 &(*treemodel)->highrule, FALSE, DEFAULT_HIGHRULE, "dsrt",
842 NULL, NULL) );
843 SCIP_CALL( SCIPaddCharParam(scip, "branching/treemodel/lowrule",
844 "scoring function to use at nodes predicted to be low in the tree ('d'efault, 's'vts, 'r'atio, 't'ree sample)",
845 &(*treemodel)->lowrule, FALSE, DEFAULT_LOWRULE, "dsrt",
846 NULL, NULL) );
847 SCIP_CALL( SCIPaddIntParam(scip, "branching/treemodel/height",
848 "estimated tree height at which we switch from using the low rule to the high rule",
849 &(*treemodel)->height, FALSE, DEFAULT_HEIGHT, 0, INT_MAX,
850 NULL, NULL) );
851 SCIP_CALL( SCIPaddCharParam(scip, "branching/treemodel/filterhigh",
852 "should dominated candidates be filtered before using the high scoring function? ('a'uto, 't'rue, 'f'alse)",
853 &(*treemodel)->filterhigh, TRUE, DEFAULT_FILTERHIGH, "atf",
854 NULL, NULL) );
855 SCIP_CALL( SCIPaddCharParam(scip, "branching/treemodel/filterlow",
856 "should dominated candidates be filtered before using the low scoring function? ('a'uto, 't'rue, 'f'alse)",
857 &(*treemodel)->filterlow, TRUE, DEFAULT_FILTERLOW, "atf",
858 NULL, NULL) );
859 SCIP_CALL( SCIPaddIntParam(scip, "branching/treemodel/maxfpiter",
860 "maximum number of fixed-point iterations when computing the ratio",
861 &(*treemodel)->maxfpiter, TRUE, DEFAULT_MAXFPITER, 1, INT_MAX,
862 NULL, NULL) );
863 SCIP_CALL( SCIPaddIntParam(scip, "branching/treemodel/maxsvtsheight",
864 "maximum height to compute the SVTS score exactly before approximating",
865 &(*treemodel)->maxsvtsheight, TRUE, DEFAULT_MAXSVTSHEIGHT, 0, INT_MAX,
866 NULL, NULL) );
867 SCIP_CALL( SCIPaddCharParam(scip, "branching/treemodel/fallbackinf",
868 "which method should be used as a fallback if the tree size estimates are infinite? ('d'efault, 'r'atio)",
869 &(*treemodel)->fallbackinf, TRUE, DEFAULT_FALLBACKINF, "dr",
870 NULL, NULL) );
871 SCIP_CALL( SCIPaddCharParam(scip, "branching/treemodel/fallbacknoprim",
872 "which method should be used as a fallback if there is no primal bound available? ('d'efault, 'r'atio)",
873 &(*treemodel)->fallbacknoprim, TRUE, DEFAULT_FALLBACKNOPRIM, "dr",
874 NULL, NULL) );
875 SCIP_CALL ( SCIPaddRealParam(scip, "branching/treemodel/smallpscost",
876 "threshold at which pseudocosts are considered small, making hybrid scores more likely to be the deciding factor in branching",
877 &(*treemodel)->smallpscost, TRUE, DEFAULT_SMALLPSCOST,
878 0.0, SCIP_REAL_MAX, NULL, NULL) );
879
880 return SCIP_OKAY;
881}
882
883/** frees the Treemodel parameter data structure */
885 SCIP* scip, /**< SCIP data structure */
886 SCIP_TREEMODEL** treemodel /**< Treemodel parameter data structure */
887 )
888{
889 assert(treemodel != NULL);
890 assert(*treemodel != NULL);
891
892 SCIPfreeBlockMemory(scip, treemodel);
893
894 assert(*treemodel == NULL);
895
896 return SCIP_OKAY;
897}
898
899/** returns TRUE if the Treemodel branching rules are enabled */
901 SCIP* scip, /**< SCIP data structure */
902 SCIP_TREEMODEL* treemodel /**< Treemodel parameter data structure */
903 )
904{
905 assert(scip != NULL);
906 return treemodel->enabled;
907}
908
909/** apply the Treemodel branching rules to attempt to select a better
910 * branching candidate than the one selected by pseudocost branching
911 */
913 SCIP* scip, /**< SCIP data structure */
914 SCIP_TREEMODEL* treemodel, /**< Treemodel parameter data structure */
915 SCIP_VAR** branchcands, /**< branching candidate storage */
916 SCIP_Real* mingains, /**< minimum gain of rounding downwards or upwards */
917 SCIP_Real* maxgains, /**< maximum gain of rounding downwards or upwards */
918 SCIP_Real* tiebreakerscore, /**< scores to use for tie breaking */
919 int nbranchcands, /**< the number of branching candidates */
920 int* bestcand /**< the best branching candidate found before the call,
921 and the best candidate after the call (possibly the same) */
922 )
923{
924 SCIP_Real localabsgap; /* The gap at the current node */
925 int bestcandheight; /* The height of the best candidate according to SCIP */
926 char scoringfunction; /* Scoring function to use (based on the estimated tree height) */
927 char filtersetting; /* Whether we should apply filtering of dominated variables */
928
929 assert(treemodel != NULL);
930 assert(treemodel->enabled);
931 assert(*bestcand >= 0);
932
933 /* Compute the dual gap at the current node */
936 else
937 localabsgap = SCIPinfinity(scip);
938
939 /* Compute an estimate of the height of the current node using the bestcand variable */
940 if( !SCIPisInfinity(scip, localabsgap) && SCIPisGT(scip, mingains[*bestcand], 0.0)
941 && SCIPisLT(scip, localabsgap/mingains[*bestcand], 1.0 * INT_MAX))
942 bestcandheight = (int)(localabsgap/mingains[*bestcand]);
943 else
944 bestcandheight = INT_MAX;
945
946 /* Decide which scoring function to use based on the estimated height of the tree */
947 if( bestcandheight < treemodel->height )
948 {
949 scoringfunction = treemodel->lowrule;
950 filtersetting = treemodel->filterlow;
951 }
952 else
953 {
954 scoringfunction = treemodel->highrule;
955 filtersetting = treemodel->filterhigh;
956 }
957
958 /* We are going to apply a Treemodel variable selection rule */
959 if( scoringfunction != 'd' )
960 {
961 SCIP_Bool* dominated; /* Whether variables are dominated */
962 SCIP_Bool autofilter; /* If auto filtering is chosen, should variables be filtered? */
963 SCIP_Bool filterdominated; /* Whether we should filter dominated variables */
964 int ndominated; /* Number of dominated variables */
965
966 /* Filtering dominated variables is suggested for SVTS and Tree Sampling rules */
967 autofilter = (filtersetting == 'a' && (scoringfunction == 's' || scoringfunction == 't'));
968 filterdominated = (autofilter || filtersetting == 't');
969
970 /* If selected, find the dominated variables */
971 if( filterdominated )
972 {
973 SCIP_CALL( SCIPallocBufferArray(scip, &dominated, nbranchcands) );
974 SCIP_CALL( findNonDominatedVars(scip, mingains, maxgains, nbranchcands, &ndominated, dominated) );
975 }
976 else
977 {
978 dominated = NULL;
979 ndominated = 0;
980 }
981
982 /* Invoke the selected scoring function */
983 switch( scoringfunction )
984 {
985 case 's':
986 SCIP_CALL( selectCandidateUsingSVTS(scip, treemodel, branchcands, mingains, maxgains, tiebreakerscore,
987 localabsgap, filterdominated, dominated, nbranchcands, ndominated, bestcand) );
988 break;
989 case 'r':
990 SCIP_CALL( selectCandidateUsingRatio(scip, treemodel, branchcands, mingains, maxgains, filterdominated,
991 dominated, nbranchcands, bestcand) );
992 break;
993 case 't':
994 SCIP_CALL( selectCandidateUsingSampling(scip, treemodel, branchcands, mingains, maxgains, tiebreakerscore,
995 localabsgap, filterdominated, dominated, nbranchcands, ndominated, bestcand) );
996 break;
997 default:
999 }
1000
1001 /* Free dominated variable buffer if it was used */
1002 if( filterdominated )
1003 {
1004 assert(dominated != NULL);
1005 SCIPfreeBufferArray(scip, &dominated);
1006 }
1007 }
1008
1009 return SCIP_OKAY;
1010}
SCIP_VAR * a
Definition: circlepacking.c:66
SCIP_VAR ** b
Definition: circlepacking.c:65
SCIP_Real * r
Definition: circlepacking.c:59
#define NULL
Definition: def.h:267
#define SCIP_REAL_MAX
Definition: def.h:174
#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 SCIP_CALL(x)
Definition: def.h:374
SCIP_Real SCIPgetNodeLowerbound(SCIP *scip, SCIP_NODE *node)
Definition: scip_prob.c:3622
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:167
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 SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
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
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisSumEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:91
void SCIPsortDownInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
void SCIPhistorySetRatioHistory(SCIP_HISTORY *history, SCIP_Bool valid, SCIP_Real ratio, SCIP_Real balance)
Definition: history.c:793
SCIP_Real SCIPhistoryGetLastRatio(SCIP_HISTORY *history)
Definition: history.c:727
SCIP_Bool SCIPhistoryIsRatioValid(SCIP_HISTORY *history)
Definition: history.c:717
SCIP_Real SCIPhistoryGetLastBalance(SCIP_HISTORY *history)
Definition: history.c:738
internal methods for branching and inference history
SCIP_Bool valid
Definition: treemodel.c:131
SCIP_Real upratio
Definition: treemodel.c:128
SCIP_Real invleft
Definition: treemodel.c:130
char fallbackinf
Definition: treemodel.c:111
char fallbacknoprim
Definition: treemodel.c:113
SCIP_Real smallpscost
Definition: treemodel.c:115
SCIP_Bool enabled
Definition: treemodel.c:95
SCIP_HISTORY * history
Definition: struct_var.h:250
static SCIP_Real integerpow(SCIP_Real a, int b)
Definition: treemodel.c:667
SCIP_RETCODE SCIPtreemodelSelectCandidate(SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR **branchcands, SCIP_Real *mingains, SCIP_Real *maxgains, SCIP_Real *tiebreakerscore, int nbranchcands, int *bestcand)
Definition: treemodel.c:912
#define DEFAULT_HIGHRULE
Definition: treemodel.c:73
SCIP_RETCODE SCIPtreemodelInit(SCIP *scip, SCIP_TREEMODEL **treemodel)
Definition: treemodel.c:826
#define DEFAULT_HEIGHT
Definition: treemodel.c:77
#define DEFAULT_LOWRULE
Definition: treemodel.c:75
#define DEFAULT_FALLBACKNOPRIM
Definition: treemodel.c:87
static SCIP_RETCODE findNonDominatedVars(SCIP *scip, SCIP_Real *a, SCIP_Real *b, int size, int *ndominated, SCIP_Bool *dominated)
Definition: treemodel.c:163
static SCIP_RETCODE selectCandidateUsingSVTS(SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR **branchcands, SCIP_Real *mingains, SCIP_Real *maxgains, SCIP_Real *tiebreakerscore, SCIP_Real localabsgap, SCIP_Bool filterdominated, SCIP_Bool *dominated, int nbranchcands, int ndominated, int *bestcand)
Definition: treemodel.c:576
SCIP_RETCODE SCIPtreemodelFree(SCIP *scip, SCIP_TREEMODEL **treemodel)
Definition: treemodel.c:884
#define DEFAULT_FILTERLOW
Definition: treemodel.c:81
static SCIP_DECL_SORTINDCOMP(sciprealcomp)
Definition: treemodel.c:137
static SCIP_Real computeSampleTreesize(SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR *var, SCIP_Real absgap, SCIP_Real leftgain, SCIP_Real rightgain)
Definition: treemodel.c:686
#define DEFAULT_ENABLE
Definition: treemodel.c:72
static SCIP_RETCODE selectCandidateUsingRatio(SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR **branchcands, SCIP_Real *mingains, SCIP_Real *maxgains, SCIP_Bool filterdominated, SCIP_Bool *dominated, int nbranchcands, int *bestcand)
Definition: treemodel.c:447
static SCIP_Bool hasBetterRatio(SCIP *scip, SCIP_RATIO *branchratio, SCIP_Real leftgain, SCIP_Real rightgain)
Definition: treemodel.c:297
#define DEFAULT_SMALLPSCOST
Definition: treemodel.c:89
#define DEFAULT_MAXFPITER
Definition: treemodel.c:83
static SCIP_Real computeSVTS(SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR *var, SCIP_Real absgap, SCIP_Real mingain, SCIP_Real maxgain)
Definition: treemodel.c:490
SCIP_Bool SCIPtreemodelIsEnabled(SCIP *scip, SCIP_TREEMODEL *treemodel)
Definition: treemodel.c:900
#define DEFAULT_FILTERHIGH
Definition: treemodel.c:79
static void computeVarRatio(SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR *var, SCIP_Real leftgain, SCIP_Real rightgain, SCIP_RATIO *branchratio)
Definition: treemodel.c:323
#define LAGUERRE_THRESHOLD
Definition: treemodel.c:69
static SCIP_RETCODE selectCandidateUsingSampling(SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR **branchcands, SCIP_Real *mingains, SCIP_Real *maxgains, SCIP_Real *tiebreakerscore, SCIP_Real localabsgap, SCIP_Bool filterdominated, SCIP_Bool *dominated, int nbranchcands, int ndominated, int *bestcand)
Definition: treemodel.c:735
#define DEFAULT_MAXSVTSHEIGHT
Definition: treemodel.c:84
#define DEFAULT_FALLBACKINF
Definition: treemodel.c:85
Branching rules based on the Single-Variable-Branching (SVB) model.
@ SCIP_PARAMETERWRONGVAL
Definition: type_retcode.h:57
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
internal methods for problem variables