Scippy

    SCIP

    Solving Constraint Integer Programs

    Modules | Functions
    Special Methods
    Public API of SCIP » Core API » Methods for managing plugins » Primal Heuristics

    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, 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 *sourcescip, SCIP *targetscip, 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,
    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.

    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
    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?
    iterlimnonnegative iteration limit for the LP solves, or -1 for dynamic setting
    nodelimitnonnegative probing node limit or -1 if no limit should be used
    lpresolvedomchgquotpercentage of immediate domain changes during probing to trigger LP resolve or -1 if diveset specific default should be used
    divecontextcontext for diving statistics

    Definition at line 221 of file heuristics.c.

    References FALSE, getDivesetIterLimit(), 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_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(), SCIPgetNConflictConssFound(), SCIPgetNContImplVars(), SCIPgetNContVars(), 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.

    Referenced by executeDivingHeuristic(), and SCIP_DECL_HEUREXEC().

    ◆ 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 953 of file heuristics.c.

    References createRows(), FALSE, Scip::messagehdlr, NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPcopyConsCompression(), SCIPcopyCuts(), SCIPcopyParamSettings(), SCIPcopyVars(), SCIPcreateProb(), SCIPenableExactSolving(), SCIPgetProbName(), SCIPincludeDefaultPlugins(), SCIPmessagehdlrIsQuiet(), SCIPsetMessagehdlrQuiet(), SCIPsetRealParam(), SCIPsnprintf(), and TRUE.

    Referenced by executeLNSHeuristic(), SCIP_DECL_HEUREXEC(), SCIPapplyProximity(), setupAndSolve(), 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
    sourcescipthe data structure for the main SCIP instance
    targetscipSCIP data structure of the subproblem
    subvarsvariables of the subproblem, NULL entries are ignored
    violpenaltythe penalty for violating the trust region

    Definition at line 1042 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(), SCIPvarIsImpliedIntegral(), and TRUE.

    Referenced by addTrustRegionConstraints(), and DECL_CHANGESUBSCIP().