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-2023 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file 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 */
126 struct SCIP_Ratio
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 };
133 typedef struct SCIP_Ratio SCIP_RATIO;
135 /** a comparison method for the next method. It simply compares two SCIP_Real */
136 static
137 SCIP_DECL_SORTINDCOMP(sciprealcomp)
138 {
139  SCIP_Real* value = (SCIP_Real*) dataptr;
140  SCIP_Real diffval;
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  */
162 static
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 */
296 static
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;
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 */
322 static
323 void computeVarRatio(
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 */
446 static
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 */
489 static
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 */
575 static
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 */
666 static
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 */
685 static
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 */
734 static
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);
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 }
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 */
934  if( !SCIPisInfinity(scip, SCIPgetUpperbound(scip)) )
935  localabsgap = SCIPgetUpperbound(scip) - SCIPgetNodeLowerbound(scip, SCIPgetCurrentNode(scip));
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:
998  return SCIP_PARAMETERWRONGVAL;
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_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:91
#define DEFAULT_FILTERHIGH
Definition: treemodel.c:82
#define DEFAULT_MAXSVTSHEIGHT
Definition: treemodel.c:89
SCIP_Bool enabled
Definition: treemodel.c:103
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPhistoryIsRatioValid(SCIP_HISTORY *history)
Definition: history.c:710
static SCIP_Real computeSampleTreesize(SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR *var, SCIP_Real absgap, SCIP_Real leftgain, SCIP_Real rightgain)
Definition: treemodel.c:694
static SCIP_RETCODE findNonDominatedVars(SCIP *scip, SCIP_Real *a, SCIP_Real *b, int size, int *ndominated, SCIP_Bool *dominated)
Definition: treemodel.c:171
SCIP_Real smallpscost
Definition: treemodel.c:123
#define FALSE
Definition: def.h:96
char fallbackinf
Definition: treemodel.c:119
SCIP_Real SCIPinfinity(SCIP *scip)
#define TRUE
Definition: def.h:95
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
Branching rules based on the Single-Variable-Branching (SVB) model.
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPhistoryGetLastRatio(SCIP_HISTORY *history)
Definition: history.c:720
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
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
internal methods for branching and inference history
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:920
#define DEFAULT_FALLBACKINF
Definition: treemodel.c:90
#define DEFAULT_FILTERLOW
Definition: treemodel.c:85
char fallbacknoprim
Definition: treemodel.c:121
#define DEFAULT_SMALLPSCOST
Definition: treemodel.c:96
void SCIPsortDownInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
static SCIP_Real computeSVTS(SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR *var, SCIP_Real absgap, SCIP_Real mingain, SCIP_Real maxgain)
Definition: treemodel.c:498
#define DEFAULT_FALLBACKNOPRIM
Definition: treemodel.c:93
SCIP_Bool valid
Definition: treemodel.c:139
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real upratio
Definition: treemodel.c:136
#define NULL
Definition: lpi_spx1.cpp:164
static void computeVarRatio(SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR *var, SCIP_Real leftgain, SCIP_Real rightgain, SCIP_RATIO *branchratio)
Definition: treemodel.c:331
SCIP_Bool SCIPisSumEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIP_CALL(x)
Definition: def.h:394
SCIP_Bool SCIPtreemodelIsEnabled(SCIP *scip, SCIP_TREEMODEL *treemodel)
Definition: treemodel.c:908
internal methods for problem variables
#define DEFAULT_HIGHRULE
Definition: treemodel.c:73
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define DEFAULT_HEIGHT
Definition: treemodel.c:79
static SCIP_Real integerpow(SCIP_Real a, int b)
Definition: treemodel.c:675
#define SCIP_Bool
Definition: def.h:93
#define DEFAULT_ENABLE
Definition: treemodel.c:72
SCIP_RETCODE SCIPtreemodelFree(SCIP *scip, SCIP_TREEMODEL **treemodel)
Definition: treemodel.c:892
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:584
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define DEFAULT_LOWRULE
Definition: treemodel.c:76
#define SCIP_REAL_MAX
Definition: def.h:187
SCIP_Real * r
Definition: circlepacking.c:59
SCIP_VAR ** b
Definition: circlepacking.c:65
static SCIP_DECL_SORTINDCOMP(sciprealcomp)
Definition: treemodel.c:145
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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_VAR * a
Definition: circlepacking.c:66
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:455
#define SCIP_Real
Definition: def.h:186
SCIP_Real invleft
Definition: treemodel.c:138
void SCIPhistorySetRatioHistory(SCIP_HISTORY *history, SCIP_Bool valid, SCIP_Real ratio, SCIP_Real balance)
Definition: history.c:742
SCIP_Real SCIPhistoryGetLastBalance(SCIP_HISTORY *history)
Definition: history.c:731
SCIP_Real SCIPgetNodeLowerbound(SCIP *scip, SCIP_NODE *node)
Definition: scip_prob.c:3622
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
static SCIP_Bool hasBetterRatio(SCIP *scip, SCIP_RATIO *branchratio, SCIP_Real leftgain, SCIP_Real rightgain)
Definition: treemodel.c:305
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_HISTORY * history
Definition: struct_var.h:250
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPtreemodelInit(SCIP *scip, SCIP_TREEMODEL **treemodel)
Definition: treemodel.c:834
#define DEFAULT_MAXFPITER
Definition: treemodel.c:88
#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:743
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