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