Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

Objective Feasibility Pump 2.0.

Author
Timo Berthold
Domenico Salvagnin

Definition in file heur_feaspump.c.

#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
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 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
scipSCIP data structure
probingscipsub-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

◆ 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
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 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
scipSCIP data structure
heurdataheuristic data structure
varvariable
solvalsolution value for this variable
alphaweight of original objective function
scalingfactorfactor 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
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
scalingfactorfactor 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
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
scalingfactorfactor 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
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 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
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 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
maxnlpiterationsregular maximal number of LP iterations
nsolsfoundtotal number of solutions found so far by SCIP
nstallloopscurrent 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().