Scippy

SCIP

Solving Constraint Integer Programs

heur_distributiondiving.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2018 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_distributiondiving.c
17  * @brief Diving heuristic that chooses fixings w.r.t. changes in the solution density after Pryor and Chinneck.
18  * @author Gregor Hendel
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include "blockmemshell/memory.h"
26 #include "scip/heuristics.h"
27 #include "scip/pub_event.h"
28 #include "scip/pub_heur.h"
29 #include "scip/pub_lp.h"
30 #include "scip/pub_message.h"
31 #include "scip/pub_var.h"
32 #include "scip/scip_event.h"
33 #include "scip/scip_general.h"
34 #include "scip/scip_heur.h"
35 #include "scip/scip_lp.h"
36 #include "scip/scip_mem.h"
37 #include "scip/scip_message.h"
38 #include "scip/scip_numerics.h"
39 #include "scip/scip_param.h"
40 #include "scip/scip_prob.h"
41 #include "scip/scip_probing.h"
42 #include "scip/scip_sol.h"
43 #include <string.h>
44 
45 #define HEUR_NAME "distributiondiving"
46 #define HEUR_DESC "Diving heuristic that chooses fixings w.r.t. changes in the solution density"
47 #define HEUR_DISPCHAR 'e'
48 #define HEUR_PRIORITY -1003300
49 #define HEUR_FREQ 10
50 #define HEUR_FREQOFS 3
51 #define HEUR_MAXDEPTH -1
52 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
53 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
54 #define EVENT_DISTRIBUTION SCIP_EVENTTYPE_BOUNDCHANGED /**< the event type to be handled by this event handler */
55 #define EVENTHDLR_NAME "eventhdlr_distributiondiving"
56 #define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY /**< bit mask that represents all supported dive types */
57 
58 #define SQUARED(x) ((x) * (x))
59 /*
60  * Default parameter settings
61  */
62 
63 #define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */
64 #define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */
65 #define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
66 #define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */
67 #define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
68  * where diving is performed (0.0: no limit) */
69 #define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
70  * where diving is performed (0.0: no limit) */
71 #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
72 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
73 #define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
74 #define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */
75 #define DEFAULT_LPSOLVEFREQ 0 /**< LP solve frequency for diving heuristics */
76 #define DEFAULT_ONLYLPBRANCHCANDS TRUE /**< should only LP branching candidates be considered instead of the slower but
77  * more general constraint handler diving variable selection? */
78 
79 #define SCOREPARAM_VALUES "lhwvd" /**< the score;largest 'd'ifference, 'l'owest cumulative probability,'h'ighest c.p.,
80  * 'v'otes lowest c.p., votes highest c.p.('w'), 'r'evolving */
81 #define SCOREPARAM_VALUESLEN 5
82 #define DEFAULT_SCOREPARAM 'r' /**< default scoring parameter to guide the diving */
83 #define DEFAULT_RANDSEED 117 /**< initial seed for random number generation */
84 
85 /* locally defined heuristic data */
86 struct SCIP_HeurData
87 {
88  SCIP_SOL* sol; /**< working solution */
89  SCIP_EVENTHDLR* eventhdlr; /**< event handler pointer */
90  SCIP_VAR** updatedvars; /**< variables to process bound change events for */
91  SCIP_Real* rowmeans; /**< row activity mean values for all rows */
92  SCIP_Real* rowvariances; /**< row activity variances for all rows */
93  SCIP_Real* currentubs; /**< variable upper bounds as currently saved in the row activities */
94  SCIP_Real* currentlbs; /**< variable lower bounds as currently saved in the row activities */
95  int* rowinfinitiesdown; /**< count the number of variables with infinite bounds which allow for always
96  * repairing the constraint right hand side */
97  int* rowinfinitiesup; /**< count the number of variables with infinite bounds which allow for always
98  * repairing the constraint left hand side */
99  int* varposs; /**< array of variable positions in the updated variables array */
100  int* varfilterposs; /**< array of event filter positions for variable events */
101  int nupdatedvars; /**< the current number of variables with pending bound changes */
102  int memsize; /**< memory size of current arrays, needed for dynamic reallocation */
103  int varpossmemsize; /**< memory size of updated vars and varposs array */
104 
105  char scoreparam; /**< score user parameter */
106  char score; /**< score to be used depending on user parameter to use fixed score or revolve */
107 };
108 
109 struct SCIP_EventhdlrData
110 {
111  SCIP_HEURDATA* heurdata; /**< the heuristic data to access distribution arrays */
112 };
113 /*
114  * local methods
115  */
116 
117 /** ensure that maxindex + 1 rows can be represented in data arrays; memory gets reallocated with 10% extra space
118  * to save some time for future allocations */
119 static
121  SCIP* scip, /**< SCIP data structure */
122  SCIP_HEURDATA* heurdata, /**< heuristic data */
123  int maxindex /**< row index at hand (size must be at least this large) */
124  )
125 {
126  int newsize;
127  int r;
128 
129  /* maxindex fits in current array -> nothing to do */
130  if( maxindex < heurdata->memsize )
131  return SCIP_OKAY;
132 
133  /* new memory size is the max index + 1 plus 10% additional space */
134  newsize = (int)SCIPfeasCeil(scip, (maxindex + 1) * 1.1);
135  assert(newsize > heurdata->memsize);
136  assert(heurdata->memsize >= 0);
137 
138  /* alloc memory arrays for row information */
139  if( heurdata->memsize == 0 )
140  {
141  SCIP_VAR** vars;
142  int v;
143  int nvars;
144 
145  SCIP_CALL( SCIPallocBufferArray(scip, &heurdata->rowinfinitiesdown, newsize) );
146  SCIP_CALL( SCIPallocBufferArray(scip, &heurdata->rowinfinitiesup, newsize) );
147  SCIP_CALL( SCIPallocBufferArray(scip, &heurdata->rowmeans, newsize) );
148  SCIP_CALL( SCIPallocBufferArray(scip, &heurdata->rowvariances, newsize) );
149 
150  assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING);
151 
152  vars = SCIPgetVars(scip);
153  nvars = SCIPgetNVars(scip);
154 
155  assert(nvars > 0);
156 
157  /* allocate variable update event processing array storage */
158  SCIP_CALL( SCIPallocBufferArray(scip, &heurdata->varfilterposs, nvars) );
159  SCIP_CALL( SCIPallocBufferArray(scip, &heurdata->varposs, nvars) );
160  SCIP_CALL( SCIPallocBufferArray(scip, &heurdata->updatedvars, nvars) );
161  SCIP_CALL( SCIPallocBufferArray(scip, &heurdata->currentubs, nvars) );
162  SCIP_CALL( SCIPallocBufferArray(scip, &heurdata->currentlbs, nvars) );
163 
164  heurdata->varpossmemsize = nvars;
165  heurdata->nupdatedvars = 0;
166 
167  /* init variable event processing data */
168  for( v = 0; v < nvars; ++v )
169  {
170  assert(SCIPvarIsActive(vars[v]));
171  assert(SCIPvarGetProbindex(vars[v]) == v);
172 
173  /* set up variable events to catch bound changes */
174  SCIP_CALL( SCIPcatchVarEvent(scip, vars[v], EVENT_DISTRIBUTION, heurdata->eventhdlr, NULL, &(heurdata->varfilterposs[v])) );
175  assert(heurdata->varfilterposs[v] >= 0);
176 
177  heurdata->varposs[v] = -1;
178  heurdata->updatedvars[v] = NULL;
179  heurdata->currentlbs[v] = SCIP_INVALID;
180  heurdata->currentubs[v] = SCIP_INVALID;
181  }
182  }
183  else
184  {
185  SCIP_CALL( SCIPreallocBufferArray(scip, &heurdata->rowinfinitiesdown, newsize) );
186  SCIP_CALL( SCIPreallocBufferArray(scip, &heurdata->rowinfinitiesup, newsize) );
187  SCIP_CALL( SCIPreallocBufferArray(scip, &heurdata->rowmeans, newsize) );
188  SCIP_CALL( SCIPreallocBufferArray(scip, &heurdata->rowvariances, newsize) );
189  }
190 
191  /* loop over extended arrays and invalidate data to trigger initialization of this row when necessary */
192  for( r = heurdata->memsize; r < newsize; ++r )
193  {
194  heurdata->rowmeans[r] = SCIP_INVALID;
195  heurdata->rowvariances[r] = SCIP_INVALID;
196  heurdata->rowinfinitiesdown[r] = 0;
197  heurdata->rowinfinitiesup[r] = 0;
198  }
199 
200  /* adjust memsize */
201  heurdata->memsize = newsize;
202 
203  return SCIP_OKAY;
204 }
205 
206 /** update the variables current lower and upper bound */
207 static
209  SCIP* scip, /**< SCIP data structure */
210  SCIP_HEURDATA* heurdata, /**< heuristic data */
211  SCIP_VAR* var /**< the variable to update current bounds */
212  )
213 {
214  int varindex;
215  SCIP_Real lblocal;
216  SCIP_Real ublocal;
217 
218  assert(var != NULL);
219 
220  varindex = SCIPvarGetProbindex(var);
221  assert(0 <= varindex && varindex < heurdata->varpossmemsize);
222  lblocal = SCIPvarGetLbLocal(var);
223  ublocal = SCIPvarGetUbLocal(var);
224 
225  assert(SCIPisFeasLE(scip, lblocal, ublocal));
226 
227  heurdata->currentlbs[varindex] = lblocal;
228  heurdata->currentubs[varindex] = ublocal;
229 }
230 
231 /** calculates the initial mean and variance of the row activity normal distribution.
232  *
233  * The mean value \f$ \mu \f$ is given by \f$ \mu = \sum_i=1^n c_i * (lb_i +ub_i) / 2 \f$ where
234  * \f$n \f$ is the number of variables, and \f$ c_i, lb_i, ub_i \f$ are the variable coefficient and
235  * bounds, respectively. With the same notation, the variance \f$ \sigma^2 \f$ is given by
236  * \f$ \sigma^2 = \sum_i=1^n c_i^2 * \sigma^2_i \f$, with the variance being
237  * \f$ \sigma^2_i = ((ub_i - lb_i + 1)^2 - 1) / 12 \f$ for integer variables and
238  * \f$ \sigma^2_i = (ub_i - lb_i)^2 / 12 \f$ for continuous variables.
239  */
240 static
241 void rowCalculateGauss(
242  SCIP* scip, /**< SCIP data structure */
243  SCIP_HEURDATA* heurdata, /**< the heuristic rule data */
244  SCIP_ROW* row, /**< the row for which the gaussian normal distribution has to be calculated */
245  SCIP_Real* mu, /**< pointer to store the mean value of the gaussian normal distribution */
246  SCIP_Real* sigma2, /**< pointer to store the variance value of the gaussian normal distribution */
247  int* rowinfinitiesdown, /**< pointer to store the number of variables with infinite bounds to DECREASE activity */
248  int* rowinfinitiesup /**< pointer to store the number of variables with infinite bounds to INCREASE activity */
249  )
250 {
251  SCIP_COL** rowcols;
252  SCIP_Real* rowvals;
253  int nrowvals;
254  int c;
255 
256  assert(scip != NULL);
257  assert(row != NULL);
258  assert(mu != NULL);
259  assert(sigma2 != NULL);
260  assert(rowinfinitiesup != NULL);
261  assert(rowinfinitiesdown != NULL);
262 
263  rowcols = SCIProwGetCols(row);
264  rowvals = SCIProwGetVals(row);
265  nrowvals = SCIProwGetNNonz(row);
266 
267  assert(nrowvals == 0 || rowcols != NULL);
268  assert(nrowvals == 0 || rowvals != NULL);
269 
270  *mu = SCIProwGetConstant(row);
271  *sigma2 = 0.0;
272  *rowinfinitiesdown = 0;
273  *rowinfinitiesup = 0;
274 
275  /* loop over nonzero row coefficients and sum up the variable contributions to mu and sigma2 */
276  for( c = 0; c < nrowvals; ++c )
277  {
278  SCIP_VAR* colvar;
279  SCIP_Real colval;
280  SCIP_Real colvarlb;
281  SCIP_Real colvarub;
282  SCIP_Real squarecoeff;
283  SCIP_Real varvariance;
284  SCIP_Real varmean;
285  int varindex;
286 
287  assert(rowcols[c] != NULL);
288  colvar = SCIPcolGetVar(rowcols[c]);
289  assert(colvar != NULL);
290 
291  colval = rowvals[c];
292  colvarlb = SCIPvarGetLbLocal(colvar);
293  colvarub = SCIPvarGetUbLocal(colvar);
294 
295  varmean = 0.0;
296  varvariance = 0.0;
297  varindex = SCIPvarGetProbindex(colvar);
298  assert((heurdata->currentlbs[varindex] == SCIP_INVALID)
299  == (heurdata->currentubs[varindex] == SCIP_INVALID)); /*lint !e777 doesn't like comparing floats for equality */
300 
301  /* variable bounds need to be watched from now on */
302  if( heurdata->currentlbs[varindex] == SCIP_INVALID ) /*lint !e777 doesn't like comparing floats for equality */
303  heurdataUpdateCurrentBounds(scip, heurdata, colvar);
304 
305  assert(!SCIPisInfinity(scip, colvarlb));
306  assert(!SCIPisInfinity(scip, -colvarub));
307  assert(SCIPisFeasLE(scip, colvarlb, colvarub));
308 
309  /* variables with infinite bounds are skipped for the calculation of the variance; they need to
310  * be accounted for by the counters for infinite row activity decrease and increase and they
311  * are used to shift the row activity mean in case they have one nonzero, but finite bound */
312  if( SCIPisInfinity(scip, -colvarlb) || SCIPisInfinity(scip, colvarub) )
313  {
314  if( SCIPisInfinity(scip, colvarub) )
315  {
316  /* an infinite upper bound gives the row an infinite maximum activity or minimum activity, if the coefficient is
317  * positive or negative, resp.
318  */
319  if( colval < 0.0 )
320  ++(*rowinfinitiesdown);
321  else
322  ++(*rowinfinitiesup);
323  }
324 
325  /* an infinite lower bound gives the row an infinite maximum activity or minimum activity, if the coefficient is
326  * negative or positive, resp.
327  */
328  if( SCIPisInfinity(scip, -colvarlb) )
329  {
330  if( colval > 0.0 )
331  ++(*rowinfinitiesdown);
332  else
333  ++(*rowinfinitiesup);
334  }
335  }
336  SCIPvarCalcDistributionParameters(scip, colvarlb, colvarub, SCIPvarGetType(colvar), &varmean, &varvariance);
337 
338  /* actual values are updated; the contribution of the variable to mu is the arithmetic mean of its bounds */
339  *mu += colval * varmean;
340 
341  /* 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 */
342  squarecoeff = SQUARED(colval);
343  *sigma2 += squarecoeff * varvariance;
344 
345  assert(!SCIPisFeasNegative(scip, *sigma2));
346  }
347 
348  SCIPdebug( SCIPprintRow(scip, row, NULL) );
349  SCIPdebugMsg(scip, " Row %s has a mean value of %g at a sigma2 of %g \n", SCIProwGetName(row), *mu, *sigma2);
350 }
351 
352 /** calculate the branching score of a variable, depending on the chosen score parameter */
353 static
355  SCIP* scip, /**< current SCIP */
356  SCIP_HEURDATA* heurdata, /**< branch rule data */
357  SCIP_VAR* var, /**< candidate variable */
358  SCIP_Real lpsolval, /**< current fractional LP-relaxation solution value */
359  SCIP_Real* upscore, /**< pointer to store the variable score when branching on it in upward direction */
360  SCIP_Real* downscore, /**< pointer to store the variable score when branching on it in downward direction */
361  char scoreparam /**< the score parameter of this heuristic */
362  )
363 {
364  SCIP_COL* varcol;
365  SCIP_ROW** colrows;
366  SCIP_Real* rowvals;
367  SCIP_Real varlb;
368  SCIP_Real varub;
369  SCIP_Real squaredbounddiff; /* current squared difference of variable bounds (ub - lb)^2 */
370  SCIP_Real newub; /* new upper bound if branching downwards */
371  SCIP_Real newlb; /* new lower bound if branching upwards */
372  SCIP_Real squaredbounddiffup; /* squared difference after branching upwards (ub - lb')^2 */
373  SCIP_Real squaredbounddiffdown; /* squared difference after branching downwards (ub' - lb)^2 */
374  SCIP_Real currentmean; /* current mean value of variable uniform distribution */
375  SCIP_Real meanup; /* mean value of variable uniform distribution after branching up */
376  SCIP_Real meandown; /* mean value of variable uniform distribution after branching down*/
377  SCIP_VARTYPE vartype;
378  int ncolrows;
379  int i;
380 
381  SCIP_Bool onlyactiverows; /* should only rows which are active at the current node be considered? */
382 
383  assert(scip != NULL);
384  assert(var != NULL);
385  assert(upscore != NULL);
386  assert(downscore != NULL);
387  assert(!SCIPisIntegral(scip, lpsolval) || SCIPvarIsBinary(var));
388  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
389 
390  varcol = SCIPvarGetCol(var);
391  assert(varcol != NULL);
392 
393  colrows = SCIPcolGetRows(varcol);
394  rowvals = SCIPcolGetVals(varcol);
395  ncolrows = SCIPcolGetNNonz(varcol);
396  varlb = SCIPvarGetLbLocal(var);
397  varub = SCIPvarGetUbLocal(var);
398  assert(varub - varlb > 0.5);
399  vartype = SCIPvarGetType(var);
400 
401  /* calculate mean and variance of variable uniform distribution before and after branching */
402  currentmean = 0.0;
403  squaredbounddiff = 0.0;
404  SCIPvarCalcDistributionParameters(scip, varlb, varub, vartype, &currentmean, &squaredbounddiff);
405 
406  /* unfixed binary variables may have an integer solution value in the LP solution, eg, at the presence of indicator constraints */
407  if( !SCIPvarIsBinary(var) )
408  {
409  newlb = SCIPfeasCeil(scip, lpsolval);
410  newub = SCIPfeasFloor(scip, lpsolval);
411  }
412  else
413  {
414  newlb = 1.0;
415  newub = 0.0;
416  }
417 
418  /* calculate the variable's uniform distribution after branching up and down, respectively. */
419  squaredbounddiffup = 0.0;
420  meanup = 0.0;
421  SCIPvarCalcDistributionParameters(scip, newlb, varub, vartype, &meanup, &squaredbounddiffup);
422 
423  /* calculate the distribution mean and variance for a variable with finite lower bound */
424  squaredbounddiffdown = 0.0;
425  meandown = 0.0;
426  SCIPvarCalcDistributionParameters(scip, varlb, newub, vartype, &meandown, &squaredbounddiffdown);
427 
428  /* initialize the variable's up and down score */
429  *upscore = 0.0;
430  *downscore = 0.0;
431 
432  onlyactiverows = FALSE;
433 
434  /* loop over the variable rows and calculate the up and down score */
435  for( i = 0; i < ncolrows; ++i )
436  {
437  SCIP_ROW* row;
438  SCIP_Real changedrowmean;
439  SCIP_Real rowmean;
440  SCIP_Real rowvariance;
441  SCIP_Real changedrowvariance;
442  SCIP_Real currentrowprob;
443  SCIP_Real newrowprobup;
444  SCIP_Real newrowprobdown;
445  SCIP_Real squaredcoeff;
446  SCIP_Real rowval;
447  int rowinfinitiesdown;
448  int rowinfinitiesup;
449  int rowpos;
450 
451  row = colrows[i];
452  rowval = rowvals[i];
453  assert(row != NULL);
454 
455  /* we access the rows by their index */
456  rowpos = SCIProwGetIndex(row);
457 
458  /* skip non-active rows if the user parameter was set this way */
459  if( onlyactiverows && SCIPisSumPositive(scip, SCIPgetRowLPFeasibility(scip, row)) )
460  continue;
461 
462  /* call method to ensure sufficient data capacity */
463  SCIP_CALL( heurdataEnsureArraySize(scip, heurdata, rowpos) );
464 
465  /* calculate row activity distribution if this is the first candidate to appear in this row */
466  if( heurdata->rowmeans[rowpos] == SCIP_INVALID ) /*lint !e777 doesn't like comparing floats for equality */
467  {
468  rowCalculateGauss(scip, heurdata, row, &heurdata->rowmeans[rowpos], &heurdata->rowvariances[rowpos],
469  &heurdata->rowinfinitiesdown[rowpos], &heurdata->rowinfinitiesup[rowpos]);
470  }
471 
472  /* retrieve the row distribution parameters from the branch rule data */
473  rowmean = heurdata->rowmeans[rowpos];
474  rowvariance = heurdata->rowvariances[rowpos];
475  rowinfinitiesdown = heurdata->rowinfinitiesdown[rowpos];
476  rowinfinitiesup = heurdata->rowinfinitiesup[rowpos];
477  assert(!SCIPisNegative(scip, rowvariance));
478 
479  currentrowprob = SCIProwCalcProbability(scip, row, rowmean, rowvariance,
480  rowinfinitiesdown, rowinfinitiesup);
481 
482  /* get variable's current expected contribution to row activity */
483  squaredcoeff = SQUARED(rowval);
484 
485  /* first, get the probability change for the row if the variable is branched on upwards. The probability
486  * can only be affected if the variable upper bound is finite
487  */
488  if( !SCIPisInfinity(scip, varub) )
489  {
490  int rowinftiesdownafterbranch;
491  int rowinftiesupafterbranch;
492 
493  /* calculate how branching would affect the row parameters */
494  changedrowmean = rowmean + rowval * (meanup - currentmean);
495  changedrowvariance = rowvariance + squaredcoeff * (squaredbounddiffup - squaredbounddiff);
496  changedrowvariance = MAX(0.0, changedrowvariance);
497 
498  rowinftiesdownafterbranch = rowinfinitiesdown;
499  rowinftiesupafterbranch = rowinfinitiesup;
500 
501  /* account for changes of the row's infinite bound contributions */
502  if( SCIPisInfinity(scip, -varlb) && rowval < 0.0 )
503  rowinftiesupafterbranch--;
504  if( SCIPisInfinity(scip, -varlb) && rowval > 0.0 )
505  rowinftiesdownafterbranch--;
506 
507  assert(rowinftiesupafterbranch >= 0);
508  assert(rowinftiesdownafterbranch >= 0);
509  newrowprobup = SCIProwCalcProbability(scip, row, changedrowmean, changedrowvariance, rowinftiesdownafterbranch,
510  rowinftiesupafterbranch);
511  }
512  else
513  newrowprobup = currentrowprob;
514 
515  /* do the same for the other branching direction */
516  if( !SCIPisInfinity(scip, varlb) )
517  {
518  int rowinftiesdownafterbranch;
519  int rowinftiesupafterbranch;
520 
521  changedrowmean = rowmean + rowval * (meandown - currentmean);
522  changedrowvariance = rowvariance + squaredcoeff * (squaredbounddiffdown - squaredbounddiff);
523  changedrowvariance = MAX(0.0, changedrowvariance);
524 
525  rowinftiesdownafterbranch = rowinfinitiesdown;
526  rowinftiesupafterbranch = rowinfinitiesup;
527 
528  /* account for changes of the row's infinite bound contributions */
529  if( SCIPisInfinity(scip, varub) && rowval > 0.0 )
530  rowinftiesupafterbranch -= 1;
531  if( SCIPisInfinity(scip, varub) && rowval < 0.0 )
532  rowinftiesdownafterbranch -= 1;
533 
534  assert(rowinftiesdownafterbranch >= 0);
535  assert(rowinftiesupafterbranch >= 0);
536  newrowprobdown = SCIProwCalcProbability(scip, row, changedrowmean, changedrowvariance, rowinftiesdownafterbranch,
537  rowinftiesupafterbranch);
538  }
539  else
540  newrowprobdown = currentrowprob;
541 
542  /* update the up and down score depending on the chosen scoring parameter */
543  SCIP_CALL( SCIPupdateDistributionScore(scip, currentrowprob, newrowprobup, newrowprobdown, upscore, downscore, scoreparam) );
544 
545  SCIPdebugMsg(scip, " Variable %s changes probability of row %s from %g to %g (branch up) or %g;\n",
546  SCIPvarGetName(var), SCIProwGetName(row), currentrowprob, newrowprobup, newrowprobdown);
547  SCIPdebugMsg(scip, " --> new variable score: %g (for branching up), %g (for branching down)\n",
548  *upscore, *downscore);
549  }
550 
551  return SCIP_OKAY;
552 }
553 
554 /** free heuristic data */
555 static
557  SCIP* scip, /**< SCIP data structure */
558  SCIP_HEURDATA* heurdata /**< heuristic data */
559  )
560 {
561  assert(heurdata->memsize == 0 || heurdata->rowmeans != NULL);
562  assert(heurdata->memsize >= 0);
563 
564  if( heurdata->varpossmemsize > 0 )
565  {
566  SCIP_VAR** vars;
567  int v;
568 
569  assert(heurdata->varpossmemsize == SCIPgetNVars(scip));
570 
571  vars = SCIPgetVars(scip);
572  for( v = heurdata->varpossmemsize - 1; v >= 0; --v )
573  {
574  SCIP_VAR* var;
575 
576  var = vars[v];
577 
578  assert(var != NULL);
579  assert(v == SCIPvarGetProbindex(var));
580  SCIP_CALL( SCIPdropVarEvent(scip, var, EVENT_DISTRIBUTION, heurdata->eventhdlr, NULL, heurdata->varfilterposs[v]) );
581  }
582  SCIPfreeBufferArray(scip, &heurdata->currentlbs);
583  SCIPfreeBufferArray(scip, &heurdata->currentubs);
584  SCIPfreeBufferArray(scip, &heurdata->updatedvars);
585  SCIPfreeBufferArray(scip, &heurdata->varposs);
586  SCIPfreeBufferArray(scip, &heurdata->varfilterposs);
587  }
588 
589  if( heurdata->memsize > 0 )
590  {
591  SCIPfreeBufferArray(scip, &heurdata->rowvariances);
592  SCIPfreeBufferArray(scip, &heurdata->rowmeans);
593  SCIPfreeBufferArray(scip, &heurdata->rowinfinitiesup);
594  SCIPfreeBufferArray(scip, &heurdata->rowinfinitiesdown);
595 
596  heurdata->memsize = 0;
597  }
598 
599  heurdata->varpossmemsize = 0;
600  heurdata->nupdatedvars = 0;
601 
602  return SCIP_OKAY;
603 }
604 
605 /** add variable to the bound change event queue; skipped if variable is already in there, or if variable has
606  * no row currently watched
607  */
608 static
610  SCIP* scip, /**< SCIP data structure */
611  SCIP_HEURDATA* heurdata, /**< heuristic data */
612  SCIP_VAR* var /**< the variable whose bound changes need to be processed */
613  )
614 {
615  int varindex;
616  int varpos;
617 
618  assert(var != NULL);
619 
620  varindex = SCIPvarGetProbindex(var);
621  assert(-1 <= varindex && varindex < heurdata->varpossmemsize);
622 
623  /* if variable is not active, it should not be watched */
624  if( varindex == -1 )
625  return;
626  varpos = heurdata->varposs[varindex];
627  assert(varpos < heurdata->nupdatedvars);
628 
629  /* nothing to do if variable is already in the queue */
630  if( varpos >= 0 )
631  {
632  assert(heurdata->updatedvars[varpos] == var);
633 
634  return;
635  }
636 
637  /* if none of the variables rows was calculated yet, variable needs not to be watched */
638  assert((heurdata->currentlbs[varindex] == SCIP_INVALID)
639  == (heurdata->currentubs[varindex] == SCIP_INVALID)); /*lint !e777 doesn't like comparing floats for equality */
640 
641  /* we don't need to enqueue the variable if it hasn't been watched so far */
642  if( heurdata->currentlbs[varindex] == SCIP_INVALID ) /*lint !e777 see above */
643  return;
644 
645  /* add the variable to the heuristic data of variables to process updates for */
646  assert(heurdata->varpossmemsize > heurdata->nupdatedvars);
647  varpos = heurdata->nupdatedvars;
648  heurdata->updatedvars[varpos] = var;
649  heurdata->varposs[varindex] = varpos;
650  ++heurdata->nupdatedvars;
651 }
652 
653 /** returns the next unprocessed variable (last in, first out) with pending bound changes, or NULL */
654 static
656  SCIP* scip, /**< SCIP data structure */
657  SCIP_HEURDATA* heurdata /**< heuristic data */
658  )
659 {
660  SCIP_VAR* var;
661  int varpos;
662  int varindex;
663 
664  assert(heurdata->nupdatedvars >= 0);
665 
666  /* return if no variable is currently pending */
667  if( heurdata->nupdatedvars == 0 )
668  return NULL;
669 
670  varpos = heurdata->nupdatedvars - 1;
671  var = heurdata->updatedvars[varpos];
672  assert(var != NULL);
673  varindex = SCIPvarGetProbindex(var);
674  assert(0 <= varindex && varindex < heurdata->varpossmemsize);
675  assert(varpos == heurdata->varposs[varindex]);
676 
677  heurdata->varposs[varindex] = -1;
678  heurdata->nupdatedvars--;
679 
680  return var;
681 }
682 
683 /** process a variable from the queue of changed variables */
684 static
686  SCIP* scip, /**< SCIP data structure */
687  SCIP_HEURDATA* heurdata, /**< heuristic data */
688  SCIP_VAR* var /**< the variable whose bound changes need to be processed */
689  )
690 {
691  SCIP_ROW** colrows;
692  SCIP_COL* varcol;
693  SCIP_Real* colvals;
694  SCIP_Real oldmean;
695  SCIP_Real newmean;
696  SCIP_Real oldvariance;
697  SCIP_Real newvariance;
698  SCIP_Real oldlb;
699  SCIP_Real newlb;
700  SCIP_Real oldub;
701  SCIP_Real newub;
702  SCIP_VARTYPE vartype;
703  int ncolrows;
704  int r;
705  int varindex;
706 
707  /* ensure that this is a probing bound change */
708  assert(SCIPinProbing(scip));
709 
710  assert(var != NULL);
711  varcol = SCIPvarGetCol(var);
712  assert(varcol != NULL);
713  colrows = SCIPcolGetRows(varcol);
714  colvals = SCIPcolGetVals(varcol);
715  ncolrows = SCIPcolGetNNonz(varcol);
716 
717  varindex = SCIPvarGetProbindex(var);
718 
719  oldlb = heurdata->currentlbs[varindex];
720  oldub = heurdata->currentubs[varindex];
721 
722  /* skip update if the variable has never been subject of previously calculated row activities */
723  assert((oldlb == SCIP_INVALID) == (oldub == SCIP_INVALID)); /*lint !e777 doesn't like comparing floats for equality */
724  if( oldlb == SCIP_INVALID ) /*lint !e777 */
725  return SCIP_OKAY;
726 
727  newlb = SCIPvarGetLbLocal(var);
728  newub = SCIPvarGetUbLocal(var);
729 
730  /* skip update if the bound change events have cancelled out */
731  if( SCIPisFeasEQ(scip, oldlb, newlb) && SCIPisFeasEQ(scip, oldub, newub) )
732  return SCIP_OKAY;
733 
734  /* calculate old and new variable distribution mean and variance */
735  oldvariance = 0.0;
736  newvariance = 0.0;
737  oldmean = 0.0;
738  newmean = 0.0;
739  vartype = SCIPvarGetType(var);
740  SCIPvarCalcDistributionParameters(scip, oldlb, oldub, vartype, &oldmean, &oldvariance);
741  SCIPvarCalcDistributionParameters(scip, newlb, newub, vartype, &newmean, &newvariance);
742 
743  /* loop over all rows of this variable and update activity distribution */
744  for( r = 0; r < ncolrows; ++r )
745  {
746  int rowpos;
747 
748  assert(colrows[r] != NULL);
749  rowpos = SCIProwGetIndex(colrows[r]);
750  assert(rowpos >= 0);
751 
752  SCIP_CALL( heurdataEnsureArraySize(scip, heurdata, rowpos) );
753 
754  /* only consider rows for which activity distribution was already calculated */
755  if( heurdata->rowmeans[rowpos] != SCIP_INVALID ) /*lint !e777 doesn't like comparing floats for equality */
756  {
757  SCIP_Real coeff;
758  SCIP_Real coeffsquared;
759  assert(heurdata->rowvariances[rowpos] != SCIP_INVALID
760  && SCIPisFeasGE(scip, heurdata->rowvariances[rowpos], 0.0)); /*lint !e777 */
761 
762  coeff = colvals[r];
763  coeffsquared = SQUARED(coeff);
764 
765  /* update variable contribution to row activity distribution */
766  heurdata->rowmeans[rowpos] += coeff * (newmean - oldmean);
767  heurdata->rowvariances[rowpos] += coeffsquared * (newvariance - oldvariance);
768  heurdata->rowvariances[rowpos] = MAX(0.0, heurdata->rowvariances[rowpos]);
769 
770  /* account for changes of the infinite contributions to row activities */
771  if( coeff > 0.0 )
772  {
773  /* if the coefficient is positive, upper bounds affect activity up */
774  if( SCIPisInfinity(scip, newub) && !SCIPisInfinity(scip, oldub) )
775  ++heurdata->rowinfinitiesup[rowpos];
776  else if( !SCIPisInfinity(scip, newub) && SCIPisInfinity(scip, oldub) )
777  --heurdata->rowinfinitiesup[rowpos];
778 
779  if( SCIPisInfinity(scip, newlb) && !SCIPisInfinity(scip, oldlb) )
780  ++heurdata->rowinfinitiesdown[rowpos];
781  else if( !SCIPisInfinity(scip, newlb) && SCIPisInfinity(scip, oldlb) )
782  --heurdata->rowinfinitiesdown[rowpos];
783  }
784  else if( coeff < 0.0 )
785  {
786  if( SCIPisInfinity(scip, newub) && !SCIPisInfinity(scip, oldub) )
787  ++heurdata->rowinfinitiesdown[rowpos];
788  else if( !SCIPisInfinity(scip, newub) && SCIPisInfinity(scip, oldub) )
789  --heurdata->rowinfinitiesdown[rowpos];
790 
791  if( SCIPisInfinity(scip, newlb) && !SCIPisInfinity(scip, oldlb) )
792  ++heurdata->rowinfinitiesup[rowpos];
793  else if( !SCIPisInfinity(scip, newlb) && SCIPisInfinity(scip, oldlb) )
794  --heurdata->rowinfinitiesup[rowpos];
795  }
796  assert(heurdata->rowinfinitiesdown[rowpos] >= 0);
797  assert(heurdata->rowinfinitiesup[rowpos] >= 0);
798  }
799  }
800 
801  /* store the new local bounds in the data */
802  heurdataUpdateCurrentBounds(scip, heurdata, var);
803 
804  return SCIP_OKAY;
805 }
806 
807 /** destructor of event handler to free user data (called when SCIP is exiting) */
808 static
809 SCIP_DECL_EVENTFREE(eventFreeDistributiondiving)
810 {
811  SCIP_EVENTHDLRDATA* eventhdlrdata;
812 
813  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
814  assert(eventhdlrdata != NULL);
815 
816  SCIPfreeBlockMemory(scip, &eventhdlrdata);
817  SCIPeventhdlrSetData(eventhdlr, NULL);
818 
819  return SCIP_OKAY;
820 }
821 
822 /*
823  * Callback methods
824  */
825 
826 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
827 static
828 SCIP_DECL_HEURCOPY(heurCopyDistributiondiving)
829 { /*lint --e{715}*/
830  assert(scip != NULL);
831  assert(heur != NULL);
832  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
833 
834  /* call inclusion method of primal heuristic */
836 
837  return SCIP_OKAY;
838 }
839 
840 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
841 static
842 SCIP_DECL_HEURFREE(heurFreeDistributiondiving) /*lint --e{715}*/
843 { /*lint --e{715}*/
844  SCIP_HEURDATA* heurdata;
845 
846  assert(heur != NULL);
847  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
848  assert(scip != NULL);
849 
850  /* free heuristic data */
851  heurdata = SCIPheurGetData(heur);
852  assert(heurdata != NULL);
853  SCIPfreeBlockMemory(scip, &heurdata);
854  SCIPheurSetData(heur, NULL);
855 
856  return SCIP_OKAY;
857 }
858 
859 
860 /** initialization method of primal heuristic (called after problem was transformed) */
861 static
862 SCIP_DECL_HEURINIT(heurInitDistributiondiving) /*lint --e{715}*/
863 { /*lint --e{715}*/
864  SCIP_HEURDATA* heurdata;
865 
866  assert(heur != NULL);
867  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
868 
869  /* get heuristic data */
870  heurdata = SCIPheurGetData(heur);
871  assert(heurdata != NULL);
872 
873  /* create working solution */
874  SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
875 
876  return SCIP_OKAY;
877 }
878 
879 
880 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
881 static
882 SCIP_DECL_HEUREXIT(heurExitDistributiondiving) /*lint --e{715}*/
883 { /*lint --e{715}*/
884  SCIP_HEURDATA* heurdata;
885 
886  assert(heur != NULL);
887  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
888 
889  /* get heuristic data */
890  heurdata = SCIPheurGetData(heur);
891  assert(heurdata != NULL);
892 
893  /* free working solution */
894  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
895 
896  return SCIP_OKAY;
897 }
898 
899 /** scoring callback for distribution diving. best candidate maximizes the distribution score */
900 static
901 SCIP_DECL_DIVESETGETSCORE(divesetGetScoreDistributiondiving)
902 { /*lint --e{715}*/
903  SCIP_HEURDATA* heurdata;
904  SCIP_Real upscore;
905  SCIP_Real downscore;
906  int varindex;
907 
908  heurdata = SCIPheurGetData(SCIPdivesetGetHeur(diveset));
909  assert(heurdata != NULL);
910 
911  /* process pending bound change events */
912  while( heurdata->nupdatedvars > 0 )
913  {
914  SCIP_VAR* nextvar;
915 
916  /* pop the next variable from the queue and process its bound changes */
917  nextvar = heurdataPopBoundChangeVar(scip, heurdata);
918  assert(nextvar != NULL);
919  SCIP_CALL( varProcessBoundChanges(scip, heurdata, nextvar) );
920  }
921 
922  assert(cand != NULL);
923 
924  varindex = SCIPvarGetProbindex(cand);
925 
926  /* terminate with a penalty for inactive variables, which the plugin can currently not score
927  * this should never happen with default settings where only LP branching candidates are iterated, but might occur
928  * if other constraint handlers try to score an inactive variable that was (multi-)aggregated or negated
929  */
930  if( varindex == - 1 )
931  {
932  *score = -1.0;
933  *roundup = FALSE;
934 
935  return SCIP_OKAY;
936  }
937 
938  /* in debug mode, ensure that all bound process events which occurred in the mean time have been captured
939  * by the heuristic event system
940  */
941  assert(SCIPisFeasLE(scip, SCIPvarGetLbLocal(cand), SCIPvarGetUbLocal(cand)));
942  assert(0 <= varindex && varindex < heurdata->varpossmemsize);
943 
944  assert((heurdata->currentlbs[varindex] == SCIP_INVALID)
945  == (heurdata->currentubs[varindex] == SCIP_INVALID));/*lint !e777 doesn't like comparing floats for equality */
946  assert((heurdata->currentlbs[varindex] == SCIP_INVALID)
947  || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(cand), heurdata->currentlbs[varindex])); /*lint !e777 */
948  assert((heurdata->currentubs[varindex] == SCIP_INVALID)
949  || SCIPisFeasEQ(scip, SCIPvarGetUbLocal(cand), heurdata->currentubs[varindex])); /*lint !e777 */
950 
951  /* if the heuristic has not captured the variable bounds yet, this can be done now */
952  if( heurdata->currentlbs[varindex] == SCIP_INVALID ) /*lint !e777 */
953  heurdataUpdateCurrentBounds(scip, heurdata, cand);
954 
955  upscore = 0.0;
956  downscore = 0.0;
957 
958  /* loop over candidate rows and determine the candidate up- and down- branching score w.r.t. the score parameter */
959  SCIP_CALL( calcBranchScore(scip, heurdata, cand, candsol, &upscore, &downscore, heurdata->score) );
960 
961  /* score is simply the maximum of the two individual scores */
962  *roundup = (upscore > downscore);
963  *score = MAX(upscore, downscore);
964 
965  return SCIP_OKAY;
966 }
967 
968 
969 /** execution method of primal heuristic */
970 static
971 SCIP_DECL_HEUREXEC(heurExecDistributiondiving)
972 { /*lint --e{715}*/
973  SCIP_HEURDATA* heurdata;
974  SCIP_DIVESET* diveset;
975  int nlprows;
976 
977  assert(heur != NULL);
978  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
979  assert(scip != NULL);
980  assert(result != NULL);
981  assert(SCIPhasCurrentNodeLP(scip));
982 
983  *result = SCIP_DIDNOTRUN;
984 
985  /* get heuristic's data */
986  heurdata = SCIPheurGetData(heur);
987  assert(heurdata != NULL);
988  nlprows = SCIPgetNLPRows(scip);
989  if( nlprows == 0 )
990  return SCIP_OKAY;
991 
992  /* terminate if there are no integer variables (note that, e.g., SOS1 variables may be present) */
993  if( SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == 0 )
994  return SCIP_OKAY;
995 
996  /* select and store the scoring parameter for this call of the heuristic */
997  if( heurdata->scoreparam == 'r' )
998  heurdata->score = SCOREPARAM_VALUES[SCIPheurGetNCalls(heur) % SCOREPARAM_VALUESLEN];
999  else
1000  heurdata->score = heurdata->scoreparam;
1001 
1002  SCIP_CALL( heurdataEnsureArraySize(scip, heurdata, nlprows) );
1003  assert(SCIPheurGetNDivesets(heur) > 0);
1004  assert(SCIPheurGetDivesets(heur) != NULL);
1005  diveset = SCIPheurGetDivesets(heur)[0];
1006  assert(diveset != NULL);
1007 
1008  SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible) );
1009 
1010  SCIP_CALL( heurdataFreeArrays(scip, heurdata) );
1011 
1012  return SCIP_OKAY;
1013 }
1014 
1015 /** event execution method of distribution branching which handles bound change events of variables */
1016 static
1017 SCIP_DECL_EVENTEXEC(eventExecDistribution)
1018 {
1019  SCIP_HEURDATA* heurdata;
1020  SCIP_EVENTHDLRDATA* eventhdlrdata;
1021  SCIP_VAR* var;
1022 
1023  assert(eventhdlr != NULL);
1024  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
1025  assert(eventhdlrdata != NULL);
1026 
1027  heurdata = eventhdlrdata->heurdata;
1028  var = SCIPeventGetVar(event);
1029 
1030  /* add the variable to the queue of unprocessed variables; method itself ensures that every variable is added at most once */
1031  heurdataAddBoundChangeVar(scip, heurdata, var);
1032 
1033  return SCIP_OKAY;
1034 }
1035 
1036 /*
1037  * heuristic specific interface methods
1038  */
1039 
1040 /** creates the distributiondiving heuristic and includes it in SCIP */
1042  SCIP* scip /**< SCIP data structure */
1043  )
1044 {
1045  SCIP_HEURDATA* heurdata;
1046  SCIP_HEUR* heur;
1047  SCIP_EVENTHDLRDATA* eventhdlrdata;
1048 
1049  /* create distributiondiving data */
1050  heurdata = NULL;
1051  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1052 
1053  heurdata->memsize = 0;
1054  heurdata->rowmeans = NULL;
1055  heurdata->rowvariances = NULL;
1056  heurdata->rowinfinitiesdown = NULL;
1057  heurdata->rowinfinitiesup = NULL;
1058  heurdata->varfilterposs = NULL;
1059  heurdata->currentlbs = NULL;
1060  heurdata->currentubs = NULL;
1061 
1062  /* create event handler first to finish heuristic data */
1063  eventhdlrdata = NULL;
1064  SCIP_CALL( SCIPallocBlockMemory(scip, &eventhdlrdata) );
1065  eventhdlrdata->heurdata = heurdata;
1066 
1067  heurdata->eventhdlr = NULL;
1068  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &heurdata->eventhdlr, EVENTHDLR_NAME,
1069  "event handler for dynamic acitivity distribution updating",
1070  eventExecDistribution, eventhdlrdata) );
1071  assert( heurdata->eventhdlr != NULL);
1072  SCIP_CALL( SCIPsetEventhdlrFree(scip, heurdata->eventhdlr, eventFreeDistributiondiving) );
1073 
1074  /* include primal heuristic */
1075  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1077  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecDistributiondiving, heurdata) );
1078 
1079  assert(heur != NULL);
1080 
1081  /* set non-NULL pointers to callback methods */
1082  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyDistributiondiving) );
1083  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeDistributiondiving) );
1084  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitDistributiondiving) );
1085  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitDistributiondiving) );
1086 
1087  /* add diveset with the defined scoring function */
1093  divesetGetScoreDistributiondiving) );
1094 
1095  SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/scoreparam",
1096  "the score;largest 'd'ifference, 'l'owest cumulative probability,'h'ighest c.p., 'v'otes lowest c.p., votes highest c.p.('w'), 'r'evolving",
1097  &heurdata->scoreparam, TRUE, DEFAULT_SCOREPARAM, "lvdhwr", NULL, NULL) );
1098 
1099  return SCIP_OKAY;
1100 }
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2134
#define DIVESET_DIVETYPES
void SCIPvarCalcDistributionParameters(SCIP *scip, SCIP_Real varlb, SCIP_Real varub, SCIP_VARTYPE vartype, SCIP_Real *mean, SCIP_Real *variance)
#define NULL
Definition: def.h:239
probability based branching rule based on an article by J. Pryor and J.W. Chinneck ...
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:412
#define SQUARED(x)
public methods for memory management
static SCIP_DECL_DIVESETGETSCORE(divesetGetScoreDistributiondiving)
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:422
#define SCOREPARAM_VALUESLEN
static SCIP_RETCODE heurdataEnsureArraySize(SCIP *scip, SCIP_HEURDATA *heurdata, int maxindex)
#define DEFAULT_RANDSEED
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:16748
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:280
SCIP_Bool SCIPisSumPositive(SCIP *scip, SCIP_Real val)
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:16790
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17399
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
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:16928
SCIP_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
Definition: heur.c:1452
#define SCOREPARAM_VALUES
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16909
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
Definition: type_event.h:138
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define FALSE
Definition: def.h:65
#define HEUR_NAME
#define HEUR_PRIORITY
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:64
#define SCIPdebug(x)
Definition: pub_message.h:74
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
methods commonly used by primal heuristics
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17036
#define HEUR_FREQ
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
public methods for problem variables
#define HEUR_USESSUBSCIP
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:187
static SCIP_RETCODE calcBranchScore(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var, SCIP_Real lpsolval, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam)
#define EVENT_DISTRIBUTION
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1175
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
static SCIP_DECL_EVENTFREE(eventFreeDistributiondiving)
#define SCIPdebugMsg
Definition: scip_message.h:88
#define HEUR_FREQOFS
SCIP_RETCODE SCIPincludeHeurDistributiondiving(SCIP *scip)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
public methods for numerical tolerances
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
void SCIPeventhdlrSetData(SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: event.c:334
SCIP_HEUR * SCIPdivesetGetHeur(SCIP_DIVESET *diveset)
Definition: heur.c:325
#define DEFAULT_MINRELDEPTH
#define EVENTHDLR_NAME
#define DEFAULT_MAXDIVEUBQUOTNOSOL
#define DEFAULT_SCOREPARAM
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1254
SCIP_RETCODE SCIPsetEventhdlrFree(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTFREE((*eventfree)))
Definition: scip_event.c:218
#define DEFAULT_LPSOLVEFREQ
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:248
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:16738
public methods for event handler plugins and event handlers
SCIP_SOL * sol
Definition: struct_heur.h:41
static SCIP_DECL_HEURCOPY(heurCopyDistributiondiving)
static SCIP_DECL_EVENTEXEC(eventExecDistribution)
#define HEUR_TIMING
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16729
static void rowCalculateGauss(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_ROW *row, SCIP_Real *mu, SCIP_Real *sigma2, int *rowinfinitiesdown, int *rowinfinitiesup)
#define DEFAULT_MAXLPITEROFS
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:629
#define DEFAULT_MAXLPITERQUOT
#define SCIP_CALL(x)
Definition: def.h:351
static SCIP_DECL_HEUREXIT(heurExitDistributiondiving)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPheurGetNDivesets(SCIP_HEUR *heur)
Definition: heur.c:1462
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1380
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:16815
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:141
public methods for primal heuristic plugins and divesets
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:16825
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
Definition: event.c:1018
#define SCIP_Bool
Definition: def.h:62
SCIP_Real SCIProwCalcProbability(SCIP *scip, SCIP_ROW *row, SCIP_Real mu, SCIP_Real sigma2, int rowinfinitiesdown, int rowinfinitiesup)
public methods for LP management
SCIP_RETCODE SCIPcreateDiveset(SCIP *scip, SCIP_DIVESET **diveset, SCIP_HEUR *heur, const char *name, SCIP_Real minreldepth, SCIP_Real maxreldepth, SCIP_Real maxlpiterquot, SCIP_Real maxdiveubquot, SCIP_Real maxdiveavgquot, SCIP_Real maxdiveubquotnosol, SCIP_Real maxdiveavgquotnosol, SCIP_Real lpresolvedomchgquot, int lpsolvefreq, int maxlpiterofs, unsigned int initialseed, SCIP_Bool backtrack, SCIP_Bool onlylpbranchcands, SCIP_Bool specificsos1score, SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)))
Definition: scip_heur.c:390
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:1034
static SCIP_DECL_HEUREXEC(heurExecDistributiondiving)
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:17057
#define HEUR_MAXDEPTH
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
static void heurdataUpdateCurrentBounds(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var)
static SCIP_RETCODE heurdataFreeArrays(SCIP *scip, SCIP_HEURDATA *heurdata)
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2089
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:152
public methods for the LP relaxation, rows and columns
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:2044
SCIP_RETCODE SCIPperformGenericDivingAlgorithm(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible)
Definition: heuristics.c:192
SCIP_Real * r
Definition: circlepacking.c:50
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:16835
Diving heuristic that chooses fixings w.r.t. changes in the solution density after Pryor and Chinneck...
public methods for managing events
general public methods
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:16713
#define MAX(x, y)
Definition: def.h:208
#define DEFAULT_BACKTRACK
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
static void heurdataAddBoundChangeVar(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var)
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:16639
public methods for solutions
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
public methods for the probing mode
public methods for message output
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:264
SCIP_Real SCIPgetRowLPFeasibility(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1911
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1999
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16848
#define SCIP_Real
Definition: def.h:150
#define DEFAULT_ONLYLPBRANCHCANDS
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:170
static SCIP_DECL_HEURFREE(heurFreeDistributiondiving)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2094
static SCIP_VAR * heurdataPopBoundChangeVar(SCIP *scip, SCIP_HEURDATA *heurdata)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16894
int SCIProwGetIndex(SCIP_ROW *row)
Definition: lp.c:16938
#define HEUR_DESC
#define HEUR_DISPCHAR
enum SCIP_Vartype SCIP_VARTYPE
Definition: type_var.h:60
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:232
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17409
#define DEFAULT_LPRESOLVEDOMCHGQUOT
#define DEFAULT_MAXDIVEUBQUOT
static SCIP_DECL_HEURINIT(heurInitDistributiondiving)
public methods for primal heuristics
static SCIP_RETCODE varProcessBoundChanges(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var)
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:324
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1165
public methods for global and local (sub)problems
#define DEFAULT_MAXRELDEPTH
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17016
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:377
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:134
#define DEFAULT_MAXDIVEAVGQUOT
memory allocation routines