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