30 #define HEUR_NAME "dins" 31 #define HEUR_DESC "distance induced neighborhood search by Ghosh" 32 #define HEUR_DISPCHAR 'D' 33 #define HEUR_PRIORITY -1105000 35 #define HEUR_FREQOFS 0 36 #define HEUR_MAXDEPTH -1 37 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE 38 #define HEUR_USESSUBSCIP TRUE 40 #define DEFAULT_NODESOFS 5000LL 41 #define DEFAULT_MAXNODES 5000LL 42 #define DEFAULT_MINNODES 50LL 43 #define DEFAULT_MINIMPROVE 0.01 44 #define DEFAULT_NODESQUOT 0.05 45 #define DEFAULT_LPLIMFAC 1.5 46 #define DEFAULT_MINFIXINGRATE 0.3 47 #define DEFAULT_NWAITINGNODES 200LL 48 #define DEFAULT_NEIGHBORHOODSIZE 18 49 #define DEFAULT_SOLNUM 5 50 #define DEFAULT_USELPROWS FALSE 52 #define DEFAULT_COPYCUTS TRUE 55 #define DEFAULT_BESTSOLLIMIT 3 56 #define DEFAULT_USEUCT FALSE 60 #define EVENTHDLR_NAME "Dins" 61 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" 128 if(
REALABS(lpsol - mipsol) >= 0.5 )
136 range = 2*lpsol-mipsol;
138 if( mipsol >= lpsol )
141 *lbptr =
MAX(*lbptr, range);
152 *ubptr =
MIN(*ubptr, range);
162 *lbptr =
MAX(*lbptr, lbglobal);
163 *ubptr =
MIN(*ubptr, ubglobal);
168 *lbptr =
MAX(mipsol, lbglobal);
169 *ubptr =
MIN(mipsol, ubglobal);
197 assert(scip !=
NULL);
198 assert(vars !=
NULL);
199 assert(fixedvars !=
NULL);
200 assert(fixedvals !=
NULL);
201 assert(binfixings !=
NULL);
202 assert(intfixings !=
NULL);
203 assert(heur !=
NULL);
207 assert(bestsol !=
NULL);
213 checklength =
MIN(nsols, heurdata->solnum);
214 assert(sols !=
NULL);
218 if( heurdata->deltalength < nbinvars )
223 assert(newsize >= nbinvars);
228 for( i = heurdata->deltalength; i < newsize; i++ )
229 heurdata->delta[i] =
TRUE;
231 heurdata->deltalength = newsize;
234 delta = heurdata->delta;
238 *intfixings = *binfixings = 0;
239 for( i = 0; i < nbinvars; i++ )
256 if( nsols > 1 && heurdata->lastnsolsfound != nsolsfound && delta[i] )
259 for( j = 1; delta[i] && j < checklength &&
SCIPgetSolHeur(scip, sols[j]) != heur ; j++ )
263 delta[i] = delta[i] &&
SCIPisFeasEQ(scip, mipsolval, solval);
270 fixedvars[nfixedvars] = vars[i];
271 fixedvals[nfixedvars] = mipsolval;
277 *binfixings = nfixedvars;
280 heurdata->lastnsolsfound = nsolsfound;
283 for( i = nbinvars; i < nbinvars + nintvars; ++i )
292 fixedvars[(nfixedvars)] = vars[i];
293 fixedvals[(nfixedvars)] = lb;
298 *intfixings = nfixedvars - *binfixings;
316 for( i = nbinvars; i < nbinvars + nintvars; ++i )
365 assert(bestsol !=
NULL);
372 rhs = (
SCIP_Real) heurdata->neighborhoodsize;
375 for( i = 0; i < nbinvars; i++ )
400 lhs, rhs,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
FALSE,
FALSE,
TRUE,
TRUE,
FALSE) );
426 assert(scip !=
NULL);
427 assert(heur !=
NULL);
428 assert(subscip !=
NULL);
429 assert(subvars !=
NULL);
430 assert(subsol !=
NULL);
452 SCIPdebugMsg(scip,
"DINS successfully found new solution\n");
471 assert(eventhdlr !=
NULL);
472 assert(eventdata !=
NULL);
474 assert(event !=
NULL);
478 assert(heurdata !=
NULL);
500 assert(heur !=
NULL);
515 assert(heur !=
NULL);
520 assert(heurdata !=
NULL);
537 assert(heur !=
NULL);
542 assert(heurdata !=
NULL);
545 heurdata->usednodes = 0;
546 heurdata->lastnsolsfound = 0;
552 if( heurdata->deltalength > 0 )
555 for( i = 0; i < heurdata->deltalength; i++ )
556 heurdata->delta[i] =
TRUE;
567 assert(heur !=
NULL);
572 assert(heurdata !=
NULL);
575 if( heurdata->deltalength > 0 )
611 assert(heur !=
NULL);
613 assert(result !=
NULL);
636 assert(heurdata !=
NULL);
652 maxnnodes += heurdata->nodesofs;
655 nsubnodes = maxnnodes - heurdata->usednodes;
656 nsubnodes =
MIN(nsubnodes , heurdata->maxnodes);
659 if( nsubnodes < heurdata->minnodes )
667 assert(nbinvars <= nvars);
670 if( nbinvars == 0 && nintvars == 0 )
680 assert(vars !=
NULL);
686 binfixings = intfixings = 0;
691 if( binfixings + intfixings == nbinvars + nintvars )
695 if( (binfixings + intfixings) / (
SCIP_Real)(
MAX(nbinvars + nintvars, 1)) < heurdata->minfixingrate )
712 heurdata->uselprows, heurdata->copycuts, &success,
NULL) );
716 if( eventhdlr ==
NULL )
722 SCIPdebugMsg(
scip,
"Copying the SCIP instance was %ssuccessful.\n", success ?
"" :
"not ");
724 SCIPdebugMsg(
scip,
"DINS subproblem: %d vars (%d binvars & %d intvars), %d cons\n",
728 for( i = 0; i < nvars; i++ )
735 if( nbinvars - binfixings > heurdata->neighborhoodsize )
741 if( intfixings < nintvars )
743 assert(nintvars > 0);
762 heurdata->nodelimit = nsubnodes;
827 cutoff =
MIN(upperbound, cutoff);
836 cutoff =
MIN(upperbound, cutoff);
841 if( !heurdata->uselprows )
843 assert(eventhdlr !=
NULL);
850 SCIPdebugMsg(
scip,
"solving DINS sub-MIP with neighborhoodsize %d and maxnodes %" SCIP_LONGINT_FORMAT
"\n", heurdata->neighborhoodsize, nsubnodes);
858 if( !heurdata->uselprows )
860 assert(eventhdlr !=
NULL);
870 SCIPdebugMsg(
scip,
"DINS used %" SCIP_LONGINT_FORMAT
"/%" SCIP_LONGINT_FORMAT
" nodes and found %d solutions\n",
SCIPgetNNodes(subscip), nsubnodes, nsubsols);
880 for( i = 0; i < nsubsols && !success; ++i )
919 assert(heur !=
NULL);
929 "number of nodes added to the contingent of the total nodes",
932 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
935 "minimum number of nodes required to start the subproblem",
938 "number of pool-solutions to be checked for flag array update (for hard fixing of binary variables)",
941 "radius (using Manhattan metric) of the incumbent's neighborhood to be searched",
944 "maximum number of nodes to regard in the subproblem",
947 "factor by which " HEUR_NAME " should at least improve the incumbent",
950 "number of nodes without incumbent change that heuristic should wait",
954 "factor by which the limit on the number of LP depends on the node limit",
958 "minimum percentage of integer variables that have to be fixable",
962 "should subproblem be created out of the rows in the LP rows?",
966 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
970 "should uct node selection be used at the beginning of the search?",
974 "limit on number of improving incumbent solutions in sub-CIP",
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
int SCIPgetNIntVars(SCIP *scip)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
#define SCIP_EVENTTYPE_LPSOLVED
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
int SCIPgetNOrigVars(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
static SCIP_RETCODE determineVariableFixings(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nbinvars, int nintvars, int *binfixings, int *intfixings)
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
SCIP_SOL ** SCIPgetSols(SCIP *scip)
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)
int SCIPsnprintf(char *t, int len, const char *s,...)
#define DEFAULT_MINFIXINGRATE
enum SCIP_Retcode SCIP_RETCODE
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
struct SCIP_HeurData SCIP_HEURDATA
static SCIP_DECL_HEURFREE(heurFreeDins)
#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)
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)
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
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 SCIPprintStatistics(SCIP *scip, FILE *file)
static SCIP_DECL_HEURINITSOL(heurInitsolDins)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
const char * SCIPgetProbName(SCIP *scip)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
SCIP_RETCODE SCIPsolve(SCIP *scip)
const char * SCIPheurGetName(SCIP_HEUR *heur)
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
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)
#define DEFAULT_NEIGHBORHOODSIZE
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
static SCIP_DECL_HEUREXITSOL(heurExitsolDins)
struct SCIP_EventData SCIP_EVENTDATA
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
#define DEFAULT_NODESQUOT
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
SCIP_RETCODE SCIPincludeHeurDins(SCIP *scip)
static SCIP_DECL_HEURCOPY(heurCopyDins)
#define SCIPallocBufferArray(scip, ptr, num)
#define DEFAULT_BESTSOLLIMIT
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)
#define DEFAULT_USELPROWS
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
static void computeIntegerVariableBounds(SCIP *scip, SCIP_VAR *var, SCIP_Real *lbptr, SCIP_Real *ubptr)
static SCIP_RETCODE reboundIntegerVariables(SCIP *scip, SCIP *subscip, SCIP_VAR **vars, SCIP_VAR **subvars, int nbinvars, int nintvars)
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 SCIPsetIntParam(SCIP *scip, const char *name, int value)
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
int SCIPgetNSols(SCIP *scip)
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
static SCIP_DECL_HEUREXEC(heurExecDins)
int SCIPgetNBinVars(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
static SCIP_RETCODE addLocalBranchingConstraint(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEURDATA *heurdata)
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success)
#define DEFAULT_MINIMPROVE
SCIP_Real SCIPgetLPObjval(SCIP *scip)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
int SCIPgetNConss(SCIP *scip)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
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_HEUR * SCIPgetSolHeur(SCIP *scip, SCIP_SOL *sol)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
#define DEFAULT_NWAITINGNODES
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
#define SCIP_CALL_ABORT(x)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
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)
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
static SCIP_DECL_EVENTEXEC(eventExecDins)
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)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
SCIP_Longint SCIPgetSolNodenum(SCIP *scip, SCIP_SOL *sol)