Scippy

SCIP

Solving Constraint Integer Programs

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

Function Documentation

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

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
scipSCIP data structure
divesetsettings for diving
worksolnon-NULL working solution
heurthe calling primal heuristic
resultSCIP result pointer
nodeinfeasibleis the current node known to be infeasible?

Definition at line 192 of file heuristics.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_LONGINT_FORMAT, 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(), SCIPdivesetGetMaxLPIterOffset(), SCIPdivesetGetMaxLPIterQuot(), SCIPdivesetGetMaxRelDepth(), SCIPdivesetGetMinRelDepth(), SCIPdivesetGetName(), SCIPdivesetGetNCalls(), SCIPdivesetGetNLPIterations(), SCIPdivesetGetSolSuccess(), 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(), 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.

◆ 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
sourcescipsource SCIP data structure
subscipsub-SCIP used by the heuristic
varmapa hashmap to store the mapping of source variables to the corresponding target variables
suffixsuffix for the problem name
fixedvarssource variables whose copies should be fixed in the target SCIP environment, or NULL
fixedvalsarray of fixing values for target SCIP variables, or NULL
nfixedvarsnumber of source variables whose copies should be fixed in the target SCIP environment, or NULL
uselprowsshould the linear relaxation of the problem defined by LP rows be copied?
copycutsshould cuts be copied (only if uselprows == FALSE)
successwas the copying successful?
validpointer to store whether the copying was valid, or NULL

Definition at line 895 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(), wrapperDins(), and wrapperRins().