Detailed Description

Objective Feasibility Pump 2.0.

Author: Timo Berthold; Domenico Salvagnin

#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_NAME "feaspump"

Definition at line 31 of file heur_feaspump.c.

Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXIT(), SCIP_DECL_HEURFREE(), SCIP_DECL_HEURINIT(), SCIPincludeHeurFeaspump(), setupSCIPparamsFP2(), and setupSCIPparamsStage3().

#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

Definition at line 38 of file heur_feaspump.c.

Referenced by SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXITSOL(), and SCIPincludeHeurFeaspump().

#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

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 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

scip	SCIP data structure
probingscip	sub-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

scip	SCIP data structure
probingscip	sub-SCIP data structure
timelimit	time limit for Stage3
memorylimit	memory 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

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 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

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

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

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

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

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 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

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 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

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 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().