Detailed Description

Objective Feasibility Pump 2.0.

Author: Timo Berthold; Domenico Salvagnin

#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/heur_feaspump.h"
#include "scip/pub_heur.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nodesel.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_pricer.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_sol.h"
#include "scip/scip_solve.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include <string.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 SCIP_HEURDISPCHAR_OBJDIVING

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

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME "feaspump"

Definition at line 55 of file heur_feaspump.c.

Referenced by setupSCIPparamsFP2(), and setupSCIPparamsStage3().

◆ HEUR_DESC

#define HEUR_DESC "objective feasibility pump 2.0"

Definition at line 56 of file heur_feaspump.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_OBJDIVING

Definition at line 57 of file heur_feaspump.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY -1000000

Definition at line 58 of file heur_feaspump.c.

◆ HEUR_FREQ

#define HEUR_FREQ 20

Definition at line 59 of file heur_feaspump.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 60 of file heur_feaspump.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 61 of file heur_feaspump.c.

◆ HEUR_TIMING

#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE

Definition at line 62 of file heur_feaspump.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 63 of file heur_feaspump.c.

◆ DEFAULT_MAXLPITERQUOT

#define DEFAULT_MAXLPITERQUOT 0.01

maximal fraction of diving LP iterations compared to node LP iterations

Definition at line 65 of file heur_feaspump.c.

◆ DEFAULT_MAXLPITEROFS

#define DEFAULT_MAXLPITEROFS 1000

additional number of allowed LP iterations

Definition at line 66 of file heur_feaspump.c.

◆ DEFAULT_MAXSOLS

#define DEFAULT_MAXSOLS 10

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

Definition at line 67 of file heur_feaspump.c.

◆ DEFAULT_MAXLOOPS

#define DEFAULT_MAXLOOPS 10000

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

Definition at line 70 of file heur_feaspump.c.

◆ DEFAULT_MAXSTALLLOOPS

#define DEFAULT_MAXSTALLLOOPS 10

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

Definition at line 71 of file heur_feaspump.c.

◆ DEFAULT_MINFLIPS

#define DEFAULT_MINFLIPS 10

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

Definition at line 72 of file heur_feaspump.c.

◆ DEFAULT_CYCLELENGTH

#define DEFAULT_CYCLELENGTH 3

maximum length of cycles to be checked explicitly in each round

Definition at line 73 of file heur_feaspump.c.

◆ DEFAULT_PERTURBFREQ

#define DEFAULT_PERTURBFREQ 100

number of iterations until a random perturbation is forced

Definition at line 74 of file heur_feaspump.c.

◆ DEFAULT_OBJFACTOR

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

◆ DEFAULT_ALPHA

#define DEFAULT_ALPHA 1.0

initial weight of the objective function in the convex combination

Definition at line 78 of file heur_feaspump.c.

◆ DEFAULT_ALPHADIFF

#define DEFAULT_ALPHADIFF 1.0

threshold difference for the convex parameter to perform perturbation

Definition at line 79 of file heur_feaspump.c.

◆ DEFAULT_BEFORECUTS

#define DEFAULT_BEFORECUTS TRUE

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

Definition at line 80 of file heur_feaspump.c.

◆ DEFAULT_USEFP20

#define DEFAULT_USEFP20 FALSE

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

Definition at line 81 of file heur_feaspump.c.

◆ DEFAULT_PERTSOLFOUND

#define DEFAULT_PERTSOLFOUND TRUE

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

Definition at line 82 of file heur_feaspump.c.

◆ DEFAULT_STAGE3

#define DEFAULT_STAGE3 FALSE

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

Definition at line 83 of file heur_feaspump.c.

◆ DEFAULT_NEIGHBORHOODSIZE

#define DEFAULT_NEIGHBORHOODSIZE 18

radius of the neighborhood to be searched in stage 3

Definition at line 84 of file heur_feaspump.c.

◆ DEFAULT_COPYCUTS

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

◆ MINLPITER

#define MINLPITER 5000

minimal number of LP iterations allowed in each LP solving call

Definition at line 91 of file heur_feaspump.c.

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED 13

initial random seed

Definition at line 93 of file heur_feaspump.c.

Function Documentation

◆ setupProbingSCIP()

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

References FALSE, NULL, SCIP_CALL, SCIP_MAXTREEDEPTH, SCIP_OKAY, SCIPblkmem(), SCIPcopyConsCompression(), SCIPcopyCuts(), SCIPcreate(), SCIPgetDepth(), SCIPgetNVars(), SCIPhashmapCreate(), setupSCIPparamsFP2(), and TRUE.

◆ setupSCIPparamsFP2()

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

◆ setupSCIPparamsStage3()

static SCIP_RETCODE setupSCIPparamsStage3	(	SCIP *	scip,
		SCIP *	probingscip
	)

static

set appropriate parameters for probing SCIP in Stage 3

Parameters

scip	SCIP data structure
probingscip	sub-SCIP data structure

Definition at line 211 of file heur_feaspump.c.

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

◆ insertFlipCand()

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

References NULL, and updateVariableRounding().

Referenced by setupSCIPparamsStage3().

◆ updateVariableRounding()

static SCIP_RETCODE updateVariableRounding	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata,
		SCIP_VAR *	var,
		SCIP_Real	solval,
		SCIP_Real	alpha,
		SCIP_Real	scalingfactor
	)

static

set solution value in rounded solution and update objective coefficient accordingly

Parameters

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

References handle1Cycle(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarObjDive(), SCIPisEQ(), SCIPisFeasLE(), SCIPisIntegral(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetObj(), and SCIPvarGetUbLocal().

Referenced by handle1Cycle(), handleCycle(), and insertFlipCand().

◆ handle1Cycle()

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

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
scalingfactor	factor to scale the original objective function with

Definition at line 369 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().

◆ handleCycle()

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

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
scalingfactor	factor to scale the original objective function with

Definition at line 415 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().

◆ addLocalBranchingConstraint()

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

References createNewSols(), 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 handleCycle().

◆ createNewSols()

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

References NULL, SCIP_CALL, SCIP_DECL_HEURCOPY(), SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetVarsData(), SCIPhashmapGetImage(), and SCIPtranslateSubSols().

Referenced by addLocalBranchingConstraint().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyFeaspump )

static

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

Definition at line 573 of file heur_feaspump.c.

Referenced by createNewSols().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeFeaspump )

static

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

Definition at line 587 of file heur_feaspump.c.

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitFeaspump )

static

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

Definition at line 607 of file heur_feaspump.c.

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitFeaspump )

static

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

Definition at line 635 of file heur_feaspump.c.

◆ SCIP_DECL_HEURINITSOL()

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

◆ SCIP_DECL_HEUREXITSOL()

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

◆ adjustedMaxNLPIterations()

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

References SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecFeaspump )

static

execution method of primal heuristic

Definition at line 705 of file heur_feaspump.c.

Referenced by adjustedMaxNLPIterations().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ DEFAULT_MAXLPITERQUOT

◆ DEFAULT_MAXLPITEROFS

◆ DEFAULT_MAXSOLS

◆ DEFAULT_MAXLOOPS

◆ DEFAULT_MAXSTALLLOOPS

◆ DEFAULT_MINFLIPS

◆ DEFAULT_CYCLELENGTH

◆ DEFAULT_PERTURBFREQ

◆ DEFAULT_OBJFACTOR

◆ DEFAULT_ALPHA

◆ DEFAULT_ALPHADIFF

◆ DEFAULT_BEFORECUTS

◆ DEFAULT_USEFP20

◆ DEFAULT_PERTSOLFOUND

◆ DEFAULT_STAGE3

◆ DEFAULT_NEIGHBORHOODSIZE

◆ DEFAULT_COPYCUTS

◆ MINLPITER

◆ DEFAULT_RANDSEED

Function Documentation

◆ setupProbingSCIP()

◆ setupSCIPparamsFP2()

◆ setupSCIPparamsStage3()

◆ insertFlipCand()

◆ updateVariableRounding()

◆ handle1Cycle()

◆ handleCycle()

◆ addLocalBranchingConstraint()

◆ createNewSols()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEUREXIT()

◆ SCIP_DECL_HEURINITSOL()

◆ SCIP_DECL_HEUREXITSOL()

◆ adjustedMaxNLPIterations()

◆ SCIP_DECL_HEUREXEC()