1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */ 7 /* fuer Informationstechnik Berlin */ 8 /* */ 9 /* SCIP is distributed under the terms of the ZIB Academic License. */ 10 /* */ 11 /* You should have received a copy of the ZIB Academic License */ 12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */ 13 /* */ 14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 15 16 /**@file type_conflict.h 17 * @ingroup TYPEDEFINITIONS 18 * @brief type definitions for conflict analysis 19 * @author Tobias Achterberg 20 * 21 * This file defines the interface for conflict handler implemented in C. 22 * 23 */ 24 25 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 26 27 #ifndef __SCIP_TYPE_CONFLICT_H__ 28 #define __SCIP_TYPE_CONFLICT_H__ 29 30 #include "scip/def.h" 31 #include "scip/type_retcode.h" 32 #include "scip/type_result.h" 33 #include "scip/type_var.h" 34 35 #ifdef __cplusplus 36 extern "C" { 37 #endif 38 39 typedef struct SCIP_Conflicthdlr SCIP_CONFLICTHDLR; /**< conflict handler to process conflict sets */ 40 typedef struct SCIP_ConflicthdlrData SCIP_CONFLICTHDLRDATA; /**< conflict handler data */ 41 typedef struct SCIP_ConflictSet SCIP_CONFLICTSET; /**< set of conflicting bound changes */ 42 typedef struct SCIP_ProofSet SCIP_PROOFSET; /**< set of variables and coefficients describing a proof-constraint of type a^Tx <= rhs */ 43 typedef struct SCIP_LPBdChgs SCIP_LPBDCHGS; /**< set of LP bound changes */ 44 typedef struct SCIP_Conflict SCIP_CONFLICT; /**< conflict analysis data structure */ 45 46 /** types of conflicts */ 47 enum SCIP_ConflictType 48 { 49 SCIP_CONFTYPE_UNKNOWN = 0, /**< unknown type */ 50 SCIP_CONFTYPE_PROPAGATION = 1, /**< conflict results from propagation */ 51 SCIP_CONFTYPE_INFEASLP = 2, /**< conflict results from an infeasible LP relaxation */ 52 SCIP_CONFTYPE_BNDEXCEEDING = 3, /**< conflict results from a boundexceeding LP relaxation */ 53 SCIP_CONFTYPE_ALTINFPROOF = 4, /**< alternative proof of an infeasible LP relaxation */ 54 SCIP_CONFTYPE_ALTBNDPROOF = 5 /**< alternative proof of a boundexceeding LP relaxation */ 55 }; 56 typedef enum SCIP_ConflictType SCIP_CONFTYPE; 57 58 /** dualray presolving strategy */ 59 enum SCIP_ConflictPresolStrat 60 { 61 SCIP_CONFPRES_DISABLED = 0, /**< no presolving */ 62 SCIP_CONFPRES_ONLYLOCAL = 1, /**< keep variables contributing with its local bound */ 63 SCIP_CONFPRES_ONLYGLOBAL = 2, /**< keep variables contributing with its global bound */ 64 SCIP_CONFPRES_BOTH = 3 /**< keep variables contributing with its global bound and add a few 65 * variables contributing with its local bound such that the 66 * constraint is not globally redundant 67 */ 68 }; 69 typedef enum SCIP_ConflictPresolStrat SCIP_CONFPRES; 70 71 /** copy method for conflict handler plugins (called when SCIP copies plugins) 72 * 73 * input: 74 * - scip : SCIP main data structure 75 * - conflicthdlr : the conflict handler itself 76 */ 77 #define SCIP_DECL_CONFLICTCOPY(x) SCIP_RETCODE x (SCIP* scip, SCIP_CONFLICTHDLR* conflicthdlr) 78 79 /** destructor of conflict handler to free conflict handler data (called when SCIP is exiting) 80 * 81 * input: 82 * - scip : SCIP main data structure 83 * - conflicthdlr : the conflict handler itself 84 */ 85 #define SCIP_DECL_CONFLICTFREE(x) SCIP_RETCODE x (SCIP* scip, SCIP_CONFLICTHDLR* conflicthdlr) 86 87 /** initialization method of conflict handler (called after problem was transformed) 88 * 89 * input: 90 * - scip : SCIP main data structure 91 * - conflicthdlr : the conflict handler itself 92 */ 93 #define SCIP_DECL_CONFLICTINIT(x) SCIP_RETCODE x (SCIP* scip, SCIP_CONFLICTHDLR* conflicthdlr) 94 95 /** deinitialization method of conflict handler (called before transformed problem is freed) 96 * 97 * input: 98 * - scip : SCIP main data structure 99 * - conflicthdlr : the conflict handler itself 100 */ 101 #define SCIP_DECL_CONFLICTEXIT(x) SCIP_RETCODE x (SCIP* scip, SCIP_CONFLICTHDLR* conflicthdlr) 102 103 /** solving process initialization method of conflict handler (called when branch and bound process is about to begin) 104 * 105 * This method is called when the presolving was finished and the branch and bound process is about to begin. 106 * The conflict handler may use this call to initialize its branch and bound specific data. 107 * 108 * input: 109 * - scip : SCIP main data structure 110 * - conflicthdlr : the conflict handler itself 111 */ 112 #define SCIP_DECL_CONFLICTINITSOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_CONFLICTHDLR* conflicthdlr) 113 114 /** solving process deinitialization method of conflict handler (called before branch and bound process data is freed) 115 * 116 * This method is called before the branch and bound process is freed. 117 * The conflict handler should use this call to clean up its branch and bound data. 118 * 119 * input: 120 * - scip : SCIP main data structure 121 * - conflicthdlr : the conflict handler itself 122 */ 123 #define SCIP_DECL_CONFLICTEXITSOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_CONFLICTHDLR* conflicthdlr) 124 125 /** conflict processing method of conflict handler (called when conflict was found) 126 * 127 * This method is called, when the conflict analysis found a conflict on variable bounds. 128 * The conflict handler may update its data accordingly and create a constraint out of the conflict set. 129 * If the parameter "resolved" is set, the conflict handler should not create a constraint, because 130 * a different conflict handler with higher priority already created a constraint. 131 * The bounds in the conflict set lead to a conflict (i.e. an infeasibility) when all enforced at the same time. 132 * Thus, a feasible conflict constraint must demand that at least one of the variables in the conflict 133 * set violates its corresponding bound, i.e., fulfills the negation of the bound change in the conflict set. 134 * For continuous variables, the negation has to be defined in a relaxed way: if, e.g., the bound in the conflict 135 * set is "x <= u", the negation to be used has to be "x >= u", and not "x > u". 136 * The given "bdchginfos" array representing the conflict set is only a reference to an internal 137 * buffer, that may be modified at any time by SCIP. The user must copy the needed information from the 138 * "bdchginfos" array to own data structures, if (s)he wants to use the information later. 139 * (S)he should not keep a pointer to the array or pointers to the single bdchginfos in the array, because these 140 * may get invalid afterwards. 141 * 142 * input: 143 * - scip : SCIP main data structure 144 * - conflicthdlr : the conflict handler itself 145 * - node : node to add resulting conflict constraint to (with SCIPaddConsNode()) 146 * - validnode : node at which the conflict constraint is valid (should be passed to SCIPaddConsNode()) 147 * - bdchginfos : array with bound changes that lead to a conflict 148 * - relaxedbds : array with relaxed bounds which are efficient to create a valid conflict 149 * - nbdchginfos : number of bound changes in the conflict set 150 * -.primalbound : the current primal bound, or -infininity if the conflict arises from an infeasible LP 151 * - separate : should the conflict constraint be separated? 152 * - local : is the conflict set only valid locally, i.e., should the constraint be created as local constraint? 153 * - dynamic : should the conflict constraint be made subject to aging? 154 * - removable : should the conflict's relaxation be made subject to LP aging and cleanup? 155 * - resolved : is the conflict set already used to create a constraint? 156 * - result : pointer to store the result of the conflict processing call 157 * 158 * possible return values for *result: 159 * - SCIP_CONSADDED : the conflict handler created a constraint out of the conflict set 160 * - SCIP_DIDNOTFIND : the conflict handler could not create a constraint out of the conflict set 161 * - SCIP_DIDNOTRUN : the conflict handler was skipped 162 */ 163 #define SCIP_DECL_CONFLICTEXEC(x) SCIP_RETCODE x (SCIP* scip, SCIP_CONFLICTHDLR* conflicthdlr, SCIP_NODE* node, \ 164 SCIP_NODE* validnode, SCIP_BDCHGINFO** bdchginfos, SCIP_Real* relaxedbds, int nbdchginfos, SCIP_CONFTYPE conftype, \ 165 SCIP_Bool cutoffinvolved, SCIP_Bool separate, SCIP_Bool local, SCIP_Bool dynamic, SCIP_Bool removable, \ 166 SCIP_Bool resolved, SCIP_RESULT* result) 167 168 #ifdef __cplusplus 169 } 170 #endif 171 172 #endif 173