Scippy

SCIP

Solving Constraint Integer Programs

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

Referenced by SCIPincludeHeurUndercover().

#define FIXINGORDERS   "CcVv"

list of orders in which variables can be fixed

Definition at line 92 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 93 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 94 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 95 of file heur_undercover.c.

Referenced by SCIP_DECL_HEUREXEC(), and SCIPapplyUndercover().

#define SUBMIPSETUPCOSTS   200

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

Definition at line 96 of file heur_undercover.c.

Referenced by SCIP_DECL_HEUREXEC().

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
scipSCIP data structure
varvariable to check
valvalue to check
globalshould global bounds be used?

Definition at line 162 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
scipSCIP data structure
varvariable to check
coeffcoefficient to check
globalshould global bounds be used?

Definition at line 182 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
scipSCIP data structure
lhsleft hand side of the constraint
rhsright hand side of the constraint
signsignature of the term

Definition at line 204 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
termcounterarray to count in how many nonlinear terms a variable appears
conscounterarray to count in how many constraints a variable appears
consmarkerwas this variable already counted for this constraint?
idxproblem index of the variable

Definition at line 217 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
scipSCIP data structure
clckclock timer
timelimittime limit

Definition at line 236 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
sciporiginal SCIP data structure
nlrownonlinear row representation of a nonlinear constraint
exprintexpression interpreter for computing sparsity pattern of the Hessian; if NULL, we will simply fix all variables in the expression tree
hessiandataworking memory for retrieving dense sparsity of Hessian matrices
coveringscipSCIP data structure for the covering problem
nvarsnumber of variables
coveringvarsarray to store the covering problem's variables
termcountercounter array for number of nonlinear nonzeros per variable
conscountercounter array for number of nonlinear constraints per variable
consmarkermarker array if constraint has been counted in conscounter
globalboundsshould global bounds on variables be used instead of local bounds at focus node?
onlyconvexifyshould we only fix/dom.red. variables creating nonconvexity?
successpointer to store whether row was processed successfully

Definition at line 252 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
sciporiginal SCIP data structure
coveringscipSCIP data structure for the covering problem
coveringvarsarray to store the covering problem's variables
globalboundsshould global bounds on variables be used instead of local bounds at focus node?
onlyconvexifyshould we only fix/dom.red. variables creating nonconvexity?
coverbdshould bounddisjunction constraints be covered (or just copied)?
coveringobjobjective function of the covering problem
successpointer to store whether the problem was created successfully

Definition at line 543 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
scipSCIP data structure of the covering problem
nvarsnumber of variables
varsvariable array
coversizesize of the cover
coverproblem indices of the variables in the cover
diversificationhow many unfixed variables have to change their value?
successpointer to store whether the cutoff constraint was created successfully
infeaspointer to store whether the cutoff proves (local or global) infeasibility

Definition at line 1333 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
scipSCIP data structure
bdlenlength of bound disjunction
bdvarsarray of variables in bound disjunction
bdtypesarray of bound types in bound disjunction
bdboundsarray of bounds in bound disjunction
localis constraint valid only locally?
dynamicis constraint subject to aging?
removableshould the relaxation be removed from the LP due to aging or cleanup?
successpointer to store whether the cutoff constraint was created successfully

Definition at line 1456 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
coveringscipSCIP data structure for the covering problem
ncoveringvarsnumber of the covering problem's variables
coveringvarsarray of the covering problem's variables
coversizesize of the computed cover
coverarray to store indices of the variables in the computed cover (should be ready to hold ncoveringvars entries)
timelimittime limit
memorylimitmemory limit
objlimitupper bound on the cover size
successfeasible cover found?

Definition at line 1556 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
sciporiginal SCIP data structure
heurdataheuristic data
nvarsnumber of variables in the original problem
varsvariables in the original problem
coversizesize of the cover
coverproblem indices of the variables in the cover
lastfailedposition in cover array of the variable the fixing of which yielded infeasibility in last dive (or >= coversize, in which case *success is always TRUE)
successhas order really been changed?

Definition at line 1672 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
sciporiginal SCIP data structure
heurdataheuristic data
varvariable in the original problem
valbuffer for returning fixing value
fixaltsource of the fixing value: 'l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution
successcould value be retrieved successfully?
bdlencurrent length of probing path
bdvarsarray of variables with bound changes along probing path
bdtypesarray of bound types in bound disjunction
oldboundsarray of bounds before fixing

Definition at line 1783 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
sciporiginal SCIP data structure
varvariable to calculate alternatives for
fixvalreference fixing value
nalternativesnumber of fixing values computed
alternativesarray to store the alternative fixing values

Definition at line 1927 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
sciporiginal SCIP data structure
valfixing value to be rounded
varcorresponding variable
locksroundingshall we round according to locks? (otherwise to nearest integer)

Definition at line 2008 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
sciporiginal SCIP data structure
subscipSCIP structure of the subproblem
subvarsthe variables of the subproblem
subsolsolution of the subproblem
newsolsolution to the original problem

Definition at line 2053 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
scipSCIP data structure of the original problem
heurheuristic data structure
coversizesize of the cover
coverproblem indices of the variables in the cover
fixingvalsfixing values for the variables in the cover
timelimittime limit
memorylimitmemory limit
nodelimitnode limit
nstallnodesnumber of stalling nodes for the subproblem
validsolvedwas problem constructed from a valid copy and solved (proven optimal or infeasible)?
solbest solution found in subproblem (if feasible); *sol must be NULL, solution will be created
nusednodesnumber of nodes used for solving the subproblem

Definition at line 2094 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
scipSCIP data structure
varvariable to fix
valfixing value
infeaspointer to store whether the fixing lead to infeasibility
bdlencurrent length of bound disjunction
bdvarsarray of variables in bound disjunction
bdtypesarray of bound types in bound disjunction
bdboundsarray of bounds in bound disjunction
oldboundsarray of bounds before fixing

Definition at line 2321 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
sciporiginal SCIP data structure
heurdataheuristic data structure
coverarray with indices of the variables in the computed cover
coversizesize of the cover
fixingvalsfixing values for the variables in the cover
bdlencurrent length of bound disjunction along the probing path
bdvarsarray of variables in bound disjunction
bdtypesarray of bound types in bound disjunction
bdboundsarray of bounds in bound disjunction
oldboundsarray of bounds before fixing
nfixedintspointer to store number of fixed integer variables
nfixedcontspointer to store number of fixed continuous variables
lastfailedposition in cover array of the variable the fixing of which yielded infeasibility
infeaspointer to store whether fix-and-propagate led to an infeasibility

Definition at line 2433 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
static SCIP_DECL_HEURCOPY ( heurCopyUndercover  )
static

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

Definition at line 3056 of file heur_undercover.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurUndercover().

static SCIP_DECL_HEURFREE ( heurFreeUndercover  )
static

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

Definition at line 3070 of file heur_undercover.c.

References NULL, SCIP_OKAY, SCIPfreeMemory, SCIPheurGetData(), and SCIPheurSetData().

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

References NULL, SCIP_CALL, SCIP_HEURTIMING_DURINGLPLOOP, SCIP_OKAY, SCIPaddLinearConsToNlpHeurSubNlp(), SCIPallocMemoryArray, SCIPfindConshdlr(), SCIPfindHeur(), SCIPheurGetData(), SCIPheurGetFreqofs(), SCIPheurSetTimingmask(), SCIPisNLPConstructed(), and TRUE.

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

References HEUR_NAME, HEUR_TIMING, NULL, SCIP_OKAY, SCIPfreeMemoryArray, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetTimingmask().

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
scipSCIP data structure
coversizebuffer for the size of the computed cover
coverpointer to store the variables (of the original SCIP) in the computed cover (should be ready to hold SCIPgetNVars(scip) entries)
timelimittime limit
memorylimitmemory limit
objlimitobjective limit: upper bound on coversize
globalboundsshould global bounds on variables be used instead of local bounds at focus node?
onlyconvexifyshould we only fix/dom.red. variables creating nonconvexity?
coverbdshould bounddisjunction constraints be covered (or just copied)?
coveringobjobjective 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)
successfeasible cover found?

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

Referenced by SCIP_DECL_HEUREXEC().