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 cons_indicator.h 17 * @ingroup CONSHDLRS 18 * @brief constraint handler for indicator constraints 19 * @author Marc Pfetsch 20 * 21 */ 22 23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 24 25 #ifndef __SCIP_CONS_INDICATOR_H__ 26 #define __SCIP_CONS_INDICATOR_H__ 27 28 29 #include "scip/def.h" 30 #include "scip/type_cons.h" 31 #include "scip/type_lp.h" 32 #include "scip/type_retcode.h" 33 #include "scip/type_scip.h" 34 #include "scip/type_sol.h" 35 #include "scip/type_var.h" 36 37 #ifdef __cplusplus 38 extern "C" { 39 #endif 40 41 /** creates the handler for indicator constraints and includes it in SCIP 42 * 43 * @ingroup ConshdlrIncludes 44 * */ 45 SCIP_EXPORT 46 SCIP_RETCODE SCIPincludeConshdlrIndicator( 47 SCIP* scip /**< SCIP data structure */ 48 ); 49 50 /**@addtogroup CONSHDLRS 51 * 52 * @{ 53 * 54 * @name Indicator Constraints 55 * 56 * @{ 57 * 58 * An indicator constraint is given by a binary variable \f$z\f$ and an inequality \f$ax \leq 59 * b\f$. It states that if \f$z = 1\f$ then \f$ax \leq b\f$ holds. 60 * 61 * This constraint is handled by adding a slack variable \f$s:\; ax - s \leq b\f$ with \f$s \geq 62 * 0\f$. The constraint is enforced by fixing \f$s\f$ to 0 if \f$z = 1\f$. 63 * 64 * @note The constraint only implements an implication not an equivalence, i.e., it does not ensure 65 * that \f$z = 1\f$ if \f$ax \leq b\f$ or equivalently if \f$s = 0\f$ holds. 66 * 67 * This constraint is equivalent to a linear constraint \f$ax - s \leq b\f$ and an SOS1 constraint on 68 * \f$z\f$ and \f$s\f$ (at most one should be nonzero). In the indicator context we can, however, 69 * separate more inequalities. 70 */ 71 72 /** creates and captures an indicator constraint 73 * 74 * @note @a binvar is checked to be binary only later. This enables a change of the type in 75 * procedures reading an instance. 76 * 77 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 78 */ 79 SCIP_EXPORT 80 SCIP_RETCODE SCIPcreateConsIndicator( 81 SCIP* scip, /**< SCIP data structure */ 82 SCIP_CONS** cons, /**< pointer to hold the created constraint (indicator or quadratic) */ 83 const char* name, /**< name of constraint */ 84 SCIP_VAR* binvar, /**< binary indicator variable (or NULL) */ 85 int nvars, /**< number of variables in the inequality */ 86 SCIP_VAR** vars, /**< array with variables of inequality (or NULL) */ 87 SCIP_Real* vals, /**< values of variables in inequality (or NULL) */ 88 SCIP_Real rhs, /**< rhs of the inequality */ 89 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. */ 90 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 91 * Usually set to TRUE. */ 92 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 93 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 94 SCIP_Bool check, /**< should the constraint be checked for feasibility? 95 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 96 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 97 * Usually set to TRUE. */ 98 SCIP_Bool local, /**< is constraint only valid locally? 99 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 100 SCIP_Bool dynamic, /**< is constraint subject to aging? 101 * Usually set to FALSE. Set to TRUE for own cuts which 102 * are separated as constraints. */ 103 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 104 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 105 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 106 * if it may be moved to a more global node? 107 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */ 108 ); 109 110 /** creates and captures an indicator constraint in its most basic version, i. e., all constraint flags are set to their 111 * basic value as explained for the method SCIPcreateConsIndicator(); all flags can be set via 112 * SCIPsetConsFLAGNAME-methods in scip.h 113 * 114 * @see SCIPcreateConsIndicator() for information about the basic constraint flag configuration 115 * 116 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 117 */ 118 SCIP_EXPORT 119 SCIP_RETCODE SCIPcreateConsBasicIndicator( 120 SCIP* scip, /**< SCIP data structure */ 121 SCIP_CONS** cons, /**< pointer to hold the created constraint (indicator or quadratic) */ 122 const char* name, /**< name of constraint */ 123 SCIP_VAR* binvar, /**< binary indicator variable (or NULL) */ 124 int nvars, /**< number of variables in the inequality */ 125 SCIP_VAR** vars, /**< array with variables of inequality (or NULL) */ 126 SCIP_Real* vals, /**< values of variables in inequality (or NULL) */ 127 SCIP_Real rhs /**< rhs of the inequality */ 128 ); 129 130 /** creates and captures an indicator constraint with given linear constraint and slack variable 131 * 132 * @note @a binvar is checked to be binary only later. This enables a change of the type in 133 * procedures reading an instance. 134 * 135 * @note we assume that @a slackvar actually appears in @a lincons and we also assume that it takes 136 * the role of a slack variable! 137 * 138 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 139 */ 140 SCIP_EXPORT 141 SCIP_RETCODE SCIPcreateConsIndicatorLinCons( 142 SCIP* scip, /**< SCIP data structure */ 143 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 144 const char* name, /**< name of constraint */ 145 SCIP_VAR* binvar, /**< binary indicator variable (or NULL) */ 146 SCIP_CONS* lincons, /**< linear constraint */ 147 SCIP_VAR* slackvar, /**< slack variable */ 148 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. */ 149 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 150 * Usually set to TRUE. */ 151 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 152 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 153 SCIP_Bool check, /**< should the constraint be checked for feasibility? 154 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 155 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 156 * Usually set to TRUE. */ 157 SCIP_Bool local, /**< is constraint only valid locally? 158 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 159 SCIP_Bool dynamic, /**< is constraint subject to aging? 160 * Usually set to FALSE. Set to TRUE for own cuts which 161 * are separated as constraints. */ 162 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 163 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 164 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 165 * if it may be moved to a more global node? 166 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */ 167 ); 168 169 /** creates and captures an indicator constraint with given linear constraint and slack variable 170 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the 171 * method SCIPcreateConsIndicator(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h 172 173 * @note @a binvar is checked to be binary only later. This enables a change of the type in 174 * procedures reading an instance. 175 * 176 * @note we assume that @a slackvar actually appears in @a lincons and we also assume that it takes 177 * the role of a slack variable! 178 * 179 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 180 * 181 * @see SCIPcreateConsIndicatorLinCons() for information about the basic constraint flag configuration 182 * 183 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 184 */ 185 SCIP_EXPORT 186 SCIP_RETCODE SCIPcreateConsBasicIndicatorLinCons( 187 SCIP* scip, /**< SCIP data structure */ 188 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 189 const char* name, /**< name of constraint */ 190 SCIP_VAR* binvar, /**< binary indicator variable (or NULL) */ 191 SCIP_CONS* lincons, /**< linear constraint */ 192 SCIP_VAR* slackvar /**< slack variable */ 193 ); 194 195 /** adds variable to the inequality of the indicator constraint */ 196 SCIP_EXPORT 197 SCIP_RETCODE SCIPaddVarIndicator( 198 SCIP* scip, /**< SCIP data structure */ 199 SCIP_CONS* cons, /**< indicator constraint */ 200 SCIP_VAR* var, /**< variable to add to the inequality */ 201 SCIP_Real val /**< value of variable */ 202 ); 203 204 /** gets the linear constraint corresponding to the indicator constraint (may be NULL) */ 205 SCIP_EXPORT 206 SCIP_CONS* SCIPgetLinearConsIndicator( 207 SCIP_CONS* cons /**< indicator constraint */ 208 ); 209 210 /** sets the linear constraint corresponding to the indicator constraint (may be NULL) */ 211 SCIP_EXPORT 212 SCIP_RETCODE SCIPsetLinearConsIndicator( 213 SCIP* scip, /**< SCIP data structure */ 214 SCIP_CONS* cons, /**< indicator constraint */ 215 SCIP_CONS* lincons /**< linear constraint */ 216 ); 217 218 /** sets binary indicator variable for indicator constraint */ 219 SCIP_EXPORT 220 SCIP_RETCODE SCIPsetBinaryVarIndicator( 221 SCIP* scip, /**< SCIP data structure */ 222 SCIP_CONS* cons, /**< indicator constraint */ 223 SCIP_VAR* binvar /**< binary variable to add to the inequality */ 224 ); 225 226 /** gets binary variable corresponding to indicator constraint */ 227 SCIP_EXPORT 228 SCIP_VAR* SCIPgetBinaryVarIndicator( 229 SCIP_CONS* cons /**< indicator constraint */ 230 ); 231 232 /** gets slack variable corresponding to indicator constraint */ 233 SCIP_EXPORT 234 SCIP_VAR* SCIPgetSlackVarIndicator( 235 SCIP_CONS* cons /**< indicator constraint */ 236 ); 237 238 /** sets upper bound for slack variable corresponding to indicator constraint 239 * 240 * Use with care if you know that the maximal violation of the corresponding constraint is at most @p ub. This bound 241 * might be improved automatically during the solution process. 242 * 243 * @pre This method should only be called if SCIP is in one of the following stages: 244 * - \ref SCIP_STAGE_INIT 245 * - \ref SCIP_STAGE_PROBLEM 246 */ 247 SCIP_EXPORT 248 SCIP_RETCODE SCIPsetSlackVarUb( 249 SCIP* scip, /**< SCIP data structure */ 250 SCIP_CONS* cons, /**< indicator constraint */ 251 SCIP_Real ub /**< upper bound for slack variable */ 252 ); 253 254 /** checks whether indicator constraint is violated w.r.t. sol */ 255 SCIP_EXPORT 256 SCIP_Bool SCIPisViolatedIndicator( 257 SCIP* scip, /**< SCIP data structure */ 258 SCIP_CONS* cons, /**< indicator constraint */ 259 SCIP_SOL* sol /**< solution, or NULL to use current node's solution */ 260 ); 261 262 /** based on values of other variables, computes slack and binary variable to turn constraint feasible */ 263 SCIP_EXPORT 264 SCIP_RETCODE SCIPmakeIndicatorFeasible( 265 SCIP* scip, /**< SCIP data structure */ 266 SCIP_CONS* cons, /**< indicator constraint */ 267 SCIP_SOL* sol, /**< solution */ 268 SCIP_Bool* changed /**< pointer to store whether the solution has been changed */ 269 ); 270 271 /** based on values of other variables, computes slack and binary variable to turn all constraints feasible */ 272 SCIP_EXPORT 273 SCIP_RETCODE SCIPmakeIndicatorsFeasible( 274 SCIP* scip, /**< SCIP data structure */ 275 SCIP_CONSHDLR* conshdlr, /**< indicator constraint handler */ 276 SCIP_SOL* sol, /**< solution */ 277 SCIP_Bool* changed /**< pointer to store whether the solution has been changed */ 278 ); 279 280 /** adds additional linear constraint that is not connected with an indicator constraint, but can be used for separation */ 281 SCIP_EXPORT 282 SCIP_RETCODE SCIPaddLinearConsIndicator( 283 SCIP* scip, /**< SCIP data structure */ 284 SCIP_CONSHDLR* conshdlr, /**< indicator constraint handler */ 285 SCIP_CONS* lincons /**< linear constraint */ 286 ); 287 288 /** adds additional globally valid row that is not connected with an indicator constraint, but can be used for separation */ 289 SCIP_EXPORT 290 SCIP_RETCODE SCIPaddRowIndicator( 291 SCIP* scip, /**< SCIP data structure */ 292 SCIP_CONSHDLR* conshdlr, /**< indicator constraint handler */ 293 SCIP_ROW* row /**< row to add */ 294 ); 295 296 /** @} */ 297 298 /** @} */ 299 300 #ifdef __cplusplus 301 } 302 #endif 303 304 #endif 305