Scippy

SCIP

Solving Constraint Integer Programs

heur_feaspump.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_feaspump.c
17  * @brief Objective Feasibility Pump 2.0
18  * @author Timo Berthold
19  * @author Domenico Salvagnin
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include <assert.h>
25 #include <string.h>
26 
27 #include "scip/heur_feaspump.h"
28 #include "scip/cons_linear.h"
29 #include "scip/pub_misc.h"
30 #include "scip/scipdefplugins.h"
31 
32 #define HEUR_NAME "feaspump"
33 #define HEUR_DESC "objective feasibility pump 2.0"
34 #define HEUR_DISPCHAR 'F'
35 #define HEUR_PRIORITY -1000000
36 #define HEUR_FREQ 20
37 #define HEUR_FREQOFS 0
38 #define HEUR_MAXDEPTH -1
39 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
40 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
41 
42 #define DEFAULT_MAXLPITERQUOT 0.01 /**< maximal fraction of diving LP iterations compared to node LP iterations */
43 #define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */
44 #define DEFAULT_MAXSOLS 10 /**< total number of feasible solutions found up to which heuristic is called
45  * (-1: no limit) */
46 #define DEFAULT_MAXLOOPS 10000 /**< maximal number of pumping rounds (-1: no limit) */
47 #define DEFAULT_MAXSTALLLOOPS 10 /**< maximal number of pumping rounds without fractionality improvement (-1: no limit) */
48 #define DEFAULT_MINFLIPS 10 /**< minimum number of random variables to flip, if a 1-cycle is encountered */
49 #define DEFAULT_CYCLELENGTH 3 /**< maximum length of cycles to be checked explicitly in each round */
50 #define DEFAULT_PERTURBFREQ 100 /**< number of iterations until a random perturbation is forced */
51 #define DEFAULT_OBJFACTOR 0.1 /**< factor by which the regard of the objective is decreased in each round,
52  * 1.0 for dynamic, depending on solutions already found */
53 #define DEFAULT_ALPHA 1.0 /**< initial weight of the objective function in the convex combination */
54 #define DEFAULT_ALPHADIFF 1.0 /**< threshold difference for the convex parameter to perform perturbation */
55 #define DEFAULT_BEFORECUTS TRUE /**< should the feasibility pump be called at root node before cut separation? */
56 #define DEFAULT_USEFP20 FALSE /**< should an iterative round-and-propagate scheme be used to find the integral points? */
57 #define DEFAULT_PERTSOLFOUND TRUE /**< should a random perturbation be performed if a feasible solution was found? */
58 #define DEFAULT_STAGE3 FALSE /**< should we solve a local branching sub-MIP if no solution could be found? */
59 #define DEFAULT_NEIGHBORHOODSIZE 18 /**< radius of the neighborhood to be searched in stage 3 */
60 #define DEFAULT_COPYCUTS TRUE /**< should all active cuts from the cutpool of the original SCIP be copied to
61  * constraints of the subscip
62  */
63 
64 #define MINLPITER 5000 /**< minimal number of LP iterations allowed in each LP solving call */
65 
66 #define DEFAULT_RANDSEED 13 /**< initial random seed */
67 
68 /** primal heuristic data */
69 struct SCIP_HeurData
70 {
71  SCIP_SOL* sol; /**< working solution */
72  SCIP_SOL* roundedsol; /**< rounded solution */
73  SCIP_Longint nlpiterations; /**< number of LP iterations used in this heuristic */
74  SCIP_Real maxlpiterquot; /**< maximal fraction of diving LP iterations compared to node LP iterations */
75  SCIP_Real objfactor; /**< factor by which the regard of the objective is decreased in each round,
76  * 1.0 for dynamic, depending on solutions already found */
77  SCIP_Real alpha; /**< initial weight of the objective function in the convex combination */
78  SCIP_Real alphadiff; /**< threshold difference for the convex parameter to perform perturbation */
79 
80  int maxlpiterofs; /**< additional number of allowed LP iterations */
81  int maxsols; /**< total number of feasible solutions found up to which heuristic is called
82  * (-1: no limit) */
83  int maxloops; /**< maximum number of loops (-1: no limit) */
84  int maxstallloops; /**< maximal number of pumping rounds without fractionality improvement (-1: no limit) */
85  int minflips; /**< minimum number of random variables to flip, if a 1-cycle is encountered */
86  int cyclelength; /**< maximum length of cycles to be checked explicitly in each round */
87  int perturbfreq; /**< number of iterations until a random perturbation is forced */
88  int nsuccess; /**< number of runs that produced at least one feasible solution */
89  int neighborhoodsize; /**< radius of the neighborhood to be searched in stage 3 */
90 
91  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
92  SCIP_Bool beforecuts; /**< should the feasibility pump be called at root node before cut separation? */
93  SCIP_Bool usefp20; /**< should an iterative round-and-propagate scheme be used to find the integral points? */
94  SCIP_Bool pertsolfound; /**< should a random perturbation be performed if a feasible solution was found? */
95  SCIP_Bool stage3; /**< should we solve a local branching sub-MIP if no solution could be found? */
96  SCIP_Bool copycuts; /**< should all active cuts from cutpool be copied to constraints in
97  * subproblem?
98  */
99 };
100 
101 /* copies SCIP to probing SCIP and creates variable hashmap */
102 static
104  SCIP* scip, /**< SCIP data structure */
105  SCIP** probingscip, /**< sub-SCIP data structure */
106  SCIP_HASHMAP** varmapfw, /**< mapping of SCIP variables to sub-SCIP variables */
107  SCIP_Bool copycuts, /**< should all active cuts from cutpool of scip copied to constraints in subscip */
108  SCIP_Bool* success /**< was copying successful? */
109  )
110 {
111  /* check if we are already at the maximal tree depth */
112  if( SCIP_MAXTREEDEPTH <= SCIPgetDepth(scip) )
113  {
114  *success = FALSE;
115  return SCIP_OKAY;
116  }
117 
118  /* initializing the subproblem */
119  SCIP_CALL( SCIPcreate(probingscip) );
120 
121  /* create the variable mapping hash map */
122  SCIP_CALL( SCIPhashmapCreate(varmapfw, SCIPblkmem(*probingscip), SCIPgetNVars(scip)) );
123  *success = FALSE;
124 
125  /* copy SCIP instance */
126  SCIP_CALL( SCIPcopyConsCompression(scip, *probingscip, *varmapfw, NULL, "feaspump", NULL, NULL, 0, FALSE, FALSE, TRUE, success) );
127 
128  if( copycuts )
129  {
130  /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
131  SCIP_CALL( SCIPcopyCuts(scip, *probingscip, *varmapfw, NULL, FALSE, NULL) );
132  }
133 
134  return SCIP_OKAY;
135 }
136 
137 /** set appropriate parameters for probing SCIP in FP2 */
138 static
140  SCIP* scip, /**< SCIP data structure */
141  SCIP* probingscip /**< sub-SCIP data structure */
142  )
143 {
144  if( SCIPisParamFixed(probingscip, "heuristics/" HEUR_NAME "/freq") )
145  {
146  SCIPwarningMessage(scip, "unfixing parameter heuristics/" HEUR_NAME "/freq in probingscip of " HEUR_NAME " heuristic to avoid recursive calls\n");
147  SCIP_CALL( SCIPunfixParam(probingscip, "heuristics/" HEUR_NAME "/freq") );
148  }
149  SCIP_CALL( SCIPsetIntParam(probingscip, "heuristics/" HEUR_NAME "/freq", -1) );
150 
151  /* do not abort subproblem on CTRL-C */
152  SCIP_CALL( SCIPsetBoolParam(probingscip, "misc/catchctrlc", FALSE) );
153 
154 #ifndef SCIP_DEBUG
155  /* disable output to console */
156  SCIP_CALL( SCIPsetIntParam(probingscip, "display/verblevel", 0) );
157 #endif
158 
159  /* disable expensive and useless stuff */
160  SCIP_CALL( SCIPsetLongintParam(probingscip, "limits/nodes", 1LL) );
161  if( SCIPisParamFixed(probingscip, "lp/solvefreq") )
162  {
163  SCIPwarningMessage(scip, "unfixing parameter lp/solvefreq in probingscip of " HEUR_NAME " heuristic to speed up propagation\n");
164  SCIP_CALL( SCIPunfixParam(probingscip, "lp/solvefreq") );
165  }
166  SCIP_CALL( SCIPsetIntParam(probingscip, "lp/solvefreq", -1) );
167  SCIP_CALL( SCIPsetBoolParam(probingscip, "conflict/enable", FALSE) );
168  SCIP_CALL( SCIPsetBoolParam(probingscip, "constraints/disableenfops", TRUE) );
169  SCIP_CALL( SCIPsetBoolParam(probingscip, "constraints/knapsack/negatedclique", FALSE) );
172  return SCIP_OKAY;
173 }
174 
175 /** set appropriate parameters for probing SCIP in Stage 3 */
176 static
178  SCIP* scip, /**< SCIP data structure */
179  SCIP* probingscip /**< sub-SCIP data structure */
180  )
181 {
182  SCIP_CALL( SCIPcopyParamSettings(scip, probingscip) );
183  /* do not abort subproblem on CTRL-C */
184  SCIP_CALL( SCIPsetBoolParam(probingscip, "misc/catchctrlc", FALSE) );
185 
186 #ifndef SCIP_DEBUG
187  /* disable output to console */
188  SCIP_CALL( SCIPsetIntParam(probingscip, "display/verblevel", 0) );
189 #endif
190  /* set limits for the subproblem */
191  SCIP_CALL( SCIPcopyLimits(scip, probingscip) );
192  SCIP_CALL( SCIPsetLongintParam(probingscip, "limits/nodes", 1000LL) );
193  SCIP_CALL( SCIPsetLongintParam(probingscip, "limits/stallnodes", 100LL) );
194 
195  /* forbid recursive call of heuristics and separators solving sub-SCIPs */
196  SCIP_CALL( SCIPsetSubscipsOff(probingscip, TRUE) );
197  if( SCIPisParamFixed(probingscip, "heuristics/" HEUR_NAME "/freq") )
198  {
199  SCIPwarningMessage(scip,"unfixing parameter heuristics/" HEUR_NAME "/freq in probingscip of " HEUR_NAME " heuristic to avoid recursive calls\n");
200  SCIP_CALL( SCIPunfixParam(probingscip, "heuristics/" HEUR_NAME "/freq") );
201  }
202  SCIP_CALL( SCIPsetIntParam(probingscip, "heuristics/feaspump/freq", -1) );
203 
204  /* disable heuristics which aim to feasibility instead of optimality */
205  if( !SCIPisParamFixed(probingscip, "heuristics/octane/freq") )
206  {
207  SCIP_CALL( SCIPsetIntParam(probingscip, "heuristics/octane/freq", -1) );
208  }
209  if( !SCIPisParamFixed(probingscip, "heuristics/objpscostdiving/freq") )
210  {
211  SCIP_CALL( SCIPsetIntParam(probingscip, "heuristics/objpscostdiving/freq", -1) );
212  }
213  if( !SCIPisParamFixed(probingscip, "heuristics/rootsoldiving/freq") )
214  {
215  SCIP_CALL( SCIPsetIntParam(probingscip, "heuristics/rootsoldiving/freq", -1) );
216  }
217 
218  /* disable cutting plane separation */
220 
221  /* disable expensive presolving */
223 
224  /* use best estimate node selection */
225  if( SCIPfindNodesel(probingscip, "estimate") != NULL && !SCIPisParamFixed(probingscip, "nodeselection/estimate/stdpriority") )
226  {
227  SCIP_CALL( SCIPsetIntParam(probingscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
228  }
229 
230  /* use inference branching */
231  if( SCIPfindBranchrule(probingscip, "inference") != NULL && !SCIPisParamFixed(probingscip, "branching/inference/priority") )
232  {
233  SCIP_CALL( SCIPsetIntParam(probingscip, "branching/inference/priority", INT_MAX/4) );
234  }
235 
236  /* disable conflict analysis */
237  if( !SCIPisParamFixed(probingscip, "conflict/enable") )
238  {
239  SCIP_CALL( SCIPsetBoolParam(probingscip, "conflict/enable", FALSE) );
240  }
241 
242  return SCIP_OKAY;
243 }
244 
245 /** checks whether a variable is one of the currently most fractional ones */
246 static
247 void insertFlipCand(
248  SCIP_VAR** mostfracvars, /**< sorted array of the currently most fractional variables */
249  SCIP_Real* mostfracvals, /**< array of their fractionality, decreasingly sorted */
250  int* nflipcands, /**< number of fractional variables already labeled to be flipped*/
251  int maxnflipcands, /**< typically randomized number of maximum amount of variables to flip */
252  SCIP_VAR* var, /**< variable to be checked */
253  SCIP_Real frac /**< fractional value of the variable */
254  )
255 {
256  int i;
257 
258  assert(mostfracvars != NULL);
259  assert(mostfracvals != NULL);
260  assert(nflipcands != NULL);
261 
262  /* instead of the fractional value use the fractionality */
263  if( frac > 0.5 )
264  frac = 1 - frac;
265 
266  /* if there are already enough candidates and the variable is less fractional, return, else reserve the last entry */
267  if( *nflipcands >= maxnflipcands )
268  {
269  if( frac <= mostfracvals[*nflipcands-1] )
270  return;
271  else
272  (*nflipcands)--;
273  }
274 
275  /* shifting var and frac through the (sorted) arrays */
276  for( i = *nflipcands; i > 0 && mostfracvals[i-1] < frac; i-- )
277  {
278  mostfracvars[i] = mostfracvars[i-1];
279  mostfracvals[i] = mostfracvals[i-1];
280  }
281  assert(0 <= i && i <= *nflipcands && *nflipcands < maxnflipcands);
282 
283  /* insert the variable and its fractionality */
284  mostfracvars[i] = var;
285  mostfracvals[i] = frac;
286 
287  /* we've found another candidate */
288  (*nflipcands)++;
289 }
290 
291 /** flips the roundings of the most fractional variables, if a 1-cycle was found */
292 static
294  SCIP* scip, /**< SCIP data structure */
295  SCIP_HEURDATA* heurdata, /**< data of this special heuristic */
296  SCIP_VAR** mostfracvars, /**< sorted array of the currently most fractional variables */
297  int nflipcands, /**< number of variables to flip */
298  SCIP_Real alpha /**< factor how much the original objective is regarded */
299  )
300 {
301  SCIP_VAR* var;
302  SCIP_Real solval;
303  SCIP_Real frac;
304  SCIP_Real newobjcoeff;
305  SCIP_Real orgobjcoeff;
306  int i;
307 
308  /* just flipping the objective coefficients from +1 to -1 and the rounding from floor to ceil */
309  for( i = 0; i < nflipcands; i++ )
310  {
311  SCIP_Real sign = 1.0;
312 
313  var = mostfracvars[i];
314  solval = SCIPvarGetLPSol(var);
315  orgobjcoeff = SCIPvarGetObj(var);
316  frac = SCIPfeasFrac(scip, solval);
317 
318  if( SCIPisEQ(scip, frac, 0.5) )
319  {
320  if( SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0 )
321  {
322  sign = -1.0;
323  solval = SCIPfeasCeil(scip, solval);
324  }
325  }
326  else if( frac > 0.5 )
327  solval = SCIPfeasFloor(scip, solval);
328  else
329  {
330  sign = -1.0;
331  solval = SCIPfeasCeil(scip, solval);
332  }
333  newobjcoeff = sign * (1.0 - alpha) + alpha * orgobjcoeff;
334 
335  /* updating the rounded solution and the objective */
336  SCIP_CALL( SCIPsetSolVal(scip, heurdata->roundedsol, var, solval) );
337  SCIP_CALL( SCIPchgVarObjDive(scip, var, newobjcoeff) );
338  }
339  return SCIP_OKAY;
340 }
341 
342 /** flips the roundings of randomly chosen fractional variables, preferring highly fractional ones,
343  * if a longer cycle was found
344  */
345 static
347  SCIP* scip, /**< SCIP data structure */
348  SCIP_HEURDATA* heurdata, /**< data of this special heuristic */
349  SCIP_VAR** vars, /**< array of all variables */
350  int nbinandintvars, /**< number of general integer and 0-1 variables */
351  SCIP_Real alpha /**< factor how much the original objective is regarded */
352  )
353 {
354  SCIP_VAR* var;
355  SCIP_Real solval;
356  SCIP_Real frac;
357  SCIP_Real newobjcoeff;
358  SCIP_Real orgobjcoeff;
359  SCIP_Real flipprob;
360  int i;
361 
362  /* just flipping the objective coefficients from +1 to -1 and the rounding from floor to ceil */
363  for( i = 0; i < nbinandintvars; i++ )
364  {
365  SCIP_Real sign = 1.0;
366 
367  /* decide arbitrarily whether the variable will be flipped or not */
368  var = vars[i];
369  solval = SCIPvarGetLPSol(var);
370  orgobjcoeff = SCIPvarGetObj(var);
371  frac = SCIPfeasFrac(scip, solval);
372  flipprob = -0.3 + SCIPrandomGetReal(heurdata->randnumgen, 0.0, 1.0);
373 
374  /* flip, iff the sum of the randomized number and the fractionality is big enough */
375  if( MIN(frac, 1.0-frac) + MAX(flipprob, 0.0) > 0.5 )
376  {
377  if( SCIPisEQ(scip, frac, 0.5) )
378  {
379  if( SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0 )
380  {
381  sign = -1.0;
382  solval = SCIPfeasCeil(scip, solval);
383  }
384  }
385  if( frac > 0.5 )
386  solval = SCIPfeasFloor(scip, solval);
387  else
388  {
389  sign = -1.0;
390  solval = SCIPfeasCeil(scip, solval);
391  }
392 
393  newobjcoeff = sign * (1.0 - alpha) + alpha * orgobjcoeff;
394 
395  SCIP_CALL( SCIPsetSolVal(scip, heurdata->roundedsol, var, solval) );
396  SCIP_CALL( SCIPchgVarObjDive(scip, var, newobjcoeff) );
397  }
398  }
399 
400  return SCIP_OKAY;
401 }
402 
403 /** create the extra constraint of local branching and add it to subscip */
404 static
406  SCIP* scip, /**< SCIP data structure of the original problem */
407  SCIP* probingscip, /**< SCIP data structure of the subproblem */
408  SCIP_HASHMAP* varmapfw, /**< mapping of SCIP variables to sub-SCIP variables */
409  SCIP_SOL* bestsol, /**< SCIP solution */
410  SCIP_Real neighborhoodsize /**< rhs for LB constraint */
411  )
412 {
413  SCIP_CONS* cons; /* local branching constraint to create */
414  SCIP_VAR** consvars;
415  SCIP_VAR** vars;
416 
417  int nbinvars;
418  int i;
419  SCIP_Real lhs;
420  SCIP_Real rhs;
421  SCIP_Real* consvals;
422  char consname[SCIP_MAXSTRLEN];
423 
424  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_localbranchcons", SCIPgetProbName(scip));
425 
426  /* get vars data */
427  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, NULL, NULL, NULL) );
428  /* memory allocation */
429  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nbinvars) );
430  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nbinvars) );
431 
432  /* set initial left and right hand sides of local branching constraint */
433  lhs = 0.0;
434  rhs = neighborhoodsize;
435 
436  /* create the distance (to incumbent) function of the binary variables */
437  for( i = 0; i < nbinvars; i++ )
438  {
439  SCIP_Real solval;
440 
441  solval = SCIPgetSolVal(scip, bestsol, vars[i]);
442  assert( SCIPisFeasIntegral(scip,solval) );
443 
444  /* is variable i part of the binary support of closest sol? */
445  if( SCIPisFeasEQ(scip,solval,1.0) )
446  {
447  consvals[i] = -1.0;
448  rhs -= 1.0;
449  lhs -= 1.0;
450  }
451  else
452  consvals[i] = 1.0;
453  consvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
454  SCIP_CALL( SCIPchgVarObj(probingscip, consvars[i], consvals[i]) );
455  assert( SCIPvarGetType(consvars[i]) == SCIP_VARTYPE_BINARY );
456  }
457 
458  /* creates localbranching constraint and adds it to subscip */
459  SCIP_CALL( SCIPcreateConsLinear(probingscip, &cons, consname, nbinvars, consvars, consvals,
460  lhs, rhs, FALSE, FALSE, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
461  SCIP_CALL( SCIPaddCons(probingscip, cons) );
462  SCIP_CALL( SCIPreleaseCons(probingscip, &cons) );
463 
464  /* free local memory */
465  SCIPfreeBufferArray(scip, &consvals);
466  SCIPfreeBufferArray(scip, &consvars);
467 
468  return SCIP_OKAY;
469 }
470 
471 /** creates new solutions for the original problem by copying the solutions of the subproblem */
472 static
474  SCIP* scip, /**< original SCIP data structure */
475  SCIP* subscip, /**< SCIP structure of the subproblem */
476  SCIP_HASHMAP* varmapfw, /**< mapping of SCIP variables to sub-SCIP variables */
477  SCIP_HEUR* heur, /**< heuristic structure */
478  SCIP_Bool* success /**< used to store whether new solution was found or not */
479  )
480 {
481  SCIP_VAR** vars; /* the original problem's variables */
482  int nvars;
483  SCIP_SOL** subsols;
484  int nsubsols;
485  SCIP_VAR** subvars;
486  SCIP_Real* subsolvals; /* solution values of the subproblem */
487  SCIP_SOL* newsol; /* solution to be created for the original problem */
488  int i;
489 
490  assert(scip != NULL);
491  assert(subscip != NULL);
492 
493  /* get variables' data */
494  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
495 
496  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
497  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
498  */
499  assert(nvars <= SCIPgetNOrigVars(subscip));
500 
501  /* for copying a solution we need an explicit mapping */
502  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
503  for( i = 0; i < nvars; i++ )
504  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
505 
506  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
507 
508  nsubsols = SCIPgetNSols(subscip);
509  subsols = SCIPgetSols(subscip);
510  *success = FALSE;
511 
512  for( i = 0; i < nsubsols && !(*success); ++i )
513  {
514  /* copy the solution */
515  SCIP_CALL( SCIPgetSolVals(subscip, subsols[i], nvars, subvars, subsolvals) );
516 
517  /* create new solution for the original problem */
518  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
519  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
520 
521  /* try to add new solution to scip and free it immediately */
522  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
523  }
524 
525  SCIPfreeBufferArray(scip, &subvars);
526  SCIPfreeBufferArray(scip, &subsolvals);
527 
528  return SCIP_OKAY;
529 }
530 
531 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
532 static
533 SCIP_DECL_HEURCOPY(heurCopyFeaspump)
534 {
535  assert(scip != NULL);
536  assert(heur != NULL);
537  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
538 
539  /* call inclusion method of primal heuristic */
541 
542  return SCIP_OKAY;
543 }
544 
545 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
546 static
547 SCIP_DECL_HEURFREE(heurFreeFeaspump)
548 {
549  SCIP_HEURDATA* heurdata;
550 
551  assert(heur != NULL);
552  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
553  assert(scip != NULL);
554 
555  /* free heuristic data */
556  heurdata = SCIPheurGetData(heur);
557  assert(heurdata != NULL);
558  SCIPfreeBlockMemory(scip, &heurdata);
559  SCIPheurSetData(heur, NULL);
560 
561  return SCIP_OKAY;
562 }
563 
564 
565 /** initialization method of primal heuristic (called after problem was transformed) */
566 static
567 SCIP_DECL_HEURINIT(heurInitFeaspump)
568 {
569  SCIP_HEURDATA* heurdata;
570 
571  assert(heur != NULL);
572  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
573 
574  /* get heuristic data */
575  heurdata = SCIPheurGetData(heur);
576  assert(heurdata != NULL);
577 
578  /* create working solution */
579  SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
580  SCIP_CALL( SCIPcreateSol(scip, &heurdata->roundedsol, heur) );
581 
582  /* initialize data */
583  heurdata->nlpiterations = 0;
584  heurdata->nsuccess = 0;
585 
586  /* create random number generator */
587  SCIP_CALL( SCIPrandomCreate(&heurdata->randnumgen, SCIPblkmem(scip),
589 
590  return SCIP_OKAY;
591 }
592 
593 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
594 static
595 SCIP_DECL_HEUREXIT(heurExitFeaspump)
596 {
597  SCIP_HEURDATA* heurdata;
598 
599  assert(heur != NULL);
600  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
601 
602  /* get heuristic data */
603  heurdata = SCIPheurGetData(heur);
604  assert(heurdata != NULL);
605 
606  /* free working solution */
607  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
608  SCIP_CALL( SCIPfreeSol(scip, &heurdata->roundedsol) );
609 
610  /* free random number generator */
611  SCIPrandomFree(&heurdata->randnumgen);
612 
613  return SCIP_OKAY;
614 }
615 
616 
617 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
618 static
619 SCIP_DECL_HEURINITSOL(heurInitsolFeaspump)
620 {
621  SCIP_HEURDATA* heurdata;
622 
623  heurdata = SCIPheurGetData(heur);
624  assert(heurdata != NULL);
625 
626  /* if the heuristic is called at the root node, we may want to be called directly after the initial root LP solve */
627  if( heurdata->beforecuts && SCIPheurGetFreqofs(heur) == 0 )
629 
630  return SCIP_OKAY;
631 }
632 
633 
634 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
635 static
636 SCIP_DECL_HEUREXITSOL(heurExitsolFeaspump)
637 {
638  /* reset the timing mask to its default value */
641  return SCIP_OKAY;
642 }
643 
644 /** calculates an adjusted maximal number of LP iterations */
645 static
647  SCIP_Longint maxnlpiterations, /**< regular maximal number of LP iterations */
648  SCIP_Longint nsolsfound, /**< total number of solutions found so far by SCIP */
649  int nstallloops /**< current number of stalling rounds */
650  )
651 {
652  if( nstallloops <= 1 )
653  {
654  if( nsolsfound == 0 )
655  return 4*maxnlpiterations;
656  else
657  return 2*maxnlpiterations;
658  }
659  else
660  return maxnlpiterations;
661 }
662 
663 /** execution method of primal heuristic */
664 static
665 SCIP_DECL_HEUREXEC(heurExecFeaspump)
666 {
667  SCIP_HEURDATA* heurdata;
668  SCIP_SOL* tmpsol; /* only used for swapping */
669  SCIP_SOL** lastroundedsols;/* solutions of the last pumping rounds (depending on heurdata->cyclelength) */
670  SCIP_SOL* closestsol; /* rounded solution closest to the LP relaxation: used for stage3 */
671  SCIP_Real* lastalphas; /* alpha values associated to solutions in lastroundedsols */
672 
673  SCIP* probingscip; /* copied SCIP structure, used for round-and-propagate loop of feasibility pump 2.0 */
674  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
675 
676 
677  SCIP_VAR** vars;
678  SCIP_VAR** pseudocands;
679  SCIP_VAR** tmppseudocands;
680  SCIP_VAR** mostfracvars; /* the 30 most fractional variables, needed to avoid 1-cycles */
681  SCIP_VAR* var;
682 
683  SCIP_Real* mostfracvals; /* the values of the variables above */
684  SCIP_Real newobjcoeff; /* used for changing the objective */
685  SCIP_Real orgobjcoeff; /* used for regarding the original objective */
686  SCIP_Real oldsolval; /* one value of the last solution */
687  SCIP_Real solval; /* one value of the actual solution */
688  SCIP_Real frac; /* the fractional part of the value above */
689  SCIP_Real objfactor; /* factor by which the regard of the objective is decreased in each round, in [0,0.99] */
690  SCIP_Real alpha; /* factor how the original objective is regarded, used for convex combination of two functions */
691  SCIP_Real objnorm; /* Euclidean norm of the objective function, used for scaling */
692  SCIP_Real scalingfactor; /* factor to scale the original objective function with */
693  SCIP_Real mindistance; /* distance of the closest rounded solution from the LP relaxation: used for stage3 */
694 
695  SCIP_Longint nlpiterations; /* number of LP iterations done during one pumping round */
696  SCIP_Longint maxnlpiterations; /* maximum number of LP iterations for this heuristic */
697  SCIP_Longint nsolsfound; /* number of solutions found by this heuristic */
698  SCIP_Longint ncalls; /* number of calls of this heuristic */
699  SCIP_Longint nbestsolsfound; /* current total number of best solution updates in SCIP */
700 
701  SCIP_LPSOLSTAT lpsolstat; /* status of the LP solution */
702 
703  int nvars; /* number of variables */
704  int nbinvars; /* number of 0-1-variables */
705  int nintvars; /* number of integer variables */
706  int nfracs; /* number of fractional variables updated after each pumping round*/
707  int nflipcands; /* how many flipcands (most frac. var.) have been found */
708  int npseudocands;
709  int maxnflipcands; /* maximal number of candidates to flip in the current pumping round */
710  int nloops; /* how many pumping rounds have been made */
711  int maxflips; /* maximum number of flips, if a 1-cycle is found (depending on heurdata->minflips) */
712  int maxloops; /* maximum number of pumping rounds */
713  int nstallloops; /* number of loops without reducing the current best number of factional variables */
714  int maxstallloops; /* maximal number of allowed stalling loops */
715  int bestnfracs; /* best number of fractional variables */
716  int i;
717  int j;
718 
719  SCIP_Bool success;
720  SCIP_Bool lperror;
721  SCIP_Bool* cycles; /* are there short cycles */
722 
723  SCIP_RETCODE retcode;
724 
725  assert(heur != NULL);
726  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
727  assert(scip != NULL);
728  assert(result != NULL);
729  assert(SCIPhasCurrentNodeLP(scip));
730 
731  *result = SCIP_DELAYED;
732 
733  /* do not call heuristic of node was already detected to be infeasible */
734  if( nodeinfeasible )
735  return SCIP_OKAY;
736 
737  /* only call heuristic, if an optimal LP solution is at hand */
739  return SCIP_OKAY;
740 
741  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
742  if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
743  return SCIP_OKAY;
744 
745  /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */
746  if( !SCIPisLPSolBasic(scip) )
747  return SCIP_OKAY;
748 
749  *result = SCIP_DIDNOTRUN;
750 
751  /* don't dive two times at the same node */
752  if( SCIPgetLastDivenode(scip) == SCIPgetNNodes(scip) && SCIPgetDepth(scip) > 0 )
753  return SCIP_OKAY;
754 
755  /* only call feaspump once at the root */
756  if( SCIPgetDepth(scip) == 0 && SCIPheurGetNCalls(heur) > 0 )
757  return SCIP_OKAY;
758 
759  /* reset the timing mask to its default value (at the root node it could be different) */
761 
762  /* only call the heuristic before cutting planes if we do not have an incumbent and no pricer exists */
763  if( heurtiming == SCIP_HEURTIMING_DURINGLPLOOP && SCIPgetNSolsFound(scip) > 0 && SCIPgetNPricers(scip) == 0 )
764  return SCIP_OKAY;
765 
766  /* get heuristic's data */
767  heurdata = SCIPheurGetData(heur);
768  assert(heurdata != NULL);
769 
770  /* only apply heuristic, if only a few solutions have been found and no pricer exists */
771  if( heurdata->maxsols >= 0 && SCIPgetNSolsFound(scip) > heurdata->maxsols && SCIPgetNPricers(scip) == 0 )
772  return SCIP_OKAY;
773 
774  /* get all variables of LP and number of fractional variables in LP solution that should be integral */
775  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
776  nfracs = SCIPgetNLPBranchCands(scip);
777  assert(0 <= nfracs && nfracs <= nbinvars + nintvars);
778  if( nfracs == 0 )
779  return SCIP_OKAY;
780 
781  /* calculate the maximal number of LP iterations until heuristic is aborted */
782  nlpiterations = SCIPgetNLPIterations(scip);
783  ncalls = SCIPheurGetNCalls(heur);
784  nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + heurdata->nsuccess;
785  maxnlpiterations = (SCIP_Longint)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxlpiterquot * nlpiterations);
786  maxnlpiterations += heurdata->maxlpiterofs;
787 
788  /* don't try to dive, if we took too many LP iterations during diving */
789  if( heurdata->nlpiterations >= maxnlpiterations )
790  return SCIP_OKAY;
791 
792  /* at the first root call, allow more iterations if there is no feasible solution yet */
793  if( SCIPheurGetNCalls(heur) == 0 && SCIPgetNSolsFound(scip) == 0 && SCIPgetDepth(scip) == 0 )
794  maxnlpiterations += nlpiterations;
795 
796  /* allow at least a certain number of LP iterations in this dive */
797  maxnlpiterations = MAX(maxnlpiterations, heurdata->nlpiterations + MINLPITER);
798 
799  /* calculate maximal number of flips and loops */
800  maxflips = 3*heurdata->minflips;
801  maxloops = (heurdata->maxloops == -1 ? INT_MAX : heurdata->maxloops);
802  maxstallloops = (heurdata->maxstallloops == -1 ? INT_MAX : heurdata->maxstallloops);
803 
804  SCIPdebugMsg(scip, "executing feasibility pump heuristic, nlpiters=%" SCIP_LONGINT_FORMAT ", maxnlpit:%" SCIP_LONGINT_FORMAT ", maxflips:%d \n",
805  nlpiterations, maxnlpiterations, maxflips);
806 
807  *result = SCIP_DIDNOTFIND;
808 
809  probingscip = NULL;
810  varmapfw = NULL;
811 
812  if( heurdata->usefp20 )
813  {
814  SCIP_CALL( setupProbingSCIP(scip, &probingscip, &varmapfw, heurdata->copycuts, &success) );
815 
816  if( success )
817  {
818  SCIP_CALL( setupSCIPparamsFP2(scip, probingscip) );
819 
820  retcode = SCIPsolve(probingscip);
821 
822  /* errors in solving the subproblem should not kill the overall solving process;
823  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */
824  if( retcode != SCIP_OKAY )
825  {
826 #ifndef NDEBUG
827  SCIP_CALL( retcode );
828 #endif
829  SCIPwarningMessage(scip, "Error while solving subproblem in feaspump heuristic; sub-SCIP terminated with code <%d>\n", retcode);
830 
831  /* free hash map and copied SCIP */
832  SCIPhashmapFree(&varmapfw);
833  SCIP_CALL( SCIPfree(&probingscip) );
834  return SCIP_OKAY;
835  }
836 
837  if( SCIPgetStage(probingscip) != SCIP_STAGE_SOLVING)
838  {
839  SCIP_STATUS probingstatus = SCIPgetStatus(probingscip);
840 
841  if( probingstatus == SCIP_STATUS_OPTIMAL )
842  {
843  assert( SCIPgetNSols(probingscip) > 0 );
844  SCIP_CALL( createNewSols(scip, probingscip, varmapfw, heur, &success) );
845  if( success )
846  *result = SCIP_FOUNDSOL;
847  }
848 
849  /* free hash map and copied SCIP */
850  SCIPhashmapFree(&varmapfw);
851  SCIP_CALL( SCIPfree(&probingscip) );
852  return SCIP_OKAY;
853  }
854  SCIP_CALL( SCIPsetLongintParam(probingscip, "limits/nodes", 2LL) );
855 
856  /* set SCIP into probing mode and create root node of the probing tree */
857  SCIP_CALL( SCIPstartProbing(probingscip) );
858 
859  /* this should always be fulfilled */
860  assert(SCIP_MAXTREEDEPTH > SCIPgetDepth(probingscip));
861 
862  SCIP_CALL( SCIPnewProbingNode(probingscip) );
863 
864  SCIPdebugMsg(scip, "successfully copied SCIP instance -> feasibility pump 2.0 can be used.\n");
865  }
866  }
867 
868  /* memory allocation */
869  SCIP_CALL( SCIPallocBufferArray(scip, &mostfracvars, maxflips) );
870  SCIP_CALL( SCIPallocBufferArray(scip, &mostfracvals, maxflips) );
871  SCIP_CALL( SCIPallocBufferArray(scip, &lastroundedsols, heurdata->cyclelength) );
872  SCIP_CALL( SCIPallocBufferArray(scip, &lastalphas, heurdata->cyclelength) );
873  SCIP_CALL( SCIPallocBufferArray(scip, &cycles, heurdata->cyclelength) );
874 
875  for( j = 0; j < heurdata->cyclelength; j++ )
876  {
877  SCIP_CALL( SCIPcreateSol(scip, &lastroundedsols[j], heur) );
878  }
879 
880  closestsol = NULL;
881  if( heurdata->stage3 )
882  {
883  SCIP_CALL( SCIPcreateSol(scip, &closestsol, heur) );
884  }
885 
886  /* start diving */
887  SCIP_CALL( SCIPstartDive(scip) );
888 
889  /* lp was solved optimal */
890  lperror = FALSE;
891  lpsolstat = SCIP_LPSOLSTAT_OPTIMAL;
892 
893  /* pumping rounds */
894  nsolsfound = SCIPgetNBestSolsFound(scip);
895  if( heurdata->objfactor == 1.0 )
896  objfactor = MIN(1.0 - 0.1 / (SCIP_Real)(1 + nsolsfound), 0.999);
897  else
898  objfactor = heurdata->objfactor;
899 
900  /* scale distance function and original objective to the same norm */
901  objnorm = SCIPgetObjNorm(scip);
902  objnorm = MAX(objnorm, 1.0);
903  scalingfactor = SQRT((SCIP_Real)(nbinvars + nintvars)) / objnorm;
904 
905  /* data initialization */
906  alpha = heurdata->alpha;
907  nloops = 0;
908  nstallloops = 0;
909  nbestsolsfound = SCIPgetNBestSolsFound(scip);
910  bestnfracs = INT_MAX;
911  mindistance = SCIPinfinity(scip);
912 
913  /* pumping loop */
914  while( nfracs > 0
915  && heurdata->nlpiterations < adjustedMaxNLPIterations(maxnlpiterations, nsolsfound, nstallloops)
916  && nloops < maxloops && nstallloops < maxstallloops
917  && !SCIPisStopped(scip) )
918  {
919  int minimum;
920  SCIP_Real* pseudocandsfrac;
921  SCIP_Longint nlpiterationsleft;
922  int iterlimit;
923 
924  /* decrease convex combination scalar */
925  nloops++;
926  alpha *= objfactor;
927 
928  SCIPdebugMsg(scip, "feasibility pump loop %d: %d fractional variables (alpha: %.4f, stall: %d/%d)\n",
929  nloops, nfracs, alpha, nstallloops, maxstallloops);
930 
931  success = FALSE;
932 
933  /* create solution from diving LP and try to round it */
934  SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) );
935  SCIP_CALL( SCIProundSol(scip, heurdata->sol, &success) );
936 
937  /* if the rounded solution is feasible and better, add it to SCIP */
938  /*if( success )
939  {
940  SCIPdebugMsg(scip, "feasibility pump trying rounded solution\n");
941  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, &success) );
942  if( success )
943  *result = SCIP_FOUNDSOL;
944  }*/
945 
946  SCIP_CALL( SCIPlinkLPSol(scip, heurdata->roundedsol) );
947 
948  /* randomly choose maximum number of variables to flip in current pumping round in case of a 1-cycle */
949  maxnflipcands = SCIPrandomGetInt(heurdata->randnumgen, MIN(nfracs/2+1, heurdata->minflips), MIN(nfracs, maxflips));
950  nflipcands = 0;
951 
952  /* get all unfixed integer variables */
953  SCIP_CALL( SCIPgetPseudoBranchCands(scip, &tmppseudocands, &npseudocands, NULL) );
954  SCIP_CALL( SCIPduplicateBufferArray(scip, &pseudocands, tmppseudocands, npseudocands) );
955 
956  /* get array of all fractional variables and sort it w.r.t. their fractionalities */
957  if( heurdata->usefp20 )
958  {
959  SCIP_CALL( SCIPallocBufferArray(scip, &pseudocandsfrac, npseudocands) );
960 
961  for( i = 0; i < npseudocands; i++ )
962  {
963  frac = SCIPfeasFrac(scip, SCIPvarGetLPSol(pseudocands[i]));
964  pseudocandsfrac[i] = MIN(frac, 1.0-frac); /* always a number between 0 and 0.5 */
965  if( SCIPvarGetType(pseudocands[i]) == SCIP_VARTYPE_BINARY )
966  pseudocandsfrac[i] -= 10.0; /* binaries always come first */
967  }
968  SCIPsortRealPtr(pseudocandsfrac, (void**)pseudocands, npseudocands);
969  SCIPfreeBufferArray(scip, &pseudocandsfrac);
970 
971  SCIPdebugMsg(scip, "iteratively fix and propagate variables\n");
972  }
973 
974  for( i = 0; i < npseudocands; i++ )
975  {
976  SCIP_VAR* probingvar;
977  SCIP_Bool infeasible;
978  SCIP_Longint ndomreds;
979 
980  var = pseudocands[i];
981  orgobjcoeff = SCIPvarGetObj(var);
982 
983  /* round the LP solution */
984  solval = SCIPvarGetLPSol(var);
985  frac = SCIPfeasFrac(scip, solval);
986 
987  solval = SCIPfloor(scip, solval+0.5);
988 
989  /* ensure, that the fixing value is inside the local domains */
990  if( heurdata->usefp20 )
991  {
992  SCIP_Real lb;
993  SCIP_Real ub;
994 
995  probingvar = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, var);
996  lb = SCIPvarGetLbLocal(probingvar);
997  ub = SCIPvarGetUbLocal(probingvar);
998 
999  solval = MAX(solval, lb);
1000  solval = MIN(solval, ub);
1001 
1002  /* fix the variable and propagate the domain change */
1003  if( !SCIPisFeasEQ(probingscip, lb, ub) )
1004  {
1005  assert(SCIPisFeasLE(probingscip, lb, ub));
1006  /* SCIP_CALL( SCIPnewProbingNode(probingscip) ); */
1007  SCIPdebugMsg(scip, "try to fix variable <%s> (domain [%f,%f] to %f\n",SCIPvarGetName(probingvar), lb, ub,
1008  solval);
1009  SCIP_CALL( SCIPfixVarProbing(probingscip, probingvar, solval) );
1010  SCIP_CALL( SCIPpropagateProbing(probingscip, -1, &infeasible, &ndomreds) );
1011  SCIPdebugMsg(scip, " -> reduced %" SCIP_LONGINT_FORMAT " domains\n", ndomreds);
1012 
1013  if( infeasible )
1014  {
1015  SCIPdebugMsg(scip, " -> infeasible!\n");
1016  SCIP_CALL( SCIPbacktrackProbing(probingscip, 0/*SCIPgetProbingDepth(probingscip)-1*/) );
1017  }
1018  }
1019  else
1020  {
1021  SCIPdebugMsg(scip, "variable <%s> is already fixed to %f\n",SCIPvarGetName(probingvar), solval);
1022  }
1023  }
1024 
1025  assert(SCIPisFeasLE(scip, SCIPvarGetLbLocal(var), solval) && SCIPisFeasLE(scip, solval, SCIPvarGetUbLocal(var)));
1026  assert(SCIPisIntegral(scip,solval));
1027  SCIP_CALL( SCIPsetSolVal(scip, heurdata->roundedsol, var, solval) );
1028 
1029  /* variables which are already integral, are treated separately */
1030  if( SCIPisFeasZero(scip, frac) )
1031  {
1032  SCIP_Real lb;
1033  SCIP_Real ub;
1034 
1035  /* variables at their bounds should be kept there */
1036  lb = SCIPvarGetLbLocal(var);
1037  ub = SCIPvarGetUbLocal(var);
1038  if( SCIPisFeasEQ(scip, solval, lb) )
1039  newobjcoeff = (1.0 - alpha)/scalingfactor + alpha * orgobjcoeff;
1040  else if( SCIPisFeasEQ(scip, solval, ub) )
1041  newobjcoeff = - (1.0 - alpha)/scalingfactor + alpha * orgobjcoeff;
1042  else
1043  newobjcoeff = alpha * orgobjcoeff;
1044  }
1045  else
1046  {
1047  SCIP_Real scale = 1.0;
1048 
1049  /* check whether the variable is one of the most fractionals and label if so */
1050  insertFlipCand(mostfracvars, mostfracvals, &nflipcands, maxnflipcands, var, frac);
1051 
1052  /* try to avoid variability; decide randomly if the LP solution can contain some noise. */
1053  if( SCIPisEQ(scip, frac, 0.5) )
1054  {
1055  if( SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0 )
1056  scale = -1.0;
1057  }
1058  else if( frac > 0.5 )
1059  scale = -1.0;
1060 
1061  newobjcoeff = scale * (1.0 - alpha)/scalingfactor + alpha * orgobjcoeff;
1062  }
1063 
1064  /* change one coefficient of the objective */
1065  SCIP_CALL( SCIPchgVarObjDive(scip, var, newobjcoeff) );
1066 
1067  }
1068 
1069  if( heurdata->usefp20 )
1070  {
1071  SCIP_CALL( SCIPbacktrackProbing(probingscip, 0) );
1072  }
1073 
1074  /* change objective coefficients for continuous variables */
1075  for( i = nbinvars+nintvars; i < nvars; i++ )
1076  {
1077  SCIP_CALL( SCIPchgVarObjDive(scip, vars[i], alpha * SCIPvarGetObj(vars[i])) );
1078  }
1079 
1080  SCIPfreeBufferArray(scip, &pseudocands);
1081 
1082  /* initialize cycle check */
1083  minimum = MIN(heurdata->cyclelength, nloops-1);
1084  for( j = 0; j < heurdata->cyclelength; j++ )
1085  cycles[j] = (nloops > j+1) && (REALABS(lastalphas[j] - alpha) < heurdata->alphadiff);
1086 
1087  /* check for j-cycles */
1088  for( i = 0; i < nbinvars+nintvars; i++ )
1089  {
1090  solval = SCIPgetSolVal(scip, heurdata->roundedsol, vars[i]);
1091 
1092  /* cycles exist, iff all solution values are equal */
1093  for( j = 0; j < minimum; j++ )
1094  {
1095  oldsolval = SCIPgetSolVal(scip, lastroundedsols[j], vars[i]);
1096  cycles[j] = cycles[j] && SCIPisFeasEQ(scip, solval, oldsolval);
1097  }
1098  }
1099 
1100  /* force to flip variables at random after a couple of pumping rounds,
1101  * or if a new best solution in the current region has been found
1102  */
1103  assert(heurdata->perturbfreq > 0);
1104  if( nloops % heurdata->perturbfreq == 0 || (heurdata->pertsolfound && SCIPgetNBestSolsFound(scip) > nbestsolsfound) )
1105  {
1106  SCIPdebugMsg(scip, " -> random perturbation\n");
1107  SCIP_CALL( handleCycle(scip, heurdata, vars, nintvars+nbinvars, alpha) );
1108  nbestsolsfound = SCIPgetNBestSolsFound(scip);
1109  }
1110  else
1111  {
1112  minimum = MIN(heurdata->cyclelength, nloops-1);
1113 
1114  for( j = 0; j < minimum; j++ )
1115  {
1116  /* if we got the same rounded solution as in some step before, we have to flip some variables */
1117  if( cycles[j] )
1118  {
1119  /* 1-cycles have a special flipping rule (flip most fractional variables) */
1120  if( j == 0 )
1121  {
1122  SCIPdebugMsg(scip, " -> avoiding 1-cycle: flipping %d candidates\n", nflipcands);
1123  SCIP_CALL( handle1Cycle(scip, heurdata, mostfracvars, nflipcands, alpha) );
1124  }
1125  else
1126  {
1127  SCIPdebugMsg(scip, " -> avoiding %d-cycle by random flip\n", j+1);
1128  SCIP_CALL( handleCycle(scip, heurdata, vars, nintvars+nbinvars, alpha) );
1129  }
1130  break;
1131  }
1132  }
1133  }
1134 
1135  /* the LP with the new (distance) objective is solved */
1136  nlpiterations = SCIPgetNLPIterations(scip);
1137  nlpiterationsleft = adjustedMaxNLPIterations(maxnlpiterations, nsolsfound, nstallloops) - heurdata->nlpiterations;
1138  iterlimit = MAX((int)nlpiterationsleft, MINLPITER);
1139  SCIPdebugMsg(scip, " -> solve LP with iteration limit %d\n", iterlimit);
1140 
1141  if( heurdata->stage3 )
1142  {
1143  SCIP_CALL( SCIPunlinkSol(scip, heurdata->roundedsol) );
1144  }
1145 
1146  retcode = SCIPsolveDiveLP(scip, iterlimit, &lperror, NULL);
1147  lpsolstat = SCIPgetLPSolstat(scip);
1148 
1149  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
1150  * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
1151  */
1152  if( retcode != SCIP_OKAY )
1153  {
1154 #ifndef NDEBUG
1155  if( lpsolstat != SCIP_LPSOLSTAT_UNBOUNDEDRAY )
1156  {
1157  SCIP_CALL( retcode );
1158  }
1159 #endif
1160  SCIPwarningMessage(scip, "Error while solving LP in Feaspump heuristic; LP solve terminated with code <%d>\n", retcode);
1161  SCIPwarningMessage(scip, "This does not affect the remaining solution procedure --> continue\n");
1162  }
1163 
1164  /* update iteration count */
1165  heurdata->nlpiterations += SCIPgetNLPIterations(scip) - nlpiterations;
1166  SCIPdebugMsg(scip, " -> number of iterations: %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ", lperror=%u, lpsolstat=%d\n",
1167  heurdata->nlpiterations, adjustedMaxNLPIterations(maxnlpiterations, nsolsfound, nstallloops), lperror, lpsolstat);
1168 
1169  /* check whether LP was solved optimal */
1170  if( lperror || lpsolstat != SCIP_LPSOLSTAT_OPTIMAL )
1171  break;
1172 
1173  if( heurdata->stage3 )
1174  {
1175  SCIP_Real distance; /* distance of the current rounded solution from the LP solution */
1176 
1177  assert(closestsol != NULL);
1178 
1179  /* calculate distance */
1180  distance = 0.0;
1181  for( i = 0; i < nbinvars+nintvars; i++ )
1182  {
1183  SCIP_Real roundedval;
1184  SCIP_Real lpval;
1185 
1186  roundedval = SCIPgetSolVal(scip, heurdata->roundedsol, vars[i]);
1187  lpval = SCIPvarGetLPSol(vars[i]);
1188  distance += REALABS(roundedval - lpval);
1189  }
1190 
1191  /* copy solution and update minimum distance */
1192  if( SCIPisLT(scip, distance, mindistance) )
1193  {
1194  for( i = 0; i < nbinvars+nintvars; i++ )
1195  {
1196  assert(SCIPisIntegral(scip,SCIPgetSolVal(scip, heurdata->roundedsol, vars[i])));
1197  SCIP_CALL( SCIPsetSolVal(scip, closestsol, vars[i], SCIPgetSolVal(scip, heurdata->roundedsol, vars[i])) );
1198  }
1199  mindistance = distance;
1200  }
1201  }
1202 
1203  /* swap the last solutions */
1204  SCIP_CALL( SCIPunlinkSol(scip, heurdata->roundedsol) );
1205  tmpsol = lastroundedsols[heurdata->cyclelength-1];
1206  for( j = heurdata->cyclelength-1; j > 0; j-- )
1207  {
1208  lastroundedsols[j] = lastroundedsols[j-1];
1209  lastalphas[j] = lastalphas[j-1];
1210  }
1211  lastroundedsols[0] = heurdata->roundedsol;
1212  lastalphas[0] = alpha;
1213  heurdata->roundedsol = tmpsol;
1214 
1215  /* check for improvement in number of fractionals */
1216  nfracs = SCIPgetNLPBranchCands(scip);
1217  if( nfracs < bestnfracs )
1218  {
1219  bestnfracs = nfracs;
1220  nstallloops = 0;
1221  }
1222  else
1223  nstallloops++;
1224 
1225  SCIPdebugMsg(scip, " -> loop finished: %d fractional variables (stall: %d/%d, iterations: %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ")\n",
1226  nfracs, nstallloops, maxstallloops, heurdata->nlpiterations, adjustedMaxNLPIterations(maxnlpiterations, nsolsfound, nstallloops));
1227  }
1228 
1229  /* try final solution, if no more fractional variables are left */
1230  if( nfracs == 0 && !lperror && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
1231  {
1232  success = FALSE;
1233 
1234  SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) );
1235  SCIPdebugMsg(scip, "feasibility pump found solution (%d fractional variables)\n", nfracs);
1236  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
1237  if( success )
1238  *result = SCIP_FOUNDSOL;
1239  }
1240 
1241  /* end diving */
1242  SCIP_CALL( SCIPendDive(scip) );
1243 
1244  /* end probing in order to be able to apply stage 3 */
1245  if( heurdata->usefp20 )
1246  {
1247  SCIP_CALL( SCIPendProbing(probingscip) );
1248  }
1249 
1250  /*if( heurdata->usefp20 )
1251  {
1252  SCIP_CALL( SCIPprintStatistics(probingscip, NULL) );
1253  }*/
1254 
1255  /* only do stage 3 if we have not found a solution yet */
1256  /* only do stage 3 if the distance of the closest infeasible solution to the polyhedron is below a certain threshold */
1257  if( heurdata->stage3 && (*result != SCIP_FOUNDSOL) && SCIPisLE(scip, mindistance, (SCIP_Real) heurdata->neighborhoodsize) )
1258  {
1259  SCIP_Bool cancopy;
1260  assert(closestsol != NULL);
1261  assert(!SCIPisInfinity(scip, mindistance) || nloops == 0);
1262 
1263  /* if we do not use feasibility pump 2.0, we have not created a copied SCIP instance yet */
1264  if( heurdata->usefp20 )
1265  {
1266  assert(probingscip != NULL);
1267  SCIP_CALL( SCIPfreeTransform(probingscip) );
1268  }
1269  else
1270  {
1271  assert(probingscip == NULL);
1272  SCIP_CALL( setupProbingSCIP(scip, &probingscip, &varmapfw, heurdata->copycuts, &success) );
1273  }
1274 
1275  /* check whether there is enough time and memory left */
1276  SCIP_CALL( SCIPcheckCopyLimits(scip, &cancopy) );
1277 
1278  if( cancopy )
1279  {
1280  SCIP_CALL( setupSCIPparamsStage3(scip, probingscip) );
1281 
1282  /* the neighborhood size is double the distance plus another ten percent */
1283  mindistance = SCIPceil(scip, 2.2*mindistance);
1284 
1285  SCIP_CALL( addLocalBranchingConstraint(scip, probingscip, varmapfw, closestsol, mindistance) );
1286 
1287  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
1288  * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
1289  */
1290  SCIP_CALL_ABORT( SCIPsolve(probingscip) );
1291 
1292  /* check, whether a solution was found */
1293  if( SCIPgetNSols(probingscip) > 0 )
1294  {
1295  success = FALSE;
1296  SCIP_CALL( createNewSols(scip, probingscip, varmapfw, heur, &success) );
1297  if( success )
1298  *result = SCIP_FOUNDSOL;
1299  }
1300  }
1301  }
1302 
1303  if( *result == SCIP_FOUNDSOL )
1304  heurdata->nsuccess++;
1305 
1306  /* free hash map and copied SCIP */
1307  if( varmapfw != NULL )
1308  SCIPhashmapFree(&varmapfw);
1309 
1310  if( probingscip != NULL )
1311  {
1312  SCIP_CALL( SCIPfree(&probingscip) );
1313  }
1314 
1315  if( heurdata->stage3 )
1316  {
1317  SCIP_CALL( SCIPfreeSol(scip, &closestsol) );
1318  }
1319 
1320  /* free memory */
1321  for( j = 0; j < heurdata->cyclelength; j++ )
1322  {
1323  SCIP_CALL( SCIPfreeSol(scip, &lastroundedsols[j]) );
1324  }
1325 
1326  SCIPfreeBufferArray(scip, &cycles);
1327  SCIPfreeBufferArray(scip, &lastalphas);
1328  SCIPfreeBufferArray(scip, &lastroundedsols);
1329  SCIPfreeBufferArray(scip, &mostfracvals);
1330  SCIPfreeBufferArray(scip, &mostfracvars);
1331 
1332  SCIPdebugMsg(scip, "feasibility pump finished [%d iterations done].\n", nloops);
1333 
1334 #ifdef SCIP_STATISTIC
1335  if( nfracs == 0 )
1336  {
1337  double objval;
1338  double primalBound;
1339 
1340  objval = SCIPgetSolOrigObj(scip, heurdata->sol);
1341  primalBound = SCIPgetPrimalbound(scip);
1342  SCIPstatisticMessage("feasibility pump found: 1, objval: %f, iterations: %d, primal bound: %f\n", objval, nloops, primalBound);
1343  }
1344  else
1345  {
1346  double primalBound;
1347 
1348  primalBound = SCIPgetPrimalbound(scip);
1349  SCIPstatisticMessage("feasibility pump found: 0, objval: +inf, iterations: %d, primal bound: %f\n", nloops, primalBound);
1350  }
1351 
1352 #endif /* SCIP_STATISTIC */
1353 
1354  return SCIP_OKAY;
1355 }
1356 
1357 
1358 /*
1359  * primal heuristic specific interface methods
1360  */
1361 
1362 /** creates the feaspump primal heuristic and includes it in SCIP */
1364  SCIP* scip /**< SCIP data structure */
1365  )
1366 {
1367  SCIP_HEURDATA* heurdata;
1368  SCIP_HEUR* heur;
1369 
1370  /* create Feaspump primal heuristic data */
1371  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1372 
1373  /* include primal heuristic */
1374  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1376  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecFeaspump, heurdata) );
1377 
1378  assert(heur != NULL);
1379 
1380  /* set non-NULL pointers to callback methods */
1381  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyFeaspump) );
1382  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeFeaspump) );
1383  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitFeaspump) );
1384  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitFeaspump) );
1385  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolFeaspump) );
1386  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolFeaspump) );
1387 
1388  /* add feaspump primal heuristic parameters */
1390  "heuristics/" HEUR_NAME "/maxlpiterquot",
1391  "maximal fraction of diving LP iterations compared to node LP iterations",
1392  &heurdata->maxlpiterquot, FALSE, DEFAULT_MAXLPITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1394  "heuristics/" HEUR_NAME "/objfactor",
1395  "factor by which the regard of the objective is decreased in each round, 1.0 for dynamic",
1396  &heurdata->objfactor, FALSE, DEFAULT_OBJFACTOR, 0.0, 1.0, NULL, NULL) );
1398  "heuristics/" HEUR_NAME "/alpha",
1399  "initial weight of the objective function in the convex combination",
1400  &heurdata->alpha, FALSE, DEFAULT_ALPHA, 0.0, 1.0, NULL, NULL) );
1402  "heuristics/" HEUR_NAME "/alphadiff",
1403  "threshold difference for the convex parameter to perform perturbation",
1404  &heurdata->alphadiff, FALSE, DEFAULT_ALPHADIFF, 0.0, 1.0, NULL, NULL) );
1405 
1406  SCIP_CALL( SCIPaddIntParam(scip,
1407  "heuristics/" HEUR_NAME "/maxlpiterofs",
1408  "additional number of allowed LP iterations",
1409  &heurdata->maxlpiterofs, FALSE, DEFAULT_MAXLPITEROFS, 0, INT_MAX, NULL, NULL) );
1410  SCIP_CALL( SCIPaddIntParam(scip,
1411  "heuristics/" HEUR_NAME "/maxsols",
1412  "total number of feasible solutions found up to which heuristic is called (-1: no limit)",
1413  &heurdata->maxsols, TRUE, DEFAULT_MAXSOLS, -1, INT_MAX, NULL, NULL) );
1414  SCIP_CALL( SCIPaddIntParam(scip,
1415  "heuristics/" HEUR_NAME "/maxloops",
1416  "maximal number of pumping loops (-1: no limit)",
1417  &heurdata->maxloops, TRUE, DEFAULT_MAXLOOPS, -1, INT_MAX, NULL, NULL) );
1418  SCIP_CALL( SCIPaddIntParam(scip,
1419  "heuristics/" HEUR_NAME "/maxstallloops",
1420  "maximal number of pumping rounds without fractionality improvement (-1: no limit)",
1421  &heurdata->maxstallloops, TRUE, DEFAULT_MAXSTALLLOOPS, -1, INT_MAX, NULL, NULL) );
1422  SCIP_CALL( SCIPaddIntParam(scip,
1423  "heuristics/" HEUR_NAME "/minflips",
1424  "minimum number of random variables to flip, if a 1-cycle is encountered",
1425  &heurdata->minflips, TRUE, DEFAULT_MINFLIPS, 1, INT_MAX, NULL, NULL) );
1426  SCIP_CALL( SCIPaddIntParam(scip,
1427  "heuristics/" HEUR_NAME "/cyclelength",
1428  "maximum length of cycles to be checked explicitly in each round",
1429  &heurdata->cyclelength, TRUE, DEFAULT_CYCLELENGTH, 1, 100, NULL, NULL) );
1430  SCIP_CALL( SCIPaddIntParam(scip,
1431  "heuristics/" HEUR_NAME "/perturbfreq",
1432  "number of iterations until a random perturbation is forced",
1433  &heurdata->perturbfreq, TRUE, DEFAULT_PERTURBFREQ, 1, INT_MAX, NULL, NULL) );
1434  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/neighborhoodsize",
1435  "radius (using Manhattan metric) of the neighborhood to be searched in stage 3",
1436  &heurdata->neighborhoodsize, FALSE, DEFAULT_NEIGHBORHOODSIZE, 1, INT_MAX, NULL, NULL) );
1437 
1439  "heuristics/" HEUR_NAME "/beforecuts",
1440  "should the feasibility pump be called at root node before cut separation?",
1441  &heurdata->beforecuts, FALSE, DEFAULT_BEFORECUTS, NULL, NULL) );
1443  "heuristics/" HEUR_NAME "/usefp20",
1444  "should an iterative round-and-propagate scheme be used to find the integral points?",
1445  &heurdata->usefp20, FALSE, DEFAULT_USEFP20, NULL, NULL) );
1447  "heuristics/" HEUR_NAME "/pertsolfound",
1448  "should a random perturbation be performed if a feasible solution was found?",
1449  &heurdata->pertsolfound, FALSE, DEFAULT_PERTSOLFOUND, NULL, NULL) );
1451  "heuristics/" HEUR_NAME "/stage3",
1452  "should we solve a local branching sub-MIP if no solution could be found?",
1453  &heurdata->stage3, FALSE, DEFAULT_STAGE3, NULL, NULL) );
1454  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
1455  "should all active cuts from cutpool be copied to constraints in subproblem?",
1456  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
1457 
1458  return SCIP_OKAY;
1459 }
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip.c:8124
#define DEFAULT_NEIGHBORHOODSIZE
Definition: heur_feaspump.c:61
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:46151
#define SCIP_HEURTIMING_DURINGLPLOOP
Definition: type_timing.h:71
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:8693
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:37672
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5095
#define DEFAULT_MAXSOLS
Definition: heur_feaspump.c:44
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46086
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:814
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip.c:35152
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip.c:41382
#define HEUR_NAME
Definition: heur_feaspump.c:32
static SCIP_DECL_HEURINIT(heurInitFeaspump)
#define HEUR_FREQOFS
Definition: heur_feaspump.c:37
#define DEFAULT_ALPHA
Definition: heur_feaspump.c:55
#define DEFAULT_CYCLELENGTH
Definition: heur_feaspump.c:50
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:42499
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
Definition: scip.c:42448
#define DEFAULT_MAXLPITEROFS
Definition: heur_feaspump.c:43
static SCIP_RETCODE addLocalBranchingConstraint(SCIP *scip, SCIP *probingscip, SCIP_HASHMAP *varmapfw, SCIP_SOL *bestsol, SCIP_Real neighborhoodsize)
static SCIP_DECL_HEUREXITSOL(heurExitsolFeaspump)
#define SCIP_MAXSTRLEN
Definition: def.h:215
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1327
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
Definition: scip.c:42664
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip.c:8092
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip.c:12071
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17222
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45803
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11505
SCIP_RETCODE SCIPsetHeuristics(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5043
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip.c:38881
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2765
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip.c:4126
#define HEUR_FREQ
Definition: heur_feaspump.c:36
SCIP_RETCODE SCIPcopyConsCompression(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip.c:3843
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:45816
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:9340
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIPstatisticMessage
Definition: pub_message.h:104
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5069
#define DEFAULT_COPYCUTS
Definition: heur_feaspump.c:62
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9184
int SCIPheurGetFreqofs(SCIP_HEUR *heur)
Definition: heur.c:1287
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21907
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:7999
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:8723
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip.h:21933
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2903
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
Definition: scip.c:46247
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45751
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:42
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip.c:696
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1102
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip.c:36161
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1260
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4202
SCIP_RETCODE SCIPcopyParamSettings(SCIP *sourcescip, SCIP *targetscip)
Definition: scip.c:3492
SCIP_Real SCIPgetObjNorm(SCIP *scip)
Definition: scip.c:11284
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip.c:46223
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:46211
const char * SCIPgetProbName(SCIP *scip)
Definition: scip.c:10724
#define DEFAULT_MAXSTALLLOOPS
Definition: heur_feaspump.c:48
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip.c:29262
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen)
Definition: misc.c:8710
#define MINLPITER
Definition: heur_feaspump.c:68
#define DEFAULT_RANDSEED
Definition: heur_feaspump.c:70
#define HEUR_USESSUBSCIP
Definition: heur_feaspump.c:40
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip.c:8108
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip.c:15777
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1181
#define HEUR_DESC
Definition: heur_feaspump.c:33
#define DEFAULT_ALPHADIFF
Definition: heur_feaspump.c:56
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip.c:4338
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12410
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip.c:34901
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:8060
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45764
static SCIP_DECL_HEURFREE(heurFreeFeaspump)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip.c:35477
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38044
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip.c:35337
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip.c:4567
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip.c:921
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
Definition: scip.c:3056
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45519
SCIPInterval sign(const SCIPInterval &x)
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip.c:35187
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2798
#define DEFAULT_STAGE3
Definition: heur_feaspump.c:60
#define NULL
Definition: lpi_spx1.cpp:137
#define REALABS(x)
Definition: def.h:159
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:17540
SCIP_RETCODE SCIPunfixParam(SCIP *scip, const char *name)
Definition: scip.c:4504
#define SCIP_CALL(x)
Definition: def.h:306
static SCIP_DECL_HEURCOPY(heurCopyFeaspump)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46112
#define DEFAULT_BEFORECUTS
Definition: heur_feaspump.c:57
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1307
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip.c:36467
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip.c:28769
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
Definition: scip.c:34969
#define DEFAULT_OBJFACTOR
Definition: heur_feaspump.c:52
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip.c:21448
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:37867
public data structures and miscellaneous methods
#define DEFAULT_MINFLIPS
Definition: heur_feaspump.c:49
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
Definition: scip.c:16873
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28854
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:57
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip.c:39073
int SCIPgetNPricers(SCIP *scip)
Definition: scip.c:5644
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:42094
#define DEFAULT_MAXLOOPS
Definition: heur_feaspump.c:47
#define MAX(x, y)
Definition: tclique_def.h:75
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip.c:39843
Objective Feasibility Pump 2.0.
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4625
unsigned int SCIPinitializeRandomSeed(SCIP *scip, int initialseedvalue)
Definition: scip.c:25467
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:37631
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17014
#define HEUR_PRIORITY
Definition: heur_feaspump.c:35
int SCIPgetNSols(SCIP *scip)
Definition: scip.c:38832
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38090
static SCIP_RETCODE handle1Cycle(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **mostfracvars, int nflipcands, SCIP_Real alpha)
Constraint handler for linear constraints in their most general form, .
static SCIP_DECL_HEUREXEC(heurExecFeaspump)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:45827
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip.c:39749
#define SCIP_MAXTREEDEPTH
Definition: def.h:242
static SCIP_RETCODE handleCycle(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, int nbinandintvars, SCIP_Real alpha)
static SCIP_DECL_HEUREXIT(heurExitFeaspump)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:8745
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11631
#define SCIP_REAL_MAX
Definition: def.h:136
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
static void insertFlipCand(SCIP_VAR **mostfracvars, SCIP_Real *mostfracvals, int *nflipcands, int maxnflipcands, SCIP_VAR *var, SCIP_Real frac)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:28897
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:45900
SCIP_RETCODE SCIPchgVarObjDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip.c:34601
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip.c:27323
#define DEFAULT_PERTURBFREQ
Definition: heur_feaspump.c:51
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip.c:8076
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip.c:8872
SCIP_Longint SCIPgetNBestSolsFound(SCIP *scip)
Definition: scip.c:42718
#define SCIP_Real
Definition: def.h:135
#define DEFAULT_PERTSOLFOUND
Definition: heur_feaspump.c:59
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
#define MIN(x, y)
Definition: memory.c:75
#define DEFAULT_MAXLPITERQUOT
Definition: heur_feaspump.c:42
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition: heur.c:1221
#define HEUR_MAXDEPTH
Definition: heur_feaspump.c:38
SCIP_RETCODE SCIPincludeHeurFeaspump(SCIP *scip)
#define SCIP_Longint
Definition: def.h:120
void SCIPsortRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
SCIP_RETCODE SCIPunlinkSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:37836
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip.c:4090
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16717
SCIP_RETCODE SCIPstartDive(SCIP *scip)
Definition: scip.c:34477
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:37909
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45777
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8044
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17232
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip.c:35092
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:46187
#define DEFAULT_USEFP20
Definition: heur_feaspump.c:58
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip.c:35055
static SCIP_RETCODE setupSCIPparamsStage3(SCIP *scip, SCIP *probingscip)
static SCIP_DECL_HEURINITSOL(heurInitsolFeaspump)
SCIP_RETCODE SCIPendDive(SCIP *scip)
Definition: scip.c:34520
#define HEUR_DISPCHAR
Definition: heur_feaspump.c:34
#define SCIP_CALL_ABORT(x)
Definition: def.h:285
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
Definition: scip.c:45949
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1092
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:41182
static SCIP_RETCODE setupSCIPparamsFP2(SCIP *scip, SCIP *probingscip)
static SCIP_Longint adjustedMaxNLPIterations(SCIP_Longint maxnlpiterations, SCIP_Longint nsolsfound, int nstallloops)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38007
default SCIP plugins
static SCIP_RETCODE createNewSols(SCIP *scip, SCIP *subscip, SCIP_HASHMAP *varmapfw, SCIP_HEUR *heur, SCIP_Bool *success)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4258
static SCIP_RETCODE setupProbingSCIP(SCIP *scip, SCIP **probingscip, SCIP_HASHMAP **varmapfw, SCIP_Bool copycuts, SCIP_Bool *success)
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip.c:5020
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:45937
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip.c:4683
#define HEUR_TIMING
Definition: heur_feaspump.c:39
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4176
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip.c:774
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37005