heur_undercover.c File Reference

Detailed Description

Undercover primal heuristic for MINLPs.

Author

Timo Berthold

Ambros Gleixner

The undercover heuristic is designed for mixed-integer nonlinear programs and tries to fix a subset of variables such as to make each constraint linear or convex. For this purpose it solves a binary program to automatically determine the minimum number of variable fixings necessary. As fixing values, we use values from the LP relaxation, the NLP relaxation, or the incumbent solution.

Definition in file heur_undercover.c.

#include <assert.h>
#include <string.h>
#include "scip/scip.h"
#include "scip/scipdefplugins.h"
#include "scip/heur_undercover.h"
#include "nlpi/exprinterpret.h"

Go to the source code of this file.

Macros
#define	HEUR_NAME   "undercover"
#define	HEUR_DESC   "solves a sub-CIP determined by a set covering approach"
#define	HEUR_DISPCHAR   'U'
#define	HEUR_PRIORITY   -1110000
#define	HEUR_FREQ   0
#define	HEUR_FREQOFS   0
#define	HEUR_MAXDEPTH   -1
#define	HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE
#define	HEUR_USESSUBSCIP   TRUE
#define	DEFAULT_FIXINGALTS   "li"
#define	DEFAULT_MAXNODES   (SCIP_Longint)500
#define	DEFAULT_MINNODES   (SCIP_Longint)500
#define	DEFAULT_NODESOFS   (SCIP_Longint)500
#define	DEFAULT_CONFLICTWEIGHT   1000.0
#define	DEFAULT_CUTOFFWEIGHT   1.0
#define	DEFAULT_INFERENCEWEIGHT   1.0
#define	DEFAULT_MAXCOVERSIZEVARS   1.0
#define	DEFAULT_MAXCOVERSIZECONSS   SCIP_REAL_MAX
#define	DEFAULT_MINCOVEREDREL   0.15
#define	DEFAULT_MINCOVEREDABS   5
#define	DEFAULT_MINIMPROVE   0.0
#define	DEFAULT_NODESQUOT   0.1
#define	DEFAULT_RECOVERDIV   0.9
#define	DEFAULT_MAXBACKTRACKS   6
#define	DEFAULT_MAXRECOVERS   0
#define	DEFAULT_MAXREORDERS   1
#define	DEFAULT_COVERINGOBJ   'u'
#define	DEFAULT_FIXINGORDER   'v'
#define	DEFAULT_BEFORECUTS   TRUE
#define	DEFAULT_FIXINTFIRST   FALSE
#define	DEFAULT_LOCKSROUNDING   TRUE
#define	DEFAULT_ONLYCONVEXIFY   FALSE
#define	DEFAULT_POSTNLP   TRUE
#define	DEFAULT_COVERBD   FALSE
#define	DEFAULT_REUSECOVER   FALSE
#define	DEFAULT_COPYCUTS   TRUE
#define	COVERINGOBJS   "cdlmtu"
#define	FIXINGORDERS   "CcVv"
#define	MAXNLPFAILS   1
#define	MAXPOSTNLPFAILS   1
#define	MINTIMELEFT   1.0
#define	SUBMIPSETUPCOSTS   200

Functions
static SCIP_Bool	varIsFixed (SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_Bool global)
static SCIP_Bool	termIsConstant (SCIP *scip, SCIP_VAR *var, SCIP_Real coeff, SCIP_Bool global)
static SCIP_Bool	termIsConvex (SCIP *scip, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool sign)
static void	incCounters (int *termcounter, int *conscounter, SCIP_Bool *consmarker, int idx)
static SCIP_RETCODE	updateTimelimit (SCIP *scip, SCIP_CLOCK *clck, SCIP_Real *timelimit)
static SCIP_RETCODE	processNlRow (SCIP *scip, SCIP_NLROW *nlrow, SCIP_EXPRINT *exprint, struct HessianData *hessiandata, SCIP *coveringscip, int nvars, SCIP_VAR **coveringvars, int *termcounter, int *conscounter, SCIP_Bool *consmarker, SCIP_Bool globalbounds, SCIP_Bool onlyconvexify, SCIP_Bool *success)
static SCIP_RETCODE	createCoveringProblem (SCIP *scip, SCIP *coveringscip, SCIP_VAR **coveringvars, SCIP_Bool globalbounds, SCIP_Bool onlyconvexify, SCIP_Bool coverbd, char coveringobj, SCIP_Bool *success)
static SCIP_RETCODE	forbidCover (SCIP *scip, int nvars, SCIP_VAR **vars, int coversize, int *cover, int diversification, SCIP_Bool *success, SCIP_Bool *infeas)
static SCIP_RETCODE	createConflict (SCIP *scip, int bdlen, SCIP_VAR **bdvars, SCIP_BOUNDTYPE *bdtypes, SCIP_Real *bdbounds, SCIP_Bool local, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool *success)
static SCIP_RETCODE	solveCoveringProblem (SCIP *coveringscip, int ncoveringvars, SCIP_VAR **coveringvars, int *coversize, int *cover, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Real objlimit, SCIP_Bool *success)
static SCIP_RETCODE	computeFixingOrder (SCIP *scip, SCIP_HEURDATA *heurdata, int nvars, SCIP_VAR **vars, int coversize, int *cover, int lastfailed, SCIP_Bool *success)
static SCIP_RETCODE	getFixingValue (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var, SCIP_Real *val, char fixalt, SCIP_Bool *success, int bdlen, SCIP_VAR **bdvars, SCIP_BOUNDTYPE *bdtypes, SCIP_Real *oldbounds)
static void	calculateAlternatives (SCIP *scip, SCIP_VAR *var, SCIP_Real fixval, int *nalternatives, SCIP_Real *alternatives)
static SCIP_RETCODE	roundFixingValue (SCIP *scip, SCIP_Real *val, SCIP_VAR *var, SCIP_Bool locksrounding)
static SCIP_RETCODE	copySol (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_SOL *subsol, SCIP_SOL **newsol)
static SCIP_RETCODE	solveSubproblem (SCIP *scip, SCIP_HEUR *heur, int coversize, int *cover, SCIP_Real *fixingvals, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Longint nodelimit, SCIP_Longint nstallnodes, SCIP_Bool *validsolved, SCIP_SOL **sol, SCIP_Longint *nusednodes)
static SCIP_RETCODE	performFixing (SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_Bool *infeas, int *bdlen, SCIP_VAR **bdvars, SCIP_BOUNDTYPE *bdtypes, SCIP_Real *bdbounds, SCIP_Real *oldbounds)
static SCIP_RETCODE	fixAndPropagate (SCIP *scip, SCIP_HEURDATA *heurdata, int *cover, int coversize, SCIP_Real *fixingvals, int *bdlen, SCIP_VAR **bdvars, SCIP_BOUNDTYPE *bdtypes, SCIP_Real *bdbounds, SCIP_Real *oldbounds, int *nfixedints, int *nfixedconts, int *lastfailed, SCIP_Bool *infeas)
static SCIP_RETCODE	SCIPapplyUndercover (SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Longint nstallnodes)
static	SCIP_DECL_HEURCOPY (heurCopyUndercover)
static	SCIP_DECL_HEURFREE (heurFreeUndercover)
static	SCIP_DECL_HEURINITSOL (heurInitsolUndercover)
static	SCIP_DECL_HEUREXITSOL (heurExitsolUndercover)
static	SCIP_DECL_HEUREXEC (heurExecUndercover)
SCIP_RETCODE	SCIPincludeHeurUndercover (SCIP *scip)
SCIP_RETCODE	SCIPcomputeCoverUndercover (SCIP *scip, int *coversize, SCIP_VAR **cover, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Real objlimit, SCIP_Bool globalbounds, SCIP_Bool onlyconvexify, SCIP_Bool coverbd, char coveringobj, SCIP_Bool *success)

Macro Definition Documentation

#define HEUR_NAME   "undercover"

Definition at line 44 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover(), and solveSubproblem().

#define HEUR_DESC   "solves a sub-CIP determined by a set covering approach"

Definition at line 45 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define HEUR_DISPCHAR   'U'

Definition at line 46 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define HEUR_PRIORITY   -1110000

Definition at line 47 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define HEUR_FREQ   0

Definition at line 48 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define HEUR_FREQOFS   0

Definition at line 49 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define HEUR_MAXDEPTH   -1

Definition at line 50 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE

Definition at line 51 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define HEUR_USESSUBSCIP   TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 52 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_FIXINGALTS   "li"

sequence of fixing values used: 'l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution

Definition at line 55 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_MAXNODES   (SCIP_Longint)500

maximum number of nodes to regard in the subproblem

Definition at line 57 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_MINNODES   (SCIP_Longint)500

minimum number of nodes to regard in the subproblem

Definition at line 58 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_NODESOFS   (SCIP_Longint)500

number of nodes added to the contingent of the total nodes

Definition at line 59 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_CONFLICTWEIGHT   1000.0

weight for conflict score in fixing order

Definition at line 61 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_CUTOFFWEIGHT   1.0

weight for cutoff score in fixing order

Definition at line 62 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_INFERENCEWEIGHT   1.0

weight for inference score in fixing order

Definition at line 63 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_MAXCOVERSIZEVARS   1.0

maximum coversize (as fraction of total number of variables)

Definition at line 64 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_MAXCOVERSIZECONSS   SCIP_REAL_MAX

maximum coversize (as ratio to the percentage of non-affected constraints)

Definition at line 65 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_MINCOVEREDREL   0.15

minimum percentage of nonlinear constraints in the original problem

Definition at line 66 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_MINCOVEREDABS   5

minimum number of nonlinear constraints in the original problem

Definition at line 67 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_MINIMPROVE   0.0

factor by which heuristic should at least improve the incumbent

Definition at line 68 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_NODESQUOT   0.1

subproblem nodes in relation to nodes of the original problem

Definition at line 69 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_RECOVERDIV   0.9

fraction of covering variables in the last cover which need to change their value when recovering

Definition at line 70 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_MAXBACKTRACKS   6

maximum number of backtracks

Definition at line 72 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_MAXRECOVERS   0

maximum number of recoverings

Definition at line 73 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_MAXREORDERS   1

maximum number of reorderings of the fixing order

Definition at line 74 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_COVERINGOBJ   'u'

objective function of the covering problem

Definition at line 76 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_FIXINGORDER   'v'

order in which variables should be fixed

Definition at line 77 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_BEFORECUTS   TRUE

should undercover called at root node before cut separation?

Definition at line 79 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_FIXINTFIRST   FALSE

should integer variables in the cover be fixed first?

Definition at line 80 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_LOCKSROUNDING   TRUE

shall LP values for integer vars be rounded according to locks?

Definition at line 81 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_ONLYCONVEXIFY   FALSE

should we only fix/dom.red. variables creating nonconvexity?

Definition at line 82 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_POSTNLP   TRUE

should the NLP heuristic be called to polish a feasible solution?

Definition at line 83 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_COVERBD   FALSE

should bounddisjunction constraints be covered (or just copied)?

Definition at line 84 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define DEFAULT_REUSECOVER   FALSE

shall the cover be re-used if a conflict was added after an infeasible subproblem?

Definition at line 85 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#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 86 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define COVERINGOBJS   "cdlmtu"

list of objective functions of the covering problem

Definition at line 93 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define FIXINGORDERS   "CcVv"

list of orders in which variables can be fixed

Definition at line 94 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

#define MAXNLPFAILS   1

maximum number of fails after which we give up solving the NLP relaxation

Definition at line 95 of file heur_undercover.c.

Referenced by getFixingValue(), and SCIPapplyUndercover().

#define MAXPOSTNLPFAILS   1

maximum number of fails after which we give up calling NLP local search

Definition at line 96 of file heur_undercover.c.

Referenced by SCIPapplyUndercover().

#define MINTIMELEFT   1.0

don't start expensive parts of the heuristics if less than this amount of time left

Definition at line 97 of file heur_undercover.c.

Referenced by SCIPapplyUndercover().

#define SUBMIPSETUPCOSTS   200

number of nodes equivalent for the costs for setting up the sub-CIP

Definition at line 98 of file heur_undercover.c.

Function Documentation

static SCIP_Bool varIsFixed ( SCIP *  scip, SCIP_VAR *  var, SCIP_Real  val, SCIP_Bool  global  )

static

determines, whether a variable is fixed to the given value

Parameters

scip	SCIP data structure
var	variable to check
val	value to check
global	should global bounds be used?

Definition at line 164 of file heur_undercover.c.

References SCIP_Bool, SCIPisFeasEQ(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().

Referenced by createCoveringProblem().

static SCIP_Bool termIsConstant ( SCIP *  scip, SCIP_VAR *  var, SCIP_Real  coeff, SCIP_Bool  global  )

static

determines, whether a term is already constant, because the variable is fixed or the coefficient is zero

Parameters

scip	SCIP data structure
var	variable to check
coeff	coefficient to check
global	should global bounds be used?

Definition at line 184 of file heur_undercover.c.

References SCIPisFeasEQ(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by createCoveringProblem(), and processNlRow().

static SCIP_Bool termIsConvex ( SCIP *  scip, SCIP_Real  lhs, SCIP_Real  rhs, SCIP_Bool  sign  )

static

determines, whether a term is convex

Parameters

scip	SCIP data structure
lhs	left hand side of the constraint
rhs	right hand side of the constraint
sign	signature of the term

Definition at line 206 of file heur_undercover.c.

References SCIPisInfinity().

Referenced by processNlRow().

static void incCounters ( int *  termcounter, int *  conscounter, SCIP_Bool *  consmarker, int  idx  )

static

increases counters

Parameters

termcounter	array to count in how many nonlinear terms a variable appears
conscounter	array to count in how many constraints a variable appears
consmarker	was this variable already counted for this constraint?
idx	problem index of the variable

Definition at line 219 of file heur_undercover.c.

References TRUE.

Referenced by createCoveringProblem(), and processNlRow().

static SCIP_RETCODE updateTimelimit ( SCIP *  scip, SCIP_CLOCK *  clck, SCIP_Real *  timelimit  )

static

update time limit

Parameters

scip	SCIP data structure
clck	clock timer
timelimit	time limit

Definition at line 238 of file heur_undercover.c.

References SCIP_CALL, SCIP_OKAY, SCIPgetClockTime(), SCIPresetClock(), and SCIPstartClock().

Referenced by SCIPapplyUndercover().

static SCIP_RETCODE processNlRow ( SCIP *  scip, SCIP_NLROW *  nlrow, SCIP_EXPRINT *  exprint, struct HessianData *  hessiandata, SCIP *  coveringscip, int  nvars, SCIP_VAR **  coveringvars, int *  termcounter, int *  conscounter, SCIP_Bool *  consmarker, SCIP_Bool  globalbounds, SCIP_Bool  onlyconvexify, SCIP_Bool *  success  )

static

analyzes a nonlinear row and adds constraints and fixings to the covering problem

Parameters

scip	original SCIP data structure
nlrow	nonlinear row representation of a nonlinear constraint
exprint	expression interpreter for computing sparsity pattern of the Hessian; if NULL, we will simply fix all variables in the expression tree
hessiandata	working memory for retrieving dense sparsity of Hessian matrices
coveringscip	SCIP data structure for the covering problem
nvars	number of variables
coveringvars	array to store the covering problem's variables
termcounter	counter array for number of nonlinear nonzeros per variable
conscounter	counter array for number of nonlinear constraints per variable
consmarker	marker array if constraint has been counted in conscounter
globalbounds	should global bounds on variables be used instead of local bounds at focus node?
onlyconvexify	should we only fix/dom.red. variables creating nonconvexity?
success	pointer to store whether row was processed successfully

Definition at line 254 of file heur_undercover.c.

References BMSclearMemoryArray, SCIP_QuadElement::coef, FALSE, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, incCounters(), NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRINTCAPABILITY_HESSIAN, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPcreateConsSetcover(), SCIPcreateSol(), SCIPdebugMessage, SCIPexprintCompile(), SCIPexprintGetCapability(), SCIPexprintHessianSparsityDense(), SCIPexprtreeGetNVars(), SCIPexprtreeGetVars(), SCIPfixVar(), SCIPgetSolVals(), SCIPlinkCurrentSol(), SCIPnlrowGetExprtree(), SCIPnlrowGetLhs(), SCIPnlrowGetName(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetQuadElems(), SCIPnlrowGetQuadVars(), SCIPnlrowGetRhs(), SCIPreallocBufferArray, SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetName(), SCIPvarGetProbindex(), termIsConstant(), termIsConvex(), and TRUE.

Referenced by createCoveringProblem().

static SCIP_RETCODE createCoveringProblem ( SCIP *  scip, SCIP *  coveringscip, SCIP_VAR **  coveringvars, SCIP_Bool  globalbounds, SCIP_Bool  onlyconvexify, SCIP_Bool  coverbd, char  coveringobj, SCIP_Bool *  success  )

static

creates the covering problem to determine a number of variables to be fixed

Parameters

scip	original SCIP data structure
coveringscip	SCIP data structure for the covering problem
coveringvars	array to store the covering problem's variables
globalbounds	should global bounds on variables be used instead of local bounds at focus node?
onlyconvexify	should we only fix/dom.red. variables creating nonconvexity?
coverbd	should bounddisjunction constraints be covered (or just copied)?
coveringobj	objective function of the covering problem
success	pointer to store whether the problem was created successfully

Definition at line 545 of file heur_undercover.c.

References BMSclearMemoryArray, FALSE, incCounters(), MAX, MIN, NULL, processNlRow(), SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_MULTAGGR, SCIP_VARTYPE_BINARY, SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPblkmem(), SCIPcalcHashtableSize(), SCIPchgVarLb(), SCIPchgVarObj(), SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNActiveConss(), SCIPcreateConsLinear(), SCIPcreateConsSetpack(), SCIPcreateProb(), SCIPcreateVar(), SCIPdebugMessage, SCIPerrorMessage, SCIPexprintCreate(), SCIPexprintFree(), SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetBinaryVarIndicator(), SCIPgetBinvarRepresentative(), SCIPgetLhsCoefsSOC(), SCIPgetLhsQuadratic(), SCIPgetLhsVarsSOC(), SCIPgetNegatedVar(), SCIPgetNLhsVarsSOC(), SCIPgetNLPNlRows(), SCIPgetNlRowQuadratic(), SCIPgetNlRowSOC(), SCIPgetNNLPNlRows(), SCIPgetNVarsAnd(), SCIPgetNVarsBounddisjunction(), SCIPgetProbName(), SCIPgetResultantAnd(), SCIPgetRhsCoefSOC(), SCIPgetRhsQuadratic(), SCIPgetRhsVarSOC(), SCIPgetVarsAnd(), SCIPgetVarsBounddisjunction(), SCIPgetVarsData(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapInsert(), SCIPinfinity(), SCIPisConcaveQuadratic(), SCIPisConvexQuadratic(), SCIPisInfinity(), SCIPisNLPConstructed(), SCIPreleaseCons(), SCIPsnprintf(), SCIPstatistic, SCIPstatisticPrintf, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNegatedVar(), SCIPvarGetNegationVar(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetProbindex(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsActive(), SCIPvarIsNegated(), termIsConstant(), TRUE, and varIsFixed().

Referenced by SCIPapplyUndercover(), and SCIPcomputeCoverUndercover().

static SCIP_RETCODE forbidCover ( SCIP *  scip, int  nvars, SCIP_VAR **  vars, int  coversize, int *  cover, int  diversification, SCIP_Bool *  success, SCIP_Bool *  infeas  )

static

adds a constraint to the covering problem to forbid the given cover

Parameters

scip	SCIP data structure of the covering problem
nvars	number of variables
vars	variable array
coversize	size of the cover
cover	problem indices of the variables in the cover
diversification	how many unfixed variables have to change their value?
success	pointer to store whether the cutoff constraint was created successfully
infeas	pointer to store whether the cutoff proves (local or global) infeasibility

Definition at line 1335 of file heur_undercover.c.

References FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateConsLinear(), SCIPcreateConsSetcover(), SCIPfreeBufferArray, SCIPgetNegatedVar(), SCIPinfinity(), SCIPisFeasGE(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetLbLocal(), and TRUE.

Referenced by SCIPapplyUndercover().

static SCIP_RETCODE createConflict ( SCIP *  scip, int  bdlen, SCIP_VAR **  bdvars, SCIP_BOUNDTYPE *  bdtypes, SCIP_Real *  bdbounds, SCIP_Bool  local, SCIP_Bool  dynamic, SCIP_Bool  removable, SCIP_Bool *  success  )

static

adds a set covering or bound disjunction constraint to the original problem

Parameters

scip	SCIP data structure
bdlen	length of bound disjunction
bdvars	array of variables in bound disjunction
bdtypes	array of bound types in bound disjunction
bdbounds	array of bounds in bound disjunction
local	is constraint valid only locally?
dynamic	is constraint subject to aging?
removable	should the relaxation be removed from the LP due to aging or cleanup?
success	pointer to store whether the cutoff constraint was created successfully

Definition at line 1458 of file heur_undercover.c.

References FALSE, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPaddConsLocal(), SCIPallocBufferArray, SCIPcreateConsBounddisjunction(), SCIPcreateConsLogicor(), SCIPfreeBufferArrayNull, SCIPgetNegatedVar(), SCIPisFeasEQ(), SCIPisFeasZero(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarIsBinary(), and TRUE.

Referenced by SCIPapplyUndercover().

static SCIP_RETCODE solveCoveringProblem ( SCIP *  coveringscip, int  ncoveringvars, SCIP_VAR **  coveringvars, int *  coversize, int *  cover, SCIP_Real  timelimit, SCIP_Real  memorylimit, SCIP_Real  objlimit, SCIP_Bool *  success  )

static

solve covering problem

Parameters

coveringscip	SCIP data structure for the covering problem
ncoveringvars	number of the covering problem's variables
coveringvars	array of the covering problem's variables
coversize	size of the computed cover
cover	array to store indices of the variables in the computed cover (should be ready to hold ncoveringvars entries)
timelimit	time limit
memorylimit	memory limit
objlimit	upper bound on the cover size
success	feasible cover found?

Definition at line 1558 of file heur_undercover.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_Real, SCIPallocBufferArray, SCIPdebug, SCIPdebugMessage, SCIPfindBranchrule(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetNOrigVars(), SCIPgetNSols(), SCIPgetSolOrigObj(), SCIPgetSolVals(), SCIPisParamFixed(), SCIPprintSol(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetRealParam(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPsolve(), SCIPsumepsilon(), SCIPvarGetObj(), SCIPwarningMessage(), and TRUE.

Referenced by SCIPapplyUndercover(), and SCIPcomputeCoverUndercover().

static SCIP_RETCODE computeFixingOrder ( SCIP *  scip, SCIP_HEURDATA *  heurdata, int  nvars, SCIP_VAR **  vars, int  coversize, int *  cover, int  lastfailed, SCIP_Bool *  success  )

static

computes fixing order and returns whether order has really been changed

Parameters

scip	original SCIP data structure
heurdata	heuristic data
nvars	number of variables in the original problem
vars	variables in the original problem
coversize	size of the cover
cover	problem indices of the variables in the cover
lastfailed	position in cover array of the variable the fixing of which yielded infeasibility in last dive (or >= coversize, in which case *success is always TRUE)
success	has order really been changed?

Definition at line 1674 of file heur_undercover.c.

References FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetVarAvgInferenceCutoffScore(), SCIPgetVarConflictScore(), SCIPinfinity(), SCIPsortDownRealInt(), SCIPsortRealInt(), SCIPvarIsIntegral(), and TRUE.

Referenced by SCIPapplyUndercover().

static SCIP_RETCODE getFixingValue ( SCIP *  scip, SCIP_HEURDATA *  heurdata, SCIP_VAR *  var, SCIP_Real *  val, char  fixalt, SCIP_Bool *  success, int  bdlen, SCIP_VAR **  bdvars, SCIP_BOUNDTYPE *  bdtypes, SCIP_Real *  oldbounds  )

static

gets fixing value

Parameters

scip	original SCIP data structure
heurdata	heuristic data
var	variable in the original problem
val	buffer for returning fixing value
fixalt	source of the fixing value: 'l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution
success	could value be retrieved successfully?
bdlen	current length of probing path
bdvars	array of variables with bound changes along probing path
bdtypes	array of bound types in bound disjunction
oldbounds	array of bounds before fixing

Definition at line 1785 of file heur_undercover.c.

References FALSE, MAXNLPFAILS, NULL, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_NLPPAR_VERBLEVEL, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_NLPSOLSTAT_GLOBOPT, SCIP_NLPSOLSTAT_LOCOPT, SCIP_OKAY, SCIP_Real, SCIPchgVarBoundsDiveNLP(), SCIPdebug, SCIPdebugMessage, SCIPgetBestSol(), SCIPgetNLPSolstat(), SCIPgetSolVal(), SCIPisGE(), SCIPisLE(), SCIPisNLPConstructed(), SCIPsetNLPInitialGuessSol(), SCIPsetNLPIntPar(), SCIPsolveDiveNLP(), SCIPstartDiveNLP(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetNLPSol(), SCIPvarGetUbLocal(), and TRUE.

Referenced by fixAndPropagate().

static void calculateAlternatives ( SCIP *  scip, SCIP_VAR *  var, SCIP_Real  fixval, int *  nalternatives, SCIP_Real *  alternatives  )

static

calculates up to four alternative values for backtracking, if fixing the variable failed. The alternatives are the two bounds of the variable, and the averages of the bounds and the fixing value. For infinite bounds, fixval +/- abs(fixval) will be used instead.

Parameters

scip	original SCIP data structure
var	variable to calculate alternatives for
fixval	reference fixing value
nalternatives	number of fixing values computed
alternatives	array to store the alternative fixing values

Definition at line 1929 of file heur_undercover.c.

References SCIP_Real, SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasZero(), SCIPisInfinity(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), and SCIPvarIsIntegral().

Referenced by fixAndPropagate().

static SCIP_RETCODE roundFixingValue ( SCIP *  scip, SCIP_Real *  val, SCIP_VAR *  var, SCIP_Bool  locksrounding  )

static

rounds the given fixing value

Parameters

scip	original SCIP data structure
val	fixing value to be rounded
var	corresponding variable
locksrounding	shall we round according to locks? (otherwise to nearest integer)

Definition at line 2010 of file heur_undercover.c.

References SCIP_OKAY, SCIP_Real, SCIPfeasCeil(), SCIPfeasFloor(), SCIPfeasFrac(), SCIPisFeasIntegral(), SCIPvarGetNLocksDown(), and SCIPvarGetNLocksUp().

Referenced by fixAndPropagate().

static SCIP_RETCODE copySol ( SCIP *  scip, SCIP *  subscip, SCIP_VAR **  subvars, SCIP_SOL *  subsol, SCIP_SOL **  newsol  )

static

copy the solution of the subproblem to newsol

Parameters

scip	original SCIP data structure
subscip	SCIP structure of the subproblem
subvars	the variables of the subproblem
subsol	solution of the subproblem
newsol	solution to the original problem

Definition at line 2055 of file heur_undercover.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetNOrigVars(), SCIPgetSolVals(), SCIPgetVarsData(), and SCIPsetSolVals().

Referenced by solveSubproblem().

static SCIP_RETCODE solveSubproblem ( SCIP *  scip, SCIP_HEUR *  heur, int  coversize, int *  cover, SCIP_Real *  fixingvals, SCIP_Real  timelimit, SCIP_Real  memorylimit, SCIP_Longint  nodelimit, SCIP_Longint  nstallnodes, SCIP_Bool *  validsolved, SCIP_SOL **  sol, SCIP_Longint *  nusednodes  )

static

solve subproblem and pass best feasible solution to original SCIP instance

Parameters

scip	SCIP data structure of the original problem
heur	heuristic data structure
coversize	size of the cover
cover	problem indices of the variables in the cover
fixingvals	fixing values for the variables in the cover
timelimit	time limit
memorylimit	memory limit
nodelimit	node limit
nstallnodes	number of stalling nodes for the subproblem
validsolved	was problem constructed from a valid copy and solved (proven optimal or infeasible)?
sol	best solution found in subproblem (if feasible); *sol must be NULL, solution will be created
nusednodes	number of nodes used for solving the subproblem

Definition at line 2096 of file heur_undercover.c.

References copySol(), FALSE, HEUR_NAME, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PARAMEMPHASIS_FEASIBILITY, SCIP_PARAMSETTING_AGGRESSIVE, SCIP_PARAMSETTING_FAST, SCIP_Real, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_OPTIMAL, SCIPallocBufferArray, SCIPblkmem(), SCIPcalcHashtableSize(), SCIPchgVarLbGlobal(), SCIPchgVarUbGlobal(), SCIPcopy(), SCIPcopyCuts(), SCIPcreate(), SCIPcreateSol(), SCIPdebug, SCIPdebugMessage, SCIPfree(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetLowerbound(), SCIPgetNNodes(), SCIPgetNSols(), SCIPgetSols(), SCIPgetStatus(), SCIPgetUpperbound(), SCIPgetVarsData(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPheurGetData(), SCIPisInfinity(), SCIPisParamFixed(), SCIPprintStatistics(), SCIPsetBoolParam(), SCIPsetEmphasis(), SCIPsetHeuristics(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetRealParam(), SCIPsolve(), SCIPtrySol(), SCIPunfixParam(), SCIPwarningMessage(), and TRUE.

Referenced by SCIPapplyUndercover().

static SCIP_RETCODE performFixing ( SCIP *  scip, SCIP_VAR *  var, SCIP_Real  val, SCIP_Bool *  infeas, int *  bdlen, SCIP_VAR **  bdvars, SCIP_BOUNDTYPE *  bdtypes, SCIP_Real *  bdbounds, SCIP_Real *  oldbounds  )

static

perform fixing of a variable and record bound disjunction information

Parameters

scip	SCIP data structure
var	variable to fix
val	fixing value
infeas	pointer to store whether the fixing lead to infeasibility
bdlen	current length of bound disjunction
bdvars	array of variables in bound disjunction
bdtypes	array of bound types in bound disjunction
bdbounds	array of bounds in bound disjunction
oldbounds	array of bounds before fixing

Definition at line 2326 of file heur_undercover.c.

References FALSE, MAX, MIN, NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), SCIPdebugMessage, SCIPfeasCeil(), SCIPgetNVars(), SCIPisFeasIntegral(), SCIPisLbBetter(), SCIPisUbBetter(), SCIPnewProbingNode(), SCIPpropagateProbing(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and SCIPvarIsIntegral().

Referenced by fixAndPropagate().

static SCIP_RETCODE fixAndPropagate ( SCIP *  scip, SCIP_HEURDATA *  heurdata, int *  cover, int  coversize, SCIP_Real *  fixingvals, int *  bdlen, SCIP_VAR **  bdvars, SCIP_BOUNDTYPE *  bdtypes, SCIP_Real *  bdbounds, SCIP_Real *  oldbounds, int *  nfixedints, int *  nfixedconts, int *  lastfailed, SCIP_Bool *  infeas  )

static

Parameters

scip	original SCIP data structure
heurdata	heuristic data structure
cover	array with indices of the variables in the computed cover
coversize	size of the cover
fixingvals	fixing values for the variables in the cover
bdlen	current length of bound disjunction along the probing path
bdvars	array of variables in bound disjunction
bdtypes	array of bound types in bound disjunction
bdbounds	array of bounds in bound disjunction
oldbounds	array of bounds before fixing
nfixedints	pointer to store number of fixed integer variables
nfixedconts	pointer to store number of fixed continuous variables
lastfailed	position in cover array of the variable the fixing of which yielded infeasibility
infeas	pointer to store whether fix-and-propagate led to an infeasibility

Definition at line 2438 of file heur_undercover.c.

References calculateAlternatives(), FALSE, getFixingValue(), MAX, MIN, NULL, performFixing(), roundFixingValue(), SCIP_Bool, SCIP_CALL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPbacktrackProbing(), SCIPdebugMessage, SCIPendProbing(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetLPSolstat(), SCIPgetProbingDepth(), SCIPgetVars(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPisIntegral(), SCIPstartProbing(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), and TRUE.

Referenced by SCIPapplyUndercover().

static SCIP_RETCODE SCIPapplyUndercover ( SCIP *  scip, SCIP_HEUR *  heur, SCIP_RESULT *  result, SCIP_Real  timelimit, SCIP_Real  memorylimit, SCIP_Longint  nstallnodes  )

static

main procedure of the undercover heuristic

Parameters

scip	original SCIP data structure
heur	heuristic data structure
result	result data structure
timelimit	time limit
memorylimit	memory limit
nstallnodes	number of stalling nodes for the subproblem

Definition at line 2637 of file heur_undercover.c.

References computeFixingOrder(), createConflict(), createCoveringProblem(), FALSE, fixAndPropagate(), forbidCover(), MAX, MAXNLPFAILS, MAXPOSTNLPFAILS, MIN, MINTIMELEFT, NULL, SCIP_Bool, SCIP_CALL, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_FOUNDSOL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIPallocBufferArray, SCIPapplyHeurSubNlp(), SCIPconshdlrGetNActiveConss(), SCIPcreate(), SCIPcreateClock(), SCIPdebugMessage, SCIPendDiveNLP(), SCIPfeasCeil(), SCIPfree(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPfreeClock(), SCIPfreeSol(), SCIPfreeTransform(), SCIPgetClockTime(), SCIPgetDepth(), SCIPgetIntParam(), SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetNConss(), SCIPgetNNlpis(), SCIPgetRealParam(), SCIPgetVarsData(), SCIPheurGetData(), SCIPincludeDefaultPlugins(), SCIPisFeasEQ(), SCIPisNLPConstructed(), SCIPreleaseVar(), SCIPstartClock(), SCIPstatistic, SCIPstatisticPrintf, SCIPvarGetLbGlobal(), solveCoveringProblem(), solveSubproblem(), TRUE, and updateTimelimit().

static SCIP_DECL_HEURCOPY ( heurCopyUndercover  )

static

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

Definition at line 3061 of file heur_undercover.c.

static SCIP_DECL_HEURFREE ( heurFreeUndercover  )

static

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

Definition at line 3075 of file heur_undercover.c.

static SCIP_DECL_HEURINITSOL ( heurInitsolUndercover  )

static

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

Definition at line 3096 of file heur_undercover.c.

static SCIP_DECL_HEUREXITSOL ( heurExitsolUndercover  )

static

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

Definition at line 3168 of file heur_undercover.c.

static SCIP_DECL_HEUREXEC ( heurExecUndercover  )

static

execution method of primal heuristic

Definition at line 3190 of file heur_undercover.c.

SCIP_RETCODE SCIPincludeHeurUndercover

(

SCIP *

scip

)

creates the undercover primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 3326 of file heur_undercover.c.

References COVERINGOBJS, DEFAULT_BEFORECUTS, DEFAULT_CONFLICTWEIGHT, DEFAULT_COPYCUTS, DEFAULT_COVERBD, DEFAULT_COVERINGOBJ, DEFAULT_CUTOFFWEIGHT, DEFAULT_FIXINGALTS, DEFAULT_FIXINGORDER, DEFAULT_FIXINTFIRST, DEFAULT_INFERENCEWEIGHT, DEFAULT_LOCKSROUNDING, DEFAULT_MAXBACKTRACKS, DEFAULT_MAXCOVERSIZECONSS, DEFAULT_MAXCOVERSIZEVARS, DEFAULT_MAXNODES, DEFAULT_MAXRECOVERS, DEFAULT_MAXREORDERS, DEFAULT_MINCOVEREDABS, DEFAULT_MINCOVEREDREL, DEFAULT_MINIMPROVE, DEFAULT_MINNODES, DEFAULT_NODESOFS, DEFAULT_NODESQUOT, DEFAULT_ONLYCONVEXIFY, DEFAULT_POSTNLP, DEFAULT_RECOVERDIV, DEFAULT_REUSECOVER, FALSE, FIXINGORDERS, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, NULL, SCIP_CALL, SCIP_LONGINT_MAX, SCIP_OKAY, SCIP_REAL_MAX, SCIP_REAL_MIN, SCIPaddBoolParam(), SCIPaddCharParam(), SCIPaddIntParam(), SCIPaddLongintParam(), SCIPaddRealParam(), SCIPaddStringParam(), SCIPallocMemory, SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurExitsol(), SCIPsetHeurFree(), SCIPsetHeurInitsol(), and TRUE.

Referenced by SCIPincludeDefaultPlugins().

SCIP_RETCODE SCIPcomputeCoverUndercover	(	SCIP *	scip,
		int *	coversize,
		SCIP_VAR **	cover,
		SCIP_Real	timelimit,
		SCIP_Real	memorylimit,
		SCIP_Real	objlimit,
		SCIP_Bool	globalbounds,
		SCIP_Bool	onlyconvexify,
		SCIP_Bool	coverbd,
		char	coveringobj,
		SCIP_Bool *	success
	)

computes a minimal set of covering variables

Parameters

scip	SCIP data structure
coversize	buffer for the size of the computed cover
cover	pointer to store the variables (of the original SCIP) in the computed cover (should be ready to hold SCIPgetNVars(scip) entries)
timelimit	time limit
memorylimit	memory limit
objlimit	objective limit: upper bound on coversize
globalbounds	should global bounds on variables be used instead of local bounds at focus node?
onlyconvexify	should we only fix/dom.red. variables creating nonconvexity?
coverbd	should bounddisjunction constraints be covered (or just copied)?
coveringobj	objective function of the covering problem ('b'ranching status, influenced nonlinear 'c'onstraints/'t'erms, 'd'omain size, 'l'ocks, 'm'in of up/down locks, 'u'nit penalties, constraint 'v'iolation)
success	feasible cover found?

Definition at line 3472 of file heur_undercover.c.

References createCoveringProblem(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcreate(), SCIPdebugMessage, SCIPfree(), SCIPfreeBufferArray, SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetVarsData(), SCIPincludeDefaultPlugins(), SCIPreleaseVar(), and solveCoveringProblem().