dive.c File Reference

Detailed Description

library methods for diving heuristics

Author

Gregor Hendel

Definition in file dive.c.

#include "scip/pub_dive.h"
#include "pub_heur.h"
#include "scip/cons_indicator.h"
#include "scip/cons_sos1.h"

Go to the source code of this file.

Macros
#define	MINLPITER   10000

Functions
static SCIP_RETCODE	solveLP (SCIP *scip, SCIP_DIVESET *diveset, SCIP_Longint maxnlpiterations, SCIP_Bool *lperror, SCIP_Bool *cutoff)
static SCIP_RETCODE	selectNextDiving (SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_Bool onlylpbranchcands, SCIP_Bool storelpcandscores, SCIP_VAR **lpcands, SCIP_Real *lpcandssol, SCIP_Real *lpcandsfrac, SCIP_Real *lpcandsscores, SCIP_Bool *lpcandroundup, int *nviollpcands, int nlpcands, SCIP_Bool *enfosuccess, SCIP_Bool *infeasible)
SCIP_RETCODE	SCIPperformGenericDivingAlgorithm (SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible)

Macro Definition Documentation

#define MINLPITER   10000

minimal number of LP iterations allowed in each LP solving call

Definition at line 28 of file dive.c.

Referenced by SCIPperformGenericDivingAlgorithm(), and solveLP().

Function Documentation

static SCIP_RETCODE solveLP ( SCIP *  scip, SCIP_DIVESET *  diveset, SCIP_Longint  maxnlpiterations, SCIP_Bool *  lperror, SCIP_Bool *  cutoff  )

static

solve probing LP

Parameters

scip	SCIP data structure
diveset	diving settings
maxnlpiterations	maximum number of allowed LP iterations
lperror	pointer to store if an internal LP error occurred
cutoff	pointer to store whether the LP was infeasible

Definition at line 33 of file dive.c.

References MAX, MINLPITER, NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPdivesetGetName(), SCIPdivesetGetNLPIterations(), SCIPgetNLPIterations(), SCIPsolveProbingLP(), SCIPupdateDivesetLPStats(), and SCIPwarningMessage().

Referenced by SCIPperformGenericDivingAlgorithm().

static SCIP_RETCODE selectNextDiving ( SCIP *  scip, SCIP_DIVESET *  diveset, SCIP_SOL *  worksol, SCIP_Bool  onlylpbranchcands, SCIP_Bool  storelpcandscores, SCIP_VAR **  lpcands, SCIP_Real *  lpcandssol, SCIP_Real *  lpcandsfrac, SCIP_Real *  lpcandsscores, SCIP_Bool *  lpcandroundup, int *  nviollpcands, int  nlpcands, SCIP_Bool *  enfosuccess, SCIP_Bool *  infeasible  )

static

select the next variable and type of diving

Parameters

scip	SCIP data structure
diveset	dive set
worksol	current working solution
onlylpbranchcands	should only LP branching candidates be considered?
storelpcandscores	should the scores of the LP candidates be updated?
lpcands	LP branching candidates, or NULL if not needed
lpcandssol	solution values LP branching candidates, or NULL if not needed
lpcandsfrac	fractionalities of LP branching candidates, or NULL if not needed
lpcandsscores	array with LP branching candidate scores, or NULL
lpcandroundup	array to remember whether the preferred branching direction is upwards
nviollpcands	pointer to store the number of LP candidates whose solution value already violates local bounds
nlpcands	number of current LP cands
enfosuccess	pointer to store whether a candidate was sucessfully found
infeasible	pointer to store whether the diving can be immediately aborted because it is infeasible

Definition at line 76 of file dive.c.

References NULL, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, SCIP_CALL, SCIP_DIVETYPE_INTEGRALITY, SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPaddDiveBoundChange(), SCIPceil(), SCIPclearDiveBoundChanges(), SCIPfloor(), SCIPgetDiveBoundChanges(), SCIPgetDivesetScore(), SCIPgetSolVal(), SCIPisGE(), SCIPisLE(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by SCIPperformGenericDivingAlgorithm().

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

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()

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?

Definition at line 188 of file dive.c.

References FALSE, MAX, MIN, 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_OKAY, SCIP_Real, SCIPABORT, SCIPallocBufferArray, SCIPbacktrackProbing(), SCIPceil(), SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), SCIPdebugMessage, SCIPdivesetGetAvgQuot(), SCIPdivesetGetAvgQuotNoSol(), SCIPdivesetGetLPResolveDomChgQuot(), SCIPdivesetGetLPSolveFreq(), SCIPdivesetGetMaxLPIterOffset(), SCIPdivesetGetMaxLPIterQuot(), SCIPdivesetGetMaxRelDepth(), SCIPdivesetGetMinRelDepth(), SCIPdivesetGetName(), SCIPdivesetGetNCalls(), SCIPdivesetGetNLPIterations(), SCIPdivesetGetSolSuccess(), SCIPdivesetGetUbQuot(), SCIPdivesetGetUbQuotNoSol(), SCIPdivesetSetWorkSolution(), SCIPdivesetUseBacktrack(), SCIPdivesetUseOnlyLPBranchcands(), SCIPenableVarHistory(), SCIPendProbing(), SCIPerrorMessage, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetAvgDualbound(), SCIPgetAvgLowerbound(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetDepthLimit(), SCIPgetDiveBoundChangeData(), SCIPgetDualbound(), SCIPgetLastDivenode(), SCIPgetLowerbound(), SCIPgetLPBranchCands(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetMaxDepth(), SCIPgetNBestSolsFound(), SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetNNodeLPIterations(), 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.