NLP diving heuristic that chooses fixings w.r.t. the fractionalities.
Definition in file heur_nlpdiving.c.
#include <assert.h>
#include <string.h>
#include "scip/heur_nlpdiving.h"
#include "scip/heur_subnlp.h"
#include "scip/heur_undercover.h"
#include "nlpi/nlpi.h"
Go to the source code of this file.
Functions | |
static SCIP_RETCODE | getNLPFracVars (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR ***nlpcands, SCIP_Real **nlpcandssol, SCIP_Real **nlpcandsfrac, int *nnlpcands) |
static SCIP_RETCODE | chooseFracVar (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **nlpcands, SCIP_Real *nlpcandssol, SCIP_Real *nlpcandsfrac, int nnlpcands, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup) |
static SCIP_RETCODE | chooseVeclenVar (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **nlpcands, SCIP_Real *nlpcandssol, SCIP_Real *nlpcandsfrac, int nnlpcands, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup) |
static SCIP_RETCODE | chooseCoefVar (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **nlpcands, SCIP_Real *nlpcandssol, SCIP_Real *nlpcandsfrac, int nnlpcands, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup) |
static void | calcPscostQuot (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var, SCIP_Real primsol, SCIP_Real frac, int rounddir, SCIP_Real *pscostquot, SCIP_Bool *roundup, SCIP_Bool prefvar) |
static SCIP_RETCODE | choosePscostVar (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **nlpcands, SCIP_Real *nlpcandssol, SCIP_Real *nlpcandsfrac, int nnlpcands, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup) |
static SCIP_RETCODE | chooseGuidedVar (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **nlpcands, SCIP_Real *nlpcandssol, SCIP_Real *nlpcandsfrac, int nnlpcands, SCIP_SOL *bestsol, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup) |
static SCIP_RETCODE | chooseDoubleVar (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **pseudocands, SCIP_Real *pseudocandsnlpsol, SCIP_Real *pseudocandslpsol, int npseudocands, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Real *bestboundval, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup) |
static SCIP_RETCODE | createNewSol (SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_HASHMAP *varmap, SCIP_SOL *subsol, SCIP_Bool *success) |
static SCIP_RETCODE | doSolveSubMIP (SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **covervars, int ncovervars, SCIP_Bool *success) |
static SCIP_RETCODE | solveSubMIP (SCIP *scip, SCIP_HEUR *heur, SCIP_VAR **covervars, int ncovervars, SCIP_Bool *success) |
static | SCIP_DECL_EVENTEXEC (eventExecNlpdiving) |
static | SCIP_DECL_HEURCOPY (heurCopyNlpdiving) |
static | SCIP_DECL_HEURFREE (heurFreeNlpdiving) |
static | SCIP_DECL_HEURINIT (heurInitNlpdiving) |
static | SCIP_DECL_HEUREXIT (heurExitNlpdiving) |
static | SCIP_DECL_HEURINITSOL (heurInitsolNlpdiving) |
static | SCIP_DECL_HEUREXEC (heurExecNlpdiving) |
SCIP_RETCODE | SCIPincludeHeurNlpdiving (SCIP *scip) |
#define HEUR_NAME "nlpdiving" |
Definition at line 33 of file heur_nlpdiving.c.
#define HEUR_DESC "NLP diving heuristic that chooses fixings w.r.t. the fractionalities" |
Definition at line 34 of file heur_nlpdiving.c.
#define HEUR_DISPCHAR 'd' |
Definition at line 35 of file heur_nlpdiving.c.
#define HEUR_PRIORITY -1003000 |
Definition at line 36 of file heur_nlpdiving.c.
#define HEUR_FREQ 10 |
Definition at line 37 of file heur_nlpdiving.c.
#define HEUR_FREQOFS 3 |
Definition at line 38 of file heur_nlpdiving.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 39 of file heur_nlpdiving.c.
#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE |
Definition at line 40 of file heur_nlpdiving.c.
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 41 of file heur_nlpdiving.c.
#define EVENTHDLR_NAME "Nlpdiving" |
Definition at line 44 of file heur_nlpdiving.c.
#define EVENTHDLR_DESC "bound change event handler for " HEUR_NAME " heuristic" |
Definition at line 45 of file heur_nlpdiving.c.
#define DEFAULT_MINRELDEPTH 0.0 |
minimal relative depth to start diving
Definition at line 52 of file heur_nlpdiving.c.
#define DEFAULT_MAXRELDEPTH 1.0 |
maximal relative depth to start diving
Definition at line 53 of file heur_nlpdiving.c.
#define DEFAULT_MAXNLPITERABS 200 |
minimial absolute number of allowed NLP iterations
Definition at line 54 of file heur_nlpdiving.c.
#define DEFAULT_MAXNLPITERREL 10 |
additional allowed number of NLP iterations relative to successfully found solutions
Definition at line 55 of file heur_nlpdiving.c.
#define DEFAULT_MAXDIVEUBQUOT 0.8 |
maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)
Definition at line 56 of file heur_nlpdiving.c.
#define DEFAULT_MAXDIVEAVGQUOT 0.0 |
maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)
Definition at line 59 of file heur_nlpdiving.c.
#define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 |
maximal UBQUOT when no solution was found yet (0.0: no limit)
Definition at line 62 of file heur_nlpdiving.c.
#define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 |
maximal AVGQUOT when no solution was found yet (0.0: no limit)
Definition at line 63 of file heur_nlpdiving.c.
#define DEFAULT_MINSUCCQUOT 0.1 |
heuristic will not run if less then this percentage of calls succeeded (0.0: no limit)
Definition at line 64 of file heur_nlpdiving.c.
#define DEFAULT_MAXFEASNLPS 10 |
maximal number of NLPs with feasible solution to solve during one dive
Definition at line 65 of file heur_nlpdiving.c.
#define DEFAULT_FIXQUOT 0.2 |
percentage of fractional variables that should be fixed before the next NLP solve
Definition at line 66 of file heur_nlpdiving.c.
#define DEFAULT_BACKTRACK TRUE |
use one level of backtracking if infeasibility is encountered?
Definition at line 67 of file heur_nlpdiving.c.
#define DEFAULT_LP FALSE |
should the LP relaxation be solved before the NLP relaxation?
Definition at line 68 of file heur_nlpdiving.c.
#define DEFAULT_PREFERLPFRACS FALSE |
prefer variables that are also fractional in LP solution?
Definition at line 69 of file heur_nlpdiving.c.
#define DEFAULT_PREFERCOVER TRUE |
should variables in a minimal cover be preferred?
Definition at line 70 of file heur_nlpdiving.c.
#define DEFAULT_SOLVESUBMIP FALSE |
should a sub-MIP be solved if all cover variables are fixed?
Definition at line 71 of file heur_nlpdiving.c.
#define DEFAULT_NLPSTART 's' |
which point should be used as starting point for the NLP solver?
Definition at line 72 of file heur_nlpdiving.c.
#define DEFAULT_VARSELRULE 'd' |
which variable selection should be used? ('f'ractionality, 'c'oefficient, 'p'seudocost, 'g'uided, 'd'ouble)
Definition at line 73 of file heur_nlpdiving.c.
#define DEFAULT_NLPFASTFAIL TRUE |
should the NLP solver stop early if it converges slow?
Definition at line 78 of file heur_nlpdiving.c.
#define DEFAULT_RANDSEED 97 |
initial random seed
Definition at line 79 of file heur_nlpdiving.c.
#define MINNLPITER 10 |
minimal number of NLP iterations allowed in each NLP solving call
Definition at line 81 of file heur_nlpdiving.c.
|
static |
gets fractional variables of last NLP solution along with solution values and fractionalities
scip | SCIP data structure |
heurdata | heuristic data structure |
nlpcands | pointer to store the array of NLP fractional variables, or NULL |
nlpcandssol | pointer to store the array of NLP fractional variables solution values, or NULL |
nlpcandsfrac | pointer to store the array of NLP fractional variables fractionalities, or NULL |
nnlpcands | pointer to store the number of NLP fractional variables , or NULL |
Definition at line 139 of file heur_nlpdiving.c.
References chooseFracVar(), SCIP_CALL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPfeastol(), SCIPgetLPSolstat(), SCIPgetNLPFracVars(), SCIPgetSolVal(), SCIPisFeasIntegral(), SCIPsetSolVal(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().
|
static |
finds best candidate variable w.r.t. fractionality:
scip | original SCIP data structure |
heurdata | heuristic data structure |
nlpcands | array of NLP fractional variables |
nlpcandssol | array of NLP fractional variables solution values |
nlpcandsfrac | array of NLP fractional variables fractionalities |
nnlpcands | number of NLP fractional variables |
varincover | hash map for variables |
covercomputed | has a minimal cover been computed? |
bestcand | pointer to store the index of the best candidate variable |
bestcandmayround | pointer to store whether best candidate is trivially roundable |
bestcandroundup | pointer to store whether best candidate should be rounded up |
Definition at line 214 of file heur_nlpdiving.c.
References chooseVeclenVar(), FALSE, SCIP_Bool, SCIP_INVALID, SCIP_OKAY, SCIP_PROBINGSCORE_PENALTYRATIO, SCIP_Real, SCIPhashmapExists(), SCIPinfinity(), SCIPisEQ(), SCIPisGT(), SCIPisLT(), SCIPrandomGetInt(), SCIPvarGetLbLocal(), SCIPvarGetObj(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), SCIPvarMayRoundDown(), SCIPvarMayRoundUp(), and TRUE.
Referenced by getNLPFracVars().
|
static |
finds best candidate variable w.r.t. vector length:
scip | original SCIP data structure |
heurdata | heuristic data structure |
nlpcands | array of NLP fractional variables |
nlpcandssol | array of NLP fractional variables solution values |
nlpcandsfrac | array of NLP fractional variables fractionalities |
nnlpcands | number of NLP fractional variables |
varincover | hash map for variables |
covercomputed | has a minimal cover been computed? |
bestcand | pointer to store the index of the best candidate variable |
bestcandmayround | pointer to store whether best candidate is trivially roundable |
bestcandroundup | pointer to store whether best candidate should be rounded up |
Definition at line 390 of file heur_nlpdiving.c.
References chooseCoefVar(), SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIP_VARTYPE_BINARY, SCIPhashmapExists(), SCIPisGT(), SCIPisLT(), SCIPsumepsilon(), SCIPvarGetLbLocal(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarGetUbLocal(), SCIPvarMayRoundDown(), SCIPvarMayRoundUp(), and TRUE.
Referenced by chooseFracVar().
|
static |
finds best candidate variable w.r.t. locking numbers:
scip | original SCIP data structure |
heurdata | heuristic data structure |
nlpcands | array of NLP fractional variables |
nlpcandssol | array of NLP fractional variables solution values |
nlpcandsfrac | array of NLP fractional variables fractionalities |
nnlpcands | number of NLP fractional variables |
varincover | hash map for variables |
covercomputed | has a minimal cover been computed? |
bestcand | pointer to store the index of the best candidate variable |
bestcandmayround | pointer to store whether best candidate is trivially roundable |
bestcandroundup | pointer to store whether best candidate should be rounded up |
Definition at line 484 of file heur_nlpdiving.c.
References calcPscostQuot(), FALSE, SCIP_Bool, SCIP_INVALID, SCIP_OKAY, SCIP_PROBINGSCORE_PENALTYRATIO, SCIP_Real, SCIPhashmapExists(), SCIPisEQ(), SCIPisGT(), SCIPisLT(), SCIPrandomGetInt(), SCIPvarGetLbLocal(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), SCIPvarMayRoundDown(), SCIPvarMayRoundUp(), and TRUE.
Referenced by chooseVeclenVar().
|
static |
calculates the pseudocost score for a given variable w.r.t. a given solution value and a given rounding direction
scip | SCIP data structure |
heurdata | heuristic data structure |
var | problem variable |
primsol | primal solution of variable |
frac | fractionality of variable |
rounddir | -1: round down, +1: round up, 0: select due to pseudo cost values |
pscostquot | pointer to store pseudo cost quotient |
roundup | pointer to store whether the variable should be rounded up |
prefvar | should this variable be preferred because it is in a minimal cover? |
Definition at line 669 of file heur_nlpdiving.c.
References choosePscostVar(), FALSE, MAX, SCIP_Real, SCIPfeasFloor(), SCIPgetVarPseudocostVal(), SCIPisEQ(), SCIPisGT(), SCIPisLT(), SCIPrandomGetInt(), SCIPvarGetRootSol(), SCIPvarIsBinary(), sqrt(), and TRUE.
Referenced by chooseCoefVar(), and choosePscostVar().
|
static |
finds best candidate variable w.r.t. pseudo costs:
scip | original SCIP data structure |
heurdata | heuristic data structure |
nlpcands | array of NLP fractional variables |
nlpcandssol | array of NLP fractional variables solution values |
nlpcandsfrac | array of NLP fractional variables fractionalities |
nnlpcands | number of NLP fractional variables |
varincover | hash map for variables |
covercomputed | has a minimal cover been computed? |
bestcand | pointer to store the index of the best candidate variable |
bestcandmayround | pointer to store whether best candidate is trivially roundable |
bestcandroundup | pointer to store whether best candidate should be rounded up |
Definition at line 749 of file heur_nlpdiving.c.
References calcPscostQuot(), chooseGuidedVar(), FALSE, SCIP_Bool, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPhashmapExists(), SCIPisGT(), SCIPisInfinity(), SCIPisLT(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarMayRoundDown(), SCIPvarMayRoundUp(), and TRUE.
Referenced by calcPscostQuot().
|
static |
finds best candidate variable w.r.t. the incumbent solution:
scip | original SCIP data structure |
heurdata | heuristic data structure |
nlpcands | array of NLP fractional variables |
nlpcandssol | array of NLP fractional variables solution values |
nlpcandsfrac | array of NLP fractional variables fractionalities |
nnlpcands | number of NLP fractional variables |
bestsol | incumbent solution |
varincover | hash map for variables |
covercomputed | has a minimal cover been computed? |
bestcand | pointer to store the index of the best candidate variable |
bestcandmayround | pointer to store whether best candidate is trivially roundable |
bestcandroundup | pointer to store whether best candidate should be rounded up |
Definition at line 871 of file heur_nlpdiving.c.
References chooseDoubleVar(), FALSE, SCIP_Bool, SCIP_INVALID, SCIP_OKAY, SCIP_PROBINGSCORE_PENALTYRATIO, SCIP_Real, SCIPgetSolVal(), SCIPhashmapExists(), SCIPinfinity(), SCIPisEQ(), SCIPisGT(), SCIPisLT(), SCIPrandomGetInt(), SCIPvarGetLbLocal(), SCIPvarGetObj(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), SCIPvarMayRoundDown(), SCIPvarMayRoundUp(), and TRUE.
Referenced by choosePscostVar().
|
static |
finds best candidate variable w.r.t. both, the LP and the NLP solution:
scip | original SCIP data structure |
heurdata | heuristic data structure |
pseudocands | array of non-fixed variables |
pseudocandsnlpsol | array of NLP solution values |
pseudocandslpsol | array of LP solution values |
npseudocands | number of NLP fractional variables |
varincover | hash map for variables |
covercomputed | has a minimal cover been computed? |
bestcand | pointer to store the index of the best candidate variable |
bestboundval | pointer to store the bound, the best candidate should be rounded to |
bestcandmayround | pointer to store whether best candidate is trivially roundable |
bestcandroundup | pointer to store whether best candidate should be rounded up |
Definition at line 1043 of file heur_nlpdiving.c.
References createNewSol(), FALSE, MAX, SCIP_Bool, SCIP_INVALID, SCIP_OKAY, SCIP_PROBINGSCORE_PENALTYRATIO, SCIP_Real, SCIPfeasCeil(), SCIPfeasFloor(), SCIPhashmapExists(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPrandomGetInt(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), SCIPvarMayRoundDown(), SCIPvarMayRoundUp(), and TRUE.
Referenced by chooseGuidedVar().
|
static |
creates a new solution for the original problem by copying the solution of the subproblem
scip | original SCIP data structure |
subscip | SCIP structure of the subproblem |
heur | heuristic structure |
varmap | hash map for variables |
subsol | solution of the subproblem |
success | used to store whether new solution was found or not |
Definition at line 1194 of file heur_nlpdiving.c.
References doSolveSubMIP(), FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcreateSol(), SCIPfreeBufferArray, SCIPgetNOrigVars(), SCIPgetSolVals(), SCIPgetVarsData(), SCIPhashmapGetImage(), SCIPsetSolVals(), SCIPtrySolFree(), and TRUE.
Referenced by chooseDoubleVar(), and doSolveSubMIP().
|
static |
todo setup and solve the subMIP
scip | SCIP data structure |
subscip | NLP diving subscip |
heur | heuristic data structure |
covervars | variables in the cover, should be fixed locally |
ncovervars | number of variables in the cover |
success | pointer to store whether a solution was found |
Definition at line 1246 of file heur_nlpdiving.c.
References createNewSol(), FALSE, SCIP_CALL, SCIP_CALL_ABORT, SCIP_Longint, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_Real, SCIPblkmem(), SCIPcopyConsCompression(), SCIPcopyLimits(), SCIPfindBranchrule(), SCIPfindNodesel(), SCIPgetLowerbound(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetSols(), SCIPgetUpperbound(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPisParamFixed(), SCIPsetBoolParam(), SCIPsetCharParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPsolve(), SCIPsumepsilon(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), solveSubMIP(), and TRUE.
Referenced by createNewSol(), and solveSubMIP().
|
static |
solves subproblem and passes best feasible solution to original SCIP instance
scip | SCIP data structure of the original problem |
heur | heuristic data structure |
covervars | variables in the cover, should be fixed locally |
ncovervars | number of variables in the cover |
success | pointer to store whether a solution was found |
Definition at line 1381 of file heur_nlpdiving.c.
References doSolveSubMIP(), SCIP_CALL, SCIP_DECL_EVENTEXEC(), SCIP_OKAY, SCIPcheckCopyLimits(), SCIPcreate(), and SCIPfree().
Referenced by doSolveSubMIP().
|
static |
Definition at line 1420 of file heur_nlpdiving.c.
Referenced by solveSubMIP().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 1485 of file heur_nlpdiving.c.
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 1499 of file heur_nlpdiving.c.
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 1519 of file heur_nlpdiving.c.
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 1553 of file heur_nlpdiving.c.
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 1587 of file heur_nlpdiving.c.
|
static |
execution method of primal heuristic
Definition at line 1609 of file heur_nlpdiving.c.