/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* */ /* This file is part of the program and library */ /* SCIP --- Solving Constraint Integer Programs */ /* */ /* Copyright 2002-2022 Zuse Institute Berlin */ /* */ /* Licensed under the Apache License, Version 2.0 (the "License"); */ /* you may not use this file except in compliance with the License. */ /* You may obtain a copy of the License at */ /* */ /* http://www.apache.org/licenses/LICENSE-2.0 */ /* */ /* Unless required by applicable law or agreed to in writing, software */ /* distributed under the License is distributed on an "AS IS" BASIS, */ /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ /* See the License for the specific language governing permissions and */ /* limitations under the License. */ /* */ /* You should have received a copy of the Apache-2.0 license */ /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ /* */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /**@file scip_conflict.h * @ingroup PUBLICCOREAPI * @brief public methods for conflict handler plugins and conflict analysis * @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_CONFLICT_H__ #define __SCIP_SCIP_CONFLICT_H__ #include "scip/def.h" #include "scip/type_conflict.h" #include "scip/type_cons.h" #include "scip/type_lp.h" #include "scip/type_result.h" #include "scip/type_retcode.h" #include "scip/type_scip.h" #include "scip/type_tree.h" #include "scip/type_var.h" #ifdef __cplusplus extern "C" { #endif /**@addtogroup PublicConflicthdlrMethods * * @{ */ /** creates a conflict handler and includes it in SCIP * * @note method has all conflict handler callbacks as arguments and is thus changed every time a new * callback is added * in future releases; consider using SCIPincludeConflicthdlrBasic() and setter functions * if you seek for a method which is less likely to change in future releases */ SCIP_EXPORT SCIP_RETCODE SCIPincludeConflicthdlr( SCIP* scip, /**< SCIP data structure */ const char* name, /**< name of conflict handler */ const char* desc, /**< description of conflict handler */ int priority, /**< priority of the conflict handler */ SCIP_DECL_CONFLICTCOPY((*conflictcopy)), /**< copy method of conflict handler or NULL if you don't want to copy your plugin into sub-SCIPs */ SCIP_DECL_CONFLICTFREE((*conflictfree)), /**< destructor of conflict handler */ SCIP_DECL_CONFLICTINIT((*conflictinit)), /**< initialize conflict handler */ SCIP_DECL_CONFLICTEXIT((*conflictexit)), /**< deinitialize conflict handler */ SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)),/**< solving process initialization method of conflict handler */ SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)),/**< solving process deinitialization method of conflict handler */ SCIP_DECL_CONFLICTEXEC((*conflictexec)), /**< conflict processing method of conflict handler */ SCIP_CONFLICTHDLRDATA* conflicthdlrdata /**< conflict handler data */ ); /** creates a conflict handler and includes it in SCIP with its most fundamental callbacks. All non-fundamental * (or optional) callbacks as, e.g., init and exit callbacks, will be set to NULL. * Optional callbacks can be set via specific setter functions SCIPsetConflicthdlrCopy(), SCIPsetConflicthdlrFree(), * SCIPsetConflicthdlrInit(), SCIPsetConflicthdlrExit(), SCIPsetConflicthdlrInitsol(), * and SCIPsetConflicthdlrExitsol() * * @note if you want to set all callbacks with a single method call, consider using SCIPincludeConflicthdlr() instead */ SCIP_EXPORT SCIP_RETCODE SCIPincludeConflicthdlrBasic( SCIP* scip, /**< SCIP data structure */ SCIP_CONFLICTHDLR** conflicthdlrptr, /**< reference to a conflict handler pointer, or NULL */ const char* name, /**< name of conflict handler */ const char* desc, /**< description of conflict handler */ int priority, /**< priority of the conflict handler */ SCIP_DECL_CONFLICTEXEC((*conflictexec)), /**< conflict processing method of conflict handler */ SCIP_CONFLICTHDLRDATA* conflicthdlrdata /**< conflict handler data */ ); /** set copy method of conflict handler */ SCIP_EXPORT SCIP_RETCODE SCIPsetConflicthdlrCopy( SCIP* scip, /**< SCIP data structure */ SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */ SCIP_DECL_CONFLICTCOPY((*conflictcopy)) /**< copy method of conflict handler */ ); /** set destructor of conflict handler */ SCIP_EXPORT SCIP_RETCODE SCIPsetConflicthdlrFree( SCIP* scip, /**< SCIP data structure */ SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */ SCIP_DECL_CONFLICTFREE((*conflictfree)) /**< destructor of conflict handler */ ); /** set initialization method of conflict handler */ SCIP_EXPORT SCIP_RETCODE SCIPsetConflicthdlrInit( SCIP* scip, /**< SCIP data structure */ SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */ SCIP_DECL_CONFLICTINIT((*conflictinit)) /**< initialize conflict handler */ ); /** set deinitialization method of conflict handler */ SCIP_EXPORT SCIP_RETCODE SCIPsetConflicthdlrExit( SCIP* scip, /**< SCIP data structure */ SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */ SCIP_DECL_CONFLICTEXIT((*conflictexit)) /**< deinitialize conflict handler */ ); /** set solving process initialization method of conflict handler */ SCIP_EXPORT SCIP_RETCODE SCIPsetConflicthdlrInitsol( SCIP* scip, /**< SCIP data structure */ SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */ SCIP_DECL_CONFLICTINITSOL((*conflictinitsol))/**< solving process initialization method of conflict handler */ ); /** set solving process deinitialization method of conflict handler */ SCIP_EXPORT SCIP_RETCODE SCIPsetConflicthdlrExitsol( SCIP* scip, /**< SCIP data structure */ SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */ SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol))/**< solving process deinitialization method of conflict handler */ ); /** returns the conflict handler of the given name, or NULL if not existing */ SCIP_EXPORT SCIP_CONFLICTHDLR* SCIPfindConflicthdlr( SCIP* scip, /**< SCIP data structure */ const char* name /**< name of conflict handler */ ); /** returns the array of currently available conflict handlers */ SCIP_EXPORT SCIP_CONFLICTHDLR** SCIPgetConflicthdlrs( SCIP* scip /**< SCIP data structure */ ); /** returns the number of currently available conflict handlers */ SCIP_EXPORT int SCIPgetNConflicthdlrs( SCIP* scip /**< SCIP data structure */ ); /** sets the priority of a conflict handler */ SCIP_EXPORT SCIP_RETCODE SCIPsetConflicthdlrPriority( SCIP* scip, /**< SCIP data structure */ SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */ int priority /**< new priority of the conflict handler */ ); /** @} */ /**@addtogroup PublicConflictMethods * * @{ */ /** return TRUE if conflict analysis is applicable; In case the function return FALSE there is no need to initialize the * conflict analysis since it will not be applied * * @return return TRUE if conflict analysis is applicable; In case the function return FALSE there is no need to initialize the * conflict analysis since it will not be applied * * @pre This method can be called if SCIP is in one of the following stages: * - \ref SCIP_STAGE_INITPRESOLVE * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_EXITPRESOLVE * - \ref SCIP_STAGE_SOLVING * * @note SCIP stage does not get changed */ SCIP_EXPORT SCIP_Bool SCIPisConflictAnalysisApplicable( SCIP* scip /**< SCIP data structure */ ); /** initializes the conflict analysis by clearing the conflict candidate queue; this method must be called before you * enter the conflict variables by calling SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPaddConflictBd(), * SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictRelaxedBd(), or SCIPaddConflictBinvar(); * * @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 SCIP is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING * * @note SCIP stage does not get changed */ SCIP_EXPORT SCIP_RETCODE SCIPinitConflictAnalysis( SCIP* scip, /**< SCIP data structure */ SCIP_CONFTYPE conftype, /**< type of conflict */ SCIP_Bool iscutoffinvolved /**< is the current cutoff bound involved? */ ); /** adds lower bound of variable at the time of the given bound change index to the conflict analysis' candidate storage; * this method should be called in one of the following two cases: * 1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictLb() should be called for each lower bound * that led to the conflict (e.g. the infeasibility of globally or locally valid constraint). * 2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictLb() should be called * for each lower bound, whose current assignment led to the deduction of the given conflict bound. * * @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 SCIP is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING * * @note SCIP stage does not get changed */ SCIP_EXPORT SCIP_RETCODE SCIPaddConflictLb( SCIP* scip, /**< SCIP data structure */ SCIP_VAR* var, /**< variable whose lower bound should be added to conflict candidate queue */ SCIP_BDCHGIDX* bdchgidx /**< bound change index representing time on path to current node, when the * conflicting bound was valid, NULL for current local bound */ ); /** adds lower bound of variable at the time of the given bound change index to the conflict analysis' candidate storage * with the additional information of a relaxed lower bound; this relaxed lower bound is the one which would be enough * to explain a certain bound change; * this method should be called in one of the following two cases: * 1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictRelaxedLb() should be called for each (relaxed) lower bound * that led to the conflict (e.g. the infeasibility of globally or locally valid constraint). * 2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictRelexedLb() should be called * for each (relaxed) lower bound, whose current assignment led to the deduction of the given conflict bound. * * @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 SCIP is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING * * @note SCIP stage does not get changed */ SCIP_EXPORT SCIP_RETCODE SCIPaddConflictRelaxedLb( SCIP* scip, /**< SCIP data structure */ SCIP_VAR* var, /**< variable whose lower bound should be added to conflict candidate queue */ SCIP_BDCHGIDX* bdchgidx, /**< bound change index representing time on path to current node, when the * conflicting bound was valid, NULL for current local bound */ SCIP_Real relaxedlb /**< the relaxed lower bound */ ); /** adds upper bound of variable at the time of the given bound change index to the conflict analysis' candidate storage; * this method should be called in one of the following two cases: * 1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictUb() should be called for each upper bound that * led to the conflict (e.g. the infeasibility of globally or locally valid constraint). * 2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictUb() should be called for * each upper bound, whose current assignment led to the deduction of the given conflict bound. * * @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 SCIP is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING * * @note SCIP stage does not get changed */ SCIP_EXPORT SCIP_RETCODE SCIPaddConflictUb( SCIP* scip, /**< SCIP data structure */ SCIP_VAR* var, /**< variable whose upper bound should be added to conflict candidate queue */ SCIP_BDCHGIDX* bdchgidx /**< bound change index representing time on path to current node, when the * conflicting bound was valid, NULL for current local bound */ ); /** adds upper bound of variable at the time of the given bound change index to the conflict analysis' candidate storage * with the additional information of a relaxed upper bound; this relaxed upper bound is the one which would be enough * to explain a certain bound change; * this method should be called in one of the following two cases: * 1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictRelaxedUb() should be called for each (relaxed) upper * bound that led to the conflict (e.g. the infeasibility of globally or locally valid constraint). * 2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictRelaxedUb() should be * called for each (relaxed) upper bound, whose current assignment led to the deduction of the given conflict * bound. * * @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 SCIP is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING * * @note SCIP stage does not get changed */ SCIP_EXPORT SCIP_RETCODE SCIPaddConflictRelaxedUb( SCIP* scip, /**< SCIP data structure */ SCIP_VAR* var, /**< variable whose upper bound should be added to conflict candidate queue */ SCIP_BDCHGIDX* bdchgidx, /**< bound change index representing time on path to current node, when the * conflicting bound was valid, NULL for current local bound */ SCIP_Real relaxedub /**< the relaxed upper bound */ ); /** adds lower or upper bound of variable at the time of the given bound change index to the conflict analysis' candidate * storage; this method should be called in one of the following two cases: * 1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictBd() should be called for each bound * that led to the conflict (e.g. the infeasibility of globally or locally valid constraint). * 2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictBd() should be called * for each bound, whose current assignment led to the deduction of the given conflict bound. * * @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 SCIP is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING * * @note SCIP stage does not get changed */ SCIP_EXPORT SCIP_RETCODE SCIPaddConflictBd( SCIP* scip, /**< SCIP data structure */ SCIP_VAR* var, /**< variable whose upper bound should be added to conflict candidate queue */ SCIP_BOUNDTYPE boundtype, /**< the type of the conflicting bound (lower or upper bound) */ SCIP_BDCHGIDX* bdchgidx /**< bound change index representing time on path to current node, when the * conflicting bound was valid, NULL for current local bound */ ); /** adds lower or upper bound of variable at the time of the given bound change index to the conflict analysis' * candidate storage; with the additional information of a relaxed upper bound; this relaxed upper bound is the one * which would be enough to explain a certain bound change; * this method should be called in one of the following two cases: * 1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictRelaxedBd() should be called for each (relaxed) * bound that led to the conflict (e.g. the infeasibility of globally or locally valid constraint). * 2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictRelaxedBd() should be * called for each (relaxed) bound, whose current assignment led to the deduction of the given conflict bound. * * @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 SCIP is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING * * @note SCIP stage does not get changed */ SCIP_EXPORT SCIP_RETCODE SCIPaddConflictRelaxedBd( SCIP* scip, /**< SCIP data structure */ SCIP_VAR* var, /**< variable whose upper bound should be added to conflict candidate queue */ SCIP_BOUNDTYPE boundtype, /**< the type of the conflicting bound (lower or upper bound) */ SCIP_BDCHGIDX* bdchgidx, /**< bound change index representing time on path to current node, when the * conflicting bound was valid, NULL for current local bound */ SCIP_Real relaxedbd /**< the relaxed bound */ ); /** adds changed bound of fixed binary variable to the conflict analysis' candidate storage; * this method should be called in one of the following two cases: * 1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictBinvar() should be called for each fixed binary * variable that led to the conflict (e.g. the infeasibility of globally or locally valid constraint). * 2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictBinvar() should be called * for each binary variable, whose current fixing led to the deduction of the given conflict bound. * * @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 SCIP is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING * * @note SCIP stage does not get changed */ SCIP_EXPORT SCIP_RETCODE SCIPaddConflictBinvar( SCIP* scip, /**< SCIP data structure */ SCIP_VAR* var /**< binary variable whose changed bound should be added to conflict queue */ ); /** checks if the given variable is already part of the current conflict set or queued for resolving with the same or * even stronger bound * * @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 SCIP is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING * * @note SCIP stage does not get changed */ SCIP_EXPORT SCIP_RETCODE SCIPisConflictVarUsed( SCIP* scip, /**< SCIP data structure */ SCIP_VAR* var, /**< variable whose upper bound should be added to conflict candidate queue */ SCIP_BOUNDTYPE boundtype, /**< the type of the conflicting bound (lower or upper bound) */ SCIP_BDCHGIDX* bdchgidx, /**< bound change index representing time on path to current node, when the * conflicting bound was valid, NULL for current local bound */ SCIP_Bool* used /**< pointer to store if the variable is already used */ ); /** returns the conflict lower bound if the variable is present in the current conflict set; otherwise the global lower * bound * * @return returns the conflict lower bound if the variable is present in the current conflict set; otherwise the global lower * bound * * @pre This method can be called if SCIP is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING * * @note SCIP stage does not get changed */ SCIP_EXPORT SCIP_Real SCIPgetConflictVarLb( SCIP* scip, /**< SCIP data structure */ SCIP_VAR* var /**< problem variable */ ); /** returns the conflict upper bound if the variable is present in the current conflict set; otherwise minus global * upper bound * * @return returns the conflict upper bound if the variable is present in the current conflict set; otherwise minus global * upper bound * * @pre This method can be called if SCIP is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING * * @note SCIP stage does not get changed */ SCIP_EXPORT SCIP_Real SCIPgetConflictVarUb( SCIP* scip, /**< SCIP data structure */ SCIP_VAR* var /**< problem variable */ ); /** analyzes conflict bounds that were added after a call to SCIPinitConflictAnalysis() with calls to * SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPaddConflictBd(), SCIPaddConflictRelaxedLb(), * SCIPaddConflictRelaxedUb(), SCIPaddConflictRelaxedBd(), or SCIPaddConflictBinvar(); on success, calls the conflict * handlers to create a conflict constraint out of the resulting conflict set; the given valid depth must be a depth * level, at which the conflict set defined by calls to SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPaddConflictBd(), * SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictRelaxedBd(), and SCIPaddConflictBinvar() is * valid for the whole subtree; if the conflict was found by a violated constraint, use SCIPanalyzeConflictCons() * instead of SCIPanalyzeConflict() to make sure, that the correct valid depth is used * * @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 SCIP is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING * * @note SCIP stage does not get changed */ SCIP_EXPORT SCIP_RETCODE SCIPanalyzeConflict( SCIP* scip, /**< SCIP data structure */ int validdepth, /**< minimal depth level at which the initial conflict set is valid */ SCIP_Bool* success /**< pointer to store whether a conflict constraint was created, or NULL */ ); /** analyzes conflict bounds that were added with calls to SCIPaddConflictLb(), SCIPaddConflictUb(), * SCIPaddConflictBd(), SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictRelaxedBd(), or * SCIPaddConflictBinvar(); on success, calls the conflict handlers to create a conflict constraint out of the * resulting conflict set; the given constraint must be the constraint that detected the conflict, i.e. the constraint * that is infeasible in the local bounds of the initial conflict set (defined by calls to SCIPaddConflictLb(), * SCIPaddConflictUb(), SCIPaddConflictBd(), SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), * SCIPaddConflictRelaxedBd(), and SCIPaddConflictBinvar()) * * @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 SCIP is in one of the following stages: * - \ref SCIP_STAGE_PRESOLVING * - \ref SCIP_STAGE_SOLVING * * @note SCIP stage does not get changed */ SCIP_EXPORT SCIP_RETCODE SCIPanalyzeConflictCons( SCIP* scip, /**< SCIP data structure */ SCIP_CONS* cons, /**< constraint that detected the conflict */ SCIP_Bool* success /**< pointer to store whether a conflict constraint was created, or NULL */ ); /**@} */ #ifdef __cplusplus } #endif #endif