Scippy

SCIP

Solving Constraint Integer Programs

branch_distribution.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-2018 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file branch_distribution.c
17  * @ingroup BRANCHINGRULES
18  * @brief probability based branching rule based on an article by J. Pryor and J.W. Chinneck
19  * @author Gregor Hendel
20  *
21  * The distribution branching rule selects a variable based on its impact on row activity distributions. More formally,
22  * let \f$ a(x) = a_1 x_1 + \dots + a_n x_n \leq b \f$ be a row of the LP. Let further \f$ l_i, u_i \in R\f$ denote the
23  * (finite) lower and upper bound, respectively, of the \f$ i \f$-th variable \f$x_i\f$.
24  * Viewing every variable \f$x_i \f$ as (continuously) uniformly distributed within its bounds, we can approximately
25  * understand the row activity \f$a(x)\f$ as a Gaussian random variate with mean value \f$ \mu = E[a(x)] = \sum_i a_i\frac{l_i + u_i}{2}\f$
26  * and variance \f$ \sigma^2 = \sum_i a_i^2 \sigma_i^2 \f$, with \f$ \sigma_i^2 = \frac{(u_i - l_i)^2}{12}\f$ for
27  * continuous and \f$ \sigma_i^2 = \frac{(u_i - l_i + 1)^2 - 1}{12}\f$ for discrete variables.
28  * With these two parameters, we can calculate the probability to satisfy the row in terms of the cumulative distribution
29  * of the standard normal distribution: \f$ P(a(x) \leq b) = \Phi(\frac{b - \mu}{\sigma})\f$.
30  *
31  * The impact of a variable on the probability to satisfy a constraint after branching can be estimated by altering
32  * the variable contribution to the sums described above. In order to keep the tree size small,
33  * variables are preferred which decrease the probability
34  * to satisfy a row because it is more likely to create infeasible subproblems.
35  *
36  * The selection of the branching variable is subject to the parameter @p scoreparam. For both branching directions,
37  * an individual score is calculated. Available options for scoring methods are:
38  * - @b d: select a branching variable with largest difference in satisfaction probability after branching
39  * - @b l: lowest cumulative probability amongst all variables on all rows (after branching).
40  * - @b h: highest cumulative probability amongst all variables on all rows (after branching).
41  * - @b v: highest number of votes for lowering row probability for all rows a variable appears in.
42  * - @b w: highest number of votes for increasing row probability for all rows a variable appears in.
43  *
44  * If the parameter @p usescipscore is set to @a TRUE, a single branching score is calculated from the respective
45  * up and down scores as defined by the SCIP branching score function (see advanced branching parameter @p scorefunc),
46  * otherwise, the variable with the single highest score is selected, and the maximizing direction is assigned
47  * higher branching priority.
48  *
49  * The original idea of probability based branching schemes appeared in:
50  *
51  * J. Pryor and J.W. Chinneck:@n
52  * Faster Integer-Feasibility in Mixed-Integer Linear Programs by Branching to Force Change@n
53  * Computers and Operations Research, vol. 38, 2011, p. 1143–1152@n
54  * (Paper: <a href="http://www.sce.carleton.ca/faculty/chinneck/docs/PryorChinneck.pdf">PDF</a>).
55  */
56 
57 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
58 
59 #include <assert.h>
60 #include <string.h>
62 
63 
64 #define BRANCHRULE_NAME "distribution"
65 #define BRANCHRULE_DESC "branching rule based on variable influence on cumulative normal distribution of row activities"
66 #define BRANCHRULE_PRIORITY 0
67 #define BRANCHRULE_MAXDEPTH -1
68 #define BRANCHRULE_MAXBOUNDDIST 1.0
69 
70 #define SCOREPARAM_VALUES "dhlvw"
71 #define DEFAULT_SCOREPARAM 'v'
72 #define DEFAULT_PRIORITY 2.0
73 #define SQRTOFTWO 1.4142136
74 #define SQUARED(x) ((x) * (x))
75 #define DEFAULT_ONLYACTIVEROWS FALSE /**< should only rows which are active at the current node be considered? */
76 #define DEFAULT_USEWEIGHTEDSCORE FALSE /**< should the branching score weigh up- and down-scores of a variable */
77 
78 /* branching rule event handler to catch variable bound changes */
79 #define EVENTHDLR_NAME "eventhdlr_distribution" /**< event handler name */
80 #define EVENT_DISTRIBUTION SCIP_EVENTTYPE_BOUNDCHANGED /**< the event tyoe to be handled by this event handler */
81 
82 /*
83  * Data structures
84  */
85 
86 /** branching rule data */
87 struct SCIP_BranchruleData
88 {
89  SCIP_EVENTHDLR* eventhdlr; /**< event handler pointer */
90  SCIP_VAR** updatedvars; /**< variables to process bound change events for */
91  SCIP_Real* rowmeans; /**< row activity mean values for all rows */
92  SCIP_Real* rowvariances; /**< row activity variances for all rows */
93  SCIP_Real* currentubs; /**< variable upper bounds as currently saved in the row activities */
94  SCIP_Real* currentlbs; /**< variable lower bounds as currently saved in the row activities */
95  int* rowinfinitiesdown; /**< count the number of variables with infinite bounds which allow for always
96  * repairing the constraint right hand side */
97  int* rowinfinitiesup; /**< count the number of variables with infinite bounds which allow for always
98  * repairing the constraint left hand side */
99  int* varposs; /**< array of variable positions in the updated variables array */
100  int* varfilterposs; /**< array of event filter positions for variable events */
101  int nupdatedvars; /**< the current number of variables with pending bound changes */
102  int memsize; /**< memory size of current arrays, needed for dynamic reallocation */
103  int varpossmemsize; /**< memory size of updated vars and varposs array */
104  char scoreparam; /**< parameter how the branch score is calculated */
105  SCIP_Bool onlyactiverows; /**< should only rows which are active at the current node be considered? */
106  SCIP_Bool usescipscore; /**< should the branching use SCIP's branching score function */
107 };
108 
109 struct SCIP_EventhdlrData
110 {
111  SCIP_BRANCHRULEDATA* branchruledata; /**< the branching rule data to access distribution arrays */
112 };
113 
114 /*
115  * Local methods
116  */
117 
118 /** ensure that maxindex + 1 rows can be represented in data arrays; memory gets reallocated with 10% extra space
119  * to save some time for future allocations */
120 static
122  SCIP* scip, /**< SCIP data structure */
123  SCIP_BRANCHRULEDATA* branchruledata, /**< branchruledata */
124  int maxindex /**< row index at hand (size must be at least this large) */
125  )
126 {
127  int newsize;
128  int r;
129 
130  /* maxindex fits in current array -> nothing to do */
131  if( maxindex < branchruledata->memsize )
132  return SCIP_OKAY;
133 
134  /* new memory size is the max index + 1 plus 10% additional space */
135  newsize = (int)SCIPfeasCeil(scip, (maxindex + 1) * 1.1);
136  assert(newsize > branchruledata->memsize);
137  assert(branchruledata->memsize >= 0);
138 
139  /* alloc memory arrays for row information */
140  if( branchruledata->memsize == 0 )
141  {
142  SCIP_VAR** vars;
143  int v;
144  int nvars;
145 
146  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->rowinfinitiesdown, newsize) );
147  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->rowinfinitiesup, newsize) );
148  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->rowmeans, newsize) );
149  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->rowvariances, newsize) );
150 
151  assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING);
152 
153  vars = SCIPgetVars(scip);
154  nvars = SCIPgetNVars(scip);
155 
156  assert(nvars > 0);
157 
158  /* allocate variable update event processing array storage */
159  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->varfilterposs, nvars) );
160  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->varposs, nvars) );
161  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->updatedvars, nvars) );
162  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->currentubs, nvars) );
163  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->currentlbs, nvars) );
164 
165  branchruledata->varpossmemsize = nvars;
166  branchruledata->nupdatedvars = 0;
167 
168  /* init variable event processing data */
169  for( v = 0; v < nvars; ++v )
170  {
171  assert(SCIPvarIsActive(vars[v]));
172  assert(SCIPvarGetProbindex(vars[v]) == v);
173 
174  /* set up variable events to catch bound changes */
175  SCIP_CALL( SCIPcatchVarEvent(scip, vars[v], EVENT_DISTRIBUTION, branchruledata->eventhdlr, NULL, &(branchruledata->varfilterposs[v])) );
176  assert(branchruledata->varfilterposs[v] >= 0);
177 
178  branchruledata->varposs[v] = -1;
179  branchruledata->updatedvars[v] = NULL;
180  branchruledata->currentlbs[v] = SCIP_INVALID;
181  branchruledata->currentubs[v] = SCIP_INVALID;
182  }
183 
184  }
185  else
186  {
187  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &branchruledata->rowinfinitiesdown, branchruledata->memsize, newsize) );
188  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &branchruledata->rowinfinitiesup, branchruledata->memsize, newsize) );
189  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &branchruledata->rowmeans, branchruledata->memsize, newsize) );
190  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &branchruledata->rowvariances, branchruledata->memsize, newsize) );
191  }
192 
193  /* loop over extended arrays and invalidate data to trigger initialization of this row when necessary */
194  for( r = branchruledata->memsize; r < newsize; ++r )
195  {
196  branchruledata->rowmeans[r] = SCIP_INVALID;
197  branchruledata->rowvariances[r] = SCIP_INVALID;
198  branchruledata->rowinfinitiesdown[r] = 0;
199  branchruledata->rowinfinitiesup[r] = 0;
200  }
201 
202  /* adjust memsize */
203  branchruledata->memsize = newsize;
204 
205  return SCIP_OKAY;
206 }
207 
208 /* update the variables current lower and upper bound */
209 static
211  SCIP* scip, /**< SCIP data structure */
212  SCIP_BRANCHRULEDATA* branchruledata, /**< branchrule data */
213  SCIP_VAR* var /**< the variable to update current bounds */
214  )
215 {
216  int varindex;
217  SCIP_Real lblocal;
218  SCIP_Real ublocal;
219 
220  assert(var != NULL);
221 
222  varindex = SCIPvarGetProbindex(var);
223  assert(0 <= varindex && varindex < branchruledata->varpossmemsize);
224  lblocal = SCIPvarGetLbLocal(var);
225  ublocal = SCIPvarGetUbLocal(var);
226 
227  assert(SCIPisFeasLE(scip, lblocal, ublocal));
228 
229  branchruledata->currentlbs[varindex] = lblocal;
230  branchruledata->currentubs[varindex] = ublocal;
231 }
232 
233 /** calculate the variable's distribution parameters (mean and variance) for the bounds specified in the arguments.
234  * special treatment of infinite bounds necessary */
236  SCIP* scip, /**< SCIP data structure */
237  SCIP_Real varlb, /**< variable lower bound */
238  SCIP_Real varub, /**< variable upper bound */
239  SCIP_VARTYPE vartype, /**< type of the variable */
240  SCIP_Real* mean, /**< pointer to store mean value */
241  SCIP_Real* variance /**< pointer to store the variance of the variable uniform distribution */
242  )
243 {
244  assert(mean != NULL);
245  assert(variance != NULL);
246 
247  /* calculate mean and variance of variable uniform distribution before and after branching */
248  if( SCIPisInfinity(scip, varub) || SCIPisInfinity(scip, -varlb) )
249  {
250  /* variables with infinite bounds are not kept in the row activity variance */
251  *variance = 0.0;
252 
253  if( !SCIPisInfinity(scip, varub) )
254  *mean = varub;
255  else if( !SCIPisInfinity(scip, -varlb) )
256  *mean = varlb;
257  else
258  *mean = 0.0;
259  }
260  else
261  {
262  /* if the variable is continuous, we assume a continuous uniform distribution, otherwise a discrete one */
263  if( vartype == SCIP_VARTYPE_CONTINUOUS )
264  *variance = SQUARED(varub - varlb);
265  else
266  *variance = SQUARED(varub - varlb + 1) - 1;
267  *variance /= 12.0;
268  *mean = (varub + varlb) * .5;
269  }
270 
271  assert(!SCIPisNegative(scip, *variance));
272 }
273 
274 /** calculates the cumulative distribution P(-infinity <= x <= value) that a normally distributed
275  * random variable x takes a value between -infinity and parameter \p value.
276  *
277  * The distribution is given by the respective mean and deviation. This implementation
278  * uses the error function SCIPerf().
279  */
281  SCIP* scip, /**< current SCIP */
282  SCIP_Real mean, /**< the mean value of the distribution */
283  SCIP_Real variance, /**< the square of the deviation of the distribution */
284  SCIP_Real value /**< the upper limit of the calculated distribution integral */
285  )
286 {
287  SCIP_Real normvalue;
288  SCIP_Real std;
289 
290  /* we need to calculate the standard deviation from the variance */
291  assert(!SCIPisNegative(scip, variance));
292  if( SCIPisFeasZero(scip, variance) )
293  std = 0.0;
294  else
295  std = sqrt(variance);
296 
297  /* special treatment for zero variance */
298  if( SCIPisFeasZero(scip, std) )
299  {
300  if( SCIPisFeasLE(scip, value, mean) )
301  return 1.0;
302  else
303  return 0.0;
304  }
305  assert( std != 0.0 ); /* for lint */
306 
307  /* scale and translate to standard normal distribution. Factor sqrt(2) is needed for SCIPerf() function */
308  normvalue = (value - mean)/(std * SQRTOFTWO);
309 
310  SCIPdebugMsg(scip, " Normalized value %g = ( %g - %g ) / (%g * 1.4142136)\n", normvalue, value, mean, std);
311 
312  /* calculate the cumulative distribution function for normvalue. For negative normvalues, we negate
313  * the normvalue and use the oddness of the SCIPerf()-function; special treatment for values close to zero.
314  */
315  if( SCIPisFeasZero(scip, normvalue) )
316  return .5;
317  else if( normvalue > 0 )
318  {
319  SCIP_Real erfresult;
320 
321  erfresult = SCIPerf(normvalue);
322  return erfresult / 2.0 + 0.5;
323  }
324  else
325  {
326  SCIP_Real erfresult;
327 
328  erfresult = SCIPerf(-normvalue);
329 
330  return 0.5 - erfresult / 2.0;
331  }
332 }
333 
334 /** calculates the probability of satisfying an LP-row under the assumption
335  * of uniformly distributed variable values.
336  *
337  * For inequalities, we use the cumulative distribution function of the standard normal
338  * distribution PHI(rhs - mu/sqrt(sigma2)) to calculate the probability
339  * for a right hand side row with mean activity mu and variance sigma2 to be satisfied.
340  * Similarly, 1 - PHI(lhs - mu/sqrt(sigma2)) is the probability to satisfy a left hand side row.
341  * For equations (lhs==rhs), we use the centeredness measure p = min(PHI(lhs'), 1-PHI(lhs'))/max(PHI(lhs'), 1 - PHI(lhs')),
342  * where lhs' = lhs - mu / sqrt(sigma2).
343  */
345  SCIP* scip, /**< current scip */
346  SCIP_ROW* row, /**< the row */
347  SCIP_Real mu, /**< the mean value of the row distribution */
348  SCIP_Real sigma2, /**< the variance of the row distribution */
349  int rowinfinitiesdown, /**< the number of variables with infinite bounds to DECREASE activity */
350  int rowinfinitiesup /**< the number of variables with infinite bounds to INCREASE activity */
351  )
352 {
353  SCIP_Real rowprobability;
354  SCIP_Real lhs;
355  SCIP_Real rhs;
356  SCIP_Real lhsprob;
357  SCIP_Real rhsprob;
358 
359  lhs = SCIProwGetLhs(row);
360  rhs = SCIProwGetRhs(row);
361 
362  lhsprob = 1.0;
363  rhsprob = 1.0;
364 
365  /* use the cumulative distribution if the row contains no variable to repair every infeasibility */
366  if( !SCIPisInfinity(scip, rhs) && rowinfinitiesdown == 0 )
367  rhsprob = SCIPcalcCumulativeDistribution(scip, mu, sigma2, rhs);
368 
369  /* use the cumulative distribution if the row contains no variable to repair every infeasibility
370  * otherwise the row can always be made feasible by increasing activity far enough
371  */
372  if( !SCIPisInfinity(scip, -lhs) && rowinfinitiesup == 0 )
373  lhsprob = 1.0 - SCIPcalcCumulativeDistribution(scip, mu, sigma2, lhs);
374 
375  assert(SCIPisFeasLE(scip, lhsprob, 1.0) && SCIPisFeasGE(scip, lhsprob, 0.0));
376  assert(SCIPisFeasLE(scip, rhsprob, 1.0) && SCIPisFeasGE(scip, rhsprob, 0.0));
377 
378  /* use centeredness measure for equations; for inequalities, the minimum of the two probabilities is the
379  * probability to satisfy the row */
380  if( SCIPisFeasEQ(scip, lhs, rhs) )
381  {
382  SCIP_Real minprobability;
383  SCIP_Real maxprobability;
384 
385  minprobability = MIN(rhsprob, lhsprob);
386  maxprobability = MAX(lhsprob, rhsprob);
387  rowprobability = minprobability / maxprobability;
388  }
389  else
390  rowprobability = MIN(rhsprob, lhsprob);
391 
392  SCIPdebug( SCIPprintRow(scip, row, NULL) );
393  SCIPdebugMsg(scip, " Row %s, mean %g, sigma2 %g, LHS %g, RHS %g has probability %g to be satisfied\n",
394  SCIProwGetName(row), mu, sigma2, lhs, rhs, rowprobability);
395 
396  assert(SCIPisFeasGE(scip, rowprobability, 0.0) && SCIPisFeasLE(scip, rowprobability, 1.0));
397 
398  return rowprobability;
399 }
400 
401 /** calculates the initial mean and variance of the row activity normal distribution.
402  *
403  * The mean value \f$ \mu \f$ is given by \f$ \mu = \sum_i=1^n c_i * (lb_i +ub_i) / 2 \f$ where
404  * \f$n \f$ is the number of variables, and \f$ c_i, lb_i, ub_i \f$ are the variable coefficient and
405  * bounds, respectively. With the same notation, the variance \f$ \sigma^2 \f$ is given by
406  * \f$ \sigma^2 = \sum_i=1^n c_i^2 * \sigma^2_i \f$, with the variance being
407  * \f$ \sigma^2_i = ((ub_i - lb_i + 1)^2 - 1) / 12 \f$ for integer variables and
408  * \f$ \sigma^2_i = (ub_i - lb_i)^2 / 12 \f$ for continuous variables.
409  */
410 static
412  SCIP* scip, /**< SCIP data structure */
413  SCIP_BRANCHRULEDATA* branchruledata, /**< the branching rule data */
414  SCIP_ROW* row, /**< the row for which the gaussian normal distribution has to be calculated */
415  SCIP_Real* mu, /**< pointer to store the mean value of the gaussian normal distribution */
416  SCIP_Real* sigma2, /**< pointer to store the variance value of the gaussian normal distribution */
417  int* rowinfinitiesdown, /**< pointer to store the number of variables with infinite bounds to DECREASE activity */
418  int* rowinfinitiesup /**< pointer to store the number of variables with infinite bounds to INCREASE activity */
419  )
420 {
421  SCIP_COL** rowcols;
422  SCIP_Real* rowvals;
423  int nrowvals;
424  int c;
425 
426  assert(scip != NULL);
427  assert(row != NULL);
428  assert(mu != NULL);
429  assert(sigma2 != NULL);
430  assert(rowinfinitiesup != NULL);
431  assert(rowinfinitiesdown != NULL);
432 
433  rowcols = SCIProwGetCols(row);
434  rowvals = SCIProwGetVals(row);
435  nrowvals = SCIProwGetNNonz(row);
436 
437  assert(nrowvals == 0 || rowcols != NULL);
438  assert(nrowvals == 0 || rowvals != NULL);
439 
440  *mu = SCIProwGetConstant(row);
441  *sigma2 = 0.0;
442  *rowinfinitiesdown = 0;
443  *rowinfinitiesup = 0;
444 
445  /* loop over nonzero row coefficients and sum up the variable contributions to mu and sigma2 */
446  for( c = 0; c < nrowvals; ++c )
447  {
448  SCIP_VAR* colvar;
449  SCIP_Real colval;
450  SCIP_Real colvarlb;
451  SCIP_Real colvarub;
452  SCIP_Real squarecoeff;
453  SCIP_Real varvariance;
454  SCIP_Real varmean;
455  int varindex;
456 
457  assert(rowcols[c] != NULL);
458  colvar = SCIPcolGetVar(rowcols[c]);
459  assert(colvar != NULL);
460 
461  colval = rowvals[c];
462  colvarlb = SCIPvarGetLbLocal(colvar);
463  colvarub = SCIPvarGetUbLocal(colvar);
464 
465  varmean = 0.0;
466  varvariance = 0.0;
467  varindex = SCIPvarGetProbindex(colvar);
468  assert((branchruledata->currentlbs[varindex] == SCIP_INVALID) == (branchruledata->currentubs[varindex] == SCIP_INVALID)); /*lint !e777*/
469 
470  /* variable bounds need to be watched from now on */
471  if( branchruledata->currentlbs[varindex] == SCIP_INVALID ) /*lint !e777*/
472  branchruledataUpdateCurrentBounds(scip, branchruledata, colvar);
473 
474  assert(!SCIPisInfinity(scip, colvarlb));
475  assert(!SCIPisInfinity(scip, -colvarub));
476  assert(SCIPisFeasLE(scip, colvarlb, colvarub));
477 
478  /* variables with infinite bounds are skipped for the calculation of the variance; they need to
479  * be accounted for by the counters for infinite row activity decrease and increase and they
480  * are used to shift the row activity mean in case they have one nonzero, but finite bound */
481  if( SCIPisInfinity(scip, -colvarlb) || SCIPisInfinity(scip, colvarub) )
482  {
483  if( SCIPisInfinity(scip, colvarub) )
484  {
485  /* an infinite upper bound gives the row an infinite maximum activity or minimum activity, if the coefficient is
486  * positive or negative, resp.
487  */
488  if( colval < 0.0 )
489  ++(*rowinfinitiesdown);
490  else
491  ++(*rowinfinitiesup);
492  }
493 
494  /* an infinite lower bound gives the row an infinite maximum activity or minimum activity, if the coefficient is
495  * negative or positive, resp.
496  */
497  if( SCIPisInfinity(scip, -colvarlb) )
498  {
499  if( colval > 0.0 )
500  ++(*rowinfinitiesdown);
501  else
502  ++(*rowinfinitiesup);
503  }
504  }
505  SCIPvarCalcDistributionParameters(scip, colvarlb, colvarub, SCIPvarGetType(colvar), &varmean, &varvariance);
506 
507  /* actual values are updated; the contribution of the variable to mu is the arithmetic mean of its bounds */
508  *mu += colval * varmean;
509 
510  /* the variance contribution of a variable is c^2 * (u - l)^2 / 12.0 for continuous and c^2 * ((u - l + 1)^2 - 1) / 12.0 for integer */
511  squarecoeff = SQUARED(colval);
512  *sigma2 += squarecoeff * varvariance;
513 
514  assert(!SCIPisFeasNegative(scip, *sigma2));
515  }
516 
517  SCIPdebug( SCIPprintRow(scip, row, NULL) );
518  SCIPdebugMsg(scip, " Row %s has a mean value of %g at a sigma2 of %g \n", SCIProwGetName(row), *mu, *sigma2);
519 }
520 
521 /** update the up- and downscore of a single variable after calculating the impact of branching on a
522  * particular row, depending on the chosen score parameter
523  */
525  SCIP* scip, /**< current SCIP pointer */
526  SCIP_Real currentprob, /**< the current probability */
527  SCIP_Real newprobup, /**< the new probability if branched upwards */
528  SCIP_Real newprobdown, /**< the new probability if branched downwards */
529  SCIP_Real* upscore, /**< pointer to store the new score for branching up */
530  SCIP_Real* downscore, /**< pointer to store the new score for branching down */
531  char scoreparam /**< parameter to determine the way the score is calculated */
532  )
533 {
534  assert(scip != NULL);
535  assert(SCIPisFeasGE(scip, currentprob, 0.0) && SCIPisFeasLE(scip, currentprob, 1.0));
536  assert(SCIPisFeasGE(scip, newprobup, 0.0) && SCIPisFeasLE(scip, newprobup, 1.0));
537  assert(SCIPisFeasGE(scip, newprobdown, 0.0) && SCIPisFeasLE(scip, newprobdown, 1.0));
538  assert(upscore != NULL);
539  assert(downscore != NULL);
540 
541  /* update up and downscore depending on score parameter */
542  switch( scoreparam )
543  {
544  case 'l' :
545  /* 'l'owest cumulative probability */
546  if( SCIPisGT(scip, 1.0 - newprobup, *upscore) )
547  *upscore = 1.0 - newprobup;
548  if( SCIPisGT(scip, 1.0 - newprobdown, *downscore) )
549  *downscore = 1.0 - newprobdown;
550  break;
551 
552  case 'd' :
553  /* biggest 'd'ifference currentprob - newprob */
554  if( SCIPisGT(scip, currentprob - newprobup, *upscore) )
555  *upscore = currentprob - newprobup;
556  if( SCIPisGT(scip, currentprob - newprobdown, *downscore) )
557  *downscore = currentprob - newprobdown;
558  break;
559 
560  case 'h' :
561  /* 'h'ighest cumulative probability */
562  if( SCIPisGT(scip, newprobup, *upscore) )
563  *upscore = newprobup;
564  if( SCIPisGT(scip, newprobdown, *downscore) )
565  *downscore = newprobdown;
566  break;
567 
568  case 'v' :
569  /* 'v'otes lowest cumulative probability */
570  if( SCIPisLT(scip, newprobup, newprobdown) )
571  *upscore += 1.0;
572  else if( SCIPisGT(scip, newprobup, newprobdown) )
573  *downscore += 1.0;
574  break;
575 
576  case 'w' :
577  /* votes highest cumulative probability */
578  if( SCIPisGT(scip, newprobup, newprobdown) )
579  *upscore += 1.0;
580  else if( SCIPisLT(scip, newprobup, newprobdown) )
581  *downscore += 1.0;
582  break;
583 
584  default :
585  SCIPerrorMessage(" ERROR! No branching scheme selected! Exiting method.\n");
586  return SCIP_INVALIDCALL;
587  }
588 
589  return SCIP_OKAY;
590 }
591 
592 /** calculate the branching score of a variable, depending on the chosen score parameter */
593 static
595  SCIP* scip, /**< current SCIP */
596  SCIP_BRANCHRULEDATA* branchruledata, /**< branch rule data */
597  SCIP_VAR* var, /**< candidate variable */
598  SCIP_Real lpsolval, /**< current fractional LP-relaxation solution value */
599  SCIP_Real* upscore, /**< pointer to store the variable score when branching on it in upward direction */
600  SCIP_Real* downscore, /**< pointer to store the variable score when branching on it in downward direction */
601  char scoreparam /**< the score parameter of this branching rule */
602  )
603 {
604  SCIP_COL* varcol;
605  SCIP_ROW** colrows;
606  SCIP_Real* rowvals;
607  SCIP_Real varlb;
608  SCIP_Real varub;
609  SCIP_Real squaredbounddiff; /* current squared difference of variable bounds (ub - lb)^2 */
610  SCIP_Real newub; /* new upper bound if branching downwards */
611  SCIP_Real newlb; /* new lower bound if branching upwards */
612  SCIP_Real squaredbounddiffup; /* squared difference after branching upwards (ub - lb')^2 */
613  SCIP_Real squaredbounddiffdown; /* squared difference after branching downwards (ub' - lb)^2 */
614  SCIP_Real currentmean; /* current mean value of variable uniform distribution */
615  SCIP_Real meanup; /* mean value of variable uniform distribution after branching up */
616  SCIP_Real meandown; /* mean value of variable uniform distribution after branching down*/
617  SCIP_VARTYPE vartype;
618  int ncolrows;
619  int i;
620 
621  SCIP_Bool onlyactiverows; /* should only rows which are active at the current node be considered? */
622 
623  assert(scip != NULL);
624  assert(var != NULL);
625  assert(upscore != NULL);
626  assert(downscore != NULL);
627  assert(!SCIPisIntegral(scip, lpsolval));
628  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
629 
630  varcol = SCIPvarGetCol(var);
631  assert(varcol != NULL);
632 
633  colrows = SCIPcolGetRows(varcol);
634  rowvals = SCIPcolGetVals(varcol);
635  ncolrows = SCIPcolGetNNonz(varcol);
636  varlb = SCIPvarGetLbLocal(var);
637  varub = SCIPvarGetUbLocal(var);
638  assert(SCIPisFeasLT(scip, varlb, varub));
639  vartype = SCIPvarGetType(var);
640 
641  /* calculate mean and variance of variable uniform distribution before and after branching */
642  currentmean = 0.0;
643  squaredbounddiff = 0.0;
644  SCIPvarCalcDistributionParameters(scip, varlb, varub, vartype, &currentmean, &squaredbounddiff);
645 
646  newlb = SCIPfeasCeil(scip, lpsolval);
647  newub = SCIPfeasFloor(scip, lpsolval);
648 
649  /* calculate the variable's uniform distribution after branching up and down, respectively. */
650  squaredbounddiffup = 0.0;
651  meanup = 0.0;
652  SCIPvarCalcDistributionParameters(scip, newlb, varub, vartype, &meanup, &squaredbounddiffup);
653 
654  /* calculate the distribution mean and variance for a variable with finite lower bound */
655  squaredbounddiffdown = 0.0;
656  meandown = 0.0;
657  SCIPvarCalcDistributionParameters(scip, varlb, newub, vartype, &meandown, &squaredbounddiffdown);
658 
659  /* initialize the variable's up and down score */
660  *upscore = 0.0;
661  *downscore = 0.0;
662 
663  onlyactiverows = branchruledata->onlyactiverows;
664 
665  /* loop over the variable rows and calculate the up and down score */
666  for( i = 0; i < ncolrows; ++i )
667  {
668  SCIP_ROW* row;
669  SCIP_Real changedrowmean;
670  SCIP_Real rowmean;
671  SCIP_Real rowvariance;
672  SCIP_Real changedrowvariance;
673  SCIP_Real currentrowprob;
674  SCIP_Real newrowprobup;
675  SCIP_Real newrowprobdown;
676  SCIP_Real squaredcoeff;
677  SCIP_Real rowval;
678  int rowinfinitiesdown;
679  int rowinfinitiesup;
680  int rowpos;
681 
682  row = colrows[i];
683  rowval = rowvals[i];
684  assert(row != NULL);
685 
686  /* we access the rows by their index */
687  rowpos = SCIProwGetIndex(row);
688 
689  /* skip non-active rows if the user parameter was set this way */
690  if( onlyactiverows && SCIPisSumPositive(scip, SCIPgetRowLPFeasibility(scip, row)) )
691  continue;
692 
693  /* call method to ensure sufficient data capacity */
694  SCIP_CALL( branchruledataEnsureArraySize(scip, branchruledata, rowpos) );
695 
696  /* calculate row activity distribution if this is the first candidate to appear in this row */
697  if( branchruledata->rowmeans[rowpos] == SCIP_INVALID ) /*lint !e777*/
698  {
699  rowCalculateGauss(scip, branchruledata, row, &branchruledata->rowmeans[rowpos], &branchruledata->rowvariances[rowpos],
700  &branchruledata->rowinfinitiesdown[rowpos], &branchruledata->rowinfinitiesup[rowpos]);
701  }
702 
703  /* retrieve the row distribution parameters from the branch rule data */
704  rowmean = branchruledata->rowmeans[rowpos];
705  rowvariance = branchruledata->rowvariances[rowpos];
706  rowinfinitiesdown = branchruledata->rowinfinitiesdown[rowpos];
707  rowinfinitiesup = branchruledata->rowinfinitiesdown[rowpos];
708  assert(!SCIPisNegative(scip, rowvariance));
709 
710  currentrowprob = SCIProwCalcProbability(scip, row, rowmean, rowvariance,
711  rowinfinitiesdown, rowinfinitiesup);
712 
713  /* get variable's current expected contribution to row activity */
714  squaredcoeff = SQUARED(rowval);
715 
716  /* first, get the probability change for the row if the variable is branched on upwards. The probability
717  * can only be affected if the variable upper bound is finite
718  */
719  if( !SCIPisInfinity(scip, varub) )
720  {
721  int rowinftiesdownafterbranch;
722  int rowinftiesupafterbranch;
723 
724  /* calculate how branching would affect the row parameters */
725  changedrowmean = rowmean + rowval * (meanup - currentmean);
726  changedrowvariance = rowvariance + squaredcoeff * (squaredbounddiffup - squaredbounddiff);
727  changedrowvariance = MAX(0.0, changedrowvariance);
728 
729  rowinftiesdownafterbranch = rowinfinitiesdown;
730  rowinftiesupafterbranch = rowinfinitiesup;
731 
732  /* account for changes of the row's infinite bound contributions */
733  if( SCIPisInfinity(scip, -varlb) && rowval < 0.0 )
734  rowinftiesupafterbranch--;
735  if( SCIPisInfinity(scip, -varlb) && rowval > 0.0 )
736  rowinftiesdownafterbranch--;
737 
738  assert(rowinftiesupafterbranch >= 0);
739  assert(rowinftiesdownafterbranch >= 0);
740  newrowprobup = SCIProwCalcProbability(scip, row, changedrowmean, changedrowvariance, rowinftiesdownafterbranch,
741  rowinftiesupafterbranch);
742  }
743  else
744  newrowprobup = currentrowprob;
745 
746  /* do the same for the other branching direction */
747  if( !SCIPisInfinity(scip, varlb) )
748  {
749  int rowinftiesdownafterbranch;
750  int rowinftiesupafterbranch;
751 
752  changedrowmean = rowmean + rowval * (meandown - currentmean);
753  changedrowvariance = rowvariance + squaredcoeff * (squaredbounddiffdown - squaredbounddiff);
754  changedrowvariance = MAX(0.0, changedrowvariance);
755 
756  rowinftiesdownafterbranch = rowinfinitiesdown;
757  rowinftiesupafterbranch = rowinfinitiesup;
758 
759  /* account for changes of the row's infinite bound contributions */
760  if( SCIPisInfinity(scip, varub) && rowval > 0.0 )
761  rowinftiesupafterbranch -= 1;
762  if( SCIPisInfinity(scip, varub) && rowval < 0.0 )
763  rowinftiesdownafterbranch -= 1;
764 
765  assert(rowinftiesdownafterbranch >= 0);
766  assert(rowinftiesupafterbranch >= 0);
767  newrowprobdown = SCIProwCalcProbability(scip, row, changedrowmean, changedrowvariance, rowinftiesdownafterbranch,
768  rowinftiesupafterbranch);
769  }
770  else
771  newrowprobdown = currentrowprob;
772 
773  /* update the up and down score depending on the chosen scoring parameter */
774  SCIP_CALL( SCIPupdateDistributionScore(scip, currentrowprob, newrowprobup, newrowprobdown, upscore, downscore, scoreparam) );
775 
776  SCIPdebugMsg(scip, " Variable %s changes probability of row %s from %g to %g (branch up) or %g;\n",
777  SCIPvarGetName(var), SCIProwGetName(row), currentrowprob, newrowprobup, newrowprobdown);
778  SCIPdebugMsg(scip, " --> new variable score: %g (for branching up), %g (for branching down)\n",
779  *upscore, *downscore);
780  }
781 
782  return SCIP_OKAY;
783 }
784 
785 /** free branchrule data */
786 static
788  SCIP* scip, /**< SCIP data structure */
789  SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */
790  )
791 {
792  assert(branchruledata->memsize == 0 || branchruledata->rowmeans != NULL);
793  assert(branchruledata->memsize >= 0);
794 
795  if( branchruledata->memsize > 0 )
796  {
797  SCIPfreeBlockMemoryArray(scip, &branchruledata->rowmeans, branchruledata->memsize);
798  SCIPfreeBlockMemoryArray(scip, &branchruledata->rowvariances, branchruledata->memsize);
799  SCIPfreeBlockMemoryArray(scip, &branchruledata->rowinfinitiesup, branchruledata->memsize);
800  SCIPfreeBlockMemoryArray(scip, &branchruledata->rowinfinitiesdown, branchruledata->memsize);
801 
802  branchruledata->memsize = 0;
803  }
804 }
805 
806 /** add variable to the bound change event queue; skipped if variable is already in there, or if variable has
807  * no row currently watched
808  */
809 static
811  SCIP* scip, /**< SCIP data structure */
812  SCIP_BRANCHRULEDATA* branchruledata, /**< branchrule data */
813  SCIP_VAR* var /**< the variable whose bound changes need to be processed */
814  )
815 {
816  int varindex;
817  int varpos;
818 
819  assert(var != NULL);
820 
821  varindex = SCIPvarGetProbindex(var);
822  assert(-1 <= varindex && varindex < branchruledata->varpossmemsize);
823 
824  /* if variable is not active, it should not be watched */
825  if( varindex == -1 )
826  return;
827  varpos = branchruledata->varposs[varindex];
828  assert(varpos < branchruledata->nupdatedvars);
829 
830  /* nothing to do if variable is already in the queue */
831  if( varpos >= 0 )
832  {
833  assert(branchruledata->updatedvars[varpos] == var);
834 
835  return;
836  }
837 
838  /* if none of the variables rows was calculated yet, variable needs not to be watched */
839  assert((branchruledata->currentlbs[varindex] == SCIP_INVALID) == (branchruledata->currentubs[varindex] == SCIP_INVALID)); /*lint !e777*/
840  if( branchruledata->currentlbs[varindex] == SCIP_INVALID ) /*lint !e777*/
841  return;
842 
843  /* add the variable to the branch rule data of variables to process updates for */
844  assert(branchruledata->varpossmemsize > branchruledata->nupdatedvars);
845  varpos = branchruledata->nupdatedvars;
846  branchruledata->updatedvars[varpos] = var;
847  branchruledata->varposs[varindex] = varpos;
848  ++branchruledata->nupdatedvars;
849 }
850 
851 /** returns the next unprocessed variable (last in, first out) with pending bound changes, or NULL */
852 static
854  SCIP* scip, /**< SCIP data structure */
855  SCIP_BRANCHRULEDATA* branchruledata /**< branchrule data */
856  )
857 {
858  SCIP_VAR* var;
859  int varpos;
860  int varindex;
861 
862  assert(branchruledata->nupdatedvars >= 0);
863 
864  /* return if no variable is currently pending */
865  if( branchruledata->nupdatedvars == 0 )
866  return NULL;
867 
868  varpos = branchruledata->nupdatedvars - 1;
869  var = branchruledata->updatedvars[varpos];
870  assert(var != NULL);
871  varindex = SCIPvarGetProbindex(var);
872  assert(0 <= varindex && varindex < branchruledata->varpossmemsize);
873  assert(varpos == branchruledata->varposs[varindex]);
874 
875  branchruledata->varposs[varindex] = -1;
876  branchruledata->nupdatedvars--;
877 
878  return var;
879 }
880 
881 /** process a variable from the queue of changed variables */
882 static
884  SCIP* scip, /**< SCIP data structure */
885  SCIP_BRANCHRULEDATA* branchruledata, /**< branchrule data */
886  SCIP_VAR* var /**< the variable whose bound changes need to be processed */
887  )
888 {
889  SCIP_ROW** colrows;
890  SCIP_COL* varcol;
891  SCIP_Real* colvals;
892  SCIP_Real oldmean;
893  SCIP_Real newmean;
894  SCIP_Real oldvariance;
895  SCIP_Real newvariance;
896  SCIP_Real oldlb;
897  SCIP_Real newlb;
898  SCIP_Real oldub;
899  SCIP_Real newub;
900  SCIP_VARTYPE vartype;
901  int ncolrows;
902  int r;
903  int varindex;
904 
905  /* skip event execution if SCIP is in Probing mode because these bound changes will be undone anyway before branching
906  * rule is called again
907  */
908  assert(!SCIPinProbing(scip));
909 
910  assert(var != NULL);
911  varcol = SCIPvarGetCol(var);
912  assert(varcol != NULL);
913  colrows = SCIPcolGetRows(varcol);
914  colvals = SCIPcolGetVals(varcol);
915  ncolrows = SCIPcolGetNNonz(varcol);
916 
917  varindex = SCIPvarGetProbindex(var);
918 
919  oldlb = branchruledata->currentlbs[varindex];
920  oldub = branchruledata->currentubs[varindex];
921 
922  /* skip update if the variable has never been subject of previously calculated row activities */
923  assert((oldlb == SCIP_INVALID) == (oldub == SCIP_INVALID)); /*lint !e777*/
924  if( oldlb == SCIP_INVALID ) /*lint !e777*/
925  return SCIP_OKAY;
926 
927  newlb = SCIPvarGetLbLocal(var);
928  newub = SCIPvarGetUbLocal(var);
929 
930  /* skip update if the bound change events have cancelled out */
931  if( SCIPisFeasEQ(scip, oldlb, newlb) && SCIPisFeasEQ(scip, oldub, newub) )
932  return SCIP_OKAY;
933 
934  /* calculate old and new variable distribution mean and variance */
935  oldvariance = 0.0;
936  newvariance = 0.0;
937  oldmean = 0.0;
938  newmean = 0.0;
939  vartype = SCIPvarGetType(var);
940  SCIPvarCalcDistributionParameters(scip, oldlb, oldub, vartype, &oldmean, &oldvariance);
941  SCIPvarCalcDistributionParameters(scip, newlb, newub, vartype, &newmean, &newvariance);
942 
943  /* loop over all rows of this variable and update activity distribution */
944  for( r = 0; r < ncolrows; ++r )
945  {
946  int rowpos;
947 
948  assert(colrows[r] != NULL);
949  rowpos = SCIProwGetIndex(colrows[r]);
950  assert(rowpos >= 0);
951 
952  SCIP_CALL( branchruledataEnsureArraySize(scip, branchruledata, rowpos) );
953 
954  /* only consider rows for which activity distribution was already calculated */
955  if( branchruledata->rowmeans[rowpos] != SCIP_INVALID ) /*lint !e777*/
956  {
957  SCIP_Real coeff;
958  SCIP_Real coeffsquared;
959  assert(branchruledata->rowvariances[rowpos] != SCIP_INVALID
960  && SCIPisFeasGE(scip, branchruledata->rowvariances[rowpos], 0.0)); /*lint !e777*/
961 
962  coeff = colvals[r];
963  coeffsquared = SQUARED(coeff);
964 
965  /* update variable contribution to row activity distribution */
966  branchruledata->rowmeans[rowpos] += coeff * (newmean - oldmean);
967  branchruledata->rowvariances[rowpos] += coeffsquared * (newvariance - oldvariance);
968  branchruledata->rowvariances[rowpos] = MAX(0.0, branchruledata->rowvariances[rowpos]);
969 
970  /* account for changes of the infinite contributions to row activities */
971  if( coeff > 0.0 )
972  {
973  /* if the coefficient is positive, upper bounds affect activity up */
974  if( SCIPisInfinity(scip, newub) && !SCIPisInfinity(scip, oldub) )
975  ++branchruledata->rowinfinitiesup[rowpos];
976  else if( !SCIPisInfinity(scip, newub) && SCIPisInfinity(scip, oldub) )
977  --branchruledata->rowinfinitiesup[rowpos];
978 
979  if( SCIPisInfinity(scip, newlb) && !SCIPisInfinity(scip, oldlb) )
980  ++branchruledata->rowinfinitiesdown[rowpos];
981  else if( !SCIPisInfinity(scip, newlb) && SCIPisInfinity(scip, oldlb) )
982  --branchruledata->rowinfinitiesdown[rowpos];
983  }
984  else if( coeff < 0.0 )
985  {
986  if( SCIPisInfinity(scip, newub) && !SCIPisInfinity(scip, oldub) )
987  ++branchruledata->rowinfinitiesdown[rowpos];
988  else if( !SCIPisInfinity(scip, newub) && SCIPisInfinity(scip, oldub) )
989  --branchruledata->rowinfinitiesdown[rowpos];
990 
991  if( SCIPisInfinity(scip, newlb) && !SCIPisInfinity(scip, oldlb) )
992  ++branchruledata->rowinfinitiesup[rowpos];
993  else if( !SCIPisInfinity(scip, newlb) && SCIPisInfinity(scip, oldlb) )
994  --branchruledata->rowinfinitiesup[rowpos];
995  }
996  assert(branchruledata->rowinfinitiesdown[rowpos] >= 0);
997  assert(branchruledata->rowinfinitiesup[rowpos] >= 0);
998  }
999  }
1000 
1001  /* store the new local bounds in the data */
1002  branchruledataUpdateCurrentBounds(scip, branchruledata, var);
1003 
1004  return SCIP_OKAY;
1005 }
1006 
1007 /** destructor of event handler to free user data (called when SCIP is exiting) */
1008 static
1009 SCIP_DECL_EVENTFREE(eventFreeDistribution)
1010 {
1011  SCIP_EVENTHDLRDATA* eventhdlrdata;
1012 
1013  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
1014  assert(eventhdlrdata != NULL);
1015 
1016  SCIPfreeBlockMemory(scip, &eventhdlrdata);
1017  SCIPeventhdlrSetData(eventhdlr, NULL);
1018 
1019  return SCIP_OKAY;
1020 }
1021 
1022 /*
1023  * Callback methods of branching rule
1024  */
1025 
1026 /** copy method for branchrule plugins (called when SCIP copies plugins) */
1027 static
1028 SCIP_DECL_BRANCHCOPY(branchCopyDistribution)
1029 { /*lint --e{715}*/
1030  assert(scip != NULL);
1031 
1033 
1034  return SCIP_OKAY;
1035 }
1036 
1037 /** solving process deinitialization method of branching rule (called before branch and bound process data is freed) */
1038 static
1039 SCIP_DECL_BRANCHEXITSOL(branchExitsolDistribution)
1040 {
1041  SCIP_BRANCHRULEDATA* branchruledata;
1042 
1043  assert(branchrule != NULL);
1044  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
1045 
1046  branchruledata = SCIPbranchruleGetData(branchrule);
1047  assert(branchruledata != NULL);
1048 
1049  /* free row arrays when branch-and-bound data is freed */
1050  branchruledataFreeArrays(scip, branchruledata);
1051 
1052  /* drop variable events at the end of branch and bound process (cannot be used after restarts, anyway) */
1053  if( branchruledata->varfilterposs != NULL)
1054  {
1055  SCIP_VAR** vars;
1056  int nvars;
1057  int v;
1058 
1059  vars = SCIPgetVars(scip);
1060  nvars = SCIPgetNVars(scip);
1061 
1062  assert(nvars > 0);
1063  for( v = 0; v < nvars; ++v )
1064  {
1065  SCIP_CALL( SCIPdropVarEvent(scip, vars[v], EVENT_DISTRIBUTION, branchruledata->eventhdlr, NULL, branchruledata->varfilterposs[v]) );
1066  }
1067  SCIPfreeBlockMemoryArray(scip, &(branchruledata->varfilterposs), nvars);
1068  }
1069  return SCIP_OKAY;
1070 }
1071 
1072 /** destructor of branching rule to free user data (called when SCIP is exiting) */
1073 static
1074 SCIP_DECL_BRANCHFREE(branchFreeDistribution)
1075 {
1076  SCIP_BRANCHRULEDATA* branchruledata;
1077 
1078  assert(branchrule != NULL);
1079  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
1080 
1081  branchruledata = SCIPbranchruleGetData(branchrule);
1082  assert(branchruledata != NULL);
1083 
1084  /* free internal arrays first */
1085  branchruledataFreeArrays(scip, branchruledata);
1086  SCIPfreeBlockMemory(scip, &branchruledata);
1087  SCIPbranchruleSetData(branchrule, NULL);
1088 
1089  return SCIP_OKAY;
1090 }
1091 
1092 /** branching execution method for fractional LP solutions */
1093 static
1094 SCIP_DECL_BRANCHEXECLP(branchExeclpDistribution)
1095 { /*lint --e{715}*/
1096  SCIP_BRANCHRULEDATA* branchruledata;
1097  SCIP_VAR** lpcands;
1098  SCIP_VAR* bestcand;
1099  SCIP_NODE* downchild;
1100  SCIP_NODE* upchild;
1101 
1102  SCIP_Real* lpcandssol;
1103 
1104  SCIP_Real bestscore;
1105  SCIP_BRANCHDIR bestbranchdir;
1106  int nlpcands;
1107  int c;
1108 
1109  assert(branchrule != NULL);
1110  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
1111  assert(scip != NULL);
1112  assert(result != NULL);
1113 
1114  *result = SCIP_DIDNOTRUN;
1115 
1116  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL, NULL, &nlpcands, NULL) );
1117 
1118  if( nlpcands == 0 )
1119  return SCIP_OKAY;
1120 
1121  if( SCIPgetNActivePricers(scip) > 0 )
1122  return SCIP_OKAY;
1123 
1124  branchruledata = SCIPbranchruleGetData(branchrule);
1125 
1126  /* if branching rule data arrays were not initialized before (usually the first call of the branching execution),
1127  * allocate arrays with an initial capacity of the number of LP rows */
1128  if( branchruledata->memsize == 0 )
1129  {
1130  int nlprows;
1131 
1132  /* get LP rows data */
1133  nlprows = SCIPgetNLPRows(scip);
1134 
1135  /* initialize arrays only if there are actual LP rows to operate on */
1136  if( nlprows > 0 )
1137  {
1138  SCIP_CALL( branchruledataEnsureArraySize(scip, branchruledata, nlprows) );
1139  }
1140  else /* if there are no LP rows, branching rule cannot be used */
1141  return SCIP_OKAY;
1142  }
1143 
1144  /* process pending bound change events */
1145  while( branchruledata->nupdatedvars > 0 )
1146  {
1147  SCIP_VAR* nextvar;
1148 
1149  /* pop the next variable from the queue and process its bound changes */
1150  nextvar = branchruledataPopBoundChangeVar(scip, branchruledata);
1151  assert(nextvar != NULL);
1152  SCIP_CALL( varProcessBoundChanges(scip, branchruledata, nextvar) );
1153  }
1154 
1155  bestscore = -1;
1156  bestbranchdir = SCIP_BRANCHDIR_AUTO;
1157  bestcand = NULL;
1158 
1159  /* invalidate the current row distribution data which is initialized on the fly when looping over the candidates */
1160 
1161  /* loop over candidate variables and calculate their score in changing the cumulative
1162  * probability of fulfilling each of their constraints */
1163  for( c = 0; c < nlpcands; ++c )
1164  {
1165  SCIP_Real upscore;
1166  SCIP_Real downscore;
1167  SCIP_VAR* lpcand;
1168  int varindex;
1169 
1170  lpcand = lpcands[c];
1171  assert(lpcand != NULL);
1172 
1173  varindex = SCIPvarGetProbindex(lpcand);
1174 
1175  /* in debug mode, ensure that all bound process events which occurred in the mean time have been captured
1176  * by the branching rule event system
1177  */
1178  assert(SCIPisFeasLE(scip, SCIPvarGetLbLocal(lpcand), SCIPvarGetUbLocal(lpcand)));
1179  assert(0 <= varindex && varindex < branchruledata->varpossmemsize);
1180 
1181  assert((branchruledata->currentlbs[varindex] == SCIP_INVALID) == (branchruledata->currentubs[varindex] == SCIP_INVALID)); /*lint !e777*/
1182  assert((branchruledata->currentlbs[varindex] == SCIP_INVALID)
1183  || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(lpcand), branchruledata->currentlbs[varindex])); /*lint !e777*/
1184  assert((branchruledata->currentubs[varindex] == SCIP_INVALID)
1185  || SCIPisFeasEQ(scip, SCIPvarGetUbLocal(lpcand), branchruledata->currentubs[varindex])); /*lint !e777*/
1186 
1187  /* if the branching rule has not captured the variable bounds yet, this can be done now */
1188  if( branchruledata->currentlbs[varindex] == SCIP_INVALID ) /*lint !e777*/
1189  {
1190  branchruledataUpdateCurrentBounds(scip, branchruledata, lpcand);
1191  }
1192 
1193  upscore = 0.0;
1194  downscore = 0.0;
1195 
1196  /* loop over candidate rows and determine the candidate up- and down- branching score w.r.t. the score parameter */
1197  SCIP_CALL( calcBranchScore(scip, branchruledata, lpcand, lpcandssol[c],
1198  &upscore, &downscore, branchruledata->scoreparam) );
1199 
1200  /* if weighted scoring is enabled, use the branching score method of SCIP to weigh up and down score */
1201  if( branchruledata->usescipscore )
1202  {
1203  SCIP_Real score;
1204 
1205  score = SCIPgetBranchScore(scip, lpcand, downscore, upscore);
1206 
1207  /* select the candidate with the highest branching score */
1208  if( score > bestscore )
1209  {
1210  bestscore = score;
1211  bestcand = lpcand;
1212  /* prioritize branching direction with the higher score */
1213  if( upscore > downscore )
1214  bestbranchdir = SCIP_BRANCHDIR_UPWARDS;
1215  else
1216  bestbranchdir = SCIP_BRANCHDIR_DOWNWARDS;
1217  }
1218  }
1219  else
1220  {
1221  /* no weighted score; keep candidate which has the single highest score in one direction */
1222  if( upscore > bestscore && upscore > downscore )
1223  {
1224  bestscore = upscore;
1225  bestbranchdir = SCIP_BRANCHDIR_UPWARDS;
1226  bestcand = lpcand;
1227  }
1228  else if( downscore > bestscore )
1229  {
1230  bestscore = downscore;
1231  bestbranchdir = SCIP_BRANCHDIR_DOWNWARDS;
1232  bestcand = lpcand;
1233  }
1234  }
1235 
1236  SCIPdebugMsg(scip, " Candidate %s has score down %g and up %g \n", SCIPvarGetName(lpcand), downscore, upscore);
1237  SCIPdebugMsg(scip, " Best candidate: %s, score %g, direction %d\n", SCIPvarGetName(bestcand), bestscore, bestbranchdir);
1238  }
1239  assert(!SCIPisFeasIntegral(scip, SCIPvarGetSol(bestcand, TRUE)));
1240  assert(bestbranchdir == SCIP_BRANCHDIR_DOWNWARDS || bestbranchdir == SCIP_BRANCHDIR_UPWARDS);
1241  assert(bestcand != NULL);
1242 
1243  SCIPdebugMsg(scip, " Branching on variable %s with bounds [%g, %g] and solution value <%g>\n", SCIPvarGetName(bestcand),
1244  SCIPvarGetLbLocal(bestcand), SCIPvarGetUbLocal(bestcand), SCIPvarGetLPSol(bestcand));
1245 
1246  /* branch on the best candidate variable */
1247  SCIP_CALL( SCIPbranchVar(scip, bestcand, &downchild, NULL, &upchild) );
1248 
1249  assert(downchild != NULL);
1250  assert(upchild != NULL);
1251 
1252  if( bestbranchdir == SCIP_BRANCHDIR_UPWARDS )
1253  {
1255  SCIPdebugMsg(scip, " Changing node priority of up-child.\n");
1256  }
1257  else
1258  {
1259  assert(bestbranchdir == SCIP_BRANCHDIR_DOWNWARDS);
1261  SCIPdebugMsg(scip, " Changing node priority of down-child.\n");
1262  }
1263 
1264  *result = SCIP_BRANCHED;
1265 
1266  return SCIP_OKAY;
1267 }
1268 
1269 /** event execution method of distribution branching which handles bound change events of variables */
1270 static
1271 SCIP_DECL_EVENTEXEC(eventExecDistribution)
1272 { /*lint --e{715}*/
1273  SCIP_BRANCHRULEDATA* branchruledata;
1274  SCIP_EVENTHDLRDATA* eventhdlrdata;
1275  SCIP_VAR* var;
1276 
1277  assert(eventhdlr != NULL);
1278  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
1279  assert(eventhdlrdata != NULL);
1280 
1281  branchruledata = eventhdlrdata->branchruledata;
1282  var = SCIPeventGetVar(event);
1283 
1284  /* add the variable to the queue of unprocessed variables; method itself ensures that every variable is added at most once */
1285  branchruledataAddBoundChangeVar(scip, branchruledata, var);
1286 
1287  return SCIP_OKAY;
1288 }
1289 
1290 
1291 /*
1292  * branching rule specific interface methods
1293  */
1294 
1295 /** creates the distribution branching rule and includes it in SCIP */
1297  SCIP* scip /**< SCIP data structure */
1298  )
1299 {
1300  SCIP_BRANCHRULE* branchrule = NULL;
1301  SCIP_BRANCHRULEDATA* branchruledata;
1302  SCIP_EVENTHDLRDATA* eventhdlrdata;
1303 
1304  /* create distribution branching rule data */
1305  branchruledata = NULL;
1306  SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
1307 
1308  branchruledata->memsize = 0;
1309  branchruledata->rowmeans = NULL;
1310  branchruledata->rowvariances = NULL;
1311  branchruledata->rowinfinitiesdown = NULL;
1312  branchruledata->rowinfinitiesup = NULL;
1313  branchruledata->varfilterposs = NULL;
1314  branchruledata->currentlbs = NULL;
1315  branchruledata->currentubs = NULL;
1316 
1317  /* create event handler first to finish branch rule data */
1318  eventhdlrdata = NULL;
1319  SCIP_CALL( SCIPallocBlockMemory(scip, &eventhdlrdata) );
1320  eventhdlrdata->branchruledata = branchruledata;
1321 
1322  branchruledata->eventhdlr = NULL;
1323  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &branchruledata->eventhdlr, EVENTHDLR_NAME,
1324  "event handler for dynamic acitivity distribution updating",
1325  eventExecDistribution, eventhdlrdata) );
1326  assert( branchruledata->eventhdlr != NULL);
1327  SCIP_CALL( SCIPsetEventhdlrFree(scip, branchruledata->eventhdlr, eventFreeDistribution) );
1328 
1329  /* include branching rule */
1331  BRANCHRULE_MAXBOUNDDIST, branchruledata) );
1332 
1333  assert(branchrule != NULL);
1334  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyDistribution) );
1335  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeDistribution) );
1336  SCIP_CALL( SCIPsetBranchruleExitsol(scip, branchrule, branchExitsolDistribution) );
1337  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpDistribution) );
1338 
1339  /* add distribution branching rule parameters */
1340  SCIP_CALL( SCIPaddCharParam(scip, "branching/" BRANCHRULE_NAME "/scoreparam",
1341  "the score;largest 'd'ifference, 'l'owest cumulative probability,'h'ighest c.p., 'v'otes lowest c.p., votes highest c.p.('w') ",
1342  &branchruledata->scoreparam, TRUE, DEFAULT_SCOREPARAM, SCOREPARAM_VALUES, NULL, NULL) );
1343 
1344  SCIP_CALL( SCIPaddBoolParam(scip, "branching/" BRANCHRULE_NAME "/onlyactiverows",
1345  "should only rows which are active at the current node be considered?",
1346  &branchruledata->onlyactiverows, TRUE, DEFAULT_ONLYACTIVEROWS, NULL, NULL) );
1347 
1348  SCIP_CALL( SCIPaddBoolParam(scip, "branching/" BRANCHRULE_NAME "/weightedscore",
1349  "should the branching score weigh up- and down-scores of a variable",
1350  &branchruledata->usescipscore, TRUE, DEFAULT_USEWEIGHTEDSCORE, NULL, NULL) );
1351 
1352  return SCIP_OKAY;
1353 }
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip.c:37001
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22604
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47363
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip.h:22593
void SCIPvarCalcDistributionParameters(SCIP *scip, SCIP_Real varlb, SCIP_Real varub, SCIP_VARTYPE vartype, SCIP_Real *mean, SCIP_Real *variance)
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1810
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22587
probability based branching rule based on an article by J. Pryor and J.W. Chinneck ...
SCIP_Real SCIPerf(SCIP_Real x)
Definition: misc.c:144
static SCIP_DECL_BRANCHFREE(branchFreeDistribution)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47298
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:821
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47311
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip.c:41226
static void branchruledataFreeArrays(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:16363
SCIP_Bool SCIPisSumPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:47274
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:16405
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
#define DEFAULT_USEWEIGHTEDSCORE
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip.c:8611
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:43
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:16543
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
Definition: type_event.h:138
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:47387
SCIP_Real SCIPvarGetSol(SCIP_VAR *var, SCIP_Bool getlpval)
Definition: var.c:12665
#define BRANCHRULE_PRIORITY
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47350
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip.c:9139
#define SQRTOFTWO
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16484
static SCIP_DECL_BRANCHCOPY(branchCopyDistribution)
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip.c:5718
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:47100
#define TRUE
Definition: def.h:63
#define SCIPdebug(x)
Definition: pub_message.h:74
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip.c:9123
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16969
static void branchruledataAddBoundChangeVar(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var)
#define EVENTHDLR_NAME
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
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.c:9086
static void branchruledataUpdateCurrentBounds(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var)
#define DEFAULT_SCOREPARAM
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
#define SCIPdebugMsg
Definition: scip.h:455
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip.c:47435
SCIP_RETCODE SCIPchgChildPrio(SCIP *scip, SCIP_NODE *child, SCIP_Real priority)
Definition: scip.c:13614
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:47423
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip.c:9221
void SCIPeventhdlrSetData(SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: event.c:298
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip.c:37456
#define BRANCHRULE_MAXBOUNDDIST
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:39
#define SCOREPARAM_VALUES
#define EVENT_DISTRIBUTION
static SCIP_VAR * branchruledataPopBoundChangeVar(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata)
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip.c:37610
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_RETCODE SCIPsetEventhdlrFree(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTFREE((*eventfree)))
Definition: scip.c:8657
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46976
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:16353
SCIP_Real SCIPcalcCumulativeDistribution(SCIP *scip, SCIP_Real mean, SCIP_Real variance, SCIP_Real value)
SCIPInterval sqrt(const SCIPInterval &x)
static SCIP_RETCODE branchruledataEnsureArraySize(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, int maxindex)
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
#define BRANCHRULE_DESC
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:17650
int SCIPgetNLPRows(SCIP *scip)
Definition: scip.c:29696
#define SCIP_CALL(x)
Definition: def.h:350
static SCIP_DECL_BRANCHEXECLP(branchExeclpDistribution)
static SCIP_RETCODE calcBranchScore(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var, SCIP_Real lpsolval, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47324
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16494
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:16430
#define SQUARED(x)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:16440
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
Definition: event.c:982
#define SCIP_Bool
Definition: def.h:61
SCIP_Real SCIProwCalcProbability(SCIP *scip, SCIP_ROW *row, SCIP_Real mu, SCIP_Real sigma2, int rowinfinitiesdown, int rowinfinitiesup)
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1820
#define MAX(x, y)
Definition: tclique_def.h:75
#define DEFAULT_PRIORITY
SCIP_RETCODE SCIPsetBranchruleExitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXITSOL((*branchexitsol)))
Definition: scip.c:9203
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip.c:41272
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:16990
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47039
static SCIP_RETCODE varProcessBoundChanges(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var)
static SCIP_DECL_BRANCHEXITSOL(branchExitsolDistribution)
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35836
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11812
#define BRANCHRULE_MAXDEPTH
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:16450
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:16328
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47002
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:47112
#define DEFAULT_ONLYACTIVEROWS
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.c:4349
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16254
static SCIP_DECL_EVENTFREE(eventFreeDistribution)
static void rowCalculateGauss(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_ROW *row, SCIP_Real *mu, SCIP_Real *sigma2, int *rowinfinitiesdown, int *rowinfinitiesup)
SCIP_Real SCIPgetRowLPFeasibility(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30977
static SCIP_DECL_EVENTEXEC(eventExecDistribution)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11767
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16781
#define SCIP_Real
Definition: def.h:149
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1932
SCIP_RETCODE SCIPupdateDistributionScore(SCIP *scip, SCIP_Real currentprob, SCIP_Real newprobup, SCIP_Real newprobdown, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam)
#define SCIP_INVALID
Definition: def.h:169
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip.c:31160
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16827
int SCIProwGetIndex(SCIP_ROW *row)
Definition: lp.c:16553
enum SCIP_Vartype SCIP_VARTYPE
Definition: type_var.h:60
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17342
#define BRANCHRULE_NAME
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:47399
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:288
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.c:4239
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16949
SCIP_RETCODE SCIPincludeBranchruleDistribution(SCIP *scip)