29 #define HEUR_NAME "locks" 30 #define HEUR_DESC "heuristic that fixes variables based on their rounding locks" 31 #define HEUR_DISPCHAR 'k' 32 #define HEUR_PRIORITY 2000 34 #define HEUR_FREQOFS 0 35 #define HEUR_MAXDEPTH -1 36 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE 37 #define HEUR_USESSUBSCIP TRUE 39 #define DEFAULT_MAXNODES 5000LL 40 #define DEFAULT_ROUNDUPPROBABILITY 0.67 41 #define DEFAULT_MINFIXINGRATE 0.25 42 #define DEFAULT_MINIMPROVE 0.01 45 #define DEFAULT_MINNODES 500LL 46 #define DEFAULT_NODESOFS 500LL 47 #define DEFAULT_NODESQUOT 0.1 48 #define DEFAULT_MAXPROPROUNDS 2 49 #define DEFAULT_UPDATELOCKS TRUE 50 #define DEFAULT_COPYCUTS TRUE 52 #define DEFAULT_USEFINALSUBMIP TRUE 54 #define DEFAULT_RANDSEED 73 96 assert(subscip !=
NULL);
97 assert(subvars !=
NULL);
98 assert(subsol !=
NULL);
99 assert(success !=
NULL);
128 assert(scip !=
NULL);
129 assert(heur !=
NULL);
145 assert(heur !=
NULL);
164 assert(heurdata !=
NULL);
167 heurdata->usednodes = 0;
186 assert(heurdata !=
NULL);
194 #define heurInitsolLocks NULL 195 #define heurExitsolLocks NULL 233 int nglbfulfilledrows;
260 assert(heurdata !=
NULL);
262 propagate = (heurdata->maxproprounds != 0);
264 if( heurdata->maxproprounds == -2 )
267 maxproprounds = heurdata->maxproprounds;
269 roundupprobability = heurdata->roundupprobability;
300 assert(vars !=
NULL);
319 nglbfulfilledrows = 0;
322 for( v = 0; v < nbinvars; ++v )
330 for( r = 0; r < nlprows; ++r )
345 lastbestscore = INT_MAX;
348 for( v = 0; v < nbinvars && !cutoff; v++ )
363 bestscore = nuplocks[v] + ndownlocks[v];
366 if( bestscore < lastbestscore )
368 for( i = v + 1; i < nbinvars; ++i )
377 sortvars[i] = sortvars[v];
381 nuplocks[i] = nuplocks[v];
384 locks = ndownlocks[i];
385 ndownlocks[i] = ndownlocks[v];
386 ndownlocks[v] = locks;
402 score = nuplocks[i] + ndownlocks[i];
403 assert(score <= lastbestscore);
405 if( score > bestscore )
410 if( bestscore == lastbestscore )
417 lastbestscore = bestscore;
424 var = sortvars[bestpos];
425 sortvars[bestpos] = sortvars[v];
428 locks = nuplocks[bestpos];
429 nuplocks[bestpos] = nuplocks[v];
432 locks = ndownlocks[bestpos];
433 ndownlocks[bestpos] = ndownlocks[v];
434 ndownlocks[v] = locks;
448 assert(v == nbinvars);
464 if( ndownlocks[v] > nuplocks[v] )
466 else if( ndownlocks[v] < nuplocks[v] )
478 if( randnumber < roundupprobability )
485 lastfixlocks = lastfixval > 0.5 ? nuplocks[v] : ndownlocks[v];
489 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]);
491 if( propagate && lastfixlocks > 0 )
501 if( lastfixval < 0.5 )
516 SCIPdebugMsg(scip,
"last fixing led to infeasibility trying other bound\n");
535 for( r = 0; r < ncolrows; ++r )
544 assert(lprows[rowpos] == row);
551 if( fulfilled[rowpos] )
558 assert(hasrhs || haslhs);
560 if( ((colvals[r] > 0) == (lastfixval < 0.5)) )
562 maxact[rowpos] -=
REALABS(colvals[r]);
564 if( ((colvals[r] > 0) == (lastfixval > 0.5)) )
566 minact[rowpos] +=
REALABS(colvals[r]);
587 for( pos = 0; pos < nbinvars; ++pos )
592 fulfilled[rowpos] =
TRUE;
598 for( w = ncols - 1; w >= 0; --w )
629 SCIPdebugMsg(scip,
"row <%s> activity [%g,%g] violates bounds, lhs = %g, rhs = %g\n",
637 SCIPdebugMsg(scip,
"found infeasible row, stopping heur\n");
641 nglbfulfilledrows += nfulfilledrows;
642 SCIPdebugMsg(scip,
"last fixing led to %d fulfilled rows, now %d of %d rows are fulfilled\n", nfulfilledrows, nglbfulfilledrows, nlprows);
644 if( nglbfulfilledrows == nlprows )
652 SCIPdebugMsg(scip,
"npscands=%d, oldnpscands=%d, heurdata->minfixingrate=%g\n", npscands, oldnpscands, heurdata->minfixingrate);
654 if( nglbfulfilledrows != nlprows && npscands > oldnpscands * (1 - heurdata->minfixingrate) )
676 SCIPwarningMessage(scip,
"Error while solving LP in LOCKS heuristic; LP solve terminated with code <%d>\n",
712 #ifdef SCIP_MORE_DEBUG 743 nstallnodes += heurdata->nodesofs;
746 nstallnodes -= heurdata->usednodes;
747 nstallnodes =
MIN(nstallnodes, heurdata->maxnodes);
750 if( nstallnodes < heurdata->minnodes )
752 SCIPdebugMsg(scip,
"skipping " HEUR_NAME ": nstallnodes=%" SCIP_LONGINT_FORMAT
", minnodes=%" SCIP_LONGINT_FORMAT
"\n", nstallnodes, heurdata->minnodes);
776 if( heurdata->copycuts )
782 for( i = 0; i < nvars; i++ )
842 minimprove = heurdata->minimprove;
858 cutoffbound =
MIN(upperbound, cutoffbound);
860 SCIPdebugMsg(scip,
"setting objlimit for subscip to %g\n", cutoffbound);
875 SCIPwarningMessage(scip,
"Error while presolving subMIP in locks heuristic; sub-SCIP terminated with code <%d>\n", retstat);
877 goto FREESCIPANDTERMINATE;
895 SCIPdebugMsg(scip,
"solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT
", maxnodes=%" SCIP_LONGINT_FORMAT
"\n", nstallnodes, heurdata->maxnodes);
903 SCIPwarningMessage(scip,
"Error while solving subMIP in locks heuristic; sub-SCIP terminated with code <%d>\n",retstat);
905 goto FREESCIPANDTERMINATE;
920 for( i = 0; i < nsubsols && !success; ++i )
934 FREESCIPANDTERMINATE:
979 heurFreeLocks, heurInitLocks, heurExitLocks,
984 "maximum number of propagation rounds to be performed in each propagation call (-1: no limit, -2: parameter settings)",
988 "minimum percentage of integer variables that have to be fixable",
992 "probability for rounding a variable up in case of ties",
996 "should a final sub-MIP be solved to costruct a feasible solution if the LP was not roundable?",
1000 "maximum number of nodes to regard in the subproblem",
1004 "number of nodes added to the contingent of the total nodes",
1008 "minimum number of nodes required to start the subproblem",
1012 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1016 "factor by which " HEUR_NAME " heuristic should at least improve the incumbent",
1020 "should all active cuts from cutpool be copied to constraints in subproblem?",
1024 "should the locks be updated based on LP rows?",
int SCIPgetNCheckConss(SCIP *scip)
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
#define DEFAULT_MINIMPROVE
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
int SCIPgetProbingDepth(SCIP *scip)
#define SCIPallocClearBufferArray(scip, ptr, num)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
int SCIProwGetNNonz(SCIP_ROW *row)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
int SCIPgetNOrigVars(SCIP *scip)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
int SCIPgetNPseudoBranchCands(SCIP *scip)
const char * SCIProwGetName(SCIP_ROW *row)
static SCIP_DECL_HEUREXEC(heurExecLocks)
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_SOL *newsol, SCIP_SOL *subsol, SCIP_Bool *success)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
SCIP_SOL ** SCIPgetSols(SCIP *scip)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
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)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
enum SCIP_Retcode SCIP_RETCODE
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_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
int SCIPvarGetProbindex(SCIP_VAR *var)
struct SCIP_HeurData SCIP_HEURDATA
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
#define SCIPfreeBufferArray(scip, ptr)
enum SCIP_LPSolStat SCIP_LPSOLSTAT
SCIP_RETCODE SCIPcreate(SCIP **scip)
#define SCIPallocBlockMemory(scip, ptr)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
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_HEUREXIT(heurExitLocks)
SCIP_Real SCIPgetRowMaxActivity(SCIP *scip, SCIP_ROW *row)
#define DEFAULT_ROUNDUPPROBABILITY
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen)
SCIP_RETCODE SCIPsolve(SCIP *scip)
const char * SCIPheurGetName(SCIP_HEUR *heur)
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
#define SCIPfreeBufferArrayNull(scip, ptr)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
SCIP_RETCODE SCIPpresolve(SCIP *scip)
static SCIP_DECL_HEURINIT(heurInitLocks)
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
static SCIP_DECL_HEURCOPY(heurCopyLocks)
SCIP_RETCODE SCIPendProbing(SCIP *scip)
const char * SCIPvarGetName(SCIP_VAR *var)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
#define DEFAULT_NODESQUOT
#define DEFAULT_UPDATELOCKS
int SCIPgetNLPRows(SCIP *scip)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
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_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
#define DEFAULT_MAXPROPROUNDS
int SCIPgetDepth(SCIP *scip)
int SCIPvarGetNLocksUp(SCIP_VAR *var)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
SCIP_RETCODE SCIPincludeHeurLocks(SCIP *scip)
unsigned int SCIPinitializeRandomSeed(SCIP *scip, int initialseedvalue)
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
int SCIPgetNSols(SCIP *scip)
#define DEFAULT_USEFINALSUBMIP
int SCIPgetNRuns(SCIP *scip)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_RETCODE SCIPflushLP(SCIP *scip)
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)
#define SCIP_MAXTREEDEPTH
int SCIPgetNBinVars(SCIP *scip)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
int SCIProwGetRank(SCIP_ROW *row)
int SCIPgetNVars(SCIP *scip)
int SCIPcolGetNNonz(SCIP_COL *col)
int SCIPvarGetNLocksDown(SCIP_VAR *var)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
int SCIPgetNConss(SCIP *scip)
SCIP_RETCODE SCIPcopy(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
int SCIProwGetLPPos(SCIP_ROW *row)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_Real SCIPgetRowMinActivity(SCIP *scip, SCIP_ROW *row)
int SCIPconshdlrGetNCheckConss(SCIP_CONSHDLR *conshdlr)
static SCIP_DECL_HEURFREE(heurFreeLocks)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
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_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
#define SCIP_CALL_ABORT(x)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
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)
SCIP_RETCODE SCIPfree(SCIP **scip)
#define DEFAULT_MINFIXINGRATE
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)