63#define HEUR_NAME "mpec"
64#define HEUR_DESC "regularization heuristic for convex and nonconvex MINLPs"
65#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING
66#define HEUR_PRIORITY -2050000
69#define HEUR_MAXDEPTH -1
70#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE
71#define HEUR_USESSUBSCIP TRUE
73#define DEFAULT_INITTHETA 0.125
74#define DEFAULT_SIGMA 0.5
75#define DEFAULT_MAXITER 100
76#define DEFAULT_MAXNLPITER 500
77#define DEFAULT_MINGAPLEFT 0.05
78#define DEFAULT_SUBNLPTRIGGER 1e-3
79#define DEFAULT_MAXNLPCOST 1e+8
80#define DEFAULT_MINIMPROVE 0.01
81#define DEFAULT_MAXNUNSUCC 10
226 SCIP_CALL(
SCIPcreateNlRow(
scip, &nlrows[
i], name, 0.0, 1, &binvars[
i], &one, sumexpr, -
SCIPinfinity(
scip), theta,
SCIP_EXPRCURV_CONCAVE) );
257 indices[
i] = startidx +
i;
402 binaryfeasible =
TRUE;
403 regularfeasible =
TRUE;
408 regularfeasible = regularfeasible &&
SCIPisLE(
scip, primal[idx] -
SQR(primal[idx]), theta);
410 maxviolreg =
MAX(maxviolreg, primal[idx] -
SQR(primal[idx]) - theta);
411 maxviolbin =
MAX(maxviolbin,
MIN(primal[idx], 1.0-primal[idx]));
413 SCIPdebugMsg(
scip,
"maxviol-regularization %g maxviol-integrality %g\n", maxviolreg, maxviolbin);
425 SCIPdebugMsg(
scip,
"call sub-NLP heuristic because binary infeasibility is small enough\n");
509 SCIPdebugMsg(
scip,
"NLP is infeasible but regularization constraints are satisfied -> stop!\n");
518 SCIPdebugMsg(
scip,
"NLP solution is not feasible for the NLP and the binary variables\n");
523 SCIPdebugMsg(
scip,
"fixing variables did not resolve infeasibility -> stop!\n");
545 lbs[j] = primal[idx] >= 0.5 ? 0.0 : 1.0;
546 ubs[j] = primal[idx] >= 0.5 ? 0.0 : 1.0;
563 initguess[idx] = primal[idx] >= 0.5 ? 0.0 : 1.0;
713 "initial regularization right-hand side value",
717 "regularization update factor",
721 "maximum number of NLP iterations per solve",
725 "maximum cost available for solving NLPs per call of the heuristic",
729 "factor by which heuristic should at least improve the incumbent",
733 "minimum amount of gap left in order to call the heuristic",
737 "maximum number of iterations of the MPEC loop",
741 "maximum number of NLP iterations per solve",
745 "maximum number of consecutive calls for which the heuristic did not find an improving solution",
power and signed power expression handlers
variable expression handler
SCIP_RETCODE SCIPcreateExprVar(SCIP *scip, SCIP_EXPR **expr, SCIP_VAR *var, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
SCIP_RETCODE SCIPcreateExprSum(SCIP *scip, SCIP_EXPR **expr, int nchildren, SCIP_EXPR **children, SCIP_Real *coefficients, SCIP_Real constant, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
SCIP_RETCODE SCIPcreateExprPow(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_Real exponent, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
SCIP_Bool SCIPisStopped(SCIP *scip)
int SCIPgetNIntVars(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
SCIP_RETCODE SCIPapplyHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_SOL *refpoint, SCIP_SOL *resultsol)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPincludeHeurMpec(SCIP *scip)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
int SCIPexprGetNChildren(SCIP_EXPR *expr)
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur,)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur,)
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
const char * SCIPheurGetName(SCIP_HEUR *heur)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBufferArrayNull(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_RETCODE SCIPaddNlpiProblemNlRows(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_NLROW **nlrows, int nnlrows)
SCIP_RETCODE SCIPcreateNlpiProblemFromNlRows(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **nlpiprob, const char *name, SCIP_NLROW **nlrows, int nnlrows, SCIP_HASHMAP *var2idx, SCIP_HASHMAP *nlrow2idx, SCIP_Real *nlscore, SCIP_Real cutoffbound, SCIP_Bool setobj, SCIP_Bool onlyconvex)
int SCIPgetNNlpis(SCIP *scip)
SCIP_NLPI ** SCIPgetNlpis(SCIP *scip)
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
int SCIPgetNNLPNlRows(SCIP *scip)
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
int SCIPnlrowGetNLinearVars(SCIP_NLROW *nlrow)
SCIP_RETCODE SCIPreleaseNlRow(SCIP *scip, SCIP_NLROW **nlrow)
SCIP_EXPR * SCIPnlrowGetExpr(SCIP_NLROW *nlrow)
SCIP_RETCODE SCIPcreateNlRow(SCIP *scip, SCIP_NLROW **nlrow, const char *name, SCIP_Real constant, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, SCIP_EXPR *expr, SCIP_Real lhs, SCIP_Real rhs, SCIP_EXPRCURV curvature)
int SCIPgetNSols(SCIP *scip)
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Real SCIPgetGap(SCIP *scip)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasRound(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
#define DEFAULT_MINIMPROVE
assert(minobj< SCIPgetCutoffbound(scip))
#define DEFAULT_SUBNLPTRIGGER
#define DEFAULT_MAXNUNSUCC
#define DEFAULT_MAXNLPITER
#define DEFAULT_MINGAPLEFT
static SCIP_RETCODE createNLP(SCIP *scip, SCIP_HEURDATA *heurdata)
#define DEFAULT_MAXNLPCOST
static SCIP_RETCODE heurExec(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_RESULT *result)
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)
#define DEFAULT_INITTHETA
static int getExprSize(SCIP_EXPR *expr)
NLP local search primal heuristic using sub-SCIPs.
memory allocation routines
#define BMSclearMemory(ptr)
#define BMScopyMemoryArray(ptr, source, num)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
public methods for managing constraints
public functions to work with algebraic expressions
public methods for primal heuristics
public methods for message output
public data structures and miscellaneous methods
public methods for NLP management
public methods for problem variables
public methods for constraint handler plugins and constraints
public methods for primal heuristic plugins and divesets
public methods for memory management
public methods for message handling
public methods for nonlinear relaxation
public methods for NLPI solver interfaces
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for solutions
public methods for querying solving statistics
public methods for timing
struct SCIP_Conshdlr SCIP_CONSHDLR
struct SCIP_Expr SCIP_EXPR
#define SCIP_DECL_HEURINITSOL(x)
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_HeurData SCIP_HEURDATA
struct SCIP_Heur SCIP_HEUR
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXITSOL(x)
#define SCIP_DECL_HEUREXEC(x)
struct SCIP_HashMap SCIP_HASHMAP
struct SCIP_NlRow SCIP_NLROW
struct SCIP_NlpiProblem SCIP_NLPIPROBLEM
struct SCIP_NlpStatistics SCIP_NLPSTATISTICS
struct SCIP_Nlpi SCIP_NLPI
#define SCIP_NLPPARAM_DEFAULT(scip)
enum SCIP_NlpSolStat SCIP_NLPSOLSTAT
@ SCIP_NLPSOLSTAT_LOCINFEASIBLE
@ SCIP_NLPSOLSTAT_FEASIBLE
struct SCIP_NlpParam SCIP_NLPPARAM
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE