/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* */ /* This file is part of the program and library */ /* SCIP --- Solving Constraint Integer Programs */ /* */ /* Copyright (C) 2002-2020 Konrad-Zuse-Zentrum */ /* fuer Informationstechnik Berlin */ /* */ /* SCIP is distributed under the terms of the ZIB Academic License. */ /* */ /* You should have received a copy of the ZIB Academic License */ /* along with SCIP; see the file COPYING. If not visit scipopt.org. */ /* */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /**@file scip_probing.h * @ingroup PUBLICCOREAPI * @brief public methods for the probing mode * @author Tobias Achterberg * @author Timo Berthold * @author Thorsten Koch * @author Alexander Martin * @author Marc Pfetsch * @author Kati Wolter * @author Gregor Hendel * @author Leona Gottwald */ /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ #ifndef __SCIP_SCIP_PROBING_H__ #define __SCIP_SCIP_PROBING_H__ #include "lpi/type_lpi.h" #include "scip/def.h" #include "scip/type_heur.h" #include "scip/type_history.h" #include "scip/type_lp.h" #include "scip/type_retcode.h" #include "scip/type_scip.h" #include "scip/type_sol.h" #include "scip/type_var.h" #ifdef __cplusplus extern "C" { #endif /**@addtogroup PublicProbingMethods * * @{ */ /** returns whether we are in probing mode; probing mode is activated via SCIPstartProbing() and stopped * via SCIPendProbing() * * @return TRUE, if SCIP is currently in probing mode, otherwise FALSE * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_TRANSFORMED * - \ref SCIP_STAGE_INITPRESOLVE * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_EXITPRESOLVE * - \ref SCIP_STAGE_PRESOLVED * - \ref SCIP_STAGE_INITSOLVE * - \ref SCIP_STAGE_SOLVING * - \ref SCIP_STAGE_SOLVED * - \ref SCIP_STAGE_EXITSOLVE */ SCIP_EXPORT SCIP_Bool SCIPinProbing( SCIP* scip /**< SCIP data structure */ ); /** initiates probing, making methods SCIPnewProbingNode(), SCIPbacktrackProbing(), SCIPchgVarLbProbing(), * SCIPchgVarUbProbing(), SCIPfixVarProbing(), SCIPpropagateProbing(), and SCIPsolveProbingLP() available * * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING * * @note The collection of variable statistics is turned off during probing. If these statistics should be collected * during probing use the method SCIPenableVarHistory() to turn the collection explicitly on. */ SCIP_EXPORT SCIP_RETCODE SCIPstartProbing( SCIP* scip /**< SCIP data structure */ ); /** creates a new probing sub node, whose changes can be undone by backtracking to a higher node in the probing path * with a call to SCIPbacktrackProbing(); * using a sub node for each set of probing bound changes can improve conflict analysis * * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING */ SCIP_EXPORT SCIP_RETCODE SCIPnewProbingNode( SCIP* scip /**< SCIP data structure */ ); /** returns the current probing depth * * @return the probing depth, i.e. the number of probing sub nodes existing in the probing path * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING */ SCIP_EXPORT int SCIPgetProbingDepth( SCIP* scip /**< SCIP data structure */ ); /** undoes all changes to the problem applied in probing up to the given probing depth; * the changes of the probing node of the given probing depth are the last ones that remain active; * changes that were applied before calling SCIPnewProbingNode() cannot be undone * * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING */ SCIP_EXPORT SCIP_RETCODE SCIPbacktrackProbing( SCIP* scip, /**< SCIP data structure */ int probingdepth /**< probing depth of the node in the probing path that should be reactivated */ ); /** quits probing and resets bounds and constraints to the focus node's environment * * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING */ SCIP_EXPORT SCIP_RETCODE SCIPendProbing( SCIP* scip /**< SCIP data structure */ ); /** injects a change of variable's lower bound into current probing node; the same can also be achieved with a call to * SCIPchgVarLb(), but in this case, the bound change would be treated like a deduction instead of a branching decision * * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING */ SCIP_EXPORT SCIP_RETCODE SCIPchgVarLbProbing( SCIP* scip, /**< SCIP data structure */ SCIP_VAR* var, /**< variable to change the bound for */ SCIP_Real newbound /**< new value for bound */ ); /** injects a change of variable's upper bound into current probing node; the same can also be achieved with a call to * SCIPchgVarUb(), but in this case, the bound change would be treated like a deduction instead of a branching decision * * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING */ SCIP_EXPORT SCIP_RETCODE SCIPchgVarUbProbing( SCIP* scip, /**< SCIP data structure */ SCIP_VAR* var, /**< variable to change the bound for */ SCIP_Real newbound /**< new value for bound */ ); /** gets variable's objective value in current probing * * @return the variable's objective value in current probing. * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_SOLVING * * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. */ SCIP_EXPORT SCIP_Real SCIPgetVarObjProbing( SCIP* scip, /**< SCIP data structure */ SCIP_VAR* var /**< variable to get the bound for */ ); /** injects a change of variable's bounds into current probing node to fix the variable to the specified value; * the same can also be achieved with a call to SCIPfixVar(), but in this case, the bound changes would be treated * like deductions instead of branching decisions * * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING */ SCIP_EXPORT SCIP_RETCODE SCIPfixVarProbing( SCIP* scip, /**< SCIP data structure */ SCIP_VAR* var, /**< variable to change the bound for */ SCIP_Real fixedval /**< value to fix variable to */ ); /** changes (column) variable's objective value during probing mode * * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING * * @pre The variable needs to be a column variable. */ SCIP_EXPORT SCIP_RETCODE SCIPchgVarObjProbing( SCIP* scip, /**< SCIP data structure */ SCIP_VAR* var, /**< variable to change the objective for */ SCIP_Real newobj /**< new objective function value */ ); /** returns whether the objective function has changed during probing mode * * @return \ref TRUE if objective has changed, \ref FALSE otherwise * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_TRANSFORMED * - \ref SCIP_STAGE_INITPRESOLVE * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_EXITPRESOLVE * - \ref SCIP_STAGE_PRESOLVED * - \ref SCIP_STAGE_INITSOLVE * - \ref SCIP_STAGE_SOLVING * - \ref SCIP_STAGE_SOLVED * - \ref SCIP_STAGE_EXITSOLVE */ SCIP_EXPORT SCIP_Bool SCIPisObjChangedProbing( SCIP* scip /**< SCIP data structure */ ); /** applies domain propagation on the probing sub problem, that was changed after SCIPstartProbing() was called; * the propagated domains of the variables can be accessed with the usual bound accessing calls SCIPvarGetLbLocal() * and SCIPvarGetUbLocal(); the propagation is only valid locally, i.e. the local bounds as well as the changed * bounds due to SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), and SCIPfixVarProbing() are used for propagation * * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING */ SCIP_EXPORT SCIP_RETCODE SCIPpropagateProbing( SCIP* scip, /**< SCIP data structure */ int maxproprounds, /**< maximal number of propagation rounds (-1: no limit, 0: parameter settings) */ SCIP_Bool* cutoff, /**< pointer to store whether the probing node can be cut off */ SCIP_Longint* ndomredsfound /**< pointer to store the number of domain reductions found, or NULL */ ); /** applies domain propagation on the probing sub problem, that was changed after SCIPstartProbing() was called; * only propagations of the binary variables fixed at the current probing node that are triggered by the implication * graph and the clique table are applied; * the propagated domains of the variables can be accessed with the usual bound accessing calls SCIPvarGetLbLocal() * and SCIPvarGetUbLocal(); the propagation is only valid locally, i.e. the local bounds as well as the changed * bounds due to SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), and SCIPfixVarProbing() are used for propagation * * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING */ SCIP_EXPORT SCIP_RETCODE SCIPpropagateProbingImplications( SCIP* scip, /**< SCIP data structure */ SCIP_Bool* cutoff /**< pointer to store whether the probing node can be cut off */ ); /** solves the LP at the current probing node (cannot be applied at preprocessing stage); * no separation or pricing is applied * * The LP has to be constructed before (you can use SCIPisLPConstructed() or SCIPconstructLP()). * * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_SOLVING */ SCIP_EXPORT SCIP_RETCODE SCIPsolveProbingLP( SCIP* scip, /**< SCIP data structure */ int itlim, /**< maximal number of LP iterations to perform, or -1 for no limit */ SCIP_Bool* lperror, /**< pointer to store whether an unresolved LP error occurred */ SCIP_Bool* cutoff /**< pointer to store whether the probing LP was infeasible or the objective * limit was reached (or NULL, if not needed) */ ); /** solves the LP at the current probing node (cannot be applied at preprocessing stage) and applies pricing * until the LP is solved to optimality; no separation is applied * * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed . See \ref * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_SOLVING */ SCIP_EXPORT SCIP_RETCODE SCIPsolveProbingLPWithPricing( SCIP* scip, /**< SCIP data structure */ SCIP_Bool pretendroot, /**< should the pricers be called as if we are at the root node? */ SCIP_Bool displayinfo, /**< should info lines be displayed after each pricing round? */ int maxpricerounds, /**< maximal number of pricing rounds (-1: no limit); * a finite limit means that the LP might not be solved to optimality! */ SCIP_Bool* lperror, /**< pointer to store whether an unresolved LP error occurred */ SCIP_Bool* cutoff /**< pointer to store whether the probing LP was infeasible or the objective * limit was reached (or NULL, if not needed) */ ); /** sets the LP state for the current probing node * * @note state and norms are stored at the node and later released by SCIP; therefore, the pointers are set * to NULL by the method * * @note the pointers to state and norms must not be NULL; however, they may point to a NULL pointer if the * respective information should not be set * * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING */ SCIP_EXPORT SCIP_RETCODE SCIPsetProbingLPState( SCIP* scip, /**< SCIP data structure */ SCIP_LPISTATE** lpistate, /**< pointer to LP state information (like basis information) */ SCIP_LPINORMS** lpinorms, /**< pointer to LP pricing norms information */ SCIP_Bool primalfeas, /**< primal feasibility when LP state information was stored */ SCIP_Bool dualfeas /**< dual feasibility when LP state information was stored */ ); /** adds a row to the LP in the current probing node * * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_SOLVING * * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. */ SCIP_EXPORT SCIP_RETCODE SCIPaddRowProbing( SCIP* scip, /**< SCIP data structure */ SCIP_ROW* row /**< row to be added */ ); /** applies the cuts in the separation storage to the LP and clears the storage afterwards; * this method can only be applied during probing; the user should resolve the probing LP afterwards * in order to get a new solution * * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_SOLVING */ SCIP_EXPORT SCIP_RETCODE SCIPapplyCutsProbing( SCIP* scip, /**< SCIP data structure */ SCIP_Bool* cutoff /**< pointer to store whether an empty domain was created */ ); /** solves relaxation(s) at the current probing node (cannot be applied at preprocessing stage); * no separation or pricing is applied * * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_SOLVING */ SCIP_EXPORT SCIP_RETCODE SCIPsolveProbingRelax( SCIP* scip, /**< SCIP data structure */ SCIP_Bool* cutoff /**< pointer to store whether a relaxation was infeasible or the objective * limit was reached (or NULL, if not needed) */ ); /** print statistics of probing */ SCIP_EXPORT char* SCIPsnprintfProbingStats( SCIP* scip, /**< SCIP data structure */ char* strbuf, /**< string buffer */ int len /**< length of string buffer */ ); /** stores the candidate score and preferred rounding direction for a candidate variable */ SCIP_EXPORT SCIP_RETCODE SCIPgetDivesetScore( SCIP* scip, /**< SCIP data structure */ SCIP_DIVESET* diveset, /**< general diving settings */ SCIP_DIVETYPE divetype, /**< represents different methods for a dive set to explore the next children */ SCIP_VAR* divecand, /**< the candidate for which the branching direction is requested */ SCIP_Real divecandsol, /**< LP solution value of the candidate */ SCIP_Real divecandfrac, /**< fractionality of the candidate */ SCIP_Real* candscore, /**< pointer to store the candidate score */ SCIP_Bool* roundup /**< pointer to store whether preferred direction for diving is upwards */ ); /** update diveset LP statistics, should be called after every LP solved by this diving heuristic */ SCIP_EXPORT void SCIPupdateDivesetLPStats( SCIP* scip, /**< SCIP data structure */ SCIP_DIVESET* diveset, /**< diving settings */ SCIP_Longint niterstoadd, /**< additional number of LP iterations to be added */ SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ ); /** update diveset statistics and global diveset statistics */ SCIP_EXPORT void SCIPupdateDivesetStats( SCIP* scip, /**< SCIP data structure */ SCIP_DIVESET* diveset, /**< diveset to be reset */ int nprobingnodes, /**< the number of probing nodes explored this time */ int nbacktracks, /**< the number of backtracks during probing this time */ SCIP_Longint nsolsfound, /**< the number of solutions found */ SCIP_Longint nbestsolsfound, /**< the number of best solutions found */ SCIP_Longint nconflictsfound, /**< number of new conflicts found this time */ SCIP_Bool leavewassol, /**< was a solution found at the leaf? */ SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ ); /** enforces a probing/diving solution by suggesting bound changes that maximize the score w.r.t. the current diving settings * * the process is guided by the enforcement priorities of the constraint handlers and the scoring mechanism provided by * the dive set. * Constraint handlers may suggest diving bound changes in decreasing order of their enforcement priority, based on the * solution values in the solution @p sol and the current local bounds of the variables. A diving bound change * is a triple (variable,branching direction,value) and is used inside SCIPperformGenericDivingAlgorithm(). * * After a successful call, SCIP holds two arrays of suggested dive bound changes, one for the preferred child * and one for the alternative. * * @see SCIPgetDiveBoundChangeData() for retrieving the dive bound change suggestions. * * The method stops after the first constraint handler was successful * * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_SOLVING * * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. */ SCIP_EXPORT SCIP_RETCODE SCIPgetDiveBoundChanges( SCIP* scip, /**< SCIP data structure */ SCIP_DIVESET* diveset, /**< diving settings to control scoring */ SCIP_SOL* sol, /**< current solution of diving mode */ SCIP_Bool* success, /**< pointer to store whether constraint handler successfully found a variable */ SCIP_Bool* infeasible /**< pointer to store whether the current node was detected to be infeasible */ ); /** adds a diving bound change to the diving bound change storage of SCIP together with the information if this is a * bound change for the preferred direction or not * * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_SOLVING * * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. */ SCIP_EXPORT SCIP_RETCODE SCIPaddDiveBoundChange( SCIP* scip, /**< SCIP data structure */ SCIP_VAR* var, /**< variable to apply the bound change to */ SCIP_BRANCHDIR dir, /**< direction of the bound change */ SCIP_Real value, /**< value to adjust this variable bound to */ SCIP_Bool preferred /**< is this a bound change for the preferred child? */ ); /** get the dive bound change data for the preferred or the alternative direction * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_SOLVING * * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. */ SCIP_EXPORT void SCIPgetDiveBoundChangeData( SCIP* scip, /**< SCIP data structure */ SCIP_VAR*** variables, /**< pointer to store variables for the specified direction */ SCIP_BRANCHDIR** directions, /**< pointer to store the branching directions */ SCIP_Real** values, /**< pointer to store bound change values */ int* ndivebdchgs, /**< pointer to store the number of dive bound changes */ SCIP_Bool preferred /**< should the dive bound changes for the preferred child be output? */ ); /** clear the dive bound change data structures * * @pre This method can be called if @p scip is in one of the following stages: * - \ref SCIP_STAGE_SOLVING * * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. */ SCIP_EXPORT void SCIPclearDiveBoundChanges( SCIP* scip /**< SCIP data structure */ ); /**@} */ #ifdef __cplusplus } #endif #endif