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_setppc.h 17 * @ingroup CONSHDLRS 18 * @brief Constraint handler for the set partitioning / packing / covering constraints \f$1^T x\ \{=, \le, \ge\}\ 1\f$. 19 * @author Tobias Achterberg 20 * @author Michael Winkler 21 * 22 */ 23 24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 25 26 #ifndef __SCIP_CONS_SETPPC_H__ 27 #define __SCIP_CONS_SETPPC_H__ 28 29 30 #include "scip/def.h" 31 #include "scip/type_cons.h" 32 #include "scip/type_lp.h" 33 #include "scip/type_retcode.h" 34 #include "scip/type_scip.h" 35 #include "scip/type_var.h" 36 37 #ifdef __cplusplus 38 extern "C" { 39 #endif 40 41 42 /** creates the handler for set partitioning / packing / covering constraints and includes it in SCIP 43 * 44 * @ingroup ConshdlrIncludes 45 * */ 46 SCIP_EXPORT 47 SCIP_RETCODE SCIPincludeConshdlrSetppc( 48 SCIP* scip /**< SCIP data structure */ 49 ); 50 51 /**@addtogroup CONSHDLRS 52 * 53 * @{ 54 * 55 * @name Set Packing/Partitioning/Covering Constraints 56 * 57 * @{ 58 * 59 * This constraint handler handles three special classes of linear constraints, namely 60 * set partitioning, set packing, and set covering constraints. 61 * For a set of binary variables \f$x_i, i=1,\dots,n\f$, a set partitioning constraint has the form 62 * \f[ 63 * \sum_{i=1}^n x_i = 1, 64 * \f] 65 * a set packing constraint has the form 66 * \f[ 67 * \sum_{i=1}^n x_i \le 1, 68 * \f] 69 * and a set covering constraint has the form 70 * \f[ 71 * \sum_{i=1}^n x_i \ge 1. 72 * \f] 73 */ 74 75 /** type of setppc constraint: set partitioning, set packing, or set covering */ 76 enum SCIP_SetppcType 77 { 78 SCIP_SETPPCTYPE_PARTITIONING = 0, /**< constraint is a set partitioning constraint: sum(x) == 1 */ 79 SCIP_SETPPCTYPE_PACKING = 1, /**< constraint is a set packing constraint: sum(x) <= 1 */ 80 SCIP_SETPPCTYPE_COVERING = 2 /**< constraint is a set covering constraint: sum(x) >= 1 */ 81 }; 82 typedef enum SCIP_SetppcType SCIP_SETPPCTYPE; 83 84 /** creates and captures a set partitioning constraint 85 * 86 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 87 */ 88 SCIP_EXPORT 89 SCIP_RETCODE SCIPcreateConsSetpart( 90 SCIP* scip, /**< SCIP data structure */ 91 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 92 const char* name, /**< name of constraint */ 93 int nvars, /**< number of variables in the constraint */ 94 SCIP_VAR** vars, /**< array with variables of constraint entries */ 95 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 96 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 97 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 98 * Usually set to TRUE. */ 99 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 100 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 101 SCIP_Bool check, /**< should the constraint be checked for feasibility? 102 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 103 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 104 * Usually set to TRUE. */ 105 SCIP_Bool local, /**< is constraint only valid locally? 106 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 107 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? 108 * Usually set to FALSE. In column generation applications, set to TRUE if pricing 109 * adds coefficients to this constraint. */ 110 SCIP_Bool dynamic, /**< is constraint subject to aging? 111 * Usually set to FALSE. Set to TRUE for own cuts which 112 * are separated as constraints. */ 113 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 114 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 115 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 116 * if it may be moved to a more global node? 117 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */ 118 ); 119 120 /** creates and captures a set partitioning constraint 121 * in its most basic variant, i. e., with all constraint flags set to their default values, which can be set 122 * afterwards using SCIPsetConsFLAGNAME() in scip.h 123 * 124 * @see SCIPcreateConsSetpart() for the default constraint flag configuration 125 * 126 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 127 */ 128 SCIP_EXPORT 129 SCIP_RETCODE SCIPcreateConsBasicSetpart( 130 SCIP* scip, /**< SCIP data structure */ 131 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 132 const char* name, /**< name of constraint */ 133 int nvars, /**< number of variables in the constraint */ 134 SCIP_VAR** vars /**< array with variables of constraint entries */ 135 ); 136 137 /** creates and captures a set packing constraint 138 * 139 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 140 */ 141 SCIP_EXPORT 142 SCIP_RETCODE SCIPcreateConsSetpack( 143 SCIP* scip, /**< SCIP data structure */ 144 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 145 const char* name, /**< name of constraint */ 146 int nvars, /**< number of variables in the constraint */ 147 SCIP_VAR** vars, /**< array with variables of constraint entries */ 148 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 149 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 150 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 151 * Usually set to TRUE. */ 152 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 153 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 154 SCIP_Bool check, /**< should the constraint be checked for feasibility? 155 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 156 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 157 * Usually set to TRUE. */ 158 SCIP_Bool local, /**< is constraint only valid locally? 159 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 160 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? 161 * Usually set to FALSE. In column generation applications, set to TRUE if pricing 162 * adds coefficients to this constraint. */ 163 SCIP_Bool dynamic, /**< is constraint subject to aging? 164 * Usually set to FALSE. Set to TRUE for own cuts which 165 * are separated as constraints. */ 166 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 167 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 168 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 169 * if it may be moved to a more global node? 170 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */ 171 ); 172 173 /** creates and captures a set packing constraint 174 * in its most basic variant, i. e., with all constraint flags set to their default values, which can be set 175 * afterwards using SCIPsetConsFLAGNAME() in scip.h 176 * 177 * @see SCIPcreateConsSetpack() for the default constraint flag configuration 178 * 179 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 180 */ 181 SCIP_EXPORT 182 SCIP_RETCODE SCIPcreateConsBasicSetpack( 183 SCIP* scip, /**< SCIP data structure */ 184 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 185 const char* name, /**< name of constraint */ 186 int nvars, /**< number of variables in the constraint */ 187 SCIP_VAR** vars /**< array with variables of constraint entries */ 188 ); 189 190 /** creates and captures a set covering constraint 191 * 192 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 193 */ 194 SCIP_EXPORT 195 SCIP_RETCODE SCIPcreateConsSetcover( 196 SCIP* scip, /**< SCIP data structure */ 197 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 198 const char* name, /**< name of constraint */ 199 int nvars, /**< number of variables in the constraint */ 200 SCIP_VAR** vars, /**< array with variables of constraint entries */ 201 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 202 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 203 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 204 * Usually set to TRUE. */ 205 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 206 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 207 SCIP_Bool check, /**< should the constraint be checked for feasibility? 208 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 209 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 210 * Usually set to TRUE. */ 211 SCIP_Bool local, /**< is constraint only valid locally? 212 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 213 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? 214 * Usually set to FALSE. In column generation applications, set to TRUE if pricing 215 * adds coefficients to this constraint. */ 216 SCIP_Bool dynamic, /**< is constraint subject to aging? 217 * Usually set to FALSE. Set to TRUE for own cuts which 218 * are separated as constraints. */ 219 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 220 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 221 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 222 * if it may be moved to a more global node? 223 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */ 224 ); 225 226 /** creates and captures a set packing constraint 227 * in its most basic variant, i. e., with all constraint flags set to their default values, which can be set 228 * afterwards using SCIPsetConsFLAGNAME() in scip.h 229 * 230 * @see SCIPcreateConsSetpack() for the default constraint flag configuration 231 * 232 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 233 */ 234 SCIP_EXPORT 235 SCIP_RETCODE SCIPcreateConsBasicSetcover( 236 SCIP* scip, /**< SCIP data structure */ 237 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 238 const char* name, /**< name of constraint */ 239 int nvars, /**< number of variables in the constraint */ 240 SCIP_VAR** vars /**< array with variables of constraint entries */ 241 ); 242 243 /** adds coefficient in set partitioning / packing / covering constraint */ 244 SCIP_EXPORT 245 SCIP_RETCODE SCIPaddCoefSetppc( 246 SCIP* scip, /**< SCIP data structure */ 247 SCIP_CONS* cons, /**< constraint data */ 248 SCIP_VAR* var /**< variable to add to the constraint */ 249 ); 250 251 /** gets number of variables in set partitioning / packing / covering constraint */ 252 SCIP_EXPORT 253 int SCIPgetNVarsSetppc( 254 SCIP* scip, /**< SCIP data structure */ 255 SCIP_CONS* cons /**< constraint data */ 256 ); 257 258 /** gets array of variables in set partitioning / packing / covering constraint */ 259 SCIP_EXPORT 260 SCIP_VAR** SCIPgetVarsSetppc( 261 SCIP* scip, /**< SCIP data structure */ 262 SCIP_CONS* cons /**< constraint data */ 263 ); 264 265 /** gets type of set partitioning / packing / covering constraint */ 266 SCIP_EXPORT 267 SCIP_SETPPCTYPE SCIPgetTypeSetppc( 268 SCIP* scip, /**< SCIP data structure */ 269 SCIP_CONS* cons /**< constraint data */ 270 ); 271 272 /** gets the dual solution of the set partitioning / packing / covering constraint in the current LP */ 273 SCIP_EXPORT 274 SCIP_Real SCIPgetDualsolSetppc( 275 SCIP* scip, /**< SCIP data structure */ 276 SCIP_CONS* cons /**< constraint data */ 277 ); 278 279 /** gets the dual Farkas value of the set partitioning / packing / covering constraint in the current infeasible LP */ 280 SCIP_EXPORT 281 SCIP_Real SCIPgetDualfarkasSetppc( 282 SCIP* scip, /**< SCIP data structure */ 283 SCIP_CONS* cons /**< constraint data */ 284 ); 285 286 /** returns the linear relaxation of the given set partitioning / packing / covering constraint; may return NULL if no 287 * LP row was yet created; the user must not modify the row! 288 */ 289 SCIP_EXPORT 290 SCIP_ROW* SCIPgetRowSetppc( 291 SCIP* scip, /**< SCIP data structure */ 292 SCIP_CONS* cons /**< constraint data */ 293 ); 294 295 /** returns current number of variables fixed to one in the constraint */ 296 SCIP_EXPORT 297 int SCIPgetNFixedonesSetppc( 298 SCIP* scip, /**< SCIP data structure */ 299 SCIP_CONS* cons /**< constraint data */ 300 ); 301 302 /** returns current number of variables fixed to zero in the constraint */ 303 SCIP_EXPORT 304 int SCIPgetNFixedzerosSetppc( 305 SCIP* scip, /**< SCIP data structure */ 306 SCIP_CONS* cons /**< constraint data */ 307 ); 308 309 /** cleans up (multi-)aggregations and fixings from setppc constraints */ 310 SCIP_EXPORT 311 SCIP_RETCODE SCIPcleanupConssSetppc( 312 SCIP* scip, /**< SCIP data structure */ 313 SCIP_Bool onlychecked, /**< should only checked constraints be cleaned up? */ 314 SCIP_Bool* infeasible, /**< pointer to return whether problem was detected to be infeasible */ 315 int* naddconss, /**< pointer to count number of added (linear) constraints */ 316 int* ndelconss, /**< pointer to count number of deleted (setppc) constraints */ 317 int* nchgcoefs, /**< pointer to count number of changed coefficients */ 318 int* nfixedvars /**< pointer to count number of fixed variables */ 319 ); 320 321 /** @} */ 322 323 /** @} */ 324 325 #ifdef __cplusplus 326 } 327 #endif 328 329 #endif 330