62#define HEUR_NAME "locks"
63#define HEUR_DESC "heuristic that fixes variables based on their rounding locks"
64#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP
65#define HEUR_PRIORITY 3000
68#define HEUR_MAXDEPTH -1
69#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
70#define HEUR_USESSUBSCIP TRUE
72#define DEFAULT_MAXNODES 5000LL
73#define DEFAULT_ROUNDUPPROBABILITY 0.67
74#define DEFAULT_MINFIXINGRATE 0.65
75#define DEFAULT_MINIMPROVE 0.01
77#define DEFAULT_MINNODES 500LL
78#define DEFAULT_NODESOFS 500LL
79#define DEFAULT_NODESQUOT 0.1
80#define DEFAULT_MAXPROPROUNDS 2
81#define DEFAULT_UPDATELOCKS TRUE
82#define DEFAULT_COPYCUTS TRUE
84#define DEFAULT_USEFINALSUBMIP TRUE
86#define DEFAULT_RANDSEED 73
87#define DEFAULT_MINFIXINGRATELP 0.0
94 SCIP_Longint maxnodes;
95 SCIP_Longint minnodes;
96 SCIP_Longint nodesofs;
98 SCIP_Real roundupprobability;
99 SCIP_Real minfixingrate;
100 SCIP_Real minfixingratelp;
101 SCIP_Real minimprove;
104 SCIP_Bool updatelocks;
107 SCIP_Bool usefinalsubmip;
185#define heurInitsolLocks NULL
186#define heurExitsolLocks NULL
196 SCIP_Bool* allrowsfulfilled
204 SCIP_Bool* fulfilled;
214 SCIP_Real lastfixval;
215 SCIP_Real randnumber;
216 SCIP_Real roundupprobability;
218 SCIP_Bool propagated;
221 SCIP_Bool updatelocks;
224 int nglbfulfilledrows;
251 *allrowsfulfilled =
FALSE;
258 maxproprounds =
heurdata->maxproprounds;
260 roundupprobability =
heurdata->roundupprobability;
282 nglbfulfilledrows = 0;
306 lastbestscore = INT_MAX;
326 bestscore = nuplocks[v] + ndownlocks[v];
329 if( bestscore < lastbestscore )
340 sortvars[
i] = sortvars[v];
344 nuplocks[
i] = nuplocks[v];
347 locks = ndownlocks[
i];
348 ndownlocks[
i] = ndownlocks[v];
349 ndownlocks[v] = locks;
365 score = nuplocks[
i] + ndownlocks[
i];
366 assert(score <= lastbestscore);
368 if( score > bestscore )
373 if( bestscore == lastbestscore )
380 lastbestscore = bestscore;
387 var = sortvars[bestpos];
388 sortvars[bestpos] = sortvars[v];
391 locks = nuplocks[bestpos];
392 nuplocks[bestpos] = nuplocks[v];
395 locks = ndownlocks[bestpos];
396 ndownlocks[bestpos] = ndownlocks[v];
397 ndownlocks[v] = locks;
427 if( ndownlocks[v] > nuplocks[v] )
429 else if( ndownlocks[v] < nuplocks[v] )
441 if( randnumber < roundupprobability )
448 lastfixlocks = lastfixval > 0.5 ? nuplocks[v] : ndownlocks[v];
452 SCIPdebugMsg(
scip,
"iteration %d: fixing variable <%s> to %d with locks (%d, %d)\n", v,
SCIPvarGetName(
var), lastfixval > 0.5 ? 1 : 0, ndownlocks[v], nuplocks[v]);
462 SCIPdebugMsg(
scip,
"last fixing led to infeasibility trying other bound\n");
468 if( lastfixval < 0.5 )
526 for(
r = 0;
r < ncolrows; ++
r )
542 if( fulfilled[rowpos] )
551 if( ((colvals[
r] > 0) == (lastfixval < 0.5)) )
553 maxact[rowpos] -=
REALABS(colvals[
r]);
555 if( ((colvals[
r] > 0) == (lastfixval > 0.5)) )
557 minact[rowpos] +=
REALABS(colvals[
r]);
578 for( pos = 0; pos <
nbinvars; ++pos )
583 fulfilled[rowpos] =
TRUE;
589 for(
w = ncols - 1;
w >= 0; --
w )
629 nglbfulfilledrows += nfulfilledrows;
630 SCIPdebugMsg(
scip,
"last fixing led to %d fulfilled rows, now %d of %d rows are fulfilled\n", nfulfilledrows, nglbfulfilledrows,
nlprows);
632 if( nglbfulfilledrows ==
nlprows )
634 *allrowsfulfilled =
TRUE;
661 SCIP_Real lowerbound;
664 SCIP_Bool allrowsfulfilled =
FALSE;
666 SCIP_Bool enabledconflicts;
726#ifdef COLLECTSTATISTICS
741 SCIPdebugMsg(
scip,
"npscands=%d, oldnpscands=%d, allrowsfulfilled=%u heurdata->minfixingrate=%g\n",
742 npscands, oldnpscands, allrowsfulfilled,
heurdata->minfixingrate);
744 if( !allrowsfulfilled && npscands > oldnpscands * (1 -
heurdata->minfixingrate) )
765 for(
i = 0;
i <
nvars && nfixedvars < nminfixings; ++
i )
771 SCIPdebugMsg(
scip,
"Fixed %d of %d (%.1f %%) variables after probing -> %s\n",
772 nfixedvars,
nvars, (100.0 * nfixedvars / (SCIP_Real)
nvars),
773 nfixedvars >= nminfixings ?
"continue and solve LP for remaining variables" :
"terminate without LP");
775 if( nfixedvars < nminfixings )
786 if( nunfixedcols > 0.5 * ncols )
789 "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n",
790 100.0 * (nunfixedcols / (SCIP_Real)ncols), nunfixedcols, ncols);
807 SCIPwarningMessage(
scip,
"Error while solving LP in LOCKS heuristic; LP solve terminated with code <%d>\n",
847#ifdef SCIP_MORE_DEBUG
873 SCIP_Longint nstallnodes;
886 nstallnodes =
MIN(nstallnodes,
heurdata->maxnodes);
889 if( nstallnodes < heurdata->minnodes )
966 SCIP_Real upperbound;
967 SCIP_Real minimprove;
968 SCIP_Real cutoffbound;
986 cutoffbound =
MIN(upperbound, cutoffbound);
1003 SCIPwarningMessage(
scip,
"Error while presolving subMIP in locks heuristic; sub-SCIP terminated with code <%d>\n", retstat);
1005 goto FREESCIPANDTERMINATE;
1029 SCIPwarningMessage(
scip,
"Error while solving subMIP in locks heuristic; sub-SCIP terminated with code <%d>\n",retstat);
1031 goto FREESCIPANDTERMINATE;
1053 FREESCIPANDTERMINATE:
1094 heurFreeLocks, heurInitLocks, heurExitLocks,
1099 "maximum number of propagation rounds to be performed in each propagation call (-1: no limit, -2: parameter settings)",
1103 "minimum percentage of integer variables that have to be fixable",
1107 "probability for rounding a variable up in case of ties",
1111 "should a final sub-MIP be solved to costruct a feasible solution if the LP was not roundable?",
1115 "maximum number of nodes to regard in the subproblem",
1119 "number of nodes added to the contingent of the total nodes",
1123 "minimum number of nodes required to start the subproblem",
1127 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1131 "factor by which " HEUR_NAME " heuristic should at least improve the incumbent",
1135 "should all active cuts from cutpool be copied to constraints in subproblem?",
1139 "should the locks be updated based on LP rows?",
1143 "minimum fixing rate over all variables (including continuous) to solve LP",
#define SCIP_MAXTREEDEPTH
#define SCIP_CALL_ABORT(x)
#define SCIP_LONGINT_FORMAT
SCIP_RETCODE SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
SCIP_RETCODE SCIPcopy(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
int SCIPgetNContVars(SCIP *scip)
int SCIPgetNCheckConss(SCIP *scip)
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
int SCIPgetNVars(SCIP *scip)
int SCIPgetNConss(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
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_Bool SCIPisParamFixed(SCIP *scip, const char *name)
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 SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
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 SCIPsetIntParam(SCIP *scip, const char *name, int value)
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
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 SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_RETCODE SCIPincludeHeurLocks(SCIP *scip)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
int SCIPgetNPseudoBranchCands(SCIP *scip)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
int SCIPcolGetNNonz(SCIP_COL *col)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
int SCIPconshdlrGetNCheckConss(SCIP_CONSHDLR *conshdlr)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
SCIP_RETCODE SCIPincludeHeur(SCIP *scip, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEURCOPY((*heurcopy)), SCIP_DECL_HEURFREE((*heurfree)), SCIP_DECL_HEURINIT((*heurinit)), SCIP_DECL_HEUREXIT((*heurexit)), SCIP_DECL_HEURINITSOL((*heurinitsol)), SCIP_DECL_HEUREXITSOL((*heurexitsol)), SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
const char * SCIPheurGetName(SCIP_HEUR *heur)
SCIP_RETCODE SCIPflushLP(SCIP *scip)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
int SCIPgetNLPRows(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
int SCIPgetNUnfixedLPCols(SCIP *scip)
int SCIPgetNLPCols(SCIP *scip)
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
#define SCIPallocClearBufferArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBufferArrayNull(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
int SCIPgetProbingDepth(SCIP *scip)
char * SCIPsnprintfProbingStats(SCIP *scip, char *strbuf, int len)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
SCIP_Bool SCIPinProbing(SCIP *scip)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_Real SCIPgetRowMinActivity(SCIP *scip, SCIP_ROW *row)
int SCIProwGetNNonz(SCIP_ROW *row)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
SCIP_Real SCIPgetRowMaxActivity(SCIP *scip, SCIP_ROW *row)
int SCIProwGetLPPos(SCIP_ROW *row)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
const char * SCIProwGetName(SCIP_ROW *row)
int SCIProwGetRank(SCIP_ROW *row)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
int SCIPgetNSols(SCIP *scip)
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
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)
SCIP_RETCODE SCIPcheckSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *feasible)
SCIP_RETCODE SCIPpresolve(SCIP *scip)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
int SCIPgetNRuns(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPsumepsilon(SCIP *scip)
int SCIPgetDepth(SCIP *scip)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
int SCIPvarGetProbindex(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
void SCIPenableVarHistory(SCIP *scip)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
assert(minobj< SCIPgetCutoffbound(scip))
SCIPlinkLPSol(scip, sol))
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
#define DEFAULT_NODESQUOT
#define DEFAULT_MINFIXINGRATELP
#define DEFAULT_ROUNDUPPROBABILITY
#define DEFAULT_MINFIXINGRATE
SCIP_RETCODE SCIPapplyLockFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Bool *cutoff, SCIP_Bool *allrowsfulfilled)
#define DEFAULT_MINIMPROVE
#define DEFAULT_UPDATELOCKS
SCIPfreeRandom(scip, &heurdata->randnumgen)
#define DEFAULT_USEFINALSUBMIP
#define DEFAULT_MAXPROPROUNDS
static SCIP_Bool propagate
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
public methods for managing constraints
public methods for primal heuristics
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
public methods for problem variables
public methods for branching rule plugins and branching
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for primal heuristic plugins and divesets
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for random numbers
public methods for solutions
public methods for querying solving statistics
public methods for timing
public methods for the branch-and-bound tree
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_HeurData SCIP_HEURDATA
#define SCIP_DECL_HEURINIT(x)
#define SCIP_DECL_HEUREXIT(x)
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXEC(x)
enum SCIP_LPSolStat SCIP_LPSOLSTAT
@ SCIP_LPSOLSTAT_INFEASIBLE
@ SCIP_LPSOLSTAT_OBJLIMIT
enum SCIP_Retcode SCIP_RETCODE