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 62 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 63 of file heur_locks.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP

Definition at line 64 of file heur_locks.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY 3000

Definition at line 65 of file heur_locks.c.

◆ HEUR_FREQ

#define HEUR_FREQ 0

Definition at line 66 of file heur_locks.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 67 of file heur_locks.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 68 of file heur_locks.c.

◆ HEUR_TIMING

#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE

Definition at line 69 of file heur_locks.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 70 of file heur_locks.c.

◆ DEFAULT_MAXNODES

#define DEFAULT_MAXNODES 5000LL

maximum number of nodes to regard in the subproblem

Definition at line 72 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 73 of file heur_locks.c.

◆ DEFAULT_MINFIXINGRATE

#define DEFAULT_MINFIXINGRATE 0.65

minimum percentage of variables that have to be fixed

Definition at line 74 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 75 of file heur_locks.c.

◆ DEFAULT_MINNODES

#define DEFAULT_MINNODES 500LL

minimum number of nodes to regard in the subproblem

Definition at line 78 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 79 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 80 of file heur_locks.c.

◆ DEFAULT_MAXPROPROUNDS

#define DEFAULT_MAXPROPROUNDS 2

maximum number of propagation rounds during probing

Definition at line 81 of file heur_locks.c.

◆ DEFAULT_UPDATELOCKS

#define DEFAULT_UPDATELOCKS TRUE

should the locks be updated based on LP rows?

Definition at line 82 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 83 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 86 of file heur_locks.c.

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED 73

initial random seed

Definition at line 89 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 90 of file heur_locks.c.

◆ heurInitsolLocks

#define heurInitsolLocks NULL

Definition at line 189 of file heur_locks.c.

◆ heurExitsolLocks

#define heurExitsolLocks NULL

Definition at line 190 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 121 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 135 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 153 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 173 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

scip	SCIP data structure
heurdata	primal heuristic data
cutoff	pointer to store if a cutoff was detected
allrowsfulfilled	pointer to store if all rows became redundant

Definition at line 196 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 660 of file heur_locks.c.

References FALSE, HEUR_NAME, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_DIDNOTFIND, SCIP_FOUNDSOL, SCIP_Longint, SCIP_LONGINT_FORMAT, 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(), SCIPflushLP(), SCIPfree(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetBoolParam(), SCIPgetCurrentNode(), SCIPgetLowerbound(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNConss(), SCIPgetNContVars(), SCIPgetNLPCols(), SCIPgetNLPIterations(), SCIPgetNLPRows(), SCIPgetNNodes(), SCIPgetNPseudoBranchCands(), SCIPgetNSols(), SCIPgetNUnfixedLPCols(), SCIPgetNVars(), SCIPgetSolvingTime(), SCIPgetStatus(), SCIPgetUpperbound(), SCIPgetVars(), SCIPgetVarsData(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPheurGetData(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPincludeHeurLocks(), SCIPisEQ(), SCIPisInfinity(), SCIPisLPSolBasic(), 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().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ DEFAULT_MAXNODES

◆ DEFAULT_ROUNDUPPROBABILITY

◆ DEFAULT_MINFIXINGRATE

◆ DEFAULT_MINIMPROVE

◆ DEFAULT_MINNODES

◆ DEFAULT_NODESOFS

◆ DEFAULT_NODESQUOT

◆ DEFAULT_MAXPROPROUNDS

◆ DEFAULT_UPDATELOCKS

◆ DEFAULT_COPYCUTS

◆ DEFAULT_USEFINALSUBMIP

◆ DEFAULT_RANDSEED

◆ DEFAULT_MINFIXINGRATELP

◆ heurInitsolLocks

◆ heurExitsolLocks

Function Documentation

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEUREXIT()

◆ SCIPapplyLockFixings()

◆ SCIP_DECL_HEUREXEC()