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