Scippy

SCIP

Solving Constraint Integer Programs

heur_feaspump.c File Reference

Detailed Description

Objective Feasibility Pump 2.0.

Author
Timo Berthold
Domenico Salvagnin

Definition in file heur_feaspump.c.

#include <assert.h>
#include <string.h>
#include "scip/heur_feaspump.h"
#include "scip/cons_linear.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
 

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, SCIP_Real timelimit, SCIP_Real memorylimit)
 
static void insertFlipCand (SCIP_VAR **mostfracvars, SCIP_Real *mostfracvals, int *nflipcands, int maxnflipcands, SCIP_VAR *var, SCIP_Real frac)
 
static SCIP_RETCODE handle1Cycle (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **mostfracvars, int nflipcands, SCIP_Real alpha)
 
static SCIP_RETCODE handleCycle (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, int nbinandintvars, SCIP_Real alpha)
 
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)
 

Macro Definition Documentation

#define HEUR_DESC   "objective feasibility pump 2.0"

Definition at line 32 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define HEUR_DISPCHAR   'F'

Definition at line 33 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define HEUR_PRIORITY   -1000000

Definition at line 34 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define HEUR_FREQ   20

Definition at line 35 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define HEUR_FREQOFS   0

Definition at line 36 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define HEUR_MAXDEPTH   -1

Definition at line 37 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERLPPLUNGE
#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 39 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define DEFAULT_MAXLPITERQUOT   0.01

maximal fraction of diving LP iterations compared to node LP iterations

Definition at line 41 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define DEFAULT_MAXLPITEROFS   1000

additional number of allowed LP iterations

Definition at line 42 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define DEFAULT_MAXSOLS   10

total number of feasible solutions found up to which heuristic is called (-1: no limit)

Definition at line 43 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define DEFAULT_MAXLOOPS   10000

maximal number of pumping rounds (-1: no limit)

Definition at line 45 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define DEFAULT_MAXSTALLLOOPS   10

maximal number of pumping rounds without fractionality improvement (-1: no limit)

Definition at line 46 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define DEFAULT_MINFLIPS   10

minimum number of random variables to flip, if a 1-cycle is encountered

Definition at line 47 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define DEFAULT_CYCLELENGTH   3

maximum length of cycles to be checked explicitly in each round

Definition at line 48 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define DEFAULT_PERTURBFREQ   100

number of iterations until a random perturbation is forced

Definition at line 49 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#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 50 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define DEFAULT_ALPHA   1.0

initial weight of the objective function in the convex combination

Definition at line 52 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define DEFAULT_ALPHADIFF   1.0

threshold difference for the convex parameter to perform perturbation

Definition at line 53 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define DEFAULT_BEFORECUTS   TRUE

should the feasibility pump be called at root node before cut separation?

Definition at line 54 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define DEFAULT_USEFP20   FALSE

should an iterative round-and-propagate scheme be used to find the integral points?

Definition at line 55 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define DEFAULT_PERTSOLFOUND   TRUE

should a random perturbation be performed if a feasible solution was found?

Definition at line 56 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define DEFAULT_STAGE3   FALSE

should we solve a local branching sub-MIP if no solution could be found?

Definition at line 57 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define DEFAULT_NEIGHBORHOODSIZE   18

radius of the neighborhood to be searched in stage 3

Definition at line 58 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#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 59 of file heur_feaspump.c.

Referenced by SCIPincludeHeurFeaspump().

#define MINLPITER   5000

minimal number of LP iterations allowed in each LP solving call

Definition at line 63 of file heur_feaspump.c.

Referenced by SCIP_DECL_HEUREXEC().

Function Documentation

static SCIP_RETCODE setupProbingSCIP ( SCIP scip,
SCIP **  probingscip,
SCIP_HASHMAP **  varmapfw,
SCIP_Bool  copycuts,
SCIP_Bool success 
)
static
Parameters
scipSCIP data structure
probingscipsub-SCIP data structure
varmapfwmapping of SCIP variables to sub-SCIP variables
copycutsshould all active cuts from cutpool of scip copied to constraints in subscip
successwas copying successful?

Definition at line 101 of file heur_feaspump.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPcopy(), SCIPcopyCuts(), SCIPcreate(), SCIPgetNVars(), SCIPhashmapCreate(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_RETCODE setupSCIPparamsFP2 ( SCIP scip,
SCIP probingscip 
)
static

set appropriate parameters for probing SCIP in FP2

Parameters
scipSCIP data structure
probingscipsub-SCIP data structure

Definition at line 130 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(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_RETCODE setupSCIPparamsStage3 ( SCIP scip,
SCIP probingscip,
SCIP_Real  timelimit,
SCIP_Real  memorylimit 
)
static

set appropriate parameters for probing SCIP in Stage 3

Parameters
scipSCIP data structure
probingscipsub-SCIP data structure
timelimittime limit for Stage3
memorylimitmemory limit for Stage3

Definition at line 168 of file heur_feaspump.c.

References FALSE, HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIPcopyParamSettings(), SCIPfindBranchrule(), SCIPfindNodesel(), SCIPisParamFixed(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetPresolving(), SCIPsetRealParam(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPunfixParam(), SCIPwarningMessage(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

static void insertFlipCand ( SCIP_VAR **  mostfracvars,
SCIP_Real mostfracvals,
int *  nflipcands,
int  maxnflipcands,
SCIP_VAR var,
SCIP_Real  frac 
)
static

checks whether a variable is one of the currently most fractional ones

Parameters
mostfracvarssorted array of the currently most fractional variables
mostfracvalsarray of their fractionality, decreasingly sorted
nflipcandsnumber of fractional variables already labeled to be flipped
maxnflipcandstypically randomized number of maximum amount of variables to flip
varvariable to be checked
fracfractional value of the variable

Definition at line 257 of file heur_feaspump.c.

References NULL.

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_RETCODE handle1Cycle ( SCIP scip,
SCIP_HEURDATA heurdata,
SCIP_VAR **  mostfracvars,
int  nflipcands,
SCIP_Real  alpha 
)
static

flips the roundings of the most fractional variables, if a 1-cycle was found

Parameters
scipSCIP data structure
heurdatadata of this special heuristic
mostfracvarssorted array of the currently most fractional variables
nflipcandsnumber of variables to flip
alphafactor how much the original objective is regarded

Definition at line 303 of file heur_feaspump.c.

References SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarObjDive(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPfeasFrac(), SCIPsetSolVal(), SCIPvarGetLPSol(), and SCIPvarGetObj().

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_RETCODE handleCycle ( SCIP scip,
SCIP_HEURDATA heurdata,
SCIP_VAR **  vars,
int  nbinandintvars,
SCIP_Real  alpha 
)
static

flips the roundings of randomly chosen fractional variables, preferring highly fractional ones, if a longer cycle was found

Parameters
scipSCIP data structure
heurdatadata of this special heuristic
varsarray of all variables
nbinandintvarsnumber of general integer and 0-1 variables
alphafactor how much the original objective is regarded

Definition at line 347 of file heur_feaspump.c.

References MAX, MIN, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarObjDive(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPfeasFrac(), SCIPgetRandomReal(), SCIPsetSolVal(), SCIPvarGetLPSol(), and SCIPvarGetObj().

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_RETCODE addLocalBranchingConstraint ( SCIP scip,
SCIP probingscip,
SCIP_HASHMAP varmapfw,
SCIP_SOL bestsol,
SCIP_Real  neighborhoodsize 
)
static

create the extra constraint of local branching and add it to subscip

Parameters
scipSCIP data structure of the original problem
probingscipSCIP data structure of the subproblem
varmapfwmapping of SCIP variables to sub-SCIP variables
bestsolSCIP solution
neighborhoodsizerhs for LB constraint

Definition at line 396 of file heur_feaspump.c.

References FALSE, NULL, 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 SCIP_DECL_HEUREXEC().

static SCIP_RETCODE createNewSols ( SCIP scip,
SCIP subscip,
SCIP_HASHMAP varmapfw,
SCIP_HEUR heur,
SCIP_Bool success 
)
static

creates new solutions for the original problem by copying the solutions of the subproblem

Parameters
sciporiginal SCIP data structure
subscipSCIP structure of the subproblem
varmapfwmapping of SCIP variables to sub-SCIP variables
heurheuristic structure
successused to store whether new solution was found or not

Definition at line 464 of file heur_feaspump.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcreateSol(), SCIPfreeBufferArray, SCIPgetNOrigVars(), SCIPgetNSols(), SCIPgetSols(), SCIPgetSolVals(), SCIPgetVarsData(), SCIPhashmapGetImage(), SCIPsetSolVals(), SCIPtrySolFree(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_DECL_HEURCOPY ( heurCopyFeaspump  )
static

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 524 of file heur_feaspump.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurFeaspump().

static SCIP_DECL_HEURFREE ( heurFreeFeaspump  )
static

destructor of primal heuristic to free user data (called when SCIP is exiting)

Definition at line 538 of file heur_feaspump.c.

References HEUR_NAME, NULL, SCIP_OKAY, SCIPfreeMemory, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().

static SCIP_DECL_HEURINIT ( heurInitFeaspump  )
static

initialization method of primal heuristic (called after problem was transformed)

Definition at line 558 of file heur_feaspump.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateSol(), SCIPheurGetData(), and SCIPheurGetName().

static SCIP_DECL_HEUREXIT ( heurExitFeaspump  )
static

deinitialization method of primal heuristic (called before transformed problem is freed)

Definition at line 583 of file heur_feaspump.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeSol(), SCIPheurGetData(), and SCIPheurGetName().

static SCIP_DECL_HEURINITSOL ( heurInitsolFeaspump  )
static

solving process initialization method of primal heuristic (called when branch and bound process is about to begin)

Definition at line 604 of file heur_feaspump.c.

References NULL, SCIP_HEURTIMING_DURINGLPLOOP, SCIP_OKAY, SCIPheurGetData(), SCIPheurGetFreqofs(), and SCIPheurSetTimingmask().

static SCIP_DECL_HEUREXITSOL ( heurExitsolFeaspump  )
static

solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)

Definition at line 621 of file heur_feaspump.c.

References HEUR_TIMING, SCIP_OKAY, and SCIPheurSetTimingmask().

static SCIP_Longint adjustedMaxNLPIterations ( SCIP_Longint  maxnlpiterations,
SCIP_Longint  nsolsfound,
int  nstallloops 
)
static

calculates an adjusted maximal number of LP iterations

Parameters
maxnlpiterationsregular maximal number of LP iterations
nsolsfoundtotal number of solutions found so far by SCIP
nstallloopscurrent number of stalling rounds

Definition at line 631 of file heur_feaspump.c.

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_DECL_HEUREXEC ( heurExecFeaspump  )
static

execution method of primal heuristic

Definition at line 650 of file heur_feaspump.c.

References addLocalBranchingConstraint(), adjustedMaxNLPIterations(), createNewSols(), FALSE, handle1Cycle(), handleCycle(), HEUR_NAME, HEUR_TIMING, insertFlipCand(), MAX, MIN, MINLPITER, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_HEURTIMING_DURINGLPLOOP, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_LPSOLSTAT_UNBOUNDEDRAY, SCIP_OKAY, SCIP_Real, SCIP_STAGE_SOLVING, SCIP_STATUS_OPTIMAL, SCIP_VARTYPE_BINARY, SCIPallocBufferArray, SCIPbacktrackProbing(), SCIPceil(), SCIPchgVarObjDive(), SCIPcreateSol(), SCIPdebugMessage, SCIPduplicateBufferArray, SCIPendDive(), SCIPendProbing(), SCIPfeasFrac(), SCIPfixVarProbing(), SCIPfloor(), SCIPfree(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPfreeTransform(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLastDivenode(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetNBestSolsFound(), SCIPgetNLPBranchCands(), SCIPgetNLPIterations(), SCIPgetNNodes(), SCIPgetNPricers(), SCIPgetNSols(), SCIPgetNSolsFound(), SCIPgetObjNorm(), SCIPgetPrimalbound(), SCIPgetPseudoBranchCands(), SCIPgetRandomInt(), SCIPgetRealParam(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPgetSolvingTime(), SCIPgetStage(), SCIPgetStatus(), SCIPgetVarsData(), SCIPhasCurrentNodeLP(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPheurGetData(), SCIPheurGetName(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPheurSetTimingmask(), SCIPinfinity(), SCIPisFeasEQ(), SCIPisFeasLE(), SCIPisFeasZero(), SCIPisGE(), SCIPisInfinity(), SCIPisIntegral(), SCIPisLE(), SCIPisLPSolBasic(), SCIPisLT(), SCIPisStopped(), SCIPlinkLPSol(), SCIPnewProbingNode(), SCIPpropagateProbing(), SCIProundSol(), SCIPsetLongintParam(), SCIPsetSolVal(), SCIPsolve(), SCIPsolveDiveLP(), SCIPsortRealPtr(), SCIPstartDive(), SCIPstartProbing(), SCIPstatisticMessage, SCIPtrySol(), SCIPunlinkSol(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarGetUbLocal(), SCIPwarningMessage(), setupProbingSCIP(), setupSCIPparamsFP2(), and setupSCIPparamsStage3().