mpec primal heuristic
Definition in file heur_mpec.c.
#include <assert.h>
#include <string.h>
#include "scip/heur_mpec.h"
#include "scip/heur_subnlp.h"
#include "nlpi/nlpi.h"
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "mpec" |
#define | HEUR_DESC "regularization heuristic for convex and nonconvex MINLPs" |
#define | HEUR_DISPCHAR 'W' |
#define | HEUR_PRIORITY -2050000 |
#define | HEUR_FREQ 50 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE |
#define | HEUR_USESSUBSCIP TRUE |
#define | DEFAULT_INITTHETA 0.125 |
#define | DEFAULT_SIGMA 0.5 |
#define | DEFAULT_MAXITER 100 |
#define | DEFAULT_MAXNLPITER 500 |
#define | DEFAULT_MINGAPLEFT 0.05 |
#define | DEFAULT_SUBNLPTRIGGER 1e-3 |
#define | DEFAULT_MAXNLPCOST 1e+8 |
#define | DEFAULT_MINIMPROVE 0.01 |
#define | DEFAULT_MAXNUNSUCC 10 |
Functions | |
static SCIP_RETCODE | createNLP (SCIP *scip, SCIP_HEURDATA *heurdata) |
static SCIP_RETCODE | freeNLP (SCIP *scip, SCIP_HEURDATA *heurdata) |
static SCIP_RETCODE | addRegularScholtes (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **binvars, int nbinvars, SCIP_Real theta, SCIP_Bool update) |
static int | getExprSize (SCIP_EXPR *expr) |
static int | getExprtreeSize (SCIP_EXPRTREE *tree) |
static SCIP_RETCODE | getTimeLeft (SCIP *scip, SCIP_Real *timeleft) |
static SCIP_RETCODE | heurExec (SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_RESULT *result) |
static | SCIP_DECL_HEURCOPY (heurCopyMpec) |
static | SCIP_DECL_HEURFREE (heurFreeMpec) |
static | SCIP_DECL_HEURINITSOL (heurInitsolMpec) |
static | SCIP_DECL_HEUREXITSOL (heurExitsolMpec) |
static | SCIP_DECL_HEUREXEC (heurExecMpec) |
SCIP_RETCODE | SCIPincludeHeurMpec (SCIP *scip) |
#define HEUR_NAME "mpec" |
Definition at line 32 of file heur_mpec.c.
Referenced by SCIP_DECL_HEURCOPY(), and SCIPincludeHeurMpec().
#define HEUR_DESC "regularization heuristic for convex and nonconvex MINLPs" |
Definition at line 33 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
#define HEUR_DISPCHAR 'W' |
Definition at line 34 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
#define HEUR_PRIORITY -2050000 |
Definition at line 35 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
#define HEUR_FREQ 50 |
Definition at line 36 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
#define HEUR_FREQOFS 0 |
Definition at line 37 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
#define HEUR_MAXDEPTH -1 |
Definition at line 38 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE |
Definition at line 39 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
#define HEUR_USESSUBSCIP TRUE |
disable the heuristic in sub-SCIPs, even though it does not use any
Definition at line 40 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
#define DEFAULT_INITTHETA 0.125 |
default initial regularization right-hand side value (< 0.25)
Definition at line 42 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
#define DEFAULT_SIGMA 0.5 |
default regularization update factor (< 1)
Definition at line 43 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
#define DEFAULT_MAXITER 100 |
default maximum number of iterations of the MPEC loop
Definition at line 44 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
#define DEFAULT_MAXNLPITER 500 |
default maximum number of NLP iterations per solve
Definition at line 45 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
#define DEFAULT_MINGAPLEFT 0.05 |
default minimum amount of gap left in order to call the heuristic
Definition at line 46 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
#define DEFAULT_SUBNLPTRIGGER 1e-3 |
default maximum integrality violation before triggering a sub-NLP call
Definition at line 47 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
#define DEFAULT_MAXNLPCOST 1e+8 |
default maximum cost available for solving NLPs per call of the heuristic
Definition at line 48 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
#define DEFAULT_MINIMPROVE 0.01 |
default factor by which heuristic should at least improve the incumbent
Definition at line 49 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
#define DEFAULT_MAXNUNSUCC 10 |
default maximum number of consecutive calls for which the heuristic did not find an improving solution
Definition at line 50 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
|
static |
creates the data structure for generating the current NLP relaxation
scip | SCIP data structure |
heurdata | heuristic data |
Definition at line 85 of file heur_mpec.c.
References FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPblkmem(), SCIPcreateNlpiProb(), SCIPdebugMsg, SCIPgetLowerbound(), SCIPgetNLPNlRows(), SCIPgetNNLPNlRows(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetUpperbound(), SCIPhashmapCreate(), SCIPinfinity(), SCIPisInfinity(), SCIPnlpiCreateProblem(), SCIPsumepsilon(), and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
frees the data structures for the NLP relaxation
scip | SCIP data structure |
heurdata | heuristic data |
Definition at line 133 of file heur_mpec.c.
References SCIP_CALL, SCIP_OKAY, SCIPhashmapFree(), and SCIPnlpiFreeProblem().
Referenced by SCIP_DECL_HEUREXEC().
|
static |
add or updates the regularization constraints to the NLP; for a given parameter theta we add for each non-fixed binary variable z the constraint z*(1-z) <= theta; if these constraint are already present we update the theta on the right-hand side
scip | SCIP data structure |
heurdata | heuristic data |
binvars | array containing all non-fixed binary variables |
nbinvars | total number of non-fixed binary variables |
theta | regularization parameter |
update | should the regularization constraints be added or updated? |
Definition at line 158 of file heur_mpec.c.
References SCIP_QuadElement::coef, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetNNLPNlRows(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPinfinity(), SCIPnlpiAddConstraints(), and SCIPnlpiChgConsSides().
Referenced by heurExec().
|
static |
recursive helper function to count the number of nodes in a sub-tree
expr | expression |
Definition at line 241 of file heur_mpec.c.
References SCIPexprGetChildren(), and SCIPexprGetNChildren().
Referenced by getExprtreeSize().
|
static |
returns the number of nodes in an expression tree
tree | expression tree |
Definition at line 261 of file heur_mpec.c.
References getExprSize(), and SCIPexprtreeGetRoot().
Referenced by heurExec().
|
static |
returns the available time limit that is left
scip | SCIP data structure |
timeleft | pointer to store the remaining time limit |
Definition at line 272 of file heur_mpec.c.
References SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPinfinity(), and SCIPisInfinity().
Referenced by heurExec().
|
static |
main execution function of the MPEC heuristic
scip | SCIP data structure |
heur | MPEC heuristic |
heurdata | heuristic data |
result | pointer to store the result |
Definition at line 293 of file heur_mpec.c.
References addRegularScholtes(), BMScopyMemoryArray, FALSE, getExprtreeSize(), getTimeLeft(), MAX, SCIP_Bool, SCIP_CALL, SCIP_FOUNDSOL, SCIP_NLPPAR_FEASTOL, SCIP_NLPPAR_ITLIM, SCIP_NLPPAR_RELOBJTOL, SCIP_NLPPAR_TILIM, SCIP_NLPPAR_VERBLEVEL, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_NLPSOLSTAT_LOCINFEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPallocBufferArray, SCIPapplyHeurSubNlp(), SCIPblkmem(), SCIPcreateSol(), SCIPdebugMsg, SCIPdualfeastol(), SCIPfeasRound(), SCIPfeastol(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPfreeSol(), SCIPgetNBinVars(), SCIPgetNLPNlRows(), SCIPgetNNLPNlRows(), SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPhashmapGetImage(), SCIPinfinity(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisLE(), SCIPisStopped(), SCIPnlpiChgVarBounds(), SCIPnlpiGetSolstat(), SCIPnlpiGetSolution(), SCIPnlpiGetStatistics(), SCIPnlpiSetInitialGuess(), SCIPnlpiSetIntPar(), SCIPnlpiSetRealPar(), SCIPnlpiSolve(), SCIPnlpStatisticsCreate(), SCIPnlpStatisticsFree(), SCIPnlpStatisticsGetNIterations(), SCIPnlrowGetExprtree(), SCIPnlrowGetNLinearVars(), SCIPnlrowGetNQuadElems(), SCIPsetSolVal(), SCIPtrySolFree(), SCIPvarGetLbLocal(), SCIPvarGetType(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 607 of file heur_mpec.c.
References HEUR_NAME, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurMpec().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 619 of file heur_mpec.c.
References SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 632 of file heur_mpec.c.
References SCIP_OKAY, SCIPfindHeur(), SCIPgetNlpis(), SCIPgetNNlpis(), and SCIPheurGetData().
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
Definition at line 651 of file heur_mpec.c.
References SCIP_OKAY, and SCIPheurGetData().
|
static |
execution method of primal heuristic
Definition at line 663 of file heur_mpec.c.
References createNLP(), freeNLP(), heurExec(), SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_OKAY, SCIPconshdlrGetNConss(), SCIPfindConshdlr(), SCIPgetGap(), SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPheurGetData(), and SCIPisNLPConstructed().