Special Methods

Detailed Description

methods commonly used by primal heuristics

Modules
	Dive sets
	methods for dive sets to control the generic diving algorithm

Functions
SCIP_RETCODE	SCIPperformGenericDivingAlgorithm (SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible, SCIP_Longint iterlim, SCIP_DIVECONTEXT divecontext)
SCIP_RETCODE	SCIPcopyLargeNeighborhoodSearch (SCIP *sourcescip, SCIP *subscip, SCIP_HASHMAP *varmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool uselprows, SCIP_Bool copycuts, SCIP_Bool *success, SCIP_Bool *valid)
SCIP_RETCODE	SCIPaddTrustregionNeighborhoodConstraint (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_Real violpenalty)

Function Documentation

SCIPperformGenericDivingAlgorithm()

SCIP_RETCODE SCIPperformGenericDivingAlgorithm	(	SCIP *	scip,
		SCIP_DIVESET *	diveset,
		SCIP_SOL *	worksol,
		SCIP_HEUR *	heur,
		SCIP_RESULT *	result,
		SCIP_Bool	nodeinfeasible,
		SCIP_Longint	iterlim,
		SCIP_DIVECONTEXT	divecontext
	)

performs a diving within the limits of the diveset parameters

This method performs a diving according to the settings defined by the diving settings diveset; Contrary to the name, SCIP enters probing mode (not diving mode) and dives along a path into the tree. Domain propagation is applied at every node in the tree, whereas probing LPs might be solved less frequently.

Starting from the current LP solution, the algorithm selects candidates which maximize the score defined by the diveset and whose solution value has not yet been rendered infeasible by propagation, and propagates the bound change on this candidate.

The algorithm iteratively selects the the next (unfixed) candidate in the list, until either enough domain changes or the resolve frequency of the LP trigger an LP resolve (and hence, the set of potential candidates changes), or the last node is proven to be infeasible. It optionally backtracks and tries the other branching direction.

After the set of remaining candidates is empty or the targeted depth is reached, the node LP is solved, and the old candidates are replaced by the new LP candidates.

See also

heur_guideddiving.c for an example implementation of a dive set controlling the diving algorithm.

Note

the node from where the algorithm is called is checked for a basic LP solution. If the solution is non-basic, e.g., when barrier without crossover is used, the method returns without performing a dive.

currently, when multiple diving heuristics call this method and solve an LP at the same node, only the first call will be executed,

See also

SCIPgetLastDiveNode().

performs a diving within the limits of the diveset parameters

This method performs a diving according to the settings defined by the diving settings diveset; Contrary to the name, SCIP enters probing mode (not diving mode) and dives along a path into the tree. Domain propagation is applied at every node in the tree, whereas probing LPs might be solved less frequently.

Starting from the current LP solution, the algorithm selects candidates which maximize the score defined by the diveset and whose solution value has not yet been rendered infeasible by propagation, and propagates the bound change on this candidate.

The algorithm iteratively selects the the next (unfixed) candidate in the list, until either enough domain changes or the resolve frequency of the LP trigger an LP resolve (and hence, the set of potential candidates changes), or the last node is proven to be infeasible. It optionally backtracks and tries the other branching direction.

After the set of remaining candidates is empty or the targeted depth is reached, the node LP is solved, and the old candidates are replaced by the new LP candidates.

See also

heur_guideddiving.c for an example implementation of a dive set controlling the diving algorithm.

Note

the node from where the algorithm is called is checked for a basic LP solution. If the solution is non-basic, e.g., when barrier without crossover is used, the method returns without performing a dive.

currently, when multiple diving heuristics call this method and solve an LP at the same node, only the first call will be executed, see SCIPgetLastDiveNode()

Parameters

scip	SCIP data structure
diveset	settings for diving
worksol	non-NULL working solution
heur	the calling primal heuristic
result	SCIP result pointer
nodeinfeasible	is the current node known to be infeasible?
iterlim	nonnegative iteration limit for the LP solves, or -1 for dynamic setting
divecontext	context for diving statistics

Definition at line 209 of file heuristics.c.

References FALSE, getDivesetIterLimit(), MAX, MINLPITER, NULL, SCIP_Bool, SCIP_BRANCHDIR_AUTO, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_FIXED, SCIP_BRANCHDIR_UPWARDS, SCIP_CALL, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_INVALID, SCIP_INVALIDDATA, SCIP_Longint, SCIP_LPSOLSTAT_INFEASIBLE, SCIP_LPSOLSTAT_NOTSOLVED, SCIP_LPSOLSTAT_OBJLIMIT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_MAXTREEDEPTH, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPallocBufferArray, SCIPbacktrackProbing(), SCIPceil(), SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), SCIPdebugMsg, SCIPdivesetGetAvgQuot(), SCIPdivesetGetAvgQuotNoSol(), SCIPdivesetGetLPResolveDomChgQuot(), SCIPdivesetGetLPSolveFreq(), SCIPdivesetGetMaxRelDepth(), SCIPdivesetGetMinRelDepth(), SCIPdivesetGetName(), SCIPdivesetGetNLPIterations(), SCIPdivesetGetUbQuot(), SCIPdivesetGetUbQuotNoSol(), SCIPdivesetSetWorkSolution(), SCIPdivesetUseBacktrack(), SCIPdivesetUseOnlyLPBranchcands(), SCIPenableVarHistory(), SCIPendProbing(), SCIPerrorMessage, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetAvgDualbound(), SCIPgetAvgLowerbound(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetDiveBoundChangeData(), SCIPgetDualbound(), SCIPgetLastDivenode(), SCIPgetLowerbound(), SCIPgetLPBranchCands(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetMaxDepth(), SCIPgetNBestSolsFound(), SCIPgetNBinVars(), SCIPgetNConflictConssFound(), SCIPgetNIntVars(), SCIPgetNNodes(), SCIPgetNSolsFound(), SCIPgetNSOS1Vars(), SCIPgetNVars(), SCIPgetProbingDepth(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPhasCurrentNodeLP(), SCIPheurGetName(), SCIPinfinity(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasLE(), SCIPisFeasLT(), SCIPisGE(), SCIPisLPSolBasic(), SCIPisLT(), SCIPisObjIntegral(), SCIPisStopped(), SCIPisZero(), SCIPlinkLPSol(), SCIPmakeIndicatorsFeasible(), SCIPmakeSOS1sFeasible(), SCIPnewProbingNode(), SCIPpropagateProbing(), SCIPreallocBufferArray, SCIPretransformObj(), SCIProundSol(), SCIPstartProbing(), SCIPtrySol(), SCIPunlinkSol(), SCIPupdateDivesetStats(), SCIPupdateVarPseudocost(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarMayRoundDown(), SCIPvarMayRoundUp(), selectNextDiving(), solveLP(), and TRUE.

SCIPcopyLargeNeighborhoodSearch()

SCIP_RETCODE SCIPcopyLargeNeighborhoodSearch	(	SCIP *	sourcescip,
		SCIP *	subscip,
		SCIP_HASHMAP *	varmap,
		const char *	suffix,
		SCIP_VAR **	fixedvars,
		SCIP_Real *	fixedvals,
		int	nfixedvars,
		SCIP_Bool	uselprows,
		SCIP_Bool	copycuts,
		SCIP_Bool *	success,
		SCIP_Bool *	valid
	)

get a sub-SCIP copy of the transformed problem

Parameters

sourcescip	source SCIP data structure
subscip	sub-SCIP used by the heuristic
varmap	a hashmap to store the mapping of source variables to the corresponding target variables
suffix	suffix for the problem name
fixedvars	source variables whose copies should be fixed in the target SCIP environment, or NULL
fixedvals	array of fixing values for target SCIP variables, or NULL
nfixedvars	number of source variables whose copies should be fixed in the target SCIP environment, or NULL
uselprows	should the linear relaxation of the problem defined by LP rows be copied?
copycuts	should cuts be copied (only if uselprows == FALSE)
success	was the copying successful?
valid	pointer to store whether the copying was valid, or NULL

Definition at line 916 of file heuristics.c.

References createRows(), FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPcopyConsCompression(), SCIPcopyCuts(), SCIPcopyParamSettings(), SCIPcopyVars(), SCIPcreateProb(), SCIPgetProbName(), SCIPincludeDefaultPlugins(), SCIPsnprintf(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC(), SCIPapplyProximity(), setupAndSolve(), setupAndSolveSubscip(), setupAndSolveSubscipCrossover(), setupAndSolveSubscipLocalbranching(), setupAndSolveSubscipMutation(), setupAndSolveSubscipTrustregion(), wrapperDins(), and wrapperRins().

SCIPaddTrustregionNeighborhoodConstraint()

SCIP_RETCODE SCIPaddTrustregionNeighborhoodConstraint	(	SCIP *	sourcescip,
		SCIP *	targetscip,
		SCIP_VAR **	subvars,
		SCIP_Real	violpenalty
	)

adds a trust region neighborhood constraint to the targetscip

a trust region constraint measures the deviation from the current incumbent solution \(x^*\) by an auxiliary continuous variable \(v \geq 0\):

\[ \sum\limits_{j\in B} |x_j^* - x_j| = v \]

Only binary variables are taken into account. The deviation is penalized in the objective function using a positive violpenalty.

Note

: the trust region constraint creates an auxiliary variable to penalize the deviation from the current incumbent solution. This variable can afterwards be accessed using SCIPfindVar() by its name 'trustregion_violationvar'

Parameters

sourcescip	the data structure for the main SCIP instance
targetscip	SCIP data structure of the subproblem
subvars	variables of the subproblem, NULL entries are ignored
violpenalty	the penalty for violating the trust region

Definition at line 990 of file heuristics.c.

References FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPcreateConsLinear(), SCIPcreateVarBasic(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetProbName(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPinfinity(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsnprintf(), SCIPvarGetType(), and TRUE.

Referenced by addTrustRegionConstraints(), and DECL_CHANGESUBSCIP().