Scippy

GCG

Branch-and-Price & Column Generation for Everyone

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