Objective Feasibility Pump 2.0.
Definition in file heur_feaspump.c.
#include <assert.h>
#include <string.h>
#include "scip/heur_feaspump.h"
#include "scip/cons_linear.h"
#include "scip/pub_misc.h"
#include "scip/scipdefplugins.h"
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "feaspump" |
#define | HEUR_DESC "objective feasibility pump 2.0" |
#define | HEUR_DISPCHAR 'F' |
#define | HEUR_PRIORITY -1000000 |
#define | HEUR_FREQ 20 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE |
#define | HEUR_USESSUBSCIP FALSE |
#define | DEFAULT_MAXLPITERQUOT 0.01 |
#define | DEFAULT_MAXLPITEROFS 1000 |
#define | DEFAULT_MAXSOLS 10 |
#define | DEFAULT_MAXLOOPS 10000 |
#define | DEFAULT_MAXSTALLLOOPS 10 |
#define | DEFAULT_MINFLIPS 10 |
#define | DEFAULT_CYCLELENGTH 3 |
#define | DEFAULT_PERTURBFREQ 100 |
#define | DEFAULT_OBJFACTOR 0.1 |
#define | DEFAULT_ALPHA 1.0 |
#define | DEFAULT_ALPHADIFF 1.0 |
#define | DEFAULT_BEFORECUTS TRUE |
#define | DEFAULT_USEFP20 FALSE |
#define | DEFAULT_PERTSOLFOUND TRUE |
#define | DEFAULT_STAGE3 FALSE |
#define | DEFAULT_NEIGHBORHOODSIZE 18 |
#define | DEFAULT_COPYCUTS TRUE |
#define | MINLPITER 5000 |
#define | DEFAULT_RANDSEED 13 |
Functions | |
static SCIP_RETCODE | setupProbingSCIP (SCIP *scip, SCIP **probingscip, SCIP_HASHMAP **varmapfw, SCIP_Bool copycuts, SCIP_Bool *success) |
static SCIP_RETCODE | setupSCIPparamsFP2 (SCIP *scip, SCIP *probingscip) |
static SCIP_RETCODE | setupSCIPparamsStage3 (SCIP *scip, SCIP *probingscip) |
static void | insertFlipCand (SCIP_VAR **mostfracvars, SCIP_Real *mostfracvals, int *nflipcands, int maxnflipcands, SCIP_VAR *var, SCIP_Real frac) |
static SCIP_RETCODE | updateVariableRounding (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var, SCIP_Real solval, SCIP_Real alpha, SCIP_Real scalingfactor) |
static SCIP_RETCODE | handle1Cycle (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **mostfracvars, int nflipcands, SCIP_Real alpha, SCIP_Real scalingfactor) |
static SCIP_RETCODE | handleCycle (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, int nbinandintvars, SCIP_Real alpha, SCIP_Real scalingfactor) |
static SCIP_RETCODE | addLocalBranchingConstraint (SCIP *scip, SCIP *probingscip, SCIP_HASHMAP *varmapfw, SCIP_SOL *bestsol, SCIP_Real neighborhoodsize) |
static SCIP_RETCODE | createNewSols (SCIP *scip, SCIP *subscip, SCIP_HASHMAP *varmapfw, SCIP_HEUR *heur, SCIP_Bool *success) |
static | SCIP_DECL_HEURCOPY (heurCopyFeaspump) |
static | SCIP_DECL_HEURFREE (heurFreeFeaspump) |
static | SCIP_DECL_HEURINIT (heurInitFeaspump) |
static | SCIP_DECL_HEUREXIT (heurExitFeaspump) |
static | SCIP_DECL_HEURINITSOL (heurInitsolFeaspump) |
static | SCIP_DECL_HEUREXITSOL (heurExitsolFeaspump) |
static SCIP_Longint | adjustedMaxNLPIterations (SCIP_Longint maxnlpiterations, SCIP_Longint nsolsfound, int nstallloops) |
static | SCIP_DECL_HEUREXEC (heurExecFeaspump) |
SCIP_RETCODE | SCIPincludeHeurFeaspump (SCIP *scip) |
#define HEUR_NAME "feaspump" |
Definition at line 32 of file heur_feaspump.c.
Referenced by setupSCIPparamsFP2(), and setupSCIPparamsStage3().
#define HEUR_DESC "objective feasibility pump 2.0" |
Definition at line 33 of file heur_feaspump.c.
#define HEUR_DISPCHAR 'F' |
Definition at line 34 of file heur_feaspump.c.
#define HEUR_PRIORITY -1000000 |
Definition at line 35 of file heur_feaspump.c.
#define HEUR_FREQ 20 |
Definition at line 36 of file heur_feaspump.c.
#define HEUR_FREQOFS 0 |
Definition at line 37 of file heur_feaspump.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 38 of file heur_feaspump.c.
#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE |
Definition at line 39 of file heur_feaspump.c.
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 40 of file heur_feaspump.c.
#define DEFAULT_MAXLPITERQUOT 0.01 |
maximal fraction of diving LP iterations compared to node LP iterations
Definition at line 42 of file heur_feaspump.c.
#define DEFAULT_MAXLPITEROFS 1000 |
additional number of allowed LP iterations
Definition at line 43 of file heur_feaspump.c.
#define DEFAULT_MAXSOLS 10 |
total number of feasible solutions found up to which heuristic is called (-1: no limit)
Definition at line 44 of file heur_feaspump.c.
#define DEFAULT_MAXLOOPS 10000 |
maximal number of pumping rounds (-1: no limit)
Definition at line 47 of file heur_feaspump.c.
#define DEFAULT_MAXSTALLLOOPS 10 |
maximal number of pumping rounds without fractionality improvement (-1: no limit)
Definition at line 48 of file heur_feaspump.c.
#define DEFAULT_MINFLIPS 10 |
minimum number of random variables to flip, if a 1-cycle is encountered
Definition at line 49 of file heur_feaspump.c.
#define DEFAULT_CYCLELENGTH 3 |
maximum length of cycles to be checked explicitly in each round
Definition at line 50 of file heur_feaspump.c.
#define DEFAULT_PERTURBFREQ 100 |
number of iterations until a random perturbation is forced
Definition at line 51 of file heur_feaspump.c.
#define DEFAULT_OBJFACTOR 0.1 |
factor by which the regard of the objective is decreased in each round, 1.0 for dynamic, depending on solutions already found
Definition at line 52 of file heur_feaspump.c.
#define DEFAULT_ALPHA 1.0 |
initial weight of the objective function in the convex combination
Definition at line 55 of file heur_feaspump.c.
#define DEFAULT_ALPHADIFF 1.0 |
threshold difference for the convex parameter to perform perturbation
Definition at line 56 of file heur_feaspump.c.
#define DEFAULT_BEFORECUTS TRUE |
should the feasibility pump be called at root node before cut separation?
Definition at line 57 of file heur_feaspump.c.
#define DEFAULT_USEFP20 FALSE |
should an iterative round-and-propagate scheme be used to find the integral points?
Definition at line 58 of file heur_feaspump.c.
#define DEFAULT_PERTSOLFOUND TRUE |
should a random perturbation be performed if a feasible solution was found?
Definition at line 59 of file heur_feaspump.c.
#define DEFAULT_STAGE3 FALSE |
should we solve a local branching sub-MIP if no solution could be found?
Definition at line 60 of file heur_feaspump.c.
#define DEFAULT_NEIGHBORHOODSIZE 18 |
radius of the neighborhood to be searched in stage 3
Definition at line 61 of file heur_feaspump.c.
#define DEFAULT_COPYCUTS TRUE |
should all active cuts from the cutpool of the original SCIP be copied to constraints of the subscip
Definition at line 62 of file heur_feaspump.c.
#define MINLPITER 5000 |
minimal number of LP iterations allowed in each LP solving call
Definition at line 68 of file heur_feaspump.c.
#define DEFAULT_RANDSEED 13 |
initial random seed
Definition at line 70 of file heur_feaspump.c.
|
static |
scip | SCIP data structure |
probingscip | sub-SCIP data structure |
varmapfw | mapping of SCIP variables to sub-SCIP variables |
copycuts | should all active cuts from cutpool of scip copied to constraints in subscip |
success | was copying successful? |
Definition at line 107 of file heur_feaspump.c.
References FALSE, SCIP_CALL, SCIP_MAXTREEDEPTH, SCIP_OKAY, SCIPblkmem(), SCIPcopyConsCompression(), SCIPcopyCuts(), SCIPcreate(), SCIPgetDepth(), SCIPgetNVars(), SCIPhashmapCreate(), setupSCIPparamsFP2(), and TRUE.
|
static |
set appropriate parameters for probing SCIP in FP2
scip | SCIP data structure |
probingscip | sub-SCIP data structure |
Definition at line 143 of file heur_feaspump.c.
References FALSE, HEUR_NAME, SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIPisParamFixed(), SCIPsetBoolParam(), SCIPsetHeuristics(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetPresolving(), SCIPunfixParam(), SCIPwarningMessage(), setupSCIPparamsStage3(), and TRUE.
Referenced by setupProbingSCIP().
|
static |
set appropriate parameters for probing SCIP in Stage 3
scip | SCIP data structure |
probingscip | sub-SCIP data structure |
Definition at line 187 of file heur_feaspump.c.
References FALSE, HEUR_NAME, insertFlipCand(), SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_Real, SCIPcopyLimits(), SCIPcopyParamSettings(), SCIPfindBranchrule(), SCIPfindNodesel(), SCIPisParamFixed(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPunfixParam(), SCIPwarningMessage(), and TRUE.
Referenced by setupSCIPparamsFP2().
|
static |
checks whether a variable is one of the currently most fractional ones
mostfracvars | sorted array of the currently most fractional variables |
mostfracvals | array of their fractionality, decreasingly sorted |
nflipcands | number of fractional variables already labeled to be flipped |
maxnflipcands | typically randomized number of maximum amount of variables to flip |
var | variable to be checked |
frac | fractional value of the variable |
Definition at line 257 of file heur_feaspump.c.
References updateVariableRounding().
Referenced by setupSCIPparamsStage3().
|
static |
set solution value in rounded solution and update objective coefficient accordingly
scip | SCIP data structure |
heurdata | heuristic data structure |
var | variable |
solval | solution value for this variable |
alpha | weight of original objective function |
scalingfactor | factor to scale the original objective function with |
Definition at line 303 of file heur_feaspump.c.
References handle1Cycle(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarObjDive(), SCIPisEQ(), SCIPisFeasLE(), SCIPisIntegral(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetObj(), and SCIPvarGetUbLocal().
Referenced by handle1Cycle(), handleCycle(), and insertFlipCand().
|
static |
flips the roundings of the most fractional variables, if a 1-cycle was found
scip | SCIP data structure |
heurdata | data of this special heuristic |
mostfracvars | sorted array of the currently most fractional variables |
nflipcands | number of variables to flip |
alpha | factor how much the original objective is regarded |
scalingfactor | factor to scale the original objective function with |
Definition at line 345 of file heur_feaspump.c.
References handleCycle(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetSolVal(), SCIPisFeasIntegral(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetUbLocal(), and updateVariableRounding().
Referenced by updateVariableRounding().
|
static |
flips the roundings of randomly chosen fractional variables, preferring highly fractional ones, if a longer cycle was found
scip | SCIP data structure |
heurdata | data of this special heuristic |
vars | array of all variables |
nbinandintvars | number of general integer and 0-1 variables |
alpha | factor how much the original objective is regarded |
scalingfactor | factor to scale the original objective function with |
Definition at line 391 of file heur_feaspump.c.
References addLocalBranchingConstraint(), MAX, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPceil(), SCIPfeasFrac(), SCIPfloor(), SCIPgetSolVal(), SCIPisFeasIntegral(), SCIPrandomGetReal(), SCIPvarGetLPSol(), and updateVariableRounding().
Referenced by handle1Cycle().
|
static |
create the extra constraint of local branching and add it to subscip
scip | SCIP data structure of the original problem |
probingscip | SCIP data structure of the subproblem |
varmapfw | mapping of SCIP variables to sub-SCIP variables |
bestsol | SCIP solution |
neighborhoodsize | rhs for LB constraint |
Definition at line 443 of file heur_feaspump.c.
References createNewSols(), FALSE, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPaddCons(), SCIPallocBufferArray, SCIPchgVarObj(), SCIPcreateConsLinear(), SCIPfreeBufferArray, SCIPgetProbName(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPhashmapGetImage(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetType(), and TRUE.
Referenced by handleCycle().
|
static |
creates new solutions for the original problem by copying the solutions of the subproblem
scip | original SCIP data structure |
subscip | SCIP structure of the subproblem |
varmapfw | mapping of SCIP variables to sub-SCIP variables |
heur | heuristic structure |
success | used to store whether new solution was found or not |
Definition at line 511 of file heur_feaspump.c.
References FALSE, SCIP_CALL, SCIP_DECL_HEURCOPY(), SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcreateSol(), SCIPfreeBufferArray, SCIPgetNOrigVars(), SCIPgetNSols(), SCIPgetSols(), SCIPgetSolVals(), SCIPgetVarsData(), SCIPhashmapGetImage(), SCIPsetSolVals(), SCIPtrySolFree(), and TRUE.
Referenced by addLocalBranchingConstraint().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 571 of file heur_feaspump.c.
Referenced by createNewSols().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 585 of file heur_feaspump.c.
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 605 of file heur_feaspump.c.
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 633 of file heur_feaspump.c.
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 657 of file heur_feaspump.c.
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
Definition at line 674 of file heur_feaspump.c.
|
static |
calculates an adjusted maximal number of LP iterations
maxnlpiterations | regular maximal number of LP iterations |
nsolsfound | total number of solutions found so far by SCIP |
nstallloops | current number of stalling rounds |
Definition at line 684 of file heur_feaspump.c.
References SCIP_DECL_HEUREXEC().
|
static |
execution method of primal heuristic
Definition at line 703 of file heur_feaspump.c.
Referenced by adjustedMaxNLPIterations().