Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

rounding locks primal heuristic

Author
Michael Winkler
Gerald Gamrath

Definition in file heur_locks.c.

#include "blockmemshell/memory.h"
#include "scip/heur_locks.h"
#include "scip/pub_cons.h"
#include "scip/pub_heur.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_sol.h"
#include "scip/scip_solve.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include "scip/scip_tree.h"
#include <string.h>

Go to the source code of this file.

Macros

#define HEUR_NAME   "locks"
 
#define HEUR_DESC   "heuristic that fixes variables based on their rounding locks"
 
#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_PROP
 
#define HEUR_PRIORITY   3000
 
#define HEUR_FREQ   0
 
#define HEUR_FREQOFS   0
 
#define HEUR_MAXDEPTH   -1
 
#define HEUR_TIMING   SCIP_HEURTIMING_BEFORENODE
 
#define HEUR_USESSUBSCIP   TRUE
 
#define DEFAULT_MAXNODES   5000LL
 
#define DEFAULT_ROUNDUPPROBABILITY   0.67
 
#define DEFAULT_MINFIXINGRATE   0.65
 
#define DEFAULT_MINIMPROVE   0.01
 
#define DEFAULT_MINNODES   500LL
 
#define DEFAULT_NODESOFS   500LL
 
#define DEFAULT_NODESQUOT   0.1
 
#define DEFAULT_MAXPROPROUNDS   2
 
#define DEFAULT_UPDATELOCKS   TRUE
 
#define DEFAULT_COPYCUTS   TRUE
 
#define DEFAULT_USEFINALSUBMIP   TRUE
 
#define DEFAULT_RANDSEED   73
 
#define DEFAULT_MINFIXINGRATELP   0.0
 
#define heurInitsolLocks   NULL
 
#define heurExitsolLocks   NULL
 

Functions

static SCIP_DECL_HEURCOPY (heurCopyLocks)
 
static SCIP_DECL_HEURFREE (heurFreeLocks)
 
static SCIP_DECL_HEURINIT (heurInitLocks)
 
static SCIP_DECL_HEUREXIT (heurExitLocks)
 
SCIP_RETCODE SCIPapplyLockFixings (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Bool *cutoff, SCIP_Bool *allrowsfulfilled)
 
static SCIP_DECL_HEUREXEC (heurExecLocks)
 
SCIP_RETCODE SCIPincludeHeurLocks (SCIP *scip)
 

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "locks"

Definition at line 53 of file heur_locks.c.

Referenced by SCIP_DECL_HEUREXEC(), and SCIPapplyLockFixings().

◆ HEUR_DESC

#define HEUR_DESC   "heuristic that fixes variables based on their rounding locks"

Definition at line 54 of file heur_locks.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_PROP

Definition at line 55 of file heur_locks.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   3000

Definition at line 56 of file heur_locks.c.

◆ HEUR_FREQ

#define HEUR_FREQ   0

Definition at line 57 of file heur_locks.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 58 of file heur_locks.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 59 of file heur_locks.c.

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_BEFORENODE

Definition at line 60 of file heur_locks.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 61 of file heur_locks.c.

◆ DEFAULT_MAXNODES

#define DEFAULT_MAXNODES   5000LL

maximum number of nodes to regard in the subproblem

Definition at line 63 of file heur_locks.c.

◆ DEFAULT_ROUNDUPPROBABILITY

#define DEFAULT_ROUNDUPPROBABILITY   0.67

probability for rounding a variable up in case of ties

Definition at line 64 of file heur_locks.c.

◆ DEFAULT_MINFIXINGRATE

#define DEFAULT_MINFIXINGRATE   0.65

minimum percentage of variables that have to be fixed

Definition at line 65 of file heur_locks.c.

◆ DEFAULT_MINIMPROVE

#define DEFAULT_MINIMPROVE   0.01

factor by which locks heuristic should at least improve the incumbent

Definition at line 66 of file heur_locks.c.

◆ DEFAULT_MINNODES

#define DEFAULT_MINNODES   500LL

minimum number of nodes to regard in the subproblem

Definition at line 69 of file heur_locks.c.

◆ DEFAULT_NODESOFS

#define DEFAULT_NODESOFS   500LL

number of nodes added to the contingent of the total nodes

Definition at line 70 of file heur_locks.c.

◆ DEFAULT_NODESQUOT

#define DEFAULT_NODESQUOT   0.1

subproblem nodes in relation to nodes of the original problem

Definition at line 71 of file heur_locks.c.

◆ DEFAULT_MAXPROPROUNDS

#define DEFAULT_MAXPROPROUNDS   2

maximum number of propagation rounds during probing

Definition at line 72 of file heur_locks.c.

◆ DEFAULT_UPDATELOCKS

#define DEFAULT_UPDATELOCKS   TRUE

should the locks be updated based on LP rows?

Definition at line 73 of file heur_locks.c.

◆ DEFAULT_COPYCUTS

#define DEFAULT_COPYCUTS   TRUE

should all active cuts from the cutpool of the original scip be copied to constraints of the subscip?

Definition at line 74 of file heur_locks.c.

◆ DEFAULT_USEFINALSUBMIP

#define DEFAULT_USEFINALSUBMIP   TRUE

should a final sub-MIP be solved to construct a feasible solution if the LP was not roundable?

Definition at line 77 of file heur_locks.c.

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   73

initial random seed

Definition at line 80 of file heur_locks.c.

◆ DEFAULT_MINFIXINGRATELP

#define DEFAULT_MINFIXINGRATELP   0.0

minimum fixing rate over all variables (including continuous) to solve LP

Definition at line 81 of file heur_locks.c.

◆ heurInitsolLocks

#define heurInitsolLocks   NULL

Definition at line 180 of file heur_locks.c.

◆ heurExitsolLocks

#define heurExitsolLocks   NULL

Definition at line 181 of file heur_locks.c.

Function Documentation

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyLocks  )
static

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 112 of file heur_locks.c.

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeLocks  )
static

free method for primal heuristic plugins (called when SCIP is exiting)

Definition at line 126 of file heur_locks.c.

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitLocks  )
static

initialization method of primal heuristic (called after problem was transformed)

Definition at line 144 of file heur_locks.c.

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitLocks  )
static

deinitialization method of primal heuristic (called before transformed problem is freed)

Definition at line 164 of file heur_locks.c.

◆ SCIPapplyLockFixings()

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

apply fix-and-propagate scheme based on variable locks

Note
probing mode of SCIP needs to be enabled before
Parameters
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 187 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().

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecLocks  )
static

execution method of primal heuristic

Definition at line 651 of file heur_locks.c.

References FALSE, HEUR_NAME, NULL, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_DIDNOTFIND, SCIP_FOUNDSOL, SCIP_Longint, SCIP_LPSOLSTAT_INFEASIBLE, SCIP_LPSOLSTAT_OBJLIMIT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_Real, SCIP_VERBLEVEL_FULL, SCIPallocBufferArray, SCIPapplyLockFixings(), SCIPblkmem(), SCIPceil(), SCIPcheckCopyLimits(), SCIPcheckSol(), SCIPconstructLP(), SCIPcopy(), SCIPcopyCuts(), SCIPcopyLimits(), SCIPcreate(), SCIPcreateSol(), SCIPcutoffNode(), SCIPdebug, SCIPdebugMsg, SCIPenableVarHistory(), SCIPendProbing(), SCIPfindBranchrule(), SCIPfindConshdlr(), SCIPflushLP(), SCIPfree(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetBoolParam(), SCIPgetCurrentNode(), SCIPgetLowerbound(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNConss(), SCIPgetNContVars(), SCIPgetNLPIterations(), SCIPgetNLPRows(), SCIPgetNNodes(), SCIPgetNPseudoBranchCands(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetSolvingTime(), SCIPgetStatus(), SCIPgetUpperbound(), SCIPgetVars(), SCIPgetVarsData(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPheurGetData(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPincludeHeurLocks(), SCIPisEQ(), SCIPisInfinity(), SCIPisParamFixed(), SCIPisStopped(), SCIPlinkLPSol(), SCIPpresolve(), SCIPprintSol(), SCIPprintStatistics(), SCIProundSol(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPsnprintfProbingStats(), SCIPsolve(), SCIPsolveProbingLP(), SCIPstartProbing(), SCIPsumepsilon(), SCIPtranslateSubSols(), SCIPtrySol(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPverbMessage(), SCIPwarningMessage(), and TRUE.

Referenced by SCIPapplyLockFixings().