Detailed Description
mpec primal heuristic
Definition in file heur_mpec.c.
#include "blockmemshell/memory.h"
#include "nlpi/nlpi.h"
#include "nlpi/pub_expr.h"
#include "scip/heur_mpec.h"
#include "scip/heur_subnlp.h"
#include "scip/pub_cons.h"
#include "scip/pub_heur.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_nlp.h"
#include "scip/pub_var.h"
#include "scip/scip_cons.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nlp.h"
#include "scip/scip_nonlinear.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include <string.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 SCIP_HEURDISPCHAR_DIVING |
#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_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) |
Macro Definition Documentation
◆ HEUR_NAME
#define HEUR_NAME "mpec" |
Definition at line 52 of file heur_mpec.c.
Referenced by SCIP_DECL_HEURCOPY(), and SCIPincludeHeurMpec().
◆ HEUR_DESC
#define HEUR_DESC "regularization heuristic for convex and nonconvex MINLPs" |
Definition at line 53 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING |
Definition at line 54 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
◆ HEUR_PRIORITY
#define HEUR_PRIORITY -2050000 |
Definition at line 55 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
◆ HEUR_FREQ
#define HEUR_FREQ 50 |
Definition at line 56 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 57 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 58 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
◆ HEUR_TIMING
#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE |
Definition at line 59 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
◆ HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP TRUE |
disable the heuristic in sub-SCIPs, even though it does not use any
Definition at line 60 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
◆ DEFAULT_INITTHETA
#define DEFAULT_INITTHETA 0.125 |
default initial regularization right-hand side value (< 0.25)
Definition at line 62 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
◆ DEFAULT_SIGMA
#define DEFAULT_SIGMA 0.5 |
default regularization update factor (< 1)
Definition at line 63 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
◆ DEFAULT_MAXITER
#define DEFAULT_MAXITER 100 |
default maximum number of iterations of the MPEC loop
Definition at line 64 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
◆ DEFAULT_MAXNLPITER
#define DEFAULT_MAXNLPITER 500 |
default maximum number of NLP iterations per solve
Definition at line 65 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
◆ DEFAULT_MINGAPLEFT
#define DEFAULT_MINGAPLEFT 0.05 |
default minimum amount of gap left in order to call the heuristic
Definition at line 66 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
◆ DEFAULT_SUBNLPTRIGGER
#define DEFAULT_SUBNLPTRIGGER 1e-3 |
default maximum integrality violation before triggering a sub-NLP call
Definition at line 67 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
◆ DEFAULT_MAXNLPCOST
#define DEFAULT_MAXNLPCOST 1e+8 |
default maximum cost available for solving NLPs per call of the heuristic
Definition at line 68 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
◆ DEFAULT_MINIMPROVE
#define DEFAULT_MINIMPROVE 0.01 |
default factor by which heuristic should at least improve the incumbent
Definition at line 69 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
◆ DEFAULT_MAXNUNSUCC
#define DEFAULT_MAXNUNSUCC 10 |
default maximum number of consecutive calls for which the heuristic did not find an improving solution
Definition at line 70 of file heur_mpec.c.
Referenced by SCIPincludeHeurMpec().
Function Documentation
◆ createNLP()
|
static |
creates the data structure for generating the current NLP relaxation
- Parameters
-
scip SCIP data structure heurdata heuristic data
Definition at line 105 of file heur_mpec.c.
References FALSE, NULL, 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().
◆ freeNLP()
|
static |
frees the data structures for the NLP relaxation
- Parameters
-
heurdata heuristic data
Definition at line 153 of file heur_mpec.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPhashmapFree(), and SCIPnlpiFreeProblem().
Referenced by SCIP_DECL_HEUREXEC().
◆ addRegularScholtes()
|
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
- Parameters
-
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 177 of file heur_mpec.c.
References SCIP_QuadElement::coef, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetNNLPNlRows(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPinfinity(), SCIPnlpiAddConstraints(), and SCIPnlpiChgConsSides().
Referenced by heurExec().
◆ getExprSize()
|
static |
recursive helper function to count the number of nodes in a sub-tree
- Parameters
-
expr expression
Definition at line 260 of file heur_mpec.c.
References NULL, SCIPexprGetChildren(), and SCIPexprGetNChildren().
Referenced by getExprtreeSize().
◆ getExprtreeSize()
|
static |
returns the number of nodes in an expression tree
- Parameters
-
tree expression tree
Definition at line 280 of file heur_mpec.c.
References getExprSize(), NULL, and SCIPexprtreeGetRoot().
Referenced by heurExec().
◆ getTimeLeft()
|
static |
returns the available time limit that is left
- Parameters
-
scip SCIP data structure timeleft pointer to store the remaining time limit
Definition at line 291 of file heur_mpec.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPinfinity(), and SCIPisInfinity().
Referenced by heurExec().
◆ heurExec()
|
static |
main execution function of the MPEC heuristic
- Parameters
-
scip SCIP data structure heur MPEC heuristic heurdata heuristic data result pointer to store the result
Definition at line 312 of file heur_mpec.c.
References addRegularScholtes(), BMScopyMemoryArray, FALSE, getExprtreeSize(), getTimeLeft(), MAX, NULL, 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(), SCIPhashmapGetImageInt(), 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().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 626 of file heur_mpec.c.
References HEUR_NAME, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurMpec().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 638 of file heur_mpec.c.
References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().
◆ SCIP_DECL_HEURINITSOL()
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 651 of file heur_mpec.c.
References NULL, SCIP_OKAY, SCIPfindHeur(), SCIPgetNlpis(), SCIPgetNNlpis(), and SCIPheurGetData().
◆ SCIP_DECL_HEUREXITSOL()
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
Definition at line 670 of file heur_mpec.c.
References NULL, SCIP_OKAY, and SCIPheurGetData().
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 682 of file heur_mpec.c.
References createNLP(), freeNLP(), heurExec(), NULL, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_OKAY, SCIPconshdlrGetNConss(), SCIPfindConshdlr(), SCIPgetGap(), SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPheurGetData(), and SCIPisNLPConstructed().