Solving Constraint Integer Programs

Detailed Description

locks primal heuristic

Michael Winkler
Gerald Gamrath

The locks heuristic is a start heuristic that first tries to fix all binary variables, then solves the resulting LP and tries to round the solution and finally solves a sub-MIP on the remaining problem if the LP solution could not be rounded. The fixing works as follows: First, all variables are sorted by their total number of rounding locks (up- and down-locks summed up). Then, looking at the variable with the highest number of locks first, the variable is fixed to the bound where there are fewer locks (in case of ties, the bound which is better w.r.t. the objective function). This fix is propagated and the activities of all LP rows are updated. If any LP row becomes redundant w.r.t. the updated bounds, we adjust the rounding locks.

Definition in file heur_locks.h.

#include "scip/def.h"
#include "scip/type_heur.h"
#include "scip/type_retcode.h"
#include "scip/type_scip.h"

Go to the source code of this file.


SCIP_RETCODE SCIPincludeHeurLocks (SCIP *scip)
SCIP_RETCODE SCIPapplyLockFixings (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Bool *cutoff, SCIP_Bool *allrowsfulfilled)

Function Documentation

◆ SCIPapplyLockFixings()

SCIP_RETCODE SCIPapplyLockFixings ( SCIP scip,
SCIP_Bool cutoff,
SCIP_Bool allrowsfulfilled 

apply fix-and-propagate scheme based on variable locks

probing mode of SCIP needs to be enabled before
scipSCIP data structure
heurdataprimal heuristic data
cutoffpointer to store if a cutoff was detected
allrowsfulfilledpointer to store if all rows became redundant

Definition at line 234 of file heur_locks.c.

References FALSE, HEUR_NAME, NULL, r, REALABS, SCIP_Bool, SCIP_CALL, SCIP_DECL_HEUREXEC(), SCIP_LOCKTYPE_MODEL, SCIP_MAXTREEDEPTH, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIP_VARTYPE_BINARY, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPbacktrackProbing(), SCIPcolGetNNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPcolGetVar(), SCIPconshdlrGetNCheckConss(), SCIPdebug, SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfindConshdlr(), SCIPfindHeur(), SCIPfixVarProbing(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetDepth(), SCIPgetLPRowsData(), SCIPgetNCheckConss(), SCIPgetNConss(), SCIPgetNLPRows(), SCIPgetProbingDepth(), SCIPgetRowMaxActivity(), SCIPgetRowMinActivity(), SCIPgetVarsData(), SCIPheurGetData(), SCIPinProbing(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasLE(), SCIPisFeasLT(), SCIPisInfinity(), SCIPisPositive(), SCIPisStopped(), SCIPnewProbingNode(), SCIPprintRow(), SCIPpropagateProbing(), SCIPrandomGetReal(), SCIProwGetCols(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwGetRank(), SCIProwGetRhs(), SCIProwGetVals(), SCIPvarGetCol(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetObj(), SCIPvarGetProbindex(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetUbLocal(), TRUE, and w.

Referenced by applyVbounds(), and SCIP_DECL_HEUREXEC().