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