31 #define HEUR_NAME "proximity" 32 #define HEUR_DESC "heuristic trying to improve the incumbent by an auxiliary proximity objective function" 33 #define HEUR_DISPCHAR 'P' 34 #define HEUR_PRIORITY -2000000 36 #define HEUR_FREQOFS 0 37 #define HEUR_MAXDEPTH -1 38 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE 39 #define HEUR_USESSUBSCIP TRUE 42 #define EVENTHDLR_NAME "Proximity" 43 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" 47 #define DEFAULT_MAXNODES 10000LL 48 #define DEFAULT_MINIMPROVE 0.02 49 #define DEFAULT_MINGAP 0.01 50 #define DEFAULT_MINNODES 1LL 51 #define DEFAULT_MINLPITERS 200LL 52 #define DEFAULT_MAXLPITERS 100000LL 53 #define DEFAULT_NODESOFS 50LL 54 #define DEFAULT_WAITINGNODES 100LL 55 #define DEFAULT_NODESQUOT 0.1 56 #define DEFAULT_USELPROWS FALSE 57 #define DEFAULT_BINVARQUOT 0.1 58 #define DEFAULT_RESTART TRUE 59 #define DEFAULT_USEFINALLP FALSE 60 #define DEFAULT_LPITERSQUOT 0.2 61 #define DEFAULT_USEUCT FALSE 123 assert(success != NULL);
127 nintvars = nvars - ncontvars;
131 if( requiresnlp || ncontvars == 0 )
138 for( v = 0; v < nvars; ++v )
148 for( v = 0; v < nintvars; ++v )
170 SCIPwarningMessage(scip,
"Error while solving LP in Proximity heuristic; LP solve terminated with code <%d>\n",retstat);
208 assert(scip != NULL);
209 assert(subscip != NULL);
210 assert(subvars != NULL);
211 assert(subsol != NULL);
212 assert(success != NULL);
236 int ncontobjvars = 0;
240 for( v = nvars - 1; v >= nvars - ncontvars; --v )
245 assert(vars[v] != NULL);
264 for( v = nvars - 1; v >= nvars - ncontvars; --v )
291 assert(subscip != NULL);
377 if( heurdata->subscip != NULL )
379 assert(heurdata->varmapfw != NULL);
380 assert(heurdata->subvars != NULL);
381 assert(heurdata->objcons != NULL);
383 SCIPdebugMsg(scip,
"Freeing subproblem of proximity heuristic\n");
389 heurdata->subscip = NULL;
390 heurdata->varmapfw = NULL;
391 heurdata->subvars = NULL;
392 heurdata->objcons = NULL;
408 assert(eventhdlr != NULL);
409 assert(eventdata != NULL);
411 assert(event != NULL);
415 assert(heurdata != NULL);
434 assert(
scip != NULL);
435 assert(heur != NULL);
450 assert( heur != NULL );
451 assert(
scip != NULL );
455 assert( heurdata != NULL );
471 assert( heur != NULL );
472 assert(
scip != NULL );
476 assert( heurdata != NULL );
479 heurdata->usednodes = 0LL;
480 heurdata->lastsolidx = -1;
481 heurdata->nusedlpiters = 0LL;
482 heurdata->subprobidx = 0;
484 heurdata->subscip = NULL;
485 heurdata->varmapfw = NULL;
486 heurdata->subvars = NULL;
487 heurdata->objcons = NULL;
489 heurdata->nsubvars = 0;
500 assert( heur != NULL );
501 assert(
scip != NULL );
505 assert( heurdata != NULL );
509 assert(heurdata->subscip == NULL && heurdata->varmapfw == NULL && heurdata->subvars == NULL && heurdata->objcons == NULL);
523 assert(heur != NULL);
524 assert(
scip != NULL);
525 assert(result != NULL);
531 assert(heurdata != NULL);
540 nnodes += heurdata->nodesofs;
543 nnodes -= heurdata->usednodes;
544 nnodes = MIN(nnodes, heurdata->maxnodes);
547 nlpiters = MIN(nlpiters, heurdata->maxlpiters);
550 if( nnodes < heurdata->minnodes )
552 SCIPdebugMsg(
scip,
"skipping proximity: nnodes=%" SCIP_LONGINT_FORMAT
", minnodes=%" SCIP_LONGINT_FORMAT
"\n", nnodes, heurdata->minnodes);
559 SCIPdebugMsg(
scip,
"skipping proximity: pure feasibility problem anyway\n");
572 nlpiters =
MAX(nlpiters, heurdata->minlpiters);
578 assert(nusednodes <= nnodes);
579 heurdata->usednodes += nusednodes;
580 nnodes -= nusednodes;
582 nlpiters -= nusedlpiters;
583 heurdata->nusedlpiters += nusedlpiters;
596 if( heurdata->subscip != NULL )
621 assert(scip != NULL);
624 assert(heur != NULL);
627 if( heurdata != NULL )
680 assert(scip != NULL);
681 assert(heur != NULL);
682 assert(result != NULL);
685 assert(0.0 <= minimprove && minimprove <= 1.0);
691 assert(heurdata != NULL);
702 assert(incumbent != NULL);
710 if( heurdata->lastsolidx == solidx )
740 objcutoff = bestobj - 1;
742 objcutoff = (1 - minimprove) * bestobj;
745 objcutoff = minimprove * lowerbound + (1 - minimprove) * (bestobj);
752 objcutoff = lowerbound;
767 heurdata->lastsolidx = solidx;
773 if( heurdata->subscip == NULL )
775 assert(heurdata->varmapfw == NULL);
776 assert(heurdata->objcons == NULL);
792 SCIPdebugMsg(scip,
"Copying the SCIP instance was %s complete.\n", valid ?
"" :
"not ");
797 if( eventhdlr == NULL )
816 for( i = 0; i < nvars; i++ )
834 adjustedbound =
MAX(large, lb + large);
835 adjustedbound = MIN(adjustedbound, inf);
840 adjustedbound = MIN(-large, ub - large);
841 adjustedbound =
MAX(adjustedbound, -inf);
860 assert(heurdata->varmapfw != NULL);
861 assert(heurdata->subvars != NULL);
862 assert(heurdata->objcons != NULL);
864 subscip = heurdata->subscip;
865 varmapfw = heurdata->varmapfw;
866 subvars = heurdata->subvars;
867 objcons = heurdata->objcons;
870 assert(eventhdlr != NULL);
911 "nnodes: %" SCIP_LONGINT_FORMAT
" " 912 "iterlim: %" SCIP_LONGINT_FORMAT
"\n",
SCIPgetNNodes(scip), nnodes, iterlim);
920 assert(nfixedvars >= 0);
931 "usednodes: %" SCIP_LONGINT_FORMAT
" " 932 "lp iters: %" SCIP_LONGINT_FORMAT
" " 933 "root iters: %" SCIP_LONGINT_FORMAT
" " 934 "Presolving Time: %.2f\n", heurdata->subprobidx,
943 if( nusednodes != NULL )
945 if( nusedlpiters != NULL )
951 assert(nsubsols == 0 || incumbent != NULL);
969 heurdata->subscip = subscip;
970 heurdata->varmapfw = varmapfw;
971 heurdata->subvars = subvars;
972 heurdata->objcons = objcons;
973 heurdata->nsubvars = nvars;
1000 assert(heur != NULL);
1010 "should subproblem be constructed based on LP row information?",
1014 "should the heuristic immediately run again on its newly found solution?",
1018 "should the heuristic solve a final LP in case of continuous objective variables?",
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",
1038 "minimum number of LP iterations performed in subproblem",
1042 "waiting nodes since last incumbent before heuristic is executed",
1046 "factor by which proximity should at least improve the incumbent",
1050 "sub-MIP node limit w.r.t number of original nodes",
1054 "threshold for percentage of binary variables required to start",
1058 "quotient of sub-MIP LP iterations with respect to LP iterations so far",
1062 "minimum primal-dual gap for which the heuristic is executed",
1066 "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)