SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
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 <assert.h>#include <string.h>#include "scip/scip.h"#include "scip/scipdefplugins.h"#include "scip/heur_undercover.h"#include "scip/pub_misc.h"#include "nlpi/exprinterpret.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_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 *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) |
| #define HEUR_NAME "undercover" |
Definition at line 45 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover(), and solveSubproblem().
| #define HEUR_DESC "solves a sub-CIP determined by a set covering approach" |
Definition at line 46 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define HEUR_DISPCHAR 'U' |
Definition at line 47 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define HEUR_PRIORITY -1110000 |
Definition at line 48 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define HEUR_FREQ 0 |
Definition at line 49 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define HEUR_FREQOFS 0 |
Definition at line 50 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define HEUR_MAXDEPTH -1 |
Definition at line 51 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 52 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 53 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 56 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 58 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 59 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 60 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define DEFAULT_CONFLICTWEIGHT 1000.0 |
weight for conflict score in fixing order
Definition at line 62 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define DEFAULT_CUTOFFWEIGHT 1.0 |
weight for cutoff score in fixing order
Definition at line 63 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define DEFAULT_INFERENCEWEIGHT 1.0 |
weight for inference score in fixing order
Definition at line 64 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 65 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 66 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 67 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define DEFAULT_MINCOVEREDABS 5 |
minimum number of nonlinear constraints in the original problem
Definition at line 68 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 69 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 70 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 71 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define DEFAULT_MAXBACKTRACKS 6 |
maximum number of backtracks
Definition at line 73 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define DEFAULT_MAXRECOVERS 0 |
maximum number of recoverings
Definition at line 74 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define DEFAULT_MAXREORDERS 1 |
maximum number of reorderings of the fixing order
Definition at line 75 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define DEFAULT_COVERINGOBJ 'u' |
objective function of the covering problem
Definition at line 77 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define DEFAULT_FIXINGORDER 'v' |
order in which variables should be fixed
Definition at line 78 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define DEFAULT_BEFORECUTS TRUE |
should undercover called at root node before cut separation?
Definition at line 80 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define DEFAULT_FIXINTFIRST FALSE |
should integer variables in the cover be fixed first?
Definition at line 81 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 82 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define DEFAULT_ONLYCONVEXIFY FALSE |
should we only fix/dom.red. variables creating nonconvexity?
Definition at line 83 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 84 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define DEFAULT_COVERBD FALSE |
should bounddisjunction constraints be covered (or just copied)?
Definition at line 85 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 86 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 87 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define DEFAULT_RANDSEED 43 /* initial random seed */ |
Definition at line 92 of file heur_undercover.c.
| #define COVERINGOBJS "cdlmtu" |
list of objective functions of the covering problem
Definition at line 95 of file heur_undercover.c.
Referenced by SCIPincludeHeurUndercover().
| #define FIXINGORDERS "CcVv" |
list of orders in which variables can be fixed
Definition at line 96 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 97 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 98 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 99 of file heur_undercover.c.
Referenced by SCIPapplyUndercover().
| #define SUBMIPSETUPCOSTS 200 |
number of nodes equivalent for the costs for setting up the sub-CIP
Definition at line 100 of file heur_undercover.c.
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 167 of file heur_undercover.c.
References SCIP_Bool, SCIPisFeasEQ(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and termIsConstant().
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 187 of file heur_undercover.c.
References SCIP_Bool, SCIPisFeasEQ(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), termIsConvex(), and TRUE.
Referenced by createCoveringProblem(), processNlRow(), and varIsFixed().
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 209 of file heur_undercover.c.
References incCounters(), SCIPisInfinity(), and sign().
Referenced by processNlRow(), and termIsConstant().
|
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 222 of file heur_undercover.c.
References TRUE, and updateTimelimit().
Referenced by createCoveringProblem(), processNlRow(), and termIsConvex().
|
static |
update time limit
| scip | SCIP data structure |
| clck | clock timer |
| timelimit | time limit |
Definition at line 241 of file heur_undercover.c.
References processNlRow(), SCIP_CALL, SCIP_OKAY, SCIPgetClockTime(), SCIPresetClock(), and SCIPstartClock().
Referenced by incCounters(), and 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 |
| exprint | expression interpreter for computing sparsity pattern of the Hessian; if NULL, we will simply fix all variables in the expression tree |
| hessiandata | working memory for retrieving dense sparsity of Hessian matrices |
| coveringscip | SCIP data structure for the covering problem |
| nvars | number of variables |
| coveringvars | array to store the covering problem's variables |
| termcounter | counter array for number of nonlinear nonzeros per variable |
| conscounter | counter array for number of nonlinear constraints per variable |
| consmarker | marker array if constraint has been counted in conscounter |
| globalbounds | should global bounds on variables be used instead of local bounds at focus node? |
| onlyconvexify | should we only fix/dom.red. variables creating nonconvexity? |
| success | pointer to store whether row was processed successfully |
Definition at line 257 of file heur_undercover.c.
References BMSclearMemoryArray, SCIP_QuadElement::coef, createCoveringProblem(), FALSE, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, incCounters(), SCIP_Bool, SCIP_CALL, SCIP_EXPRINTCAPABILITY_HESSIAN, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPcreateConsSetcover(), SCIPcreateSol(), SCIPdebugMsg, 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(), and updateTimelimit().
|
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? |
| coverbd | should bounddisjunction constraints be covered (or just copied)? |
| coveringobj | objective function of the covering problem |
| success | pointer to store whether the problem was created successfully |
Definition at line 548 of file heur_undercover.c.
References BMSclearMemoryArray, FALSE, forbidCover(), incCounters(), MAX, processNlRow(), SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_MULTAGGR, SCIP_VARTYPE_BINARY, SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPblkmem(), SCIPchgVarLb(), SCIPchgVarObj(), SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNActiveConss(), SCIPcreateConsLinear(), SCIPcreateConsSetpack(), SCIPcreateProb(), SCIPcreateVar(), SCIPdebugMsg, 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(), SCIPisFeasEQ(), 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 computeCoverUndercover(), processNlRow(), 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 1356 of file heur_undercover.c.
References createConflict(), FALSE, 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().
|
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 1479 of file heur_undercover.c.
References FALSE, 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().
|
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 1579 of file heur_undercover.c.
References computeFixingOrder(), FALSE, SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_Real, SCIPallocBufferArray, SCIPdebug, SCIPdebugMsg, 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 computeCoverUndercover(), createConflict(), 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 1695 of file heur_undercover.c.
References FALSE, getFixingValue(), MAX, 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().
|
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 1810 of file heur_undercover.c.
References calculateAlternatives(), FALSE, MAX, MAXNLPFAILS, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_NLPPAR_VERBLEVEL, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_NLPSOLSTAT_GLOBOPT, SCIP_NLPSOLSTAT_LOCOPT, SCIP_OKAY, SCIP_Real, SCIPchgVarBoundsDiveNLP(), SCIPdebug, SCIPdebugMsg, SCIPgetBestSol(), SCIPgetNLPSolstat(), SCIPgetSolVal(), SCIPisGE(), SCIPisLE(), SCIPisNLPConstructed(), SCIPsetNLPInitialGuessSol(), SCIPsetNLPIntPar(), SCIPsolveDiveNLP(), SCIPstartDiveNLP(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetNLPSol(), SCIPvarGetUbLocal(), and TRUE.
Referenced by computeFixingOrder(), and 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 1960 of file heur_undercover.c.
References roundFixingValue(), SCIP_Real, SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasZero(), SCIPisInfinity(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), and SCIPvarIsIntegral().
Referenced by fixAndPropagate(), and getFixingValue().
|
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 2041 of file heur_undercover.c.
References copySol(), SCIP_OKAY, SCIP_Real, SCIPfeasCeil(), SCIPfeasFloor(), SCIPfeasFrac(), SCIPisFeasIntegral(), SCIPvarGetNLocksDown(), and SCIPvarGetNLocksUp().
Referenced by calculateAlternatives(), and fixAndPropagate().
|
static |
copy the solution of the subproblem to newsol
| scip | original SCIP data structure |
| subscip | SCIP structure of the subproblem |
| subvars | the variables of the subproblem |
| subsol | solution of the subproblem |
| newsol | solution to the original problem |
Definition at line 2086 of file heur_undercover.c.
References SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetNOrigVars(), SCIPgetSolVals(), SCIPgetVarsData(), SCIPsetSolVals(), and solveSubproblem().
Referenced by roundFixingValue(), and solveSubproblem().
|
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 2127 of file heur_undercover.c.
References copySol(), FALSE, HEUR_NAME, 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(), SCIPcreateSol(), 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(), SCIPtrySol(), SCIPunfixParam(), SCIPwarningMessage(), and TRUE.
Referenced by copySol(), and 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 2373 of file heur_undercover.c.
References FALSE, fixAndPropagate(), MAX, 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().
|
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 2493 of file heur_undercover.c.
References calculateAlternatives(), FALSE, getFixingValue(), MAX, 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().
|
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 2692 of file heur_undercover.c.
References computeFixingOrder(), createConflict(), createCoveringProblem(), FALSE, fixAndPropagate(), forbidCover(), MAX, MAXNLPFAILS, MAXPOSTNLPFAILS, MINTIMELEFT, SCIP_Bool, SCIP_CALL, SCIP_DECL_HEURCOPY(), 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(), solveCoveringProblem(), solveSubproblem(), TRUE, and updateTimelimit().
Referenced by fixAndPropagate().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 3116 of file heur_undercover.c.
Referenced by SCIPapplyUndercover().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 3130 of file heur_undercover.c.
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 3150 of file heur_undercover.c.
|
static |
deinitialization method of primal heuristic
Definition at line 3170 of file heur_undercover.c.
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 3189 of file heur_undercover.c.
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
Definition at line 3262 of file heur_undercover.c.
|
static |
execution method of primal heuristic
Definition at line 3284 of file heur_undercover.c.
|
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? |
| coverbd | should bounddisjunction constraints be covered (or just copied)? |
| coveringobj | objective function of the covering problem ('b'ranching status, influenced nonlinear 'c'onstraints/'t'erms, 'd'omain size, 'l'ocks, 'm'in of up/down locks, 'u'nit penalties, constraint 'v'iolation) |
| success | feasible cover found? |
Definition at line 3568 of file heur_undercover.c.
References createCoveringProblem(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcomputeCoverUndercover(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetVarsData(), SCIPincludeDefaultPlugins(), SCIPreleaseVar(), and solveCoveringProblem().
Referenced by SCIPcomputeCoverUndercover(), and SCIPincludeHeurUndercover().