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