32 #define HEUR_NAME "mpec" 33 #define HEUR_DESC "regularization heuristic for convex and nonconvex MINLPs" 34 #define HEUR_DISPCHAR 'W' 35 #define HEUR_PRIORITY -2050000 37 #define HEUR_FREQOFS 0 38 #define HEUR_MAXDEPTH -1 39 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE 40 #define HEUR_USESSUBSCIP TRUE 42 #define DEFAULT_INITTHETA 0.125 43 #define DEFAULT_SIGMA 0.5 44 #define DEFAULT_MAXITER 100 45 #define DEFAULT_MAXNLPITER 500 46 #define DEFAULT_MINGAPLEFT 0.05 47 #define DEFAULT_SUBNLPTRIGGER 1e-3 48 #define DEFAULT_MAXNLPCOST 1e+8 49 #define DEFAULT_MINIMPROVE 0.01 50 #define DEFAULT_MAXNUNSUCC 10 92 assert(heurdata != NULL);
93 assert(heurdata->nlpi != NULL);
96 if( heurdata->nlpiprob != NULL )
118 cutoff = MIN(upperbound, cutoff);
126 heurdata->nlpiprob, heurdata->var2idx, NULL, cutoff,
TRUE,
FALSE) );
138 assert(heurdata != NULL);
141 if( heurdata->nlpiprob == NULL )
144 assert(heurdata->nlpi != NULL);
145 assert(heurdata->var2idx != NULL);
169 assert(binvars != NULL);
170 assert(nbinvars > 0);
183 for( i = 0; i < nbinvars; ++i )
193 assert(heurdata->var2idx != NULL);
199 quadelems->
idx1 = lininds[0];
200 quadelems->
idx2 = lininds[0];
201 quadelems->
coef = -1.0;
204 &lininds, &linvals, &nquadelems, &quadelems, NULL, NULL, NULL) );
222 for( i = 0; i < nbinvars; ++i )
226 indices[i] = startidx + i;
248 assert(expr != NULL);
279 assert(timeleft != NULL);
308 SCIP_Real nlpcostleft = heurdata->maxnlpcost;
315 assert(heurdata->nlpiprob != NULL);
316 assert(heurdata->var2idx != NULL);
317 assert(heurdata->nlpi != NULL);
318 assert(result != NULL);
330 binvars[nbinvars++] = var;
347 assert(nlrow != NULL);
387 if( timeleft <= 0.0 )
403 SCIPdebugMsg(scip,
"error occured during NLP solve -> stop!\n");
413 assert(primal != NULL);
416 binaryfeasible =
TRUE;
417 regularfeasible =
TRUE;
418 for( j = 0; j < nbinvars; ++j )
422 regularfeasible = regularfeasible &&
SCIPisLE(scip, primal[idx] - SQR(primal[idx]), theta);
424 maxviolreg =
MAX(maxviolreg, primal[idx] - SQR(primal[idx]) - theta);
425 maxviolbin =
MAX(maxviolbin, MIN(primal[idx], 1.0-primal[idx]));
427 SCIPdebugMsg(scip,
"maxviol-regularization %g maxviol-integrality %g\n", maxviolreg, maxviolbin);
432 if( !subnlpcalled && heurdata->subnlp != NULL
433 && (
SCIPisLE(scip, maxviolbin, heurdata->subnlptrigger) || nlpcostleft <= 0.0)
439 SCIPdebugMsg(scip,
"call sub-NLP heuristic because binary infeasibility is small enough\n");
451 heurdata->minimprove, NULL,
454 SCIPdebugMsg(scip,
"result of sub-NLP call: %d\n", subnlpresult);
459 SCIPdebugMsg(scip,
"sub-NLP found a feasible solution -> stop!\n");
486 SCIPdebugMsg(scip,
"found a solution (stored = %u)\n", stored);
498 SCIPdebugMsg(scip,
"update theta from %g -> %g\n", theta, theta*heurdata->sigma);
506 theta *= heurdata->sigma;
512 for( j = 0; j < nbinvars; ++j )
526 SCIPdebugMsg(scip,
"NLP is infeasible but regularization constraints are satisfied -> stop!\n");
535 SCIPdebugMsg(scip,
"NLP solution is not feasible for the NLP and the binary variables\n");
540 SCIPdebugMsg(scip,
"fixing variables did not resolve infeasibility -> stop!\n");
550 for( j = 0; j < nbinvars; ++j )
555 if(
SCIPisFeasLE(scip, primal[idx] - SQR(primal[idx]), theta) )
562 lbs[j] = primal[idx] >= 0.5 ? 0.0 : 1.0;
563 ubs[j] = primal[idx] >= 0.5 ? 0.0 : 1.0;
568 SCIPdebugMsg(scip,
"fixed %d binary variables\n", nfixedvars);
577 for( j = 0; j < nbinvars; ++j )
580 initguess[idx] = primal[idx] >= 0.5 ? 0.0 : 1.0;
622 assert(heurdata != NULL);
636 assert(heurdata != NULL);
637 assert(heurdata->nlpi == NULL);
655 assert(heurdata != NULL);
656 heurdata->nlpi = NULL;
670 assert(heurdata != NULL);
677 || heurdata->nunsucc > heurdata->maxnunsucc )
696 heurdata->nunsucc = (*result ==
SCIP_FOUNDSOL) ? 0 : heurdata->nunsucc + 1;
723 assert(heur != NULL);
733 "initial regularization right-hand side value",
737 "regularization update factor",
741 "maximum number of NLP iterations per solve",
745 "maximum cost available for solving NLPs per call of the heuristic",
749 "factor by which heuristic should at least improve the incumbent",
753 "minimum amount of gap left in order to call the heuristic",
757 "maximum number of iterations of the MPEC loop",
761 "maximum number of NLP iterations per solve",
765 "maximum number of consecutive calls for which the heuristic did not find an improving solution",
enum SCIP_Result SCIP_RESULT
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
SCIP_RETCODE SCIPincludeHeurMpec(SCIP *scip)
int SCIPgetNIntVars(SCIP *scip)
static SCIP_RETCODE heurExec(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_RESULT *result)
int SCIPgetNNLPNlRows(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_RETCODE SCIPnlpiGetStatistics(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_NLPSTATISTICS *statistics)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
static SCIP_DECL_HEURFREE(heurFreeMpec)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_RETCODE SCIPcreateNlpiProb(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLROW **nlrows, int nnlrows, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_Real *nlscore, SCIP_Real cutoffbound, SCIP_Bool setobj, SCIP_Bool onlyconvex)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
internal methods for NLPI solver interfaces
SCIP_RETCODE SCIPnlpiCreateProblem(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **problem, const char *name)
SCIP_Real SCIPfeasRound(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_RETCODE SCIPnlpiGetSolution(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_Real **primalvalues, SCIP_Real **consdualvalues, SCIP_Real **varlbdualvalues, SCIP_Real **varubdualvalues, SCIP_Real *objval)
SCIP_Real SCIPdualfeastol(SCIP *scip)
#define DEFAULT_SUBNLPTRIGGER
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
SCIP_RETCODE SCIPnlpiAddConstraints(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, int nconss, const SCIP_Real *lhss, const SCIP_Real *rhss, const int *nlininds, int *const *lininds, SCIP_Real *const *linvals, const int *nquadelems, SCIP_QUADELEM *const *quadelems, int *const *exprvaridxs, SCIP_EXPRTREE *const *exprtrees, const char **names)
static SCIP_RETCODE createNLP(SCIP *scip, SCIP_HEURDATA *heurdata)
#define DEFAULT_MAXNLPITER
SCIP_Real SCIPinfinity(SCIP *scip)
enum SCIP_Retcode SCIP_RETCODE
#define DEFAULT_MAXNLPCOST
int SCIPnlrowGetNLinearVars(SCIP_NLROW *nlrow)
struct SCIP_HeurData SCIP_HEURDATA
#define SCIPfreeBlockMemory(scip, ptr)
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 SCIPnlpiChgVarBounds(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, int nvars, const int *indices, const SCIP_Real *lbs, const SCIP_Real *ubs)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
void SCIPnlpStatisticsFree(BMS_BLKMEM *blkmem, SCIP_NLPSTATISTICS **statistics)
#define SCIPfreeBufferArray(scip, ptr)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define SCIPallocBlockMemory(scip, ptr)
#define DEFAULT_MAXNUNSUCC
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)
#define DEFAULT_MINGAPLEFT
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
int SCIPnlrowGetNQuadElems(SCIP_NLROW *nlrow)
static SCIP_DECL_HEUREXITSOL(heurExitsolMpec)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPnlpiSolve(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem)
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
static SCIP_RETCODE getTimeLeft(SCIP *scip, SCIP_Real *timeleft)
const char * SCIPheurGetName(SCIP_HEUR *heur)
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
static int getExprtreeSize(SCIP_EXPRTREE *tree)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
enum SCIP_NlpSolStat SCIP_NLPSOLSTAT
#define SCIPfreeBufferArrayNull(scip, ptr)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
static SCIP_DECL_HEURCOPY(heurCopyMpec)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
int SCIPgetNNlpis(SCIP *scip)
SCIP_RETCODE SCIPnlpiChgConsSides(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, int nconss, const int *indices, const SCIP_Real *lhss, const SCIP_Real *rhss)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_RETCODE SCIPnlpiSetInitialGuess(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_Real *primalvalues, SCIP_Real *consdualvalues, SCIP_Real *varlbdualvalues, SCIP_Real *varubdualvalues)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_HEUREXEC(heurExecMpec)
SCIP_EXPR * SCIPexprtreeGetRoot(SCIP_EXPRTREE *tree)
SCIP_NLPSOLSTAT SCIPnlpiGetSolstat(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem)
static SCIP_RETCODE freeNLP(SCIP *scip, SCIP_HEURDATA *heurdata)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPnlpiFreeProblem(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **problem)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
#define DEFAULT_INITTHETA
SCIP_RETCODE SCIPnlpiSetIntPar(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_NLPPARAM type, int ival)
SCIP_Real SCIPgetGap(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)
int SCIPexprGetNChildren(SCIP_EXPR *expr)
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
int SCIPgetNSols(SCIP *scip)
#define BMScopyMemoryArray(ptr, source, num)
SCIP_RETCODE SCIPapplyHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_SOL *refpoint, SCIP_Longint itercontingent, SCIP_Real timelimit, SCIP_Real minimprove, SCIP_Longint *iterused, SCIP_SOL *resultsol)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define BMSclearMemory(ptr)
int SCIPgetNBinVars(SCIP *scip)
static int getExprSize(SCIP_EXPR *expr)
int SCIPgetNVars(SCIP *scip)
SCIP_EXPRTREE * SCIPnlrowGetExprtree(SCIP_NLROW *nlrow)
static SCIP_DECL_HEURINITSOL(heurInitsolMpec)
NLP local search primal heuristic using sub-SCIPs.
SCIP_RETCODE SCIPnlpStatisticsCreate(BMS_BLKMEM *blkmem, SCIP_NLPSTATISTICS **statistics)
static SCIP_RETCODE addRegularScholtes(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **binvars, int nbinvars, SCIP_Real theta, SCIP_Bool update)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
SCIP_Bool SCIPisStopped(SCIP *scip)
int SCIPnlpStatisticsGetNIterations(SCIP_NLPSTATISTICS *statistics)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_NLPI ** SCIPgetNlpis(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
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)
#define DEFAULT_MINIMPROVE
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
SCIP_RETCODE SCIPnlpiSetRealPar(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_NLPPARAM type, SCIP_Real dval)