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