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-2019 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 visit 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 
60 #include "scip/pub_branch.h"
61 #include "scip/pub_event.h"
62 #include "scip/pub_lp.h"
63 #include "scip/pub_message.h"
64 #include "scip/pub_misc.h"
65 #include "scip/pub_var.h"
66 #include "scip/scip_branch.h"
67 #include "scip/scip_event.h"
68 #include "scip/scip_general.h"
69 #include "scip/scip_lp.h"
70 #include "scip/scip_message.h"
71 #include "scip/scip_mem.h"
72 #include "scip/scip_numerics.h"
73 #include "scip/scip_param.h"
74 #include "scip/scip_pricer.h"
75 #include "scip/scip_prob.h"
76 #include "scip/scip_probing.h"
77 #include <string.h>
78 
79 
80 #define BRANCHRULE_NAME "distribution"
81 #define BRANCHRULE_DESC "branching rule based on variable influence on cumulative normal distribution of row activities"
82 #define BRANCHRULE_PRIORITY 0
83 #define BRANCHRULE_MAXDEPTH -1
84 #define BRANCHRULE_MAXBOUNDDIST 1.0
85 
86 #define SCOREPARAM_VALUES "dhlvw"
87 #define DEFAULT_SCOREPARAM 'v'
88 #define DEFAULT_PRIORITY 2.0
89 #define SQRTOFTWO 1.4142136
90 #define SQUARED(x) ((x) * (x))
91 #define DEFAULT_ONLYACTIVEROWS FALSE /**< should only rows which are active at the current node be considered? */
92 #define DEFAULT_USEWEIGHTEDSCORE FALSE /**< should the branching score weigh up- and down-scores of a variable */
93 
94 /* branching rule event handler to catch variable bound changes */
95 #define EVENTHDLR_NAME "eventhdlr_distribution" /**< event handler name */
96 #define EVENT_DISTRIBUTION SCIP_EVENTTYPE_BOUNDCHANGED /**< the event tyoe to be handled by this event handler */
97 
98 /*
99  * Data structures
100  */
101 
102 /** branching rule data */
103 struct SCIP_BranchruleData
104 {
105  SCIP_EVENTHDLR* eventhdlr; /**< event handler pointer */
106  SCIP_VAR** updatedvars; /**< variables to process bound change events for */
107  SCIP_Real* rowmeans; /**< row activity mean values for all rows */
108  SCIP_Real* rowvariances; /**< row activity variances for all rows */
109  SCIP_Real* currentubs; /**< variable upper bounds as currently saved in the row activities */
110  SCIP_Real* currentlbs; /**< variable lower bounds as currently saved in the row activities */
111  int* rowinfinitiesdown; /**< count the number of variables with infinite bounds which allow for always
112  * repairing the constraint right hand side */
113  int* rowinfinitiesup; /**< count the number of variables with infinite bounds which allow for always
114  * repairing the constraint left hand side */
115  int* varposs; /**< array of variable positions in the updated variables array */
116  int* varfilterposs; /**< array of event filter positions for variable events */
117  int nupdatedvars; /**< the current number of variables with pending bound changes */
118  int memsize; /**< memory size of current arrays, needed for dynamic reallocation */
119  int varpossmemsize; /**< memory size of updated vars and varposs array */
120  char scoreparam; /**< parameter how the branch score is calculated */
121  SCIP_Bool onlyactiverows; /**< should only rows which are active at the current node be considered? */
122  SCIP_Bool usescipscore; /**< should the branching use SCIP's branching score function */
123 };
124 
125 struct SCIP_EventhdlrData
126 {
127  SCIP_BRANCHRULEDATA* branchruledata; /**< the branching rule data to access distribution arrays */
128 };
129 
130 /*
131  * Local methods
132  */
133 
134 /** ensure that maxindex + 1 rows can be represented in data arrays; memory gets reallocated with 10% extra space
135  * to save some time for future allocations */
136 static
138  SCIP* scip, /**< SCIP data structure */
139  SCIP_BRANCHRULEDATA* branchruledata, /**< branchruledata */
140  int maxindex /**< row index at hand (size must be at least this large) */
141  )
142 {
143  int newsize;
144  int r;
145 
146  /* maxindex fits in current array -> nothing to do */
147  if( maxindex < branchruledata->memsize )
148  return SCIP_OKAY;
149 
150  /* new memory size is the max index + 1 plus 10% additional space */
151  newsize = (int)SCIPfeasCeil(scip, (maxindex + 1) * 1.1);
152  assert(newsize > branchruledata->memsize);
153  assert(branchruledata->memsize >= 0);
154 
155  /* alloc memory arrays for row information */
156  if( branchruledata->memsize == 0 )
157  {
158  SCIP_VAR** vars;
159  int v;
160  int nvars;
161 
162  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->rowinfinitiesdown, newsize) );
163  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->rowinfinitiesup, newsize) );
164  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->rowmeans, newsize) );
165  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->rowvariances, newsize) );
166 
167  assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING);
168 
169  vars = SCIPgetVars(scip);
170  nvars = SCIPgetNVars(scip);
171 
172  assert(nvars > 0);
173 
174  /* allocate variable update event processing array storage */
175  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->varfilterposs, nvars) );
176  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->varposs, nvars) );
177  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->updatedvars, nvars) );
178  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->currentubs, nvars) );
179  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->currentlbs, nvars) );
180 
181  branchruledata->varpossmemsize = nvars;
182  branchruledata->nupdatedvars = 0;
183 
184  /* init variable event processing data */
185  for( v = 0; v < nvars; ++v )
186  {
187  assert(SCIPvarIsActive(vars[v]));
188  assert(SCIPvarGetProbindex(vars[v]) == v);
189 
190  /* set up variable events to catch bound changes */
191  SCIP_CALL( SCIPcatchVarEvent(scip, vars[v], EVENT_DISTRIBUTION, branchruledata->eventhdlr, NULL, &(branchruledata->varfilterposs[v])) );
192  assert(branchruledata->varfilterposs[v] >= 0);
193 
194  branchruledata->varposs[v] = -1;
195  branchruledata->updatedvars[v] = NULL;
196  branchruledata->currentlbs[v] = SCIP_INVALID;
197  branchruledata->currentubs[v] = SCIP_INVALID;
198  }
199  }
200  else
201  {
202  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &branchruledata->rowinfinitiesdown, branchruledata->memsize, newsize) );
203  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &branchruledata->rowinfinitiesup, branchruledata->memsize, newsize) );
204  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &branchruledata->rowmeans, branchruledata->memsize, newsize) );
205  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &branchruledata->rowvariances, branchruledata->memsize, newsize) );
206  }
207 
208  /* loop over extended arrays and invalidate data to trigger initialization of this row when necessary */
209  for( r = branchruledata->memsize; r < newsize; ++r )
210  {
211  branchruledata->rowmeans[r] = SCIP_INVALID;
212  branchruledata->rowvariances[r] = SCIP_INVALID;
213  branchruledata->rowinfinitiesdown[r] = 0;
214  branchruledata->rowinfinitiesup[r] = 0;
215  }
216 
217  /* adjust memsize */
218  branchruledata->memsize = newsize;
219 
220  return SCIP_OKAY;
221 }
222 
223 /* update the variables current lower and upper bound */
224 static
226  SCIP* scip, /**< SCIP data structure */
227  SCIP_BRANCHRULEDATA* branchruledata, /**< branchrule data */
228  SCIP_VAR* var /**< the variable to update current bounds */
229  )
230 {
231  int varindex;
232  SCIP_Real lblocal;
233  SCIP_Real ublocal;
234 
235  assert(var != NULL);
236 
237  varindex = SCIPvarGetProbindex(var);
238  assert(0 <= varindex && varindex < branchruledata->varpossmemsize);
239  lblocal = SCIPvarGetLbLocal(var);
240  ublocal = SCIPvarGetUbLocal(var);
241 
242  assert(SCIPisFeasLE(scip, lblocal, ublocal));
243 
244  branchruledata->currentlbs[varindex] = lblocal;
245  branchruledata->currentubs[varindex] = ublocal;
246 }
247 
248 /** calculate the variable's distribution parameters (mean and variance) for the bounds specified in the arguments.
249  * special treatment of infinite bounds necessary */
251  SCIP* scip, /**< SCIP data structure */
252  SCIP_Real varlb, /**< variable lower bound */
253  SCIP_Real varub, /**< variable upper bound */
254  SCIP_VARTYPE vartype, /**< type of the variable */
255  SCIP_Real* mean, /**< pointer to store mean value */
256  SCIP_Real* variance /**< pointer to store the variance of the variable uniform distribution */
257  )
258 {
259  assert(mean != NULL);
260  assert(variance != NULL);
261 
262  /* calculate mean and variance of variable uniform distribution before and after branching */
263  if( SCIPisInfinity(scip, varub) || SCIPisInfinity(scip, -varlb) )
264  {
265  /* variables with infinite bounds are not kept in the row activity variance */
266  *variance = 0.0;
267 
268  if( !SCIPisInfinity(scip, varub) )
269  *mean = varub;
270  else if( !SCIPisInfinity(scip, -varlb) )
271  *mean = varlb;
272  else
273  *mean = 0.0;
274  }
275  else
276  {
277  /* if the variable is continuous, we assume a continuous uniform distribution, otherwise a discrete one */
278  if( vartype == SCIP_VARTYPE_CONTINUOUS )
279  *variance = SQUARED(varub - varlb);
280  else
281  *variance = SQUARED(varub - varlb + 1) - 1;
282  *variance /= 12.0;
283  *mean = (varub + varlb) * .5;
284  }
285 
286  assert(!SCIPisNegative(scip, *variance));
287 }
288 
289 /** calculates the cumulative distribution P(-infinity <= x <= value) that a normally distributed
290  * random variable x takes a value between -infinity and parameter \p value.
291  *
292  * The distribution is given by the respective mean and deviation. This implementation
293  * uses the error function SCIPerf().
294  */
296  SCIP* scip, /**< current SCIP */
297  SCIP_Real mean, /**< the mean value of the distribution */
298  SCIP_Real variance, /**< the square of the deviation of the distribution */
299  SCIP_Real value /**< the upper limit of the calculated distribution integral */
300  )
301 {
302  SCIP_Real normvalue;
303  SCIP_Real std;
304 
305  /* we need to calculate the standard deviation from the variance */
306  assert(!SCIPisNegative(scip, variance));
307  if( SCIPisFeasZero(scip, variance) )
308  std = 0.0;
309  else
310  std = sqrt(variance);
311 
312  /* special treatment for zero variance */
313  if( SCIPisFeasZero(scip, std) )
314  {
315  if( SCIPisFeasLE(scip, value, mean) )
316  return 1.0;
317  else
318  return 0.0;
319  }
320  assert( std != 0.0 ); /* for lint */
321 
322  /* scale and translate to standard normal distribution. Factor sqrt(2) is needed for SCIPerf() function */
323  normvalue = (value - mean)/(std * SQRTOFTWO);
324 
325  SCIPdebugMsg(scip, " Normalized value %g = ( %g - %g ) / (%g * 1.4142136)\n", normvalue, value, mean, std);
326 
327  /* calculate the cumulative distribution function for normvalue. For negative normvalues, we negate
328  * the normvalue and use the oddness of the SCIPerf()-function; special treatment for values close to zero.
329  */
330  if( SCIPisFeasZero(scip, normvalue) )
331  return .5;
332  else if( normvalue > 0 )
333  {
334  SCIP_Real erfresult;
335 
336  erfresult = SCIPerf(normvalue);
337  return erfresult / 2.0 + 0.5;
338  }
339  else
340  {
341  SCIP_Real erfresult;
342 
343  erfresult = SCIPerf(-normvalue);
344 
345  return 0.5 - erfresult / 2.0;
346  }
347 }
348 
349 /** calculates the probability of satisfying an LP-row under the assumption
350  * of uniformly distributed variable values.
351  *
352  * For inequalities, we use the cumulative distribution function of the standard normal
353  * distribution PHI(rhs - mu/sqrt(sigma2)) to calculate the probability
354  * for a right hand side row with mean activity mu and variance sigma2 to be satisfied.
355  * Similarly, 1 - PHI(lhs - mu/sqrt(sigma2)) is the probability to satisfy a left hand side row.
356  * For equations (lhs==rhs), we use the centeredness measure p = min(PHI(lhs'), 1-PHI(lhs'))/max(PHI(lhs'), 1 - PHI(lhs')),
357  * where lhs' = lhs - mu / sqrt(sigma2).
358  */
360  SCIP* scip, /**< current scip */
361  SCIP_ROW* row, /**< the row */
362  SCIP_Real mu, /**< the mean value of the row distribution */
363  SCIP_Real sigma2, /**< the variance of the row distribution */
364  int rowinfinitiesdown, /**< the number of variables with infinite bounds to DECREASE activity */
365  int rowinfinitiesup /**< the number of variables with infinite bounds to INCREASE activity */
366  )
367 {
368  SCIP_Real rowprobability;
369  SCIP_Real lhs;
370  SCIP_Real rhs;
371  SCIP_Real lhsprob;
372  SCIP_Real rhsprob;
373 
374  lhs = SCIProwGetLhs(row);
375  rhs = SCIProwGetRhs(row);
376 
377  lhsprob = 1.0;
378  rhsprob = 1.0;
379 
380  /* use the cumulative distribution if the row contains no variable to repair every infeasibility */
381  if( !SCIPisInfinity(scip, rhs) && rowinfinitiesdown == 0 )
382  rhsprob = SCIPcalcCumulativeDistribution(scip, mu, sigma2, rhs);
383 
384  /* use the cumulative distribution if the row contains no variable to repair every infeasibility
385  * otherwise the row can always be made feasible by increasing activity far enough
386  */
387  if( !SCIPisInfinity(scip, -lhs) && rowinfinitiesup == 0 )
388  lhsprob = 1.0 - SCIPcalcCumulativeDistribution(scip, mu, sigma2, lhs);
389 
390  assert(SCIPisFeasLE(scip, lhsprob, 1.0) && SCIPisFeasGE(scip, lhsprob, 0.0));
391  assert(SCIPisFeasLE(scip, rhsprob, 1.0) && SCIPisFeasGE(scip, rhsprob, 0.0));
392 
393  /* use centeredness measure for equations; for inequalities, the minimum of the two probabilities is the
394  * probability to satisfy the row */
395  if( SCIPisFeasEQ(scip, lhs, rhs) )
396  {
397  SCIP_Real minprobability;
398  SCIP_Real maxprobability;
399 
400  minprobability = MIN(rhsprob, lhsprob);
401  maxprobability = MAX(lhsprob, rhsprob);
402  rowprobability = minprobability / maxprobability;
403  }
404  else
405  rowprobability = MIN(rhsprob, lhsprob);
406 
407  SCIPdebug( SCIPprintRow(scip, row, NULL) );
408  SCIPdebugMsg(scip, " Row %s, mean %g, sigma2 %g, LHS %g, RHS %g has probability %g to be satisfied\n",
409  SCIProwGetName(row), mu, sigma2, lhs, rhs, rowprobability);
410 
411  assert(SCIPisFeasGE(scip, rowprobability, 0.0) && SCIPisFeasLE(scip, rowprobability, 1.0));
412 
413  return rowprobability;
414 }
415 
416 /** calculates the initial mean and variance of the row activity normal distribution.
417  *
418  * The mean value \f$ \mu \f$ is given by \f$ \mu = \sum_i=1^n c_i * (lb_i +ub_i) / 2 \f$ where
419  * \f$n \f$ is the number of variables, and \f$ c_i, lb_i, ub_i \f$ are the variable coefficient and
420  * bounds, respectively. With the same notation, the variance \f$ \sigma^2 \f$ is given by
421  * \f$ \sigma^2 = \sum_i=1^n c_i^2 * \sigma^2_i \f$, with the variance being
422  * \f$ \sigma^2_i = ((ub_i - lb_i + 1)^2 - 1) / 12 \f$ for integer variables and
423  * \f$ \sigma^2_i = (ub_i - lb_i)^2 / 12 \f$ for continuous variables.
424  */
425 static
427  SCIP* scip, /**< SCIP data structure */
428  SCIP_BRANCHRULEDATA* branchruledata, /**< the branching rule data */
429  SCIP_ROW* row, /**< the row for which the gaussian normal distribution has to be calculated */
430  SCIP_Real* mu, /**< pointer to store the mean value of the gaussian normal distribution */
431  SCIP_Real* sigma2, /**< pointer to store the variance value of the gaussian normal distribution */
432  int* rowinfinitiesdown, /**< pointer to store the number of variables with infinite bounds to DECREASE activity */
433  int* rowinfinitiesup /**< pointer to store the number of variables with infinite bounds to INCREASE activity */
434  )
435 {
436  SCIP_COL** rowcols;
437  SCIP_Real* rowvals;
438  int nrowvals;
439  int c;
440 
441  assert(scip != NULL);
442  assert(row != NULL);
443  assert(mu != NULL);
444  assert(sigma2 != NULL);
445  assert(rowinfinitiesup != NULL);
446  assert(rowinfinitiesdown != NULL);
447 
448  rowcols = SCIProwGetCols(row);
449  rowvals = SCIProwGetVals(row);
450  nrowvals = SCIProwGetNNonz(row);
451 
452  assert(nrowvals == 0 || rowcols != NULL);
453  assert(nrowvals == 0 || rowvals != NULL);
454 
455  *mu = SCIProwGetConstant(row);
456  *sigma2 = 0.0;
457  *rowinfinitiesdown = 0;
458  *rowinfinitiesup = 0;
459 
460  /* loop over nonzero row coefficients and sum up the variable contributions to mu and sigma2 */
461  for( c = 0; c < nrowvals; ++c )
462  {
463  SCIP_VAR* colvar;
464  SCIP_Real colval;
465  SCIP_Real colvarlb;
466  SCIP_Real colvarub;
467  SCIP_Real squarecoeff;
468  SCIP_Real varvariance;
469  SCIP_Real varmean;
470  int varindex;
471 
472  assert(rowcols[c] != NULL);
473  colvar = SCIPcolGetVar(rowcols[c]);
474  assert(colvar != NULL);
475 
476  colval = rowvals[c];
477  colvarlb = SCIPvarGetLbLocal(colvar);
478  colvarub = SCIPvarGetUbLocal(colvar);
479 
480  varmean = 0.0;
481  varvariance = 0.0;
482  varindex = SCIPvarGetProbindex(colvar);
483  assert((branchruledata->currentlbs[varindex] == SCIP_INVALID) == (branchruledata->currentubs[varindex] == SCIP_INVALID)); /*lint !e777*/
484 
485  /* variable bounds need to be watched from now on */
486  if( branchruledata->currentlbs[varindex] == SCIP_INVALID ) /*lint !e777*/
487  branchruledataUpdateCurrentBounds(scip, branchruledata, colvar);
488 
489  assert(!SCIPisInfinity(scip, colvarlb));
490  assert(!SCIPisInfinity(scip, -colvarub));
491  assert(SCIPisFeasLE(scip, colvarlb, colvarub));
492 
493  /* variables with infinite bounds are skipped for the calculation of the variance; they need to
494  * be accounted for by the counters for infinite row activity decrease and increase and they
495  * are used to shift the row activity mean in case they have one nonzero, but finite bound */
496  if( SCIPisInfinity(scip, -colvarlb) || SCIPisInfinity(scip, colvarub) )
497  {
498  if( SCIPisInfinity(scip, colvarub) )
499  {
500  /* an infinite upper bound gives the row an infinite maximum activity or minimum activity, if the coefficient is
501  * positive or negative, resp.
502  */
503  if( colval < 0.0 )
504  ++(*rowinfinitiesdown);
505  else
506  ++(*rowinfinitiesup);
507  }
508 
509  /* an infinite lower bound gives the row an infinite maximum activity or minimum activity, if the coefficient is
510  * negative or positive, resp.
511  */
512  if( SCIPisInfinity(scip, -colvarlb) )
513  {
514  if( colval > 0.0 )
515  ++(*rowinfinitiesdown);
516  else
517  ++(*rowinfinitiesup);
518  }
519  }
520  SCIPvarCalcDistributionParameters(scip, colvarlb, colvarub, SCIPvarGetType(colvar), &varmean, &varvariance);
521 
522  /* actual values are updated; the contribution of the variable to mu is the arithmetic mean of its bounds */
523  *mu += colval * varmean;
524 
525  /* 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 */
526  squarecoeff = SQUARED(colval);
527  *sigma2 += squarecoeff * varvariance;
528 
529  assert(!SCIPisFeasNegative(scip, *sigma2));
530  }
531 
532  SCIPdebug( SCIPprintRow(scip, row, NULL) );
533  SCIPdebugMsg(scip, " Row %s has a mean value of %g at a sigma2 of %g \n", SCIProwGetName(row), *mu, *sigma2);
534 }
535 
536 /** update the up- and downscore of a single variable after calculating the impact of branching on a
537  * particular row, depending on the chosen score parameter
538  */
540  SCIP* scip, /**< current SCIP pointer */
541  SCIP_Real currentprob, /**< the current probability */
542  SCIP_Real newprobup, /**< the new probability if branched upwards */
543  SCIP_Real newprobdown, /**< the new probability if branched downwards */
544  SCIP_Real* upscore, /**< pointer to store the new score for branching up */
545  SCIP_Real* downscore, /**< pointer to store the new score for branching down */
546  char scoreparam /**< parameter to determine the way the score is calculated */
547  )
548 {
549  assert(scip != NULL);
550  assert(SCIPisFeasGE(scip, currentprob, 0.0) && SCIPisFeasLE(scip, currentprob, 1.0));
551  assert(SCIPisFeasGE(scip, newprobup, 0.0) && SCIPisFeasLE(scip, newprobup, 1.0));
552  assert(SCIPisFeasGE(scip, newprobdown, 0.0) && SCIPisFeasLE(scip, newprobdown, 1.0));
553  assert(upscore != NULL);
554  assert(downscore != NULL);
555 
556  /* update up and downscore depending on score parameter */
557  switch( scoreparam )
558  {
559  case 'l' :
560  /* 'l'owest cumulative probability */
561  if( SCIPisGT(scip, 1.0 - newprobup, *upscore) )
562  *upscore = 1.0 - newprobup;
563  if( SCIPisGT(scip, 1.0 - newprobdown, *downscore) )
564  *downscore = 1.0 - newprobdown;
565  break;
566 
567  case 'd' :
568  /* biggest 'd'ifference currentprob - newprob */
569  if( SCIPisGT(scip, currentprob - newprobup, *upscore) )
570  *upscore = currentprob - newprobup;
571  if( SCIPisGT(scip, currentprob - newprobdown, *downscore) )
572  *downscore = currentprob - newprobdown;
573  break;
574 
575  case 'h' :
576  /* 'h'ighest cumulative probability */
577  if( SCIPisGT(scip, newprobup, *upscore) )
578  *upscore = newprobup;
579  if( SCIPisGT(scip, newprobdown, *downscore) )
580  *downscore = newprobdown;
581  break;
582 
583  case 'v' :
584  /* 'v'otes lowest cumulative probability */
585  if( SCIPisLT(scip, newprobup, newprobdown) )
586  *upscore += 1.0;
587  else if( SCIPisGT(scip, newprobup, newprobdown) )
588  *downscore += 1.0;
589  break;
590 
591  case 'w' :
592  /* votes highest cumulative probability */
593  if( SCIPisGT(scip, newprobup, newprobdown) )
594  *upscore += 1.0;
595  else if( SCIPisLT(scip, newprobup, newprobdown) )
596  *downscore += 1.0;
597  break;
598 
599  default :
600  SCIPerrorMessage(" ERROR! No branching scheme selected! Exiting method.\n");
601  return SCIP_INVALIDCALL;
602  }
603 
604  return SCIP_OKAY;
605 }
606 
607 /** calculate the branching score of a variable, depending on the chosen score parameter */
608 static
610  SCIP* scip, /**< current SCIP */
611  SCIP_BRANCHRULEDATA* branchruledata, /**< branch rule data */
612  SCIP_VAR* var, /**< candidate variable */
613  SCIP_Real lpsolval, /**< current fractional LP-relaxation solution value */
614  SCIP_Real* upscore, /**< pointer to store the variable score when branching on it in upward direction */
615  SCIP_Real* downscore, /**< pointer to store the variable score when branching on it in downward direction */
616  char scoreparam /**< the score parameter of this branching rule */
617  )
618 {
619  SCIP_COL* varcol;
620  SCIP_ROW** colrows;
621  SCIP_Real* rowvals;
622  SCIP_Real varlb;
623  SCIP_Real varub;
624  SCIP_Real squaredbounddiff; /* current squared difference of variable bounds (ub - lb)^2 */
625  SCIP_Real newub; /* new upper bound if branching downwards */
626  SCIP_Real newlb; /* new lower bound if branching upwards */
627  SCIP_Real squaredbounddiffup; /* squared difference after branching upwards (ub - lb')^2 */
628  SCIP_Real squaredbounddiffdown; /* squared difference after branching downwards (ub' - lb)^2 */
629  SCIP_Real currentmean; /* current mean value of variable uniform distribution */
630  SCIP_Real meanup; /* mean value of variable uniform distribution after branching up */
631  SCIP_Real meandown; /* mean value of variable uniform distribution after branching down*/
632  SCIP_VARTYPE vartype;
633  int ncolrows;
634  int i;
635 
636  SCIP_Bool onlyactiverows; /* should only rows which are active at the current node be considered? */
637 
638  assert(scip != NULL);
639  assert(var != NULL);
640  assert(upscore != NULL);
641  assert(downscore != NULL);
642  assert(!SCIPisIntegral(scip, lpsolval));
643  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
644 
645  varcol = SCIPvarGetCol(var);
646  assert(varcol != NULL);
647 
648  colrows = SCIPcolGetRows(varcol);
649  rowvals = SCIPcolGetVals(varcol);
650  ncolrows = SCIPcolGetNNonz(varcol);
651  varlb = SCIPvarGetLbLocal(var);
652  varub = SCIPvarGetUbLocal(var);
653  assert(SCIPisFeasLT(scip, varlb, varub));
654  vartype = SCIPvarGetType(var);
655 
656  /* calculate mean and variance of variable uniform distribution before and after branching */
657  currentmean = 0.0;
658  squaredbounddiff = 0.0;
659  SCIPvarCalcDistributionParameters(scip, varlb, varub, vartype, &currentmean, &squaredbounddiff);
660 
661  newlb = SCIPfeasCeil(scip, lpsolval);
662  newub = SCIPfeasFloor(scip, lpsolval);
663 
664  /* calculate the variable's uniform distribution after branching up and down, respectively. */
665  squaredbounddiffup = 0.0;
666  meanup = 0.0;
667  SCIPvarCalcDistributionParameters(scip, newlb, varub, vartype, &meanup, &squaredbounddiffup);
668 
669  /* calculate the distribution mean and variance for a variable with finite lower bound */
670  squaredbounddiffdown = 0.0;
671  meandown = 0.0;
672  SCIPvarCalcDistributionParameters(scip, varlb, newub, vartype, &meandown, &squaredbounddiffdown);
673 
674  /* initialize the variable's up and down score */
675  *upscore = 0.0;
676  *downscore = 0.0;
677 
678  onlyactiverows = branchruledata->onlyactiverows;
679 
680  /* loop over the variable rows and calculate the up and down score */
681  for( i = 0; i < ncolrows; ++i )
682  {
683  SCIP_ROW* row;
684  SCIP_Real changedrowmean;
685  SCIP_Real rowmean;
686  SCIP_Real rowvariance;
687  SCIP_Real changedrowvariance;
688  SCIP_Real currentrowprob;
689  SCIP_Real newrowprobup;
690  SCIP_Real newrowprobdown;
691  SCIP_Real squaredcoeff;
692  SCIP_Real rowval;
693  int rowinfinitiesdown;
694  int rowinfinitiesup;
695  int rowpos;
696 
697  row = colrows[i];
698  rowval = rowvals[i];
699  assert(row != NULL);
700 
701  /* we access the rows by their index */
702  rowpos = SCIProwGetIndex(row);
703 
704  /* skip non-active rows if the user parameter was set this way */
705  if( onlyactiverows && SCIPisSumPositive(scip, SCIPgetRowLPFeasibility(scip, row)) )
706  continue;
707 
708  /* call method to ensure sufficient data capacity */
709  SCIP_CALL( branchruledataEnsureArraySize(scip, branchruledata, rowpos) );
710 
711  /* calculate row activity distribution if this is the first candidate to appear in this row */
712  if( branchruledata->rowmeans[rowpos] == SCIP_INVALID ) /*lint !e777*/
713  {
714  rowCalculateGauss(scip, branchruledata, row, &branchruledata->rowmeans[rowpos], &branchruledata->rowvariances[rowpos],
715  &branchruledata->rowinfinitiesdown[rowpos], &branchruledata->rowinfinitiesup[rowpos]);
716  }
717 
718  /* retrieve the row distribution parameters from the branch rule data */
719  rowmean = branchruledata->rowmeans[rowpos];
720  rowvariance = branchruledata->rowvariances[rowpos];
721  rowinfinitiesdown = branchruledata->rowinfinitiesdown[rowpos];
722  rowinfinitiesup = branchruledata->rowinfinitiesdown[rowpos];
723  assert(!SCIPisNegative(scip, rowvariance));
724 
725  currentrowprob = SCIProwCalcProbability(scip, row, rowmean, rowvariance,
726  rowinfinitiesdown, rowinfinitiesup);
727 
728  /* get variable's current expected contribution to row activity */
729  squaredcoeff = SQUARED(rowval);
730 
731  /* first, get the probability change for the row if the variable is branched on upwards. The probability
732  * can only be affected if the variable upper bound is finite
733  */
734  if( !SCIPisInfinity(scip, varub) )
735  {
736  int rowinftiesdownafterbranch;
737  int rowinftiesupafterbranch;
738 
739  /* calculate how branching would affect the row parameters */
740  changedrowmean = rowmean + rowval * (meanup - currentmean);
741  changedrowvariance = rowvariance + squaredcoeff * (squaredbounddiffup - squaredbounddiff);
742  changedrowvariance = MAX(0.0, changedrowvariance);
743 
744  rowinftiesdownafterbranch = rowinfinitiesdown;
745  rowinftiesupafterbranch = rowinfinitiesup;
746 
747  /* account for changes of the row's infinite bound contributions */
748  if( SCIPisInfinity(scip, -varlb) && rowval < 0.0 )
749  rowinftiesupafterbranch--;
750  if( SCIPisInfinity(scip, -varlb) && rowval > 0.0 )
751  rowinftiesdownafterbranch--;
752 
753  assert(rowinftiesupafterbranch >= 0);
754  assert(rowinftiesdownafterbranch >= 0);
755  newrowprobup = SCIProwCalcProbability(scip, row, changedrowmean, changedrowvariance, rowinftiesdownafterbranch,
756  rowinftiesupafterbranch);
757  }
758  else
759  newrowprobup = currentrowprob;
760 
761  /* do the same for the other branching direction */
762  if( !SCIPisInfinity(scip, varlb) )
763  {
764  int rowinftiesdownafterbranch;
765  int rowinftiesupafterbranch;
766 
767  changedrowmean = rowmean + rowval * (meandown - currentmean);
768  changedrowvariance = rowvariance + squaredcoeff * (squaredbounddiffdown - squaredbounddiff);
769  changedrowvariance = MAX(0.0, changedrowvariance);
770 
771  rowinftiesdownafterbranch = rowinfinitiesdown;
772  rowinftiesupafterbranch = rowinfinitiesup;
773 
774  /* account for changes of the row's infinite bound contributions */
775  if( SCIPisInfinity(scip, varub) && rowval > 0.0 )
776  rowinftiesupafterbranch -= 1;
777  if( SCIPisInfinity(scip, varub) && rowval < 0.0 )
778  rowinftiesdownafterbranch -= 1;
779 
780  assert(rowinftiesdownafterbranch >= 0);
781  assert(rowinftiesupafterbranch >= 0);
782  newrowprobdown = SCIProwCalcProbability(scip, row, changedrowmean, changedrowvariance, rowinftiesdownafterbranch,
783  rowinftiesupafterbranch);
784  }
785  else
786  newrowprobdown = currentrowprob;
787 
788  /* update the up and down score depending on the chosen scoring parameter */
789  SCIP_CALL( SCIPupdateDistributionScore(scip, currentrowprob, newrowprobup, newrowprobdown, upscore, downscore, scoreparam) );
790 
791  SCIPdebugMsg(scip, " Variable %s changes probability of row %s from %g to %g (branch up) or %g;\n",
792  SCIPvarGetName(var), SCIProwGetName(row), currentrowprob, newrowprobup, newrowprobdown);
793  SCIPdebugMsg(scip, " --> new variable score: %g (for branching up), %g (for branching down)\n",
794  *upscore, *downscore);
795  }
796 
797  return SCIP_OKAY;
798 }
799 
800 /** free branchrule data */
801 static
803  SCIP* scip, /**< SCIP data structure */
804  SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */
805  )
806 {
807  assert(branchruledata->memsize == 0 || branchruledata->rowmeans != NULL);
808  assert(branchruledata->memsize >= 0);
809 
810  if( branchruledata->memsize > 0 )
811  {
812  SCIPfreeBlockMemoryArray(scip, &branchruledata->rowmeans, branchruledata->memsize);
813  SCIPfreeBlockMemoryArray(scip, &branchruledata->rowvariances, branchruledata->memsize);
814  SCIPfreeBlockMemoryArray(scip, &branchruledata->rowinfinitiesup, branchruledata->memsize);
815  SCIPfreeBlockMemoryArray(scip, &branchruledata->rowinfinitiesdown, branchruledata->memsize);
816 
817  branchruledata->memsize = 0;
818  }
819 }
820 
821 /** add variable to the bound change event queue; skipped if variable is already in there, or if variable has
822  * no row currently watched
823  */
824 static
826  SCIP* scip, /**< SCIP data structure */
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* scip, /**< SCIP data structure */
870  SCIP_BRANCHRULEDATA* branchruledata /**< branchrule data */
871  )
872 {
873  SCIP_VAR* var;
874  int varpos;
875  int varindex;
876 
877  assert(branchruledata->nupdatedvars >= 0);
878 
879  /* return if no variable is currently pending */
880  if( branchruledata->nupdatedvars == 0 )
881  return NULL;
882 
883  varpos = branchruledata->nupdatedvars - 1;
884  var = branchruledata->updatedvars[varpos];
885  assert(var != NULL);
886  varindex = SCIPvarGetProbindex(var);
887  assert(0 <= varindex && varindex < branchruledata->varpossmemsize);
888  assert(varpos == branchruledata->varposs[varindex]);
889 
890  branchruledata->varposs[varindex] = -1;
891  branchruledata->nupdatedvars--;
892 
893  return var;
894 }
895 
896 /** process a variable from the queue of changed variables */
897 static
899  SCIP* scip, /**< SCIP data structure */
900  SCIP_BRANCHRULEDATA* branchruledata, /**< branchrule data */
901  SCIP_VAR* var /**< the variable whose bound changes need to be processed */
902  )
903 {
904  SCIP_ROW** colrows;
905  SCIP_COL* varcol;
906  SCIP_Real* colvals;
907  SCIP_Real oldmean;
908  SCIP_Real newmean;
909  SCIP_Real oldvariance;
910  SCIP_Real newvariance;
911  SCIP_Real oldlb;
912  SCIP_Real newlb;
913  SCIP_Real oldub;
914  SCIP_Real newub;
915  SCIP_VARTYPE vartype;
916  int ncolrows;
917  int r;
918  int varindex;
919 
920  /* skip event execution if SCIP is in Probing mode because these bound changes will be undone anyway before branching
921  * rule is called again
922  */
923  assert(!SCIPinProbing(scip));
924 
925  assert(var != NULL);
926  varcol = SCIPvarGetCol(var);
927  assert(varcol != NULL);
928  colrows = SCIPcolGetRows(varcol);
929  colvals = SCIPcolGetVals(varcol);
930  ncolrows = SCIPcolGetNNonz(varcol);
931 
932  varindex = SCIPvarGetProbindex(var);
933 
934  oldlb = branchruledata->currentlbs[varindex];
935  oldub = branchruledata->currentubs[varindex];
936 
937  /* skip update if the variable has never been subject of previously calculated row activities */
938  assert((oldlb == SCIP_INVALID) == (oldub == SCIP_INVALID)); /*lint !e777*/
939  if( oldlb == SCIP_INVALID ) /*lint !e777*/
940  return SCIP_OKAY;
941 
942  newlb = SCIPvarGetLbLocal(var);
943  newub = SCIPvarGetUbLocal(var);
944 
945  /* skip update if the bound change events have cancelled out */
946  if( SCIPisFeasEQ(scip, oldlb, newlb) && SCIPisFeasEQ(scip, oldub, newub) )
947  return SCIP_OKAY;
948 
949  /* calculate old and new variable distribution mean and variance */
950  oldvariance = 0.0;
951  newvariance = 0.0;
952  oldmean = 0.0;
953  newmean = 0.0;
954  vartype = SCIPvarGetType(var);
955  SCIPvarCalcDistributionParameters(scip, oldlb, oldub, vartype, &oldmean, &oldvariance);
956  SCIPvarCalcDistributionParameters(scip, newlb, newub, vartype, &newmean, &newvariance);
957 
958  /* loop over all rows of this variable and update activity distribution */
959  for( r = 0; r < ncolrows; ++r )
960  {
961  int rowpos;
962 
963  assert(colrows[r] != NULL);
964  rowpos = SCIProwGetIndex(colrows[r]);
965  assert(rowpos >= 0);
966 
967  SCIP_CALL( branchruledataEnsureArraySize(scip, branchruledata, rowpos) );
968 
969  /* only consider rows for which activity distribution was already calculated */
970  if( branchruledata->rowmeans[rowpos] != SCIP_INVALID ) /*lint !e777*/
971  {
972  SCIP_Real coeff;
973  SCIP_Real coeffsquared;
974  assert(branchruledata->rowvariances[rowpos] != SCIP_INVALID
975  && SCIPisFeasGE(scip, branchruledata->rowvariances[rowpos], 0.0)); /*lint !e777*/
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(scip, 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  assert((branchruledata->currentlbs[varindex] == SCIP_INVALID) == (branchruledata->currentubs[varindex] == SCIP_INVALID)); /*lint !e777*/
1197  assert((branchruledata->currentlbs[varindex] == SCIP_INVALID)
1198  || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(lpcand), branchruledata->currentlbs[varindex])); /*lint !e777*/
1199  assert((branchruledata->currentubs[varindex] == SCIP_INVALID)
1200  || SCIPisFeasEQ(scip, SCIPvarGetUbLocal(lpcand), branchruledata->currentubs[varindex])); /*lint !e777*/
1201 
1202  /* if the branching rule has not captured the variable bounds yet, this can be done now */
1203  if( branchruledata->currentlbs[varindex] == SCIP_INVALID ) /*lint !e777*/
1204  {
1205  branchruledataUpdateCurrentBounds(scip, branchruledata, lpcand);
1206  }
1207 
1208  upscore = 0.0;
1209  downscore = 0.0;
1210 
1211  /* loop over candidate rows and determine the candidate up- and down- branching score w.r.t. the score parameter */
1212  SCIP_CALL( calcBranchScore(scip, branchruledata, lpcand, lpcandssol[c],
1213  &upscore, &downscore, branchruledata->scoreparam) );
1214 
1215  /* if weighted scoring is enabled, use the branching score method of SCIP to weigh up and down score */
1216  if( branchruledata->usescipscore )
1217  {
1218  SCIP_Real score;
1219 
1220  score = SCIPgetBranchScore(scip, lpcand, downscore, upscore);
1221 
1222  /* select the candidate with the highest branching score */
1223  if( score > bestscore )
1224  {
1225  bestscore = score;
1226  bestcand = lpcand;
1227  /* prioritize branching direction with the higher score */
1228  if( upscore > downscore )
1229  bestbranchdir = SCIP_BRANCHDIR_UPWARDS;
1230  else
1231  bestbranchdir = SCIP_BRANCHDIR_DOWNWARDS;
1232  }
1233  }
1234  else
1235  {
1236  /* no weighted score; keep candidate which has the single highest score in one direction */
1237  if( upscore > bestscore && upscore > downscore )
1238  {
1239  bestscore = upscore;
1240  bestbranchdir = SCIP_BRANCHDIR_UPWARDS;
1241  bestcand = lpcand;
1242  }
1243  else if( downscore > bestscore )
1244  {
1245  bestscore = downscore;
1246  bestbranchdir = SCIP_BRANCHDIR_DOWNWARDS;
1247  bestcand = lpcand;
1248  }
1249  }
1250 
1251  SCIPdebugMsg(scip, " Candidate %s has score down %g and up %g \n", SCIPvarGetName(lpcand), downscore, upscore);
1252  SCIPdebugMsg(scip, " Best candidate: %s, score %g, direction %d\n", SCIPvarGetName(bestcand), bestscore, bestbranchdir);
1253  }
1254  assert(!SCIPisFeasIntegral(scip, SCIPvarGetSol(bestcand, TRUE)));
1255  assert(bestbranchdir == SCIP_BRANCHDIR_DOWNWARDS || bestbranchdir == SCIP_BRANCHDIR_UPWARDS);
1256  assert(bestcand != NULL);
1257 
1258  SCIPdebugMsg(scip, " Branching on variable %s with bounds [%g, %g] and solution value <%g>\n", SCIPvarGetName(bestcand),
1259  SCIPvarGetLbLocal(bestcand), SCIPvarGetUbLocal(bestcand), SCIPvarGetLPSol(bestcand));
1260 
1261  /* branch on the best candidate variable */
1262  SCIP_CALL( SCIPbranchVar(scip, bestcand, &downchild, NULL, &upchild) );
1263 
1264  assert(downchild != NULL);
1265  assert(upchild != NULL);
1266 
1267  if( bestbranchdir == SCIP_BRANCHDIR_UPWARDS )
1268  {
1270  SCIPdebugMsg(scip, " Changing node priority of up-child.\n");
1271  }
1272  else
1273  {
1274  assert(bestbranchdir == SCIP_BRANCHDIR_DOWNWARDS);
1276  SCIPdebugMsg(scip, " Changing node priority of down-child.\n");
1277  }
1278 
1279  *result = SCIP_BRANCHED;
1280 
1281  return SCIP_OKAY;
1282 }
1283 
1284 /** event execution method of distribution branching which handles bound change events of variables */
1285 static
1286 SCIP_DECL_EVENTEXEC(eventExecDistribution)
1287 { /*lint --e{715}*/
1288  SCIP_BRANCHRULEDATA* branchruledata;
1289  SCIP_EVENTHDLRDATA* eventhdlrdata;
1290  SCIP_VAR* var;
1291 
1292  assert(eventhdlr != NULL);
1293  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
1294  assert(eventhdlrdata != NULL);
1295 
1296  branchruledata = eventhdlrdata->branchruledata;
1297  var = SCIPeventGetVar(event);
1298 
1299  /* add the variable to the queue of unprocessed variables; method itself ensures that every variable is added at most once */
1300  branchruledataAddBoundChangeVar(scip, branchruledata, var);
1301 
1302  return SCIP_OKAY;
1303 }
1304 
1305 
1306 /*
1307  * branching rule specific interface methods
1308  */
1309 
1310 /** creates the distribution branching rule and includes it in SCIP */
1312  SCIP* scip /**< SCIP data structure */
1313  )
1314 {
1315  SCIP_BRANCHRULE* branchrule = NULL;
1316  SCIP_BRANCHRULEDATA* branchruledata;
1317  SCIP_EVENTHDLRDATA* eventhdlrdata;
1318 
1319  /* create distribution branching rule data */
1320  branchruledata = NULL;
1321  SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
1322 
1323  branchruledata->memsize = 0;
1324  branchruledata->rowmeans = NULL;
1325  branchruledata->rowvariances = NULL;
1326  branchruledata->rowinfinitiesdown = NULL;
1327  branchruledata->rowinfinitiesup = NULL;
1328  branchruledata->varfilterposs = NULL;
1329  branchruledata->currentlbs = NULL;
1330  branchruledata->currentubs = NULL;
1331 
1332  /* create event handler first to finish branch rule data */
1333  eventhdlrdata = NULL;
1334  SCIP_CALL( SCIPallocBlockMemory(scip, &eventhdlrdata) );
1335  eventhdlrdata->branchruledata = branchruledata;
1336 
1337  branchruledata->eventhdlr = NULL;
1338  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &branchruledata->eventhdlr, EVENTHDLR_NAME,
1339  "event handler for dynamic acitivity distribution updating",
1340  eventExecDistribution, eventhdlrdata) );
1341  assert( branchruledata->eventhdlr != NULL);
1342  SCIP_CALL( SCIPsetEventhdlrFree(scip, branchruledata->eventhdlr, eventFreeDistribution) );
1343 
1344  /* include branching rule */
1346  BRANCHRULE_MAXBOUNDDIST, branchruledata) );
1347 
1348  assert(branchrule != NULL);
1349  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyDistribution) );
1350  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeDistribution) );
1351  SCIP_CALL( SCIPsetBranchruleExitsol(scip, branchrule, branchExitsolDistribution) );
1352  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpDistribution) );
1353 
1354  /* add distribution branching rule parameters */
1355  SCIP_CALL( SCIPaddCharParam(scip, "branching/" BRANCHRULE_NAME "/scoreparam",
1356  "the score;largest 'd'ifference, 'l'owest cumulative probability,'h'ighest c.p., 'v'otes lowest c.p., votes highest c.p.('w') ",
1357  &branchruledata->scoreparam, TRUE, DEFAULT_SCOREPARAM, SCOREPARAM_VALUES, NULL, NULL) );
1358 
1359  SCIP_CALL( SCIPaddBoolParam(scip, "branching/" BRANCHRULE_NAME "/onlyactiverows",
1360  "should only rows which are active at the current node be considered?",
1361  &branchruledata->onlyactiverows, TRUE, DEFAULT_ONLYACTIVEROWS, NULL, NULL) );
1362 
1363  SCIP_CALL( SCIPaddBoolParam(scip, "branching/" BRANCHRULE_NAME "/weightedscore",
1364  "should the branching score weigh up- and down-scores of a variable",
1365  &branchruledata->usescipscore, TRUE, DEFAULT_USEWEIGHTEDSCORE, NULL, NULL) );
1366 
1367  return SCIP_OKAY;
1368 }
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:384
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:116
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:105
void SCIPvarCalcDistributionParameters(SCIP *scip, SCIP_Real varlb, SCIP_Real varub, SCIP_VARTYPE vartype, SCIP_Real *mean, SCIP_Real *variance)
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1848
#define NULL
Definition: def.h:246
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:99
probability based branching rule based on an article by J. Pryor and J.W. Chinneck ...
SCIP_Real SCIPerf(SCIP_Real x)
Definition: misc.c:144
static SCIP_DECL_BRANCHFREE(branchFreeDistribution)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for SCIP parameter handling
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:411
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for memory management
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:422
static void branchruledataFreeArrays(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:16838
SCIP_Bool SCIPisSumPositive(SCIP *scip, SCIP_Real val)
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:16880
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17400
#define DEFAULT_USEWEIGHTEDSCORE
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:172
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:43
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17018
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
Definition: type_event.h:138
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetSol(SCIP_VAR *var, SCIP_Bool getlpval)
Definition: var.c:12741
#define BRANCHRULE_PRIORITY
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:158
#define SQRTOFTWO
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16959
static SCIP_DECL_BRANCHCOPY(branchCopyDistribution)
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip_pricer.c:418
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:71
#define SCIPdebug(x)
Definition: pub_message.h:74
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:142
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17037
static void branchruledataAddBoundChangeVar(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var)
#define EVENTHDLR_NAME
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
public methods for branching rules
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:105
static void branchruledataUpdateCurrentBounds(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var)
#define DEFAULT_SCOREPARAM
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
#define SCIPdebugMsg
Definition: scip_message.h:88
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
public methods for numerical tolerances
SCIP_RETCODE SCIPchgChildPrio(SCIP *scip, SCIP_NODE *child, SCIP_Real priority)
Definition: scip_prob.c:3844
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:238
void SCIPeventhdlrSetData(SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: event.c:334
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip_branch.c:838
#define BRANCHRULE_MAXBOUNDDIST
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:39
#define SCOREPARAM_VALUES
#define EVENT_DISTRIBUTION
static SCIP_VAR * branchruledataPopBoundChangeVar(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata)
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:992
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_RETCODE SCIPsetEventhdlrFree(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTFREE((*eventfree)))
Definition: scip_event.c:218
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:16828
SCIP_Real SCIPcalcCumulativeDistribution(SCIP *scip, SCIP_Real mean, SCIP_Real variance, SCIP_Real value)
public methods for event handler plugins and event handlers
SCIPInterval sqrt(const SCIPInterval &x)
Definition: pqueue.h:28
static SCIP_RETCODE branchruledataEnsureArraySize(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, int maxindex)
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16730
#define BRANCHRULE_DESC
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:17718
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:629
#define SCIP_CALL(x)
Definition: def.h:358
static SCIP_DECL_BRANCHEXECLP(branchExeclpDistribution)
static SCIP_RETCODE calcBranchScore(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var, SCIP_Real lpsolval, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16969
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:16905
#define SQUARED(x)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:16915
public data structures and miscellaneous methods
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
Definition: event.c:1018
#define SCIP_Bool
Definition: def.h:69
SCIP_Real SCIProwCalcProbability(SCIP *scip, SCIP_ROW *row, SCIP_Real mu, SCIP_Real sigma2, int rowinfinitiesdown, int rowinfinitiesup)
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1858
#define MIN(x, y)
Definition: def.h:216
public methods for LP management
#define DEFAULT_PRIORITY
SCIP_RETCODE SCIPsetBranchruleExitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXITSOL((*branchexitsol)))
Definition: scip_branch.c:222
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:468
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17058
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE varProcessBoundChanges(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var)
static SCIP_DECL_BRANCHEXITSOL(branchExitsolDistribution)
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:152
public methods for the LP relaxation, rows and columns
public methods for variable pricer plugins
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:2044
SCIP_Real * r
Definition: circlepacking.c:50
#define BRANCHRULE_MAXDEPTH
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:16925
public methods for branching rule plugins and branching
public methods for managing events
general public methods
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:16803
#define MAX(x, y)
Definition: def.h:215
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
#define DEFAULT_ONLYACTIVEROWS
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:239
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16729
public methods for the probing mode
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
SCIP_Real SCIPgetRowLPFeasibility(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1916
static SCIP_DECL_EVENTEXEC(eventExecDistribution)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1999
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16849
#define SCIP_Real
Definition: def.h:157
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1970
public methods for message handling
SCIP_RETCODE SCIPupdateDistributionScore(SCIP *scip, SCIP_Real currentprob, SCIP_Real newprobup, SCIP_Real newprobdown, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam)
#define SCIP_INVALID
Definition: def.h:177
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2099
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16895
int SCIProwGetIndex(SCIP_ROW *row)
Definition: lp.c:17028
enum SCIP_Vartype SCIP_VARTYPE
Definition: type_var.h:60
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17410
#define BRANCHRULE_NAME
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:324
public methods for global and local (sub)problems
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:129
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17017
SCIP_RETCODE SCIPincludeBranchruleDistribution(SCIP *scip)