Undercover primal heuristic for MINLPs.
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.
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 coverand, SCIP_Bool coverbd, SCIP_Bool coverind, SCIP_Bool covernl, 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 coverand, SCIP_Bool coverbd, SCIP_Bool coverind, SCIP_Bool covernl, 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 coverand, SCIP_Bool coverbd, SCIP_Bool coverind, SCIP_Bool covernl, char coveringobj, SCIP_Bool *success) |
#define HEUR_NAME "undercover" |
Definition at line 87 of file heur_undercover.c.
Definition at line 88 of file heur_undercover.c.
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 89 of file heur_undercover.c.
#define HEUR_PRIORITY -1110000 |
Definition at line 90 of file heur_undercover.c.
#define HEUR_FREQ 0 |
Definition at line 91 of file heur_undercover.c.
#define HEUR_FREQOFS 0 |
Definition at line 92 of file heur_undercover.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 93 of file heur_undercover.c.
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 94 of file heur_undercover.c.
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 95 of file heur_undercover.c.
#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().
#define DEFAULT_MAXNODES (SCIP_Longint)50 |
maximum number of nodes to regard in the subproblem
Definition at line 100 of file heur_undercover.c.
#define DEFAULT_MINNODES (SCIP_Longint)50 |
minimum number of nodes to regard in the subproblem
Definition at line 101 of file heur_undercover.c.
#define DEFAULT_NODESOFS (SCIP_Longint)50 |
number of nodes added to the contingent of the total nodes
Definition at line 102 of file heur_undercover.c.
#define DEFAULT_CONFLICTWEIGHT 1000.0 |
weight for conflict score in fixing order
Definition at line 104 of file heur_undercover.c.
#define DEFAULT_CUTOFFWEIGHT 1.0 |
weight for cutoff score in fixing order
Definition at line 105 of file heur_undercover.c.
#define DEFAULT_INFERENCEWEIGHT 1.0 |
weight for inference score in fixing order
Definition at line 106 of file heur_undercover.c.
#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().
#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().
#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().
#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().
#define DEFAULT_MINIMPROVE 0.0 |
factor by which heuristic should at least improve the incumbent
Definition at line 111 of file heur_undercover.c.
#define DEFAULT_NODESQUOT 0.1 |
subproblem nodes in relation to nodes of the original problem
Definition at line 112 of file heur_undercover.c.
#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().
#define DEFAULT_MAXBACKTRACKS 6 |
maximum number of backtracks
Definition at line 115 of file heur_undercover.c.
#define DEFAULT_MAXRECOVERS 0 |
maximum number of recoverings
Definition at line 116 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
#define DEFAULT_MAXREORDERS 1 |
maximum number of reorderings of the fixing order
Definition at line 117 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
#define DEFAULT_COVERINGOBJ 'u' |
objective function of the covering problem
Definition at line 119 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
#define DEFAULT_FIXINGORDER 'v' |
order in which variables should be fixed
Definition at line 120 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
#define DEFAULT_BEFORECUTS TRUE |
should undercover called at root node before cut separation?
Definition at line 122 of file heur_undercover.c.
#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().
#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().
#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().
#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().
#define DEFAULT_COVERAND TRUE |
should and constraints be covered (or just copied)?
Definition at line 127 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
#define DEFAULT_COVERBD FALSE |
should bounddisjunction constraints be covered (or just copied)?
Definition at line 128 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
#define DEFAULT_COVERIND FALSE |
should indicator constraints be covered (or just copied)?
Definition at line 129 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
#define DEFAULT_COVERNL TRUE |
should nonlinear constraints be covered (or just copied)?
Definition at line 130 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 131 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 132 of file heur_undercover.c.
#define DEFAULT_RANDSEED 43 /* initial random seed */ |
Definition at line 135 of file heur_undercover.c.
#define COVERINGOBJS "cdlmtu" |
list of objective functions of the covering problem
Definition at line 138 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
#define FIXINGORDERS "CcVv" |
list of orders in which variables can be fixed
Definition at line 139 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 140 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 141 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 142 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 143 of file heur_undercover.c.
Referenced by SCIP_DECL_HEUREXEC().
determines, whether a variable is fixed to the given value
scip | SCIP data structure |
var | variable to check |
val | value to check |
global | should global bounds be used? |
Definition at line 204 of file heur_undercover.c.
References SCIP_Bool, SCIP_Real, SCIPisFeasEQ(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and var.
Referenced by createCoveringProblem().
|
static |
determines, whether a term is already constant, because the variable is fixed or the coefficient is zero
scip | SCIP data structure |
var | variable to check |
coeff | coefficient to check |
global | should global bounds be used? |
Definition at line 224 of file heur_undercover.c.
References SCIP_Bool, SCIP_Real, SCIPisFeasEQ(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and var.
Referenced by createCoveringProblem(), and processNlRow().
determines, whether a term is convex
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 245 of file heur_undercover.c.
References SCIP_Bool, SCIP_Real, and SCIPisInfinity().
Referenced by processNlRow().
|
static |
increases counters
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 258 of file heur_undercover.c.
References SCIP_Bool, and TRUE.
Referenced by createCoveringProblem(), and processNlRow().
|
static |
update time limit
scip | SCIP data structure |
clck | clock timer |
timelimit | time limit |
Definition at line 277 of file heur_undercover.c.
References SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetClockTime(), SCIPresetClock(), and SCIPstartClock().
Referenced by SCIPapplyUndercover().
|
static |
analyzes a nonlinear row and adds constraints and fixings to the covering problem
scip | original SCIP data structure |
nlrow | nonlinear row representation of a nonlinear constraint |
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 293 of file heur_undercover.c.
References assert(), BMSclearMemoryArray, FALSE, incCounters(), NULL, nvars, 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().
|
static |
creates the covering problem to determine a number of variables to be fixed
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? |
coverand | should and constraints be covered (or just copied)? |
coverbd | should bounddisjunction constraints be covered (or just copied)? |
coverind | should indicator constraints be covered (or just copied)? |
covernl | should nonlinear 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 485 of file heur_undercover.c.
References assert(), BMSclearMemoryArray, c, FALSE, i, incCounters(), MIN, NULL, nvars, 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(), SCIPgetSubscipDepth(), SCIPgetVarsAnd(), SCIPgetVarsBounddisjunction(), SCIPgetVarsData(), SCIPinfinity(), SCIPisFeasEQ(), SCIPreleaseCons(), SCIPsetSubscipDepth(), SCIPsnprintf(), SCIPstatistic, SCIPstatisticPrintf, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNegatedVar(), SCIPvarGetNegationVar(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetProbindex(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsActive(), SCIPvarIsNegated(), SCIPvarIsRelaxationOnly(), termIsConstant(), TRUE, varIsFixed(), and vars.
Referenced by computeCoverUndercover(), and SCIPapplyUndercover().
|
static |
adds a constraint to the covering problem to forbid the given cover
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 1102 of file heur_undercover.c.
References assert(), FALSE, i, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateConsLinear(), SCIPcreateConsSetcover(), SCIPfreeBufferArray, SCIPgetNegatedVar(), SCIPinfinity(), SCIPisFeasGE(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetLbLocal(), TRUE, and vars.
Referenced by SCIPapplyUndercover().
|
static |
adds a set covering or bound disjunction constraint to the original problem
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 1225 of file heur_undercover.c.
References assert(), FALSE, i, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPaddConsLocal(), SCIPallocBufferArray, SCIPcreateConsBounddisjunction(), SCIPcreateConsLogicor(), SCIPfreeBufferArrayNull, SCIPgetNegatedVar(), SCIPisFeasEQ(), SCIPisFeasZero(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarIsBinary(), and TRUE.
Referenced by SCIPapplyUndercover().
|
static |
solve covering problem
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 1325 of file heur_undercover.c.
References assert(), FALSE, i, NULL, SCIP_Bool, 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(), and SCIPapplyUndercover().
|
static |
computes fixing order and returns whether order has really been changed
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 1436 of file heur_undercover.c.
References assert(), FALSE, heurdata, i, MAX, MIN, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIP_Real, SCIPallocBufferArray, SCIPepsilon(), SCIPfreeBufferArray, SCIPgetVarAvgInferenceCutoffScore(), SCIPgetVarConflictScore(), SCIPinfinity(), SCIPrandomGetReal(), SCIPsortDownRealInt(), SCIPsortRealInt(), SCIPvarIsIntegral(), TRUE, var, and vars.
Referenced by SCIPapplyUndercover().
|
static |
gets fixing value
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 1550 of file heur_undercover.c.
References assert(), FALSE, heurdata, i, MAX, MAXNLPFAILS, MIN, NULL, SCIP_Bool, 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(), TRUE, and var.
Referenced by fixAndPropagate().
|
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.
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 1697 of file heur_undercover.c.
References ABS, assert(), SCIP_Real, SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasZero(), SCIPisInfinity(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), SCIPvarIsIntegral(), and var.
Referenced by fixAndPropagate().
|
static |
rounds the given fixing value
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 1778 of file heur_undercover.c.
References SCIP_Bool, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIPfeasCeil(), SCIPfeasFloor(), SCIPfeasFrac(), SCIPisFeasIntegral(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), var, and x.
Referenced by fixAndPropagate().
|
static |
solve subproblem and pass best feasible solution to original SCIP instance
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 |
fixedvals | 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 1822 of file heur_undercover.c.
References assert(), cutoff, FALSE, HEUR_NAME, heurdata, i, MIN, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, 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(), sol, TRUE, and vars.
Referenced by SCIPapplyUndercover().
|
static |
perform fixing of a variable and record bound disjunction information
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 2066 of file heur_undercover.c.
References assert(), FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_MAXTREEDEPTH, SCIP_OKAY, SCIP_Real, SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), SCIPdebugMsg, SCIPfeasCeil(), SCIPgetDepth(), SCIPgetNVars(), SCIPisFeasIntegral(), SCIPisLbBetter(), SCIPisUbBetter(), SCIPnewProbingNode(), SCIPpropagateProbing(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), and var.
Referenced by fixAndPropagate().
|
static |
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 2186 of file heur_undercover.c.
References assert(), calculateAlternatives(), FALSE, getFixingValue(), heurdata, i, MAX, MIN, NULL, performFixing(), roundFixingValue(), SCIP_Bool, SCIP_CALL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPbacktrackProbing(), SCIPdebugMsg, SCIPendProbing(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetLPSolstat(), SCIPgetProbingDepth(), SCIPgetVars(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPisIntegral(), SCIPstartProbing(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), TRUE, and vars.
Referenced by SCIPapplyUndercover().
|
static |
main procedure of the undercover heuristic
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 2389 of file heur_undercover.c.
References assert(), computeFixingOrder(), createConflict(), createCoveringProblem(), FALSE, fixAndPropagate(), forbidCover(), heurdata, i, MAX, MAXNLPFAILS, MAXPOSTNLPFAILS, MIN, MINTIMELEFT, NULL, nvars, result, SCIP_Bool, SCIP_CALL, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_FOUNDSOL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIPallocBufferArray, SCIPapplyHeurSubNlp(), SCIPconshdlrGetNActiveConss(), SCIPcreate(), SCIPcreateClock(), SCIPdebugMsg, 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(), SCIPvarIsRelaxationOnly(), sol, solveCoveringProblem(), solveSubproblem(), TRUE, updateTimelimit(), and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 2821 of file heur_undercover.c.
References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurUndercover().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 2835 of file heur_undercover.c.
References assert(), heurdata, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 2855 of file heur_undercover.c.
References assert(), DEFAULT_RANDSEED, heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPheurGetData(), and TRUE.
|
static |
deinitialization method of primal heuristic
Definition at line 2875 of file heur_undercover.c.
References assert(), heurdata, NULL, SCIP_OKAY, SCIPfreeRandom(), and SCIPheurGetData().
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 2894 of file heur_undercover.c.
References assert(), h, heurdata, NULL, SCIP_CALL, SCIP_HEURTIMING_DURINGLPLOOP, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPfindConshdlr(), SCIPfindHeur(), SCIPheurGetData(), SCIPheurGetFreqofs(), and SCIPheurSetTimingmask().
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
Definition at line 2954 of file heur_undercover.c.
References assert(), HEUR_NAME, HEUR_TIMING, heurdata, NULL, SCIP_OKAY, SCIPfreeBlockMemoryArray, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetTimingmask().
|
static |
execution method of primal heuristic
Definition at line 2976 of file heur_undercover.c.
References assert(), FALSE, h, HEUR_TIMING, heurdata, i, MAX, MIN, MINTIMELEFT, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIP_Real, SCIPapplyUndercover(), SCIPconshdlrGetNActiveConss(), SCIPdebugMsg, SCIPgetBoolParam(), SCIPgetDepth(), SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetNLPNlRows(), SCIPgetNNlpis(), SCIPgetNNLPNlRows(), SCIPgetNNodes(), SCIPgetProbName(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPheurGetData(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPheurSetTimingmask(), SCIPisInfinity(), SCIPisNLPConstructed(), SCIPisStopped(), SCIPnlrowGetExpr(), and SUBMIPSETUPCOSTS.
|
static |
create and solve covering problem
scip | SCIP data structure |
coveringscip | SCIP instance for covering problem |
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? |
coverand | should and constraints be covered (or just copied)? |
coverbd | should bounddisjunction constraints be covered (or just copied)? |
coverind | should indicator constraints be covered (or just copied)? |
covernl | should nonlinear 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 3272 of file heur_undercover.c.
References assert(), createCoveringProblem(), i, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetVarsData(), SCIPincludeDefaultPlugins(), SCIPreleaseVar(), solveCoveringProblem(), and vars.
Referenced by SCIPcomputeCoverUndercover().