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