heur_gcgfeaspump.c File Reference

Detailed Description

Objective Feasibility Pump 2.0.

Author

Timo Berthold

Domenico Salvagnin

Christian Puchert

Definition in file heur_gcgfeaspump.c.

#include <assert.h>
#include <string.h>
#include "heur_gcgfeaspump.h"
#include "gcg.h"
#include "scip/scipdefplugins.h"
#include "scip/cons_linear.h"
#include "scip/misc.h"

Go to the source code of this file.

Data Structures
struct	SCIP_HeurData

Macros
#define	HEUR_NAME   "gcgfeaspump"
#define	HEUR_DESC   "objective feasibility pump 2.0"
#define	HEUR_DISPCHAR   'F'
#define	HEUR_PRIORITY   -1000000
#define	HEUR_FREQ   -1
#define	HEUR_FREQOFS   0
#define	HEUR_MAXDEPTH   -1
#define	HEUR_TIMING   SCIP_HEURTIMING_AFTERPLUNGE
#define	HEUR_USESSUBSCIP   TRUE
#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   1.0
#define	DEFAULT_ALPHADIFF   1.0
#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	setupDivingSCIP (SCIP *scip, SCIP **divingscip, SCIP_HASHMAP **varmapfw, SCIP_Bool copycuts, SCIP_Bool *success)
static SCIP_RETCODE	getDivingLPSol (SCIP *scip, SCIP *divingscip, SCIP_HASHMAP *varmapfw, SCIP_SOL *lpsol)
static SCIP_RETCODE	getNFracs (SCIP *scip, SCIP_SOL *lpsol, int *nfracs)
static SCIP_RETCODE	setupProbingSCIP (SCIP *scip, SCIP **probingscip, SCIP_HASHMAP **varmapfw, SCIP_Bool copycuts, SCIP_Bool *success)
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 *divingscip, SCIP_HASHMAP *varmapfw, SCIP_HEURDATA *heurdata, SCIP_VAR **mostfracvars, int nflipcands, SCIP_Real alpha)
static SCIP_RETCODE	handleCycle (SCIP *scip, SCIP *divingscip, SCIP_HASHMAP *varmapfw, 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_HEURFREE (heurFreeGcgfeaspump)
static	SCIP_DECL_HEURINIT (heurInitGcgfeaspump)
static	SCIP_DECL_HEUREXIT (heurExitGcgfeaspump)
static SCIP_Longint	adjustedMaxNLPIterations (SCIP_Longint maxnlpiterations, SCIP_Longint nsolsfound, int nstallloops)
static	SCIP_DECL_HEUREXEC (heurExecGcgfeaspump)
SCIP_RETCODE	SCIPincludeHeurGcgfeaspump (SCIP *scip)

Macro Definition Documentation

HEUR_NAME

#define HEUR_NAME   "gcgfeaspump"

Definition at line 48 of file heur_gcgfeaspump.c.

HEUR_DESC

#define HEUR_DESC   "objective feasibility pump 2.0"

Definition at line 49 of file heur_gcgfeaspump.c.

HEUR_DISPCHAR

#define HEUR_DISPCHAR   'F'

Definition at line 50 of file heur_gcgfeaspump.c.

HEUR_PRIORITY

#define HEUR_PRIORITY   -1000000

Definition at line 51 of file heur_gcgfeaspump.c.

HEUR_FREQ

#define HEUR_FREQ   -1

Definition at line 52 of file heur_gcgfeaspump.c.

HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 53 of file heur_gcgfeaspump.c.

HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 54 of file heur_gcgfeaspump.c.

HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERPLUNGE

Definition at line 55 of file heur_gcgfeaspump.c.

HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 56 of file heur_gcgfeaspump.c.

DEFAULT_MAXLPITERQUOT

#define DEFAULT_MAXLPITERQUOT   0.01

maximal fraction of diving LP iterations compared to node LP iterations

Definition at line 58 of file heur_gcgfeaspump.c.

DEFAULT_MAXLPITEROFS

#define DEFAULT_MAXLPITEROFS   1000

additional number of allowed LP iterations

Definition at line 59 of file heur_gcgfeaspump.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 60 of file heur_gcgfeaspump.c.

DEFAULT_MAXLOOPS

#define DEFAULT_MAXLOOPS   10000

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

Definition at line 62 of file heur_gcgfeaspump.c.

DEFAULT_MAXSTALLLOOPS

#define DEFAULT_MAXSTALLLOOPS   10

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

Definition at line 63 of file heur_gcgfeaspump.c.

DEFAULT_MINFLIPS

#define DEFAULT_MINFLIPS   10

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

Definition at line 64 of file heur_gcgfeaspump.c.

DEFAULT_CYCLELENGTH

#define DEFAULT_CYCLELENGTH   3

maximum length of cycles to be checked explicitly in each round

Definition at line 65 of file heur_gcgfeaspump.c.

DEFAULT_PERTURBFREQ

#define DEFAULT_PERTURBFREQ   100

number of iterations until a random perturbation is forced

Definition at line 66 of file heur_gcgfeaspump.c.

DEFAULT_OBJFACTOR

#define DEFAULT_OBJFACTOR   1.0

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 67 of file heur_gcgfeaspump.c.

DEFAULT_ALPHADIFF

#define DEFAULT_ALPHADIFF   1.0

threshold difference for the convex parameter to perform perturbation

Definition at line 69 of file heur_gcgfeaspump.c.

DEFAULT_USEFP20

#define DEFAULT_USEFP20   FALSE

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

Definition at line 70 of file heur_gcgfeaspump.c.

DEFAULT_PERTSOLFOUND

#define DEFAULT_PERTSOLFOUND   TRUE

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

Definition at line 71 of file heur_gcgfeaspump.c.

DEFAULT_STAGE3

#define DEFAULT_STAGE3   FALSE

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

Definition at line 72 of file heur_gcgfeaspump.c.

DEFAULT_NEIGHBORHOODSIZE

#define DEFAULT_NEIGHBORHOODSIZE   18

radius of the neighborhood to be searched in stage 3

Definition at line 73 of file heur_gcgfeaspump.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 74 of file heur_gcgfeaspump.c.

MINLPITER

#define MINLPITER   5000

minimal number of LP iterations allowed in each LP solving call

Definition at line 78 of file heur_gcgfeaspump.c.

DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   13

initial random seed

Definition at line 80 of file heur_gcgfeaspump.c.

Function Documentation

setupDivingSCIP()

static SCIP_RETCODE setupDivingSCIP ( SCIP *  scip, SCIP **  divingscip, SCIP_HASHMAP **  varmapfw, SCIP_Bool  copycuts, SCIP_Bool *  success  )

static

copies SCIP to diving SCIP and creates variable hashmap

Parameters

scip	SCIP data structure
divingscip	diving 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 probingscip
success	was copying successful?

Definition at line 116 of file heur_gcgfeaspump.c.

Referenced by SCIP_DECL_HEUREXEC().

getDivingLPSol()

static SCIP_RETCODE getDivingLPSol ( SCIP *  scip, SCIP *  divingscip, SCIP_HASHMAP *  varmapfw, SCIP_SOL *  lpsol  )

static

Parameters

scip	SCIP data structure
divingscip	diving SCIP data structure
varmapfw	mapping of SCIP variables to sub-SCIP variables
lpsol	data structure to store the solution

Definition at line 186 of file heur_gcgfeaspump.c.

Referenced by SCIP_DECL_HEUREXEC().

getNFracs()

static SCIP_RETCODE getNFracs ( SCIP *  scip, SCIP_SOL *  lpsol, int *  nfracs  )

static

Parameters

scip	SCIP data structure
lpsol	data structure to store the solution
nfracs	pointer to store number of fractional variables

Definition at line 226 of file heur_gcgfeaspump.c.

Referenced by SCIP_DECL_HEUREXEC().

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 probingscip
success	was copying successful?

Definition at line 255 of file heur_gcgfeaspump.c.

Referenced by SCIP_DECL_HEUREXEC().

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 284 of file heur_gcgfeaspump.c.

Referenced by SCIP_DECL_HEUREXEC().

handle1Cycle()

static SCIP_RETCODE handle1Cycle ( SCIP *  scip, SCIP *  divingscip, SCIP_HASHMAP *  varmapfw, 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
divingscip	diving SCIP data structure
varmapfw	mapping of SCIP variables to sub-SCIP variables
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 330 of file heur_gcgfeaspump.c.

Referenced by SCIP_DECL_HEUREXEC().

handleCycle()

static SCIP_RETCODE handleCycle ( SCIP *  scip, SCIP *  divingscip, SCIP_HASHMAP *  varmapfw, 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
divingscip	diving SCIP data structure
varmapfw	mapping of SCIP variables to sub-SCIP variables
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 379 of file heur_gcgfeaspump.c.

Referenced by SCIP_DECL_HEUREXEC().

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 434 of file heur_gcgfeaspump.c.

Referenced by SCIP_DECL_HEUREXEC().

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 502 of file heur_gcgfeaspump.c.

Referenced by SCIP_DECL_HEUREXEC().

SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeGcgfeaspump  )

static

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

Definition at line 562 of file heur_gcgfeaspump.c.

References HEUR_NAME.

SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitGcgfeaspump  )

static

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

Definition at line 582 of file heur_gcgfeaspump.c.

References DEFAULT_RANDSEED, and HEUR_NAME.

SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitGcgfeaspump  )

static

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

Definition at line 610 of file heur_gcgfeaspump.c.

References HEUR_NAME.

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 634 of file heur_gcgfeaspump.c.

Referenced by SCIP_DECL_HEUREXEC().

SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecGcgfeaspump  )

static

execution method of primal heuristic

Definition at line 653 of file heur_gcgfeaspump.c.

References addLocalBranchingConstraint(), adjustedMaxNLPIterations(), createNewSols(), GCGgetMasterprob(), getDivingLPSol(), getNFracs(), handle1Cycle(), handleCycle(), HEUR_NAME, insertFlipCand(), MINLPITER, setupDivingSCIP(), and setupProbingSCIP().

SCIPincludeHeurGcgfeaspump()

SCIP_RETCODE SCIPincludeHeurGcgfeaspump

(

SCIP *

scip

)

creates the gcgfeaspump primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1424 of file heur_gcgfeaspump.c.

References DEFAULT_ALPHADIFF, DEFAULT_COPYCUTS, DEFAULT_CYCLELENGTH, DEFAULT_MAXLOOPS, DEFAULT_MAXLPITEROFS, DEFAULT_MAXLPITERQUOT, DEFAULT_MAXSOLS, DEFAULT_MAXSTALLLOOPS, DEFAULT_MINFLIPS, DEFAULT_NEIGHBORHOODSIZE, DEFAULT_OBJFACTOR, DEFAULT_PERTSOLFOUND, DEFAULT_PERTURBFREQ, DEFAULT_STAGE3, DEFAULT_USEFP20, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, and HEUR_USESSUBSCIP.

Referenced by SCIPincludeGcgPlugins().