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