Scippy

SCIP

Solving Constraint Integer Programs

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 "blockmemshell/memory.h"
#include "scip/cons_and.h"
#include "scip/cons_bounddisjunction.h"
#include "scip/cons_nonlinear.h"
#include "scip/cons_indicator.h"
#include "scip/cons_linear.h"
#include "scip/cons_logicor.h"
#include "scip/cons_setppc.h"
#include "scip/heur_subnlp.h"
#include "scip/heur_undercover.h"
#include "scip/pub_cons.h"
#include "scip/pub_expr.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_nlp.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scipdefplugins.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_nlp.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.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_timing.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   "undercover"
 
#define HEUR_DESC   "solves a sub-CIP determined by a set covering approach"
 
#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_LNS
 
#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 DEFAULT_RANDSEED   43 /* initial random seed */
 
#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 *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 solveSubproblem (SCIP *scip, SCIP_HEUR *heur, int coversize, int *cover, SCIP_Real *fixedvals, 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_HEURINIT (heurInitUndercover)
 
static SCIP_DECL_HEUREXIT (heurExitUndercover)
 
static SCIP_DECL_HEURINITSOL (heurInitsolUndercover)
 
static SCIP_DECL_HEUREXITSOL (heurExitsolUndercover)
 
static SCIP_DECL_HEUREXEC (heurExecUndercover)
 
SCIP_RETCODE SCIPincludeHeurUndercover (SCIP *scip)
 
static SCIP_RETCODE computeCoverUndercover (SCIP *scip, SCIP *coveringscip, 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)
 
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

◆ HEUR_NAME

#define HEUR_NAME   "undercover"

Definition at line 87 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover(), and solveSubproblem().

◆ HEUR_DESC

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

Definition at line 88 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_LNS

Definition at line 89 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -1110000

Definition at line 90 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ HEUR_FREQ

#define HEUR_FREQ   0

Definition at line 91 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 92 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 93 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE

Definition at line 94 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 95 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_FIXINGALTS

#define DEFAULT_FIXINGALTS   "li"

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

Definition at line 98 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_MAXNODES

#define DEFAULT_MAXNODES   (SCIP_Longint)500

maximum number of nodes to regard in the subproblem

Definition at line 100 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_MINNODES

#define DEFAULT_MINNODES   (SCIP_Longint)500

minimum number of nodes to regard in the subproblem

Definition at line 101 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_NODESOFS

#define DEFAULT_NODESOFS   (SCIP_Longint)500

number of nodes added to the contingent of the total nodes

Definition at line 102 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_CONFLICTWEIGHT

#define DEFAULT_CONFLICTWEIGHT   1000.0

weight for conflict score in fixing order

Definition at line 104 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_CUTOFFWEIGHT

#define DEFAULT_CUTOFFWEIGHT   1.0

weight for cutoff score in fixing order

Definition at line 105 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_INFERENCEWEIGHT

#define DEFAULT_INFERENCEWEIGHT   1.0

weight for inference score in fixing order

Definition at line 106 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_MAXCOVERSIZEVARS

#define DEFAULT_MAXCOVERSIZEVARS   1.0

maximum coversize (as fraction of total number of variables)

Definition at line 107 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_MAXCOVERSIZECONSS

#define DEFAULT_MAXCOVERSIZECONSS   SCIP_REAL_MAX

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

Definition at line 108 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_MINCOVEREDREL

#define DEFAULT_MINCOVEREDREL   0.15

minimum percentage of nonlinear constraints in the original problem

Definition at line 109 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_MINCOVEREDABS

#define DEFAULT_MINCOVEREDABS   5

minimum number of nonlinear constraints in the original problem

Definition at line 110 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_MINIMPROVE

#define DEFAULT_MINIMPROVE   0.0

factor by which heuristic should at least improve the incumbent

Definition at line 111 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_NODESQUOT

#define DEFAULT_NODESQUOT   0.1

subproblem nodes in relation to nodes of the original problem

Definition at line 112 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_RECOVERDIV

#define DEFAULT_RECOVERDIV   0.9

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

Definition at line 113 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_MAXBACKTRACKS

#define DEFAULT_MAXBACKTRACKS   6

maximum number of backtracks

Definition at line 115 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_MAXRECOVERS

#define DEFAULT_MAXRECOVERS   0

maximum number of recoverings

Definition at line 116 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_MAXREORDERS

#define DEFAULT_MAXREORDERS   1

maximum number of reorderings of the fixing order

Definition at line 117 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_COVERINGOBJ

#define DEFAULT_COVERINGOBJ   'u'

objective function of the covering problem

Definition at line 119 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_FIXINGORDER

#define DEFAULT_FIXINGORDER   'v'

order in which variables should be fixed

Definition at line 120 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_BEFORECUTS

#define DEFAULT_BEFORECUTS   TRUE

should undercover called at root node before cut separation?

Definition at line 122 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_FIXINTFIRST

#define DEFAULT_FIXINTFIRST   FALSE

should integer variables in the cover be fixed first?

Definition at line 123 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_LOCKSROUNDING

#define DEFAULT_LOCKSROUNDING   TRUE

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

Definition at line 124 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_ONLYCONVEXIFY

#define DEFAULT_ONLYCONVEXIFY   FALSE

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

Definition at line 125 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_POSTNLP

#define DEFAULT_POSTNLP   TRUE

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

Definition at line 126 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_COVERBD

#define DEFAULT_COVERBD   FALSE

should bounddisjunction constraints be covered (or just copied)?

Definition at line 127 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_REUSECOVER

#define DEFAULT_REUSECOVER   FALSE

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

Definition at line 128 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

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

Referenced by SCIPincludeHeurUndercover().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   43 /* initial random seed */

Definition at line 134 of file heur_undercover.c.

◆ COVERINGOBJS

#define COVERINGOBJS   "cdlmtu"

list of objective functions of the covering problem

Definition at line 137 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ FIXINGORDERS

#define FIXINGORDERS   "CcVv"

list of orders in which variables can be fixed

Definition at line 138 of file heur_undercover.c.

Referenced by SCIPincludeHeurUndercover().

◆ MAXNLPFAILS

#define MAXNLPFAILS   1

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

Definition at line 139 of file heur_undercover.c.

Referenced by getFixingValue(), and SCIPapplyUndercover().

◆ MAXPOSTNLPFAILS

#define MAXPOSTNLPFAILS   1

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

Definition at line 140 of file heur_undercover.c.

Referenced by SCIPapplyUndercover().

◆ MINTIMELEFT

#define MINTIMELEFT   1.0

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

Definition at line 141 of file heur_undercover.c.

Referenced by SCIPapplyUndercover().

◆ SUBMIPSETUPCOSTS

#define SUBMIPSETUPCOSTS   200

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

Definition at line 142 of file heur_undercover.c.

Function Documentation

◆ varIsFixed()

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

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

Referenced by createCoveringProblem().

◆ termIsConstant()

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

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

Referenced by createCoveringProblem(), processNlRow(), and varIsFixed().

◆ termIsConvex()

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

References incCounters(), and SCIPisInfinity().

Referenced by processNlRow(), and termIsConstant().

◆ incCounters()

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

References TRUE, and updateTimelimit().

Referenced by createCoveringProblem(), processNlRow(), and termIsConvex().

◆ updateTimelimit()

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

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

Referenced by incCounters(), and SCIPapplyUndercover().

◆ processNlRow()

static SCIP_RETCODE processNlRow ( SCIP scip,
SCIP_NLROW nlrow,
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
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 289 of file heur_undercover.c.

References BMSclearMemoryArray, createCoveringProblem(), FALSE, incCounters(), NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_EXPRCURV_LINEAR, SCIP_EXPRITER_DFS, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPcheckExprQuadratic(), SCIPcreateConsSetcover(), SCIPcreateExpriter(), SCIPdebugMsg, SCIPexprAreQuadraticExprsVariables(), SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPfixVar(), SCIPfreeExpriter(), SCIPgetVarExprVar(), SCIPisExprVar(), SCIPisInfinity(), SCIPnlrowGetCurvature(), SCIPnlrowGetExpr(), SCIPnlrowGetLhs(), SCIPnlrowGetName(), SCIPnlrowGetRhs(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetName(), SCIPvarGetProbindex(), termIsConstant(), termIsConvex(), and TRUE.

Referenced by createCoveringProblem(), and updateTimelimit().

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

References BMSclearMemoryArray, FALSE, forbidCover(), incCounters(), NULL, processNlRow(), SCIP_Bool, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_MULTAGGR, SCIP_VARTYPE_BINARY, SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPchgVarLb(), SCIPchgVarObj(), SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNActiveConss(), SCIPcreateConsLinear(), SCIPcreateProb(), SCIPcreateVar(), SCIPdebugMsg, SCIPerrorMessage, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetBinaryVarIndicator(), SCIPgetBinvarRepresentative(), SCIPgetNegatedVar(), SCIPgetNlRowNonlinear(), SCIPgetNVarsAnd(), SCIPgetNVarsBounddisjunction(), SCIPgetProbName(), SCIPgetResultantAnd(), SCIPgetVarsAnd(), SCIPgetVarsBounddisjunction(), SCIPgetVarsData(), SCIPinfinity(), SCIPisFeasEQ(), SCIPreleaseCons(), SCIPsnprintf(), SCIPstatistic, SCIPstatisticPrintf, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNegatedVar(), SCIPvarGetNegationVar(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetProbindex(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsActive(), SCIPvarIsNegated(), SCIPvarIsRelaxationOnly(), termIsConstant(), TRUE, and varIsFixed().

Referenced by computeCoverUndercover(), processNlRow(), and SCIPapplyUndercover().

◆ forbidCover()

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

References createConflict(), 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 createCoveringProblem(), and SCIPapplyUndercover().

◆ createConflict()

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 1217 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(), solveCoveringProblem(), and TRUE.

Referenced by forbidCover(), and SCIPapplyUndercover().

◆ solveCoveringProblem()

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

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

Referenced by computeCoverUndercover(), createConflict(), and SCIPapplyUndercover().

◆ computeFixingOrder()

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

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

Referenced by SCIPapplyUndercover(), and solveCoveringProblem().

◆ getFixingValue()

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

References calculateAlternatives(), FALSE, MAX, MAXNLPFAILS, NULL, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_NLPSOLSTAT_GLOBOPT, SCIP_NLPSOLSTAT_LOCOPT, SCIP_OKAY, SCIP_Real, SCIPchgVarBoundsDiveNLP(), SCIPdebugMsg, SCIPgetBestSol(), SCIPgetNLPSolstat(), SCIPgetSolVal(), SCIPisGE(), SCIPisLE(), SCIPisNLPConstructed(), SCIPsetNLPInitialGuessSol(), SCIPsolveNLP, SCIPstartDiveNLP(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetNLPSol(), SCIPvarGetUbLocal(), and TRUE.

Referenced by computeFixingOrder(), and fixAndPropagate().

◆ calculateAlternatives()

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

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

Referenced by fixAndPropagate(), and getFixingValue().

◆ roundFixingValue()

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

References SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIPfeasCeil(), SCIPfeasFloor(), SCIPfeasFrac(), SCIPisFeasIntegral(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), solveSubproblem(), and x.

Referenced by calculateAlternatives(), and fixAndPropagate().

◆ solveSubproblem()

static SCIP_RETCODE solveSubproblem ( SCIP scip,
SCIP_HEUR heur,
int  coversize,
int *  cover,
SCIP_Real fixedvals,
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
fixedvalsfixing 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 1814 of file heur_undercover.c.

References FALSE, HEUR_NAME, NULL, performFixing(), 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(), SCIPcopyConsCompression(), SCIPcopyCuts(), SCIPcreate(), SCIPdebug, SCIPdebugMsg, SCIPfree(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetLowerbound(), SCIPgetNNodes(), SCIPgetNSols(), SCIPgetSols(), SCIPgetStatus(), SCIPgetUpperbound(), SCIPgetVarsData(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPheurGetData(), SCIPisInfinity(), SCIPisParamFixed(), SCIPmergeVariableStatistics(), SCIPprintStatistics(), SCIPsetBoolParam(), SCIPsetEmphasis(), SCIPsetHeuristics(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetRealParam(), SCIPsolve(), SCIPtranslateSubSol(), SCIPtrySol(), SCIPunfixParam(), SCIPwarningMessage(), and TRUE.

Referenced by roundFixingValue(), and SCIPapplyUndercover().

◆ performFixing()

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

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

Referenced by fixAndPropagate(), and solveSubproblem().

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

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

Referenced by performFixing(), and SCIPapplyUndercover().

◆ SCIPapplyUndercover()

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

static SCIP_DECL_HEURCOPY ( heurCopyUndercover  )
static

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

Definition at line 2808 of file heur_undercover.c.

Referenced by SCIPapplyUndercover().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeUndercover  )
static

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

Definition at line 2822 of file heur_undercover.c.

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitUndercover  )
static

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

Definition at line 2842 of file heur_undercover.c.

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitUndercover  )
static

deinitialization method of primal heuristic

Definition at line 2862 of file heur_undercover.c.

◆ SCIP_DECL_HEURINITSOL()

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

◆ SCIP_DECL_HEUREXITSOL()

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

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecUndercover  )
static

execution method of primal heuristic

Definition at line 2958 of file heur_undercover.c.

◆ computeCoverUndercover()

static SCIP_RETCODE computeCoverUndercover ( SCIP scip,
SCIP coveringscip,
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 
)
static

create and solve covering problem

Parameters
scipSCIP data structure
coveringscipSCIP instance for covering problem
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 3242 of file heur_undercover.c.

References createCoveringProblem(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcomputeCoverUndercover(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetVarsData(), SCIPincludeDefaultPlugins(), SCIPreleaseVar(), and solveCoveringProblem().

Referenced by SCIPcomputeCoverUndercover(), and SCIPincludeHeurUndercover().