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-2016 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  SCIPdebugMessage(" 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  SCIPdebugMessage(" 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  SCIPdebugMessage(" 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  SCIPdebugMessage(" 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  SCIPdebugMessage(" --> 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  return SCIP_OKAY;
806 }
807 
808 /** add variable to the bound change event queue; skipped if variable is already in there, or if variable has
809  * no row currently watched
810  */
811 static
813  SCIP* scip, /**< SCIP data structure */
814  SCIP_BRANCHRULEDATA* branchruledata, /**< branchrule data */
815  SCIP_VAR* var /**< the variable whose bound changes need to be processed */
816  )
817 {
818  int varindex;
819  int varpos;
820 
821  assert(var != NULL);
822 
823  varindex = SCIPvarGetProbindex(var);
824  assert(-1 <= varindex && varindex < branchruledata->varpossmemsize);
825 
826  /* if variable is not active, it should not be watched */
827  if( varindex == -1 )
828  return;
829  varpos = branchruledata->varposs[varindex];
830  assert(varpos < branchruledata->nupdatedvars);
831 
832  /* nothing to do if variable is already in the queue */
833  if( varpos >= 0 )
834  {
835  assert(branchruledata->updatedvars[varpos] == var);
836 
837  return;
838  }
839 
840  /* if none of the variables rows was calculated yet, variable needs not to be watched */
841  assert((branchruledata->currentlbs[varindex] == SCIP_INVALID) == (branchruledata->currentubs[varindex] == SCIP_INVALID)); /*lint !e777*/
842  if( branchruledata->currentlbs[varindex] == SCIP_INVALID ) /*lint !e777*/
843  return;
844 
845  /* add the variable to the branch rule data of variables to process updates for */
846  assert(branchruledata->varpossmemsize > branchruledata->nupdatedvars);
847  varpos = branchruledata->nupdatedvars;
848  branchruledata->updatedvars[varpos] = var;
849  branchruledata->varposs[varindex] = varpos;
850  ++branchruledata->nupdatedvars;
851 }
852 
853 /** returns the next unprocessed variable (last in, first out) with pending bound changes, or NULL */
854 static
856  SCIP* scip, /**< SCIP data structure */
857  SCIP_BRANCHRULEDATA* branchruledata /**< branchrule data */
858  )
859 {
860  SCIP_VAR* var;
861  int varpos;
862  int varindex;
863 
864  assert(branchruledata->nupdatedvars >= 0);
865 
866  /* return if no variable is currently pending */
867  if( branchruledata->nupdatedvars == 0 )
868  return NULL;
869 
870  varpos = branchruledata->nupdatedvars - 1;
871  var = branchruledata->updatedvars[varpos];
872  assert(var != NULL);
873  varindex = SCIPvarGetProbindex(var);
874  assert(0 <= varindex && varindex < branchruledata->varpossmemsize);
875  assert(varpos == branchruledata->varposs[varindex]);
876 
877  branchruledata->varposs[varindex] = -1;
878  branchruledata->nupdatedvars--;
879 
880  return var;
881 }
882 
883 /** process a variable from the queue of changed variables */
884 static
886  SCIP* scip, /**< SCIP data structure */
887  SCIP_BRANCHRULEDATA* branchruledata, /**< branchrule data */
888  SCIP_VAR* var /**< the variable whose bound changes need to be processed */
889  )
890 {
891  SCIP_ROW** colrows;
892  SCIP_COL* varcol;
893  SCIP_Real* colvals;
894  SCIP_Real oldmean;
895  SCIP_Real newmean;
896  SCIP_Real oldvariance;
897  SCIP_Real newvariance;
898  SCIP_Real oldlb;
899  SCIP_Real newlb;
900  SCIP_Real oldub;
901  SCIP_Real newub;
902  SCIP_VARTYPE vartype;
903  int ncolrows;
904  int r;
905  int varindex;
906 
907  /* skip event execution if SCIP is in Probing mode because these bound changes will be undone anyway before branching
908  * rule is called again
909  */
910  assert(!SCIPinProbing(scip));
911 
912  assert(var != NULL);
913  varcol = SCIPvarGetCol(var);
914  assert(varcol != NULL);
915  colrows = SCIPcolGetRows(varcol);
916  colvals = SCIPcolGetVals(varcol);
917  ncolrows = SCIPcolGetNNonz(varcol);
918 
919  varindex = SCIPvarGetProbindex(var);
920 
921  oldlb = branchruledata->currentlbs[varindex];
922  oldub = branchruledata->currentubs[varindex];
923 
924  /* skip update if the variable has never been subject of previously calculated row activities */
925  assert((oldlb == SCIP_INVALID) == (oldub == SCIP_INVALID)); /*lint !e777*/
926  if( oldlb == SCIP_INVALID ) /*lint !e777*/
927  return SCIP_OKAY;
928 
929  newlb = SCIPvarGetLbLocal(var);
930  newub = SCIPvarGetUbLocal(var);
931 
932  /* skip update if the bound change events have cancelled out */
933  if( SCIPisFeasEQ(scip, oldlb, newlb) && SCIPisFeasEQ(scip, oldub, newub) )
934  return SCIP_OKAY;
935 
936  /* calculate old and new variable distribution mean and variance */
937  oldvariance = 0.0;
938  newvariance = 0.0;
939  oldmean = 0.0;
940  newmean = 0.0;
941  vartype = SCIPvarGetType(var);
942  SCIPvarCalcDistributionParameters(scip, oldlb, oldub, vartype, &oldmean, &oldvariance);
943  SCIPvarCalcDistributionParameters(scip, newlb, newub, vartype, &newmean, &newvariance);
944 
945  /* loop over all rows of this variable and update activity distribution */
946  for( r = 0; r < ncolrows; ++r )
947  {
948  int rowpos;
949 
950  assert(colrows[r] != NULL);
951  rowpos = SCIProwGetIndex(colrows[r]);
952  assert(rowpos >= 0);
953 
954  SCIP_CALL( branchruledataEnsureArraySize(scip, branchruledata, rowpos) );
955 
956  /* only consider rows for which activity distribution was already calculated */
957  if( branchruledata->rowmeans[rowpos] != SCIP_INVALID ) /*lint !e777*/
958  {
959  SCIP_Real coeff;
960  SCIP_Real coeffsquared;
961  assert(branchruledata->rowvariances[rowpos] != SCIP_INVALID
962  && SCIPisFeasGE(scip, branchruledata->rowvariances[rowpos], 0.0)); /*lint !e777*/
963 
964  coeff = colvals[r];
965  coeffsquared = SQUARED(coeff);
966 
967  /* update variable contribution to row activity distribution */
968  branchruledata->rowmeans[rowpos] += coeff * (newmean - oldmean);
969  branchruledata->rowvariances[rowpos] += coeffsquared * (newvariance - oldvariance);
970  branchruledata->rowvariances[rowpos] = MAX(0.0, branchruledata->rowvariances[rowpos]);
971 
972  /* account for changes of the infinite contributions to row activities */
973  if( coeff > 0.0 )
974  {
975  /* if the coefficient is positive, upper bounds affect activity up */
976  if( SCIPisInfinity(scip, newub) && !SCIPisInfinity(scip, oldub) )
977  ++branchruledata->rowinfinitiesup[rowpos];
978  else if( !SCIPisInfinity(scip, newub) && SCIPisInfinity(scip, oldub) )
979  --branchruledata->rowinfinitiesup[rowpos];
980 
981  if( SCIPisInfinity(scip, newlb) && !SCIPisInfinity(scip, oldlb) )
982  ++branchruledata->rowinfinitiesdown[rowpos];
983  else if( !SCIPisInfinity(scip, newlb) && SCIPisInfinity(scip, oldlb) )
984  --branchruledata->rowinfinitiesdown[rowpos];
985  }
986  else if( coeff < 0.0 )
987  {
988  if( SCIPisInfinity(scip, newub) && !SCIPisInfinity(scip, oldub) )
989  ++branchruledata->rowinfinitiesdown[rowpos];
990  else if( !SCIPisInfinity(scip, newub) && SCIPisInfinity(scip, oldub) )
991  --branchruledata->rowinfinitiesdown[rowpos];
992 
993  if( SCIPisInfinity(scip, newlb) && !SCIPisInfinity(scip, oldlb) )
994  ++branchruledata->rowinfinitiesup[rowpos];
995  else if( !SCIPisInfinity(scip, newlb) && SCIPisInfinity(scip, oldlb) )
996  --branchruledata->rowinfinitiesup[rowpos];
997  }
998  assert(branchruledata->rowinfinitiesdown[rowpos] >= 0);
999  assert(branchruledata->rowinfinitiesup[rowpos] >= 0);
1000  }
1001  }
1002 
1003  /* store the new local bounds in the data */
1004  branchruledataUpdateCurrentBounds(scip, branchruledata, var);
1005 
1006  return SCIP_OKAY;
1007 }
1008 
1009 /** destructor of event handler to free user data (called when SCIP is exiting) */
1010 static
1011 SCIP_DECL_EVENTFREE(eventFreeDistribution)
1012 {
1013  SCIP_EVENTHDLRDATA* eventhdlrdata;
1014 
1015  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
1016  assert(eventhdlrdata != NULL);
1017 
1018  SCIPfreeMemory(scip, &eventhdlrdata);
1019  SCIPeventhdlrSetData(eventhdlr, NULL);
1020 
1021  return SCIP_OKAY;
1022 }
1023 
1024 /*
1025  * Callback methods of branching rule
1026  */
1027 
1028 /** copy method for branchrule plugins (called when SCIP copies plugins) */
1029 static
1030 SCIP_DECL_BRANCHCOPY(branchCopyDistribution)
1031 { /*lint --e{715}*/
1032  assert(scip != NULL);
1033 
1035 
1036  return SCIP_OKAY;
1037 }
1038 
1039 /** solving process deinitialization method of branching rule (called before branch and bound process data is freed) */
1040 static
1041 SCIP_DECL_BRANCHEXITSOL(branchExitsolDistribution)
1042 {
1043  SCIP_BRANCHRULEDATA* branchruledata;
1044 
1045  assert(branchrule != NULL);
1046  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
1047 
1048  branchruledata = SCIPbranchruleGetData(branchrule);
1049  assert(branchruledata != NULL);
1050 
1051  /* free row arrays when branch-and-bound data is freed */
1052  SCIP_CALL( branchruledataFreeArrays(scip, branchruledata) );
1053 
1054  /* drop variable events at the end of branch and bound process (cannot be used after restarts, anyway) */
1055  if( branchruledata->varfilterposs != NULL)
1056  {
1057  SCIP_VAR** vars;
1058  int nvars;
1059  int v;
1060 
1061  vars = SCIPgetVars(scip);
1062  nvars = SCIPgetNVars(scip);
1063 
1064  assert(nvars > 0);
1065  for( v = 0; v < nvars; ++v )
1066  {
1067  SCIP_CALL( SCIPdropVarEvent(scip, vars[v], EVENT_DISTRIBUTION, branchruledata->eventhdlr, NULL, branchruledata->varfilterposs[v]) );
1068  }
1069  SCIPfreeBlockMemoryArray(scip, &(branchruledata->varfilterposs), nvars);
1070  }
1071  return SCIP_OKAY;
1072 }
1073 
1074 /** destructor of branching rule to free user data (called when SCIP is exiting) */
1075 static
1076 SCIP_DECL_BRANCHFREE(branchFreeDistribution)
1077 {
1078  SCIP_BRANCHRULEDATA* branchruledata;
1079 
1080  assert(branchrule != NULL);
1081  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
1082 
1083  branchruledata = SCIPbranchruleGetData(branchrule);
1084  assert(branchruledata != NULL);
1085 
1086  /* free internal arrays first */
1087  SCIP_CALL( branchruledataFreeArrays(scip, branchruledata) );
1088  SCIPfreeMemory(scip, &branchruledata);
1089  SCIPbranchruleSetData(branchrule, NULL);
1090 
1091  return SCIP_OKAY;
1092 }
1093 
1094 /** branching execution method for fractional LP solutions */
1095 static
1096 SCIP_DECL_BRANCHEXECLP(branchExeclpDistribution)
1097 { /*lint --e{715}*/
1098  SCIP_BRANCHRULEDATA* branchruledata;
1099  SCIP_VAR** lpcands;
1100  SCIP_VAR* bestcand;
1101  SCIP_NODE* downchild;
1102  SCIP_NODE* upchild;
1103 
1104  SCIP_Real* lpcandssol;
1105 
1106  SCIP_Real bestscore;
1107  SCIP_BRANCHDIR bestbranchdir;
1108  int nlpcands;
1109  int c;
1110 
1111  assert(branchrule != NULL);
1112  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
1113  assert(scip != NULL);
1114  assert(result != NULL);
1115 
1116  *result = SCIP_DIDNOTRUN;
1117 
1118  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL, NULL, &nlpcands, NULL) );
1119 
1120  if( nlpcands == 0 )
1121  return SCIP_OKAY;
1122 
1123  if( SCIPgetNActivePricers(scip) > 0 )
1124  return SCIP_OKAY;
1125 
1126  branchruledata = SCIPbranchruleGetData(branchrule);
1127 
1128  /* if branching rule data arrays were not initialized before (usually the first call of the branching execution),
1129  * allocate arrays with an initial capacity of the number of LP rows */
1130  if( branchruledata->memsize == 0 )
1131  {
1132  int nlprows;
1133 
1134  /* get LP rows data */
1135  nlprows = SCIPgetNLPRows(scip);
1136 
1137  /* initialize arrays only if there are actual LP rows to operate on */
1138  if( nlprows > 0 )
1139  {
1140  SCIP_CALL( branchruledataEnsureArraySize(scip, branchruledata, nlprows) );
1141  }
1142  else /* if there are no LP rows, branching rule cannot be used */
1143  return SCIP_OKAY;
1144  }
1145 
1146  /* process pending bound change events */
1147  while( branchruledata->nupdatedvars > 0 )
1148  {
1149  SCIP_VAR* nextvar;
1150 
1151  /* pop the next variable from the queue and process its bound changes */
1152  nextvar = branchruledataPopBoundChangeVar(scip, branchruledata);
1153  assert(nextvar != NULL);
1154  SCIP_CALL( varProcessBoundChanges(scip, branchruledata, nextvar) );
1155  }
1156 
1157  bestscore = -1;
1158  bestbranchdir = SCIP_BRANCHDIR_AUTO;
1159  bestcand = NULL;
1160 
1161  /* invalidate the current row distribution data which is initialized on the fly when looping over the candidates */
1162 
1163  /* loop over candidate variables and calculate their score in changing the cumulative
1164  * probability of fulfilling each of their constraints */
1165  for( c = 0; c < nlpcands; ++c )
1166  {
1167  SCIP_Real upscore;
1168  SCIP_Real downscore;
1169  SCIP_VAR* lpcand;
1170  int varindex;
1171 
1172  lpcand = lpcands[c];
1173  assert(lpcand != NULL);
1174 
1175  varindex = SCIPvarGetProbindex(lpcand);
1176 
1177  /* in debug mode, ensure that all bound process events which occurred in the mean time have been captured
1178  * by the branching rule event system
1179  */
1180  assert(SCIPisFeasLE(scip, SCIPvarGetLbLocal(lpcand), SCIPvarGetUbLocal(lpcand)));
1181  assert(0 <= varindex && varindex < branchruledata->varpossmemsize);
1182 
1183  assert((branchruledata->currentlbs[varindex] == SCIP_INVALID) == (branchruledata->currentubs[varindex] == SCIP_INVALID)); /*lint !e777*/
1184  assert((branchruledata->currentlbs[varindex] == SCIP_INVALID)
1185  || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(lpcand), branchruledata->currentlbs[varindex])); /*lint !e777*/
1186  assert((branchruledata->currentubs[varindex] == SCIP_INVALID)
1187  || SCIPisFeasEQ(scip, SCIPvarGetUbLocal(lpcand), branchruledata->currentubs[varindex])); /*lint !e777*/
1188 
1189  /* if the branching rule has not captured the variable bounds yet, this can be done now */
1190  if( branchruledata->currentlbs[varindex] == SCIP_INVALID ) /*lint !e777*/
1191  {
1192  branchruledataUpdateCurrentBounds(scip, branchruledata, lpcand);
1193  }
1194 
1195  upscore = 0.0;
1196  downscore = 0.0;
1197 
1198  /* loop over candidate rows and determine the candidate up- and down- branching score w.r.t. the score parameter */
1199  SCIP_CALL( calcBranchScore(scip, branchruledata, lpcand, lpcandssol[c],
1200  &upscore, &downscore, branchruledata->scoreparam) );
1201 
1202  /* if weighted scoring is enabled, use the branching score method of SCIP to weigh up and down score */
1203  if( branchruledata->usescipscore )
1204  {
1205  SCIP_Real score;
1206 
1207  score = SCIPgetBranchScore(scip, lpcand, downscore, upscore);
1208 
1209  /* select the candidate with the highest branching score */
1210  if( score > bestscore )
1211  {
1212  bestscore = score;
1213  bestcand = lpcand;
1214  /* prioritize branching direction with the higher score */
1215  if( upscore > downscore )
1216  bestbranchdir = SCIP_BRANCHDIR_UPWARDS;
1217  else
1218  bestbranchdir = SCIP_BRANCHDIR_DOWNWARDS;
1219  }
1220  }
1221  else
1222  {
1223  /* no weighted score; keep candidate which has the single highest score in one direction */
1224  if( upscore > bestscore && upscore > downscore )
1225  {
1226  bestscore = upscore;
1227  bestbranchdir = SCIP_BRANCHDIR_UPWARDS;
1228  bestcand = lpcand;
1229  }
1230  else if( downscore > bestscore )
1231  {
1232  bestscore = downscore;
1233  bestbranchdir = SCIP_BRANCHDIR_DOWNWARDS;
1234  bestcand = lpcand;
1235  }
1236  }
1237 
1238  SCIPdebugMessage(" Candidate %s has score down %g and up %g \n", SCIPvarGetName(lpcand), downscore, upscore);
1239  SCIPdebugMessage(" Best candidate: %s, score %g, direction %d\n", SCIPvarGetName(bestcand), bestscore, bestbranchdir);
1240  }
1241  assert(!SCIPisFeasIntegral(scip, SCIPvarGetSol(bestcand, TRUE)));
1242  assert(bestbranchdir == SCIP_BRANCHDIR_DOWNWARDS || bestbranchdir == SCIP_BRANCHDIR_UPWARDS);
1243  assert(bestcand != NULL);
1244 
1245  SCIPdebugMessage(" Branching on variable %s with bounds [%g, %g] and solution value <%g>\n", SCIPvarGetName(bestcand),
1246  SCIPvarGetLbLocal(bestcand), SCIPvarGetUbLocal(bestcand), SCIPvarGetLPSol(bestcand));
1247 
1248  /* branch on the best candidate variable */
1249  SCIP_CALL( SCIPbranchVar(scip, bestcand, &downchild, NULL, &upchild) );
1250 
1251  assert(downchild != NULL);
1252  assert(upchild != NULL);
1253 
1254  if( bestbranchdir == SCIP_BRANCHDIR_UPWARDS )
1255  {
1257  SCIPdebugMessage(" Changing node priority of up-child.\n");
1258  }
1259  else
1260  {
1261  assert(bestbranchdir == SCIP_BRANCHDIR_DOWNWARDS);
1263  SCIPdebugMessage(" Changing node priority of down-child.\n");
1264  }
1265 
1266  *result = SCIP_BRANCHED;
1267 
1268  return SCIP_OKAY;
1269 }
1270 
1271 /** event execution method of distribution branching which handles bound change events of variables */
1272 static
1273 SCIP_DECL_EVENTEXEC(eventExecDistribution)
1274 { /*lint --e{715}*/
1275  SCIP_BRANCHRULEDATA* branchruledata;
1276  SCIP_EVENTHDLRDATA* eventhdlrdata;
1277  SCIP_VAR* var;
1278 
1279  assert(eventhdlr != NULL);
1280  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
1281  assert(eventhdlrdata != NULL);
1282 
1283  branchruledata = eventhdlrdata->branchruledata;
1284  var = SCIPeventGetVar(event);
1285 
1286  /* add the variable to the queue of unprocessed variables; method itself ensures that every variable is added at most once */
1287  branchruledataAddBoundChangeVar(scip, branchruledata, var);
1288 
1289  return SCIP_OKAY;
1290 }
1291 
1292 
1293 /*
1294  * branching rule specific interface methods
1295  */
1296 
1297 /** creates the distribution branching rule and includes it in SCIP */
1299  SCIP* scip /**< SCIP data structure */
1300  )
1301 {
1302  SCIP_BRANCHRULE* branchrule = NULL;
1303  SCIP_BRANCHRULEDATA* branchruledata;
1304  SCIP_EVENTHDLRDATA* eventhdlrdata;
1305 
1306  /* create distribution branching rule data */
1307  branchruledata = NULL;
1308  SCIP_CALL( SCIPallocMemory(scip, &branchruledata) );
1309 
1310  branchruledata->memsize = 0;
1311  branchruledata->rowmeans = NULL;
1312  branchruledata->rowvariances = NULL;
1313  branchruledata->rowinfinitiesdown = NULL;
1314  branchruledata->rowinfinitiesup = NULL;
1315  branchruledata->varfilterposs = NULL;
1316  branchruledata->currentlbs = NULL;
1317  branchruledata->currentubs = NULL;
1318 
1319  /* create event handler first to finish branch rule data */
1320  eventhdlrdata = NULL;
1321  SCIP_CALL( SCIPallocMemory(scip, &eventhdlrdata) );
1322  eventhdlrdata->branchruledata = branchruledata;
1323 
1324  branchruledata->eventhdlr = NULL;
1325  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &branchruledata->eventhdlr, EVENTHDLR_NAME,
1326  "event handler for dynamic acitivity distribution updating",
1327  eventExecDistribution, eventhdlrdata) );
1328  assert( branchruledata->eventhdlr != NULL);
1329  SCIP_CALL( SCIPsetEventhdlrFree(scip, branchruledata->eventhdlr, eventFreeDistribution) );
1330 
1331  /* include branching rule */
1333  BRANCHRULE_MAXBOUNDDIST, branchruledata) );
1334 
1335  assert(branchrule != NULL);
1336  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyDistribution) );
1337  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeDistribution) );
1338  SCIP_CALL( SCIPsetBranchruleExitsol(scip, branchrule, branchExitsolDistribution) );
1339  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpDistribution) );
1340 
1341  /* add distribution branching rule parameters */
1342  SCIP_CALL( SCIPaddCharParam(scip, "branching/" BRANCHRULE_NAME "/scoreparam",
1343  "the score;largest 'd'ifference, 'l'owest cumulative probability,'h'ighest c.p., 'v'otes lowest c.p., votes highest c.p.('w') ",
1344  &branchruledata->scoreparam, TRUE, DEFAULT_SCOREPARAM, SCOREPARAM_VALUES, NULL, NULL) );
1345 
1346  SCIP_CALL( SCIPaddBoolParam(scip, "branching/" BRANCHRULE_NAME "/onlyactiverows",
1347  "should only rows which are active at the current node be considered?",
1348  &branchruledata->onlyactiverows, TRUE, DEFAULT_ONLYACTIVEROWS, NULL, NULL) );
1349 
1350  SCIP_CALL( SCIPaddBoolParam(scip, "branching/" BRANCHRULE_NAME "/weightedscore",
1351  "should the branching score weigh up- and down-scores of a variable",
1352  &branchruledata->usescipscore, TRUE, DEFAULT_USEWEIGHTEDSCORE, NULL, NULL) );
1353 
1354  return SCIP_OKAY;
1355 }
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip.c:33125
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:10698
#define SCIPallocMemory(scip, ptr)
Definition: scip.h:20526
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16443
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_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip.c:33734
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:41648
static SCIP_RETCODE branchruledataFreeArrays(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:20573
SCIP_Real SCIPvarGetSol(SCIP_VAR *var, SCIP_Bool getlpval)
Definition: var.c:12514
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41920
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:10653
#define NULL
Definition: lpi_spx.cpp:130
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17113
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:42032
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
Definition: event.c:940
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:18915
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:18861
#define DEFAULT_USEWEIGHTEDSCORE
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:43
SCIP_RETCODE SCIPincludeBranchruleDistribution(SCIP *scip)
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
Definition: type_event.h:129
#define BRANCHRULE_PRIORITY
#define SQRTOFTWO
int SCIProwGetIndex(SCIP_ROW *row)
Definition: lp.c:18984
static SCIP_DECL_BRANCHCOPY(branchCopyDistribution)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip.c:7778
#define TRUE
Definition: def.h:55
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPchgChildPrio(SCIP *scip, SCIP_NODE *child, SCIP_Real priority)
Definition: scip.c:12396
#define SCIP_CALL(x)
Definition: def.h:266
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1877
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:41972
static void branchruledataAddBoundChangeVar(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var)
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip.c:5017
#define EVENTHDLR_NAME
SCIP_Real SCIPcalcCumulativeDistribution(SCIP *scip, SCIP_Real mean, SCIP_Real variance, SCIP_Real value)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:42008
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:20556
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip.c:8290
#define SCIPdebugMessage
Definition: pub_message.h:77
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip.c:8306
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:18881
static void branchruledataUpdateCurrentBounds(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var)
#define DEFAULT_SCOREPARAM
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip.c:42044
void SCIPeventhdlrSetData(SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: event.c:298
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:3547
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16562
#define BRANCHRULE_MAXBOUNDDIST
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:39
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip.c:8388
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip.c:36622
#define SCIPfreeMemory(scip, ptr)
Definition: scip.h:20542
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41585
#define SCOREPARAM_VALUES
#define EVENT_DISTRIBUTION
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:8253
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:18784
static SCIP_VAR * branchruledataPopBoundChangeVar(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:41709
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:18925
SCIP_Bool SCIPisSumPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:41883
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:41996
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1765
SCIPInterval sqrt(const SCIPInterval &x)
SCIP_Real SCIPgetRowLPFeasibility(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:28151
static SCIP_RETCODE branchruledataEnsureArraySize(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, int maxindex)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41907
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip.h:20562
#define BRANCHRULE_DESC
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:16771
void SCIPvarCalcDistributionParameters(SCIP *scip, SCIP_Real varlb, SCIP_Real varub, SCIP_VARTYPE vartype, SCIP_Real *mean, SCIP_Real *variance)
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:288
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)
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:18974
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:32131
#define SQUARED(x)
SCIP_RETCODE SCIPupdateDistributionScore(SCIP *scip, SCIP_Real currentprob, SCIP_Real newprobup, SCIP_Real newprobdown, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41611
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17123
#define SCIP_Bool
Definition: def.h:53
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:801
#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:8370
static SCIP_RETCODE varProcessBoundChanges(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var)
static SCIP_DECL_BRANCHEXITSOL(branchExitsolDistribution)
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:17431
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip.c:36668
#define BRANCHRULE_MAXDEPTH
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16608
#define DEFAULT_ONLYACTIVEROWS
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1755
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip.c:33580
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:41721
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 * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:18871
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41933
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16750
static SCIP_DECL_EVENTEXEC(eventExecDistribution)
#define SCIP_Real
Definition: def.h:127
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:3657
#define MIN(x, y)
Definition: memory.c:67
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip.c:28334
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41959
#define SCIP_INVALID
Definition: def.h:147
SCIP_RETCODE SCIPsetEventhdlrFree(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTFREE((*eventfree)))
Definition: scip.c:7824
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:18836
enum SCIP_Vartype SCIP_VARTYPE
Definition: type_var.h:58
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16730
#define SCIPdebug(x)
Definition: pub_message.h:74
SCIP_Real SCIProwCalcProbability(SCIP *scip, SCIP_ROW *row, SCIP_Real mu, SCIP_Real sigma2, int rowinfinitiesdown, int rowinfinitiesup)
#define BRANCHRULE_NAME
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:18685
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:18794
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:18759
int SCIPgetNLPRows(SCIP *scip)
Definition: scip.c:26806