33 #define HEUR_NAME "proximity" 34 #define HEUR_DESC "heuristic trying to improve the incumbent by an auxiliary proximity objective function" 35 #define HEUR_DISPCHAR 'P' 36 #define HEUR_PRIORITY -2000000 38 #define HEUR_FREQOFS 0 39 #define HEUR_MAXDEPTH -1 40 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE 41 #define HEUR_USESSUBSCIP TRUE 44 #define EVENTHDLR_NAME "Proximity" 45 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" 49 #define DEFAULT_MAXNODES 10000LL 50 #define DEFAULT_MINIMPROVE 0.02 51 #define DEFAULT_MINGAP 0.01 52 #define DEFAULT_MINNODES 1LL 53 #define DEFAULT_MINLPITERS 200LL 54 #define DEFAULT_MAXLPITERS 100000LL 55 #define DEFAULT_NODESOFS 50LL 56 #define DEFAULT_WAITINGNODES 100LL 57 #define DEFAULT_NODESQUOT 0.1 58 #define DEFAULT_USELPROWS FALSE 59 #define DEFAULT_BINVARQUOT 0.1 60 #define DEFAULT_RESTART TRUE 61 #define DEFAULT_USEFINALLP FALSE 62 #define DEFAULT_LPITERSQUOT 0.2 63 #define DEFAULT_USEUCT FALSE 125 assert(success !=
NULL);
129 nintvars = nvars - ncontvars;
133 if( requiresnlp || ncontvars == 0 )
140 for( v = 0; v < nvars; ++v )
149 for( v = 0; v < nintvars; ++v )
171 SCIPwarningMessage(scip,
"Error while solving LP in Proximity heuristic; LP solve terminated with code <%d>\n",retstat);
209 assert(scip !=
NULL);
210 assert(subscip !=
NULL);
211 assert(subvars !=
NULL);
212 assert(subsol !=
NULL);
213 assert(success !=
NULL);
242 sumofobjsquares = 0.0;
243 for( v = nvars - 1; v >= nvars - ncontvars; --v )
248 assert(vars[v] !=
NULL);
266 for( v = nvars - 1; v >= nvars - ncontvars; --v )
293 assert(subscip !=
NULL);
380 if( heurdata->subscip !=
NULL )
383 assert(heurdata->varmapfw !=
NULL);
384 assert(heurdata->subvars !=
NULL);
385 assert(heurdata->objcons !=
NULL);
387 SCIPdebugMsg(scip,
"Freeing subproblem of proximity heuristic\n");
393 heurdata->subscip =
NULL;
394 heurdata->varmapfw =
NULL;
395 heurdata->subvars =
NULL;
396 heurdata->objcons =
NULL;
412 assert(eventhdlr !=
NULL);
413 assert(eventdata !=
NULL);
415 assert(event !=
NULL);
419 assert(heurdata !=
NULL);
437 assert(heur !=
NULL);
452 assert( heur !=
NULL );
457 assert( heurdata !=
NULL );
473 assert( heur !=
NULL );
478 assert( heurdata !=
NULL );
481 heurdata->usednodes = 0LL;
482 heurdata->lastsolidx = -1;
483 heurdata->nusedlpiters = 0LL;
484 heurdata->subprobidx = 0;
486 heurdata->subscip =
NULL;
487 heurdata->varmapfw =
NULL;
488 heurdata->subvars =
NULL;
489 heurdata->objcons =
NULL;
491 heurdata->nsubvars = 0;
502 assert( heur !=
NULL );
507 assert( heurdata !=
NULL );
511 assert(heurdata->subscip ==
NULL && heurdata->varmapfw ==
NULL 512 && heurdata->subvars ==
NULL && heurdata->objcons ==
NULL);
527 assert(heur !=
NULL);
529 assert(result !=
NULL);
535 assert(heurdata !=
NULL);
544 nnodes += heurdata->nodesofs;
547 nnodes -= heurdata->usednodes;
548 nnodes =
MIN(nnodes, heurdata->maxnodes);
551 nlpiters =
MIN(nlpiters, heurdata->maxlpiters);
554 if( nnodes < heurdata->minnodes )
556 SCIPdebugMsg(
scip,
"skipping proximity: nnodes=%" SCIP_LONGINT_FORMAT
", minnodes=%" SCIP_LONGINT_FORMAT
"\n", nnodes, heurdata->minnodes);
563 SCIPdebugMsg(
scip,
"skipping proximity: pure feasibility problem anyway\n");
581 nlpiters =
MAX(nlpiters, heurdata->minlpiters);
587 assert(nusednodes <= nnodes);
588 heurdata->usednodes += nusednodes;
589 nnodes -= nusednodes;
591 nlpiters -= nusedlpiters;
592 heurdata->nusedlpiters += nusedlpiters;
605 if( heurdata->subscip !=
NULL )
630 assert(scip !=
NULL);
633 assert(heur !=
NULL);
636 if( heurdata !=
NULL )
689 assert(scip !=
NULL);
690 assert(heur !=
NULL);
691 assert(result !=
NULL);
694 assert(0.0 <= minimprove && minimprove <= 1.0);
700 assert(heurdata !=
NULL);
711 assert(incumbent !=
NULL);
719 if( heurdata->lastsolidx == solidx )
747 objcutoff = lowerbound + (1 - minimprove) * (bestobj - lowerbound);
754 objcutoff = lowerbound;
769 heurdata->lastsolidx = solidx;
775 if( heurdata->subscip ==
NULL )
777 assert(heurdata->varmapfw ==
NULL);
778 assert(heurdata->objcons ==
NULL);
794 SCIPdebugMsg(scip,
"Copying the SCIP instance was %s complete.\n", valid ?
"" :
"not ");
799 if( eventhdlr ==
NULL )
818 for( i = 0; i < nvars; i++ )
836 adjustedbound =
MAX(large, lb+large);
837 adjustedbound =
MIN(adjustedbound, inf);
842 adjustedbound =
MIN(-large, ub-large);
843 adjustedbound =
MAX(adjustedbound, -inf);
862 assert(heurdata->varmapfw !=
NULL);
863 assert(heurdata->subvars !=
NULL);
864 assert(heurdata->objcons !=
NULL);
866 subscip = heurdata->subscip;
867 varmapfw = heurdata->varmapfw;
868 subvars = heurdata->subvars;
869 objcons = heurdata->objcons;
872 assert(eventhdlr !=
NULL);
913 "nnodes: %" SCIP_LONGINT_FORMAT
" " 914 "iterlim: %" SCIP_LONGINT_FORMAT
"\n",
SCIPgetNNodes(scip), nnodes, iterlim);
922 assert(nfixedvars >= 0);
933 "usednodes: %" SCIP_LONGINT_FORMAT
" " 934 "lp iters: %" SCIP_LONGINT_FORMAT
" " 935 "root iters: %" SCIP_LONGINT_FORMAT
" " 936 "Presolving Time: %.2f\n", heurdata->subprobidx,
945 if( nusednodes !=
NULL )
947 if( nusedlpiters !=
NULL )
953 assert(nsubsols == 0 || incumbent !=
NULL);
971 heurdata->subscip = subscip;
972 heurdata->varmapfw = varmapfw;
973 heurdata->subvars = subvars;
974 heurdata->objcons = objcons;
975 heurdata->nsubvars = nvars;
1003 assert(heur !=
NULL);
1022 "maximum number of nodes to regard in the subproblem",
1026 "number of nodes added to the contingent of the total nodes",
1030 "minimum number of nodes required to start the subproblem",
1034 "maximum number of LP iterations to be performed in the subproblem",
1041 "waiting nodes since last incumbent before heuristic is executed", &heurdata->waitingnodes,
TRUE,
DEFAULT_WAITINGNODES,
1045 "factor by which proximity should at least improve the incumbent",
1052 "threshold for percentage of binary variables required to start",
1056 "quotient of sub-MIP LP iterations with respect to LP iterations so far",
1060 "minimum primal-dual gap for which the heuristic is executed",
1064 "should uct node selection be used at the beginning of the search?",
enum SCIP_Result SCIP_RESULT
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
#define DEFAULT_USELPROWS
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Longint SCIPgetNRootLPIterations(SCIP *scip)
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_Real SCIPfeastol(SCIP *scip)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
#define DEFAULT_MINIMPROVE
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_RETCODE SCIPincludeHeurProximity(SCIP *scip)
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
static SCIP_DECL_EVENTEXEC(eventExecProximity)
static SCIP_DECL_HEURCOPY(heurCopyProximity)
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
static SCIP_RETCODE solveLp(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
int SCIPgetNOrigVars(SCIP *scip)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
static SCIP_DECL_HEURINIT(heurInitProximity)
#define DEFAULT_BINVARQUOT
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
static SCIP_RETCODE deleteSubproblem(SCIP *scip, SCIP_HEURDATA *heurdata)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
#define DEFAULT_USEFINALLP
SCIP_Real SCIPinfinity(SCIP *scip)
enum SCIP_Retcode SCIP_RETCODE
#define SCIPstatisticMessage
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
SCIP_RETCODE SCIPchgVarLbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_Longint SCIPgetNRootFirstLPIterations(SCIP *scip)
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_EVENTHDLR * SCIPfindEventhdlr(SCIP *scip, const char *name)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
#define SCIPfreeBufferArray(scip, ptr)
SCIP_RETCODE SCIPcreate(SCIP **scip)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define SCIPallocBlockMemory(scip, ptr)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetPresolvingTime(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetObjNorm(SCIP *scip)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
int SCIPgetNFixedVars(SCIP *scip)
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
#define DEFAULT_MINLPITERS
SCIP_RETCODE SCIPsolve(SCIP *scip)
const char * SCIPheurGetName(SCIP_HEUR *heur)
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
#define DEFAULT_LPITERSQUOT
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
SCIP_RETCODE SCIPdeleteSubproblemProximity(SCIP *scip)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
SCIP_RETCODE SCIPpresolve(SCIP *scip)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool usefinallp, SCIP_Bool *success)
struct SCIP_EventData SCIP_EVENTDATA
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
static SCIP_DECL_HEUREXEC(heurExecProximity)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_NODESQUOT
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
#define DEFAULT_MAXLPITERS
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
SCIP_Longint SCIPsolGetNodenum(SCIP_SOL *sol)
SCIP_Real SCIPgetGap(SCIP *scip)
SCIP_RETCODE SCIPchgVarUbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
int SCIPgetNSols(SCIP *scip)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Constraint handler for linear constraints in their most general form, .
int SCIPgetNObjVars(SCIP *scip)
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
int SCIPgetNBinVars(SCIP *scip)
#define SCIP_EVENTTYPE_NODESOLVED
int SCIPgetNVars(SCIP *scip)
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
#define DEFAULT_WAITINGNODES
static SCIP_DECL_HEURFREE(heurFreeProximity)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
SCIP_RETCODE SCIPcopyLargeNeighborhoodSearch(SCIP *sourcescip, SCIP *subscip, SCIP_HASHMAP *varmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool uselprows, SCIP_Bool copycuts, SCIP_Bool *success, SCIP_Bool *valid)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
SCIP_Bool SCIPisStopped(SCIP *scip)
static SCIP_DECL_HEUREXITSOL(heurExitsolProximity)
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
SCIP_RETCODE SCIPstartDive(SCIP *scip)
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
SCIP_RETCODE SCIPapplyProximity(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real minimprove, SCIP_Longint nnodes, SCIP_Longint nlpiters, SCIP_Longint *nusednodes, SCIP_Longint *nusedlpiters, SCIP_Bool freesubscip)
SCIP_RETCODE SCIPendDive(SCIP *scip)
#define SCIP_CALL_ABORT(x)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
int SCIPsolGetIndex(SCIP_SOL *sol)
improvement heuristic which uses an auxiliary objective instead of the original objective function wh...
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 SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
static SCIP_RETCODE setupSubproblem(SCIP_HEURDATA *heurdata, SCIP *subscip)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)