methods commonly used by primal heuristics
Topics | |
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, int nodelimit, SCIP_Real lpresolvedomchgquot, 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) |
SCIP_RETCODE SCIPperformGenericDivingAlgorithm | ( | SCIP * | scip, |
SCIP_DIVESET * | diveset, | ||
SCIP_SOL * | worksol, | ||
SCIP_HEUR * | heur, | ||
SCIP_RESULT * | result, | ||
SCIP_Bool | nodeinfeasible, | ||
SCIP_Longint | iterlim, | ||
int | nodelimit, | ||
SCIP_Real | lpresolvedomchgquot, | ||
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.
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.
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 |
nodelimit | nonnegative probing node limit or -1 if no limit should be used |
lpresolvedomchgquot | percentage of immediate domain changes during probing to trigger LP resolve or -1 if diveset specific default should be used |
divecontext | context for diving statistics |
Definition at line 220 of file heuristics.c.
References assert(), backtracked, c, cutoff, depth, diveset, FALSE, getDivesetIterLimit(), lpcands, lpcandsfrac, lpcandssol, lperror, MAX, maxdepth, maxdivedepth, maxnlpiterations, MIN, MINLPITER, nlpcands, NULL, result, SCIP_Bool, SCIP_BRANCHDIR_AUTO, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_FIXED, SCIP_BRANCHDIR_UPWARDS, SCIP_CALL, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_DIVECONTEXT_SCHEDULER, 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(), 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(), searchavgbound, searchbound, searchubbound, selectNextDiving(), solveLP(), and TRUE.
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
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 951 of file heuristics.c.
References assert(), createRows(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPcopyConsCompression(), SCIPcopyCuts(), SCIPcopyParamSettings(), SCIPcopyVars(), SCIPcreateProb(), SCIPgetProbName(), SCIPincludeDefaultPlugins(), SCIPsetRealParam(), SCIPsnprintf(), TRUE, and valid.
Referenced by executeLNSHeuristic(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXEC(), SCIPapplyProximity(), setupAndSolve(), setupAndSolveSubscipCrossover(), setupAndSolveSubscipLocalbranching(), setupAndSolveSubscipMutation(), setupAndSolveSubscipTrustregion(), wrapperDins(), and wrapperRins().
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
.
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
.
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 1029 of file heuristics.c.
References assert(), FALSE, i, nbinvars, NULL, nvars, 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(), TRUE, and vars.
Referenced by addTrustRegionConstraints(), DECL_CHANGESUBSCIP(), and DECL_CHANGESUBSCIP().