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_pseudoboolean.h 26 * @ingroup CONSHDLRS 27 * @brief constraint handler for pseudoboolean constraints 28 * @author Stefan Heinz 29 * @author Michael Winkler 30 */ 31 32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 33 34 #ifndef __SCIP_CONS_PSEUDOBOOLEAN_H__ 35 #define __SCIP_CONS_PSEUDOBOOLEAN_H__ 36 37 38 #include "scip/def.h" 39 #include "scip/type_cons.h" 40 #include "scip/type_retcode.h" 41 #include "scip/type_scip.h" 42 #include "scip/type_var.h" 43 44 #ifdef __cplusplus 45 extern "C" { 46 #endif 47 48 #define ARTIFICIALVARNAMEPREFIX "andresultant_" 49 50 51 52 /** creates the handler for pseudoboolean constraints and includes it in SCIP 53 * 54 * @ingroup ConshdlrIncludes 55 * */ 56 SCIP_EXPORT 57 SCIP_RETCODE SCIPincludeConshdlrPseudoboolean( 58 SCIP* scip /**< SCIP data structure */ 59 ); 60 61 /**@addtogroup CONSHDLRS 62 * 63 * @{ 64 * 65 * @name Pseudoboolean Constraints 66 * 67 * @{ 68 * 69 * The constraint handler deals with pseudo boolean constraints. These are constraints of the form 70 * \f[ 71 * \mbox{lhs} \leq \sum_{k=0}^m c_k \cdot x_k + \sum_{i=0}^n c_i \cdot \prod_{j \in I_i} x_j \leq \mbox{rhs} 72 * \f] 73 * where all \f$x\f$ are binary. 74 */ 75 76 /** solution status after solving LP */ 77 enum SCIP_LinearConsType 78 { 79 SCIP_LINEARCONSTYPE_INVALIDCONS = -1, /**< this is no valid linear constraint type */ 80 SCIP_LINEARCONSTYPE_LINEAR = 0, /**< this is the common linear constraint */ 81 SCIP_LINEARCONSTYPE_LOGICOR = 1, /**< this is a logicor constraint */ 82 SCIP_LINEARCONSTYPE_KNAPSACK = 2, /**< this is a knapsack constraint */ 83 #ifndef WITHEQKNAPSACK 84 SCIP_LINEARCONSTYPE_SETPPC = 3 /**< this is a setppc constraint */ 85 #else 86 SCIP_LINEARCONSTYPE_SETPPC = 3, /**< this is a setppc constraint */ 87 SCIP_LINEARCONSTYPE_EQKNAPSACK = 4 /**< this is a equality knapsack constraint */ 88 #endif 89 }; 90 typedef enum SCIP_LinearConsType SCIP_LINEARCONSTYPE; 91 92 /** creates and captures a pseudoboolean constraint, with given linear and and-constraints 93 * 94 * @note intvar must currently be NULL 95 */ 96 SCIP_EXPORT 97 SCIP_RETCODE SCIPcreateConsPseudobooleanWithConss( 98 SCIP* scip, /**< SCIP data structure */ 99 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 100 const char* name, /**< name of constraint */ 101 SCIP_CONS* lincons, /**< associated linear constraint */ 102 SCIP_LINEARCONSTYPE linconstype, /**< linear constraint type of associated linear constraint */ 103 SCIP_CONS** andconss, /**< associated and-constraints */ 104 SCIP_Real* andcoefs, /**< associated coefficients of and-constraints */ 105 int nandconss, /**< number of associated and-constraints */ 106 SCIP_VAR* indvar, /**< indicator variable if it's a soft constraint, or NULL */ 107 SCIP_Real weight, /**< weight of the soft constraint, if it is one */ 108 SCIP_Bool issoftcons, /**< is this a soft constraint */ 109 SCIP_VAR* intvar, /**< an artificial variable which was added only for the objective function, 110 * if this variable is not NULL this constraint (without this integer 111 * variable) describes the objective function */ 112 SCIP_Real lhs, /**< left hand side of constraint */ 113 SCIP_Real rhs, /**< right hand side of constraint */ 114 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 115 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 116 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 117 * Usually set to TRUE. */ 118 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 119 * TRUE for model constraints, FALSE for additional, redundant 120 * constraints. */ 121 SCIP_Bool check, /**< should the constraint be checked for feasibility? 122 * TRUE for model constraints, FALSE for additional, redundant 123 * constraints. */ 124 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 125 * Usually set to TRUE. */ 126 SCIP_Bool local, /**< is constraint only valid locally? 127 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching 128 * constraints. */ 129 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? 130 * Usually set to FALSE. In column generation applications, set to TRUE if 131 * pricing adds coefficients to this constraint. */ 132 SCIP_Bool dynamic, /**< is constraint subject to aging? 133 * Usually set to FALSE. Set to TRUE for own cuts which are seperated as 134 * constraints. */ 135 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 136 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user 137 * cuts'. */ 138 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 139 * if it may be moved to a more global node? 140 * Usually set to FALSE. Set to TRUE to for constraints that represent 141 * node data. */ 142 ); 143 144 /** creates and captures a pseudoboolean constraint 145 * 146 * @note linear and nonlinear terms can be added using SCIPaddCoefPseudoboolean() and SCIPaddTermPseudoboolean(), 147 * respectively 148 * 149 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 150 * 151 * @note intvar must currently be NULL 152 */ 153 SCIP_EXPORT 154 SCIP_RETCODE SCIPcreateConsPseudoboolean( 155 SCIP* scip, /**< SCIP data structure */ 156 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 157 const char* name, /**< name of constraint */ 158 SCIP_VAR** linvars, /**< variables of the linear part, or NULL */ 159 int nlinvars, /**< number of variables of the linear part */ 160 SCIP_Real* linvals, /**< coefficients of linear part, or NULL */ 161 SCIP_VAR*** terms, /**< nonlinear terms of variables, or NULL */ 162 int nterms, /**< number of terms of variables of nonlinear term */ 163 int* ntermvars, /**< number of variables in nonlinear terms, or NULL */ 164 SCIP_Real* termvals, /**< coefficients of nonlinear parts, or NULL */ 165 SCIP_VAR* indvar, /**< indicator variable if it's a soft constraint, or NULL */ 166 SCIP_Real weight, /**< weight of the soft constraint, if it is one */ 167 SCIP_Bool issoftcons, /**< is this a soft constraint */ 168 SCIP_VAR* intvar, /**< an artificial variable which was added only for the objective function, 169 * if this variable is not NULL this constraint (without this integer 170 * variable) describes the objective function */ 171 SCIP_Real lhs, /**< left hand side of constraint */ 172 SCIP_Real rhs, /**< right hand side of constraint */ 173 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 174 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 175 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 176 * Usually set to TRUE. */ 177 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 178 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 179 SCIP_Bool check, /**< should the constraint be checked for feasibility? 180 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 181 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 182 * Usually set to TRUE. */ 183 SCIP_Bool local, /**< is constraint only valid locally? 184 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 185 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? 186 * Usually set to FALSE. In column generation applications, set to TRUE if pricing 187 * adds coefficients to this constraint. */ 188 SCIP_Bool dynamic, /**< is constraint subject to aging? 189 * Usually set to FALSE. Set to TRUE for own cuts which 190 * are separated as constraints. */ 191 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 192 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 193 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 194 * if it may be moved to a more global node? 195 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */ 196 ); 197 198 /** creates and captures a pseudoboolean constraint 199 * in its most basic variant, i. e., with all constraint flags set to their default values, which can be set 200 * afterwards using SCIPsetConsFLAGNAME() in scip.h 201 * 202 * @see SCIPcreateConsPseudoboolean() for the default constraint flag configuration 203 * 204 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 205 * 206 * @note intvar must currently be NULL 207 */ 208 SCIP_EXPORT 209 SCIP_RETCODE SCIPcreateConsBasicPseudoboolean( 210 SCIP* scip, /**< SCIP data structure */ 211 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 212 const char* name, /**< name of constraint */ 213 SCIP_VAR** linvars, /**< variables of the linear part, or NULL */ 214 int nlinvars, /**< number of variables of the linear part */ 215 SCIP_Real* linvals, /**< coefficients of linear part, or NULL */ 216 SCIP_VAR*** terms, /**< nonlinear terms of variables, or NULL */ 217 int nterms, /**< number of terms of variables of nonlinear term */ 218 int* ntermvars, /**< number of variables in nonlinear terms, or NULL */ 219 SCIP_Real* termvals, /**< coefficients of nonlinear parts, or NULL */ 220 SCIP_VAR* indvar, /**< indicator variable if it's a soft constraint, or NULL */ 221 SCIP_Real weight, /**< weight of the soft constraint, if it is one */ 222 SCIP_Bool issoftcons, /**< is this a soft constraint */ 223 SCIP_VAR* intvar, /**< a artificial variable which was added only for the objective function, 224 * if this variable is not NULL this constraint (without this integer 225 * variable) describes the objective function */ 226 SCIP_Real lhs, /**< left hand side of constraint */ 227 SCIP_Real rhs /**< right hand side of constraint */ 228 ); 229 230 /** adds linear term pseudo boolean constraint (if it is not zero) 231 * 232 * @note you can only add a coefficient if the special type of linear constraint won't changed 233 * 234 * @todo if adding a coefficient would change the type of the special linear constraint, we need to erase it and 235 * create a new linear constraint 236 */ 237 SCIP_EXPORT 238 SCIP_RETCODE SCIPaddCoefPseudoboolean( 239 SCIP*const scip, /**< SCIP data structure */ 240 SCIP_CONS*const cons, /**< pseudoboolean constraint */ 241 SCIP_VAR* const var, /**< variable of constraint entry */ 242 SCIP_Real const val /**< coefficient of constraint entry */ 243 ); 244 245 /** adds nonlinear term to pseudo boolean constraint (if it is not zero) 246 * 247 * @note you can only add a coefficient if the special type of linear constraint won't changed 248 * 249 * @todo if adding a coefficient would change the type of the special linear constraint, we need to erase it and 250 * create a new linear constraint 251 */ 252 SCIP_EXPORT 253 SCIP_RETCODE SCIPaddTermPseudoboolean( 254 SCIP*const scip, /**< SCIP data structure */ 255 SCIP_CONS*const cons, /**< pseudoboolean constraint */ 256 SCIP_VAR**const vars, /**< variables of the nonlinear term */ 257 int const nvars, /**< number of variables of the nonlinear term */ 258 SCIP_Real const val /**< coefficient of constraint entry */ 259 ); 260 261 /** gets indicator variable of pseudoboolean constraint, or NULL if there is no */ 262 SCIP_EXPORT 263 SCIP_VAR* SCIPgetIndVarPseudoboolean( 264 SCIP*const scip, /**< SCIP data structure */ 265 SCIP_CONS*const cons /**< pseudoboolean constraint */ 266 ); 267 268 /** gets linear constraint of pseudoboolean constraint */ 269 SCIP_EXPORT 270 SCIP_CONS* SCIPgetLinearConsPseudoboolean( 271 SCIP*const scip, /**< SCIP data structure */ 272 SCIP_CONS*const cons /**< pseudoboolean constraint */ 273 ); 274 275 /** gets type of linear constraint of pseudoboolean constraint */ 276 SCIP_EXPORT 277 SCIP_LINEARCONSTYPE SCIPgetLinearConsTypePseudoboolean( 278 SCIP*const scip, /**< SCIP data structure */ 279 SCIP_CONS*const cons /**< pseudoboolean constraint */ 280 ); 281 282 /** gets number of linear variables without artificial terms variables of pseudoboolean constraint */ 283 SCIP_EXPORT 284 int SCIPgetNLinVarsWithoutAndPseudoboolean( 285 SCIP*const scip, /**< SCIP data structure */ 286 SCIP_CONS*const cons /**< pseudoboolean constraint */ 287 ); 288 289 /** gets linear constraint of pseudoboolean constraint */ 290 SCIP_EXPORT 291 SCIP_RETCODE SCIPgetLinDatasWithoutAndPseudoboolean( 292 SCIP*const scip, /**< SCIP data structure */ 293 SCIP_CONS*const cons, /**< pseudoboolean constraint */ 294 SCIP_VAR**const linvars, /**< array to store and-constraints */ 295 SCIP_Real*const lincoefs, /**< array to store and-coefficients */ 296 int*const nlinvars /**< pointer to store the required array size for and-constraints, have to 297 * be initialized with size of given array */ 298 ); 299 300 /** gets and-constraints of pseudoboolean constraint */ 301 SCIP_EXPORT 302 SCIP_RETCODE SCIPgetAndDatasPseudoboolean( 303 SCIP*const scip, /**< SCIP data structure */ 304 SCIP_CONS*const cons, /**< pseudoboolean constraint */ 305 SCIP_CONS**const andconss, /**< array to store and-constraints */ 306 SCIP_Real*const andcoefs, /**< array to store and-coefficients */ 307 int*const nandconss /**< pointer to store the required array size for and-constraints, have to 308 * be initialized with size of given array */ 309 ); 310 311 /** gets number of and constraints of pseudoboolean constraint */ 312 SCIP_EXPORT 313 int SCIPgetNAndsPseudoboolean( 314 SCIP*const scip, /**< SCIP data structure */ 315 SCIP_CONS*const cons /**< pseudoboolean constraint */ 316 ); 317 318 /** changes left hand side of pseudoboolean constraint 319 * 320 * @note you can only change the left hand side if the special type of linear constraint won't changed 321 * 322 * @todo if changing the left hand side would change the type of the special linear constraint, we need to erase it 323 * and create a new linear constraint 324 */ 325 SCIP_EXPORT 326 SCIP_RETCODE SCIPchgLhsPseudoboolean( 327 SCIP*const scip, /**< SCIP data structure */ 328 SCIP_CONS*const cons, /**< pseudoboolean constraint */ 329 SCIP_Real const lhs /**< new left hand side */ 330 ); 331 332 /** changes right hand side of pseudoboolean constraint 333 * 334 * @note you can only change the right hand side if the special type of linear constraint won't changed 335 * 336 * @todo if changing the right hand side would change the type of the special linear constraint, we need to erase it 337 * and create a new linear constraint 338 */ 339 SCIP_EXPORT 340 SCIP_RETCODE SCIPchgRhsPseudoboolean( 341 SCIP*const scip, /**< SCIP data structure */ 342 SCIP_CONS*const cons, /**< pseudoboolean constraint */ 343 SCIP_Real const rhs /**< new right hand side */ 344 ); 345 346 /** get left hand side of pseudoboolean constraint */ 347 SCIP_EXPORT 348 SCIP_Real SCIPgetLhsPseudoboolean( 349 SCIP*const scip, /**< SCIP data structure */ 350 SCIP_CONS*const cons /**< pseudoboolean constraint */ 351 ); 352 353 /** get right hand side of pseudoboolean constraint */ 354 SCIP_EXPORT 355 SCIP_Real SCIPgetRhsPseudoboolean( 356 SCIP*const scip, /**< SCIP data structure */ 357 SCIP_CONS*const cons /**< pseudoboolean constraint */ 358 ); 359 360 /** @} */ 361 362 /** @} */ 363 364 #ifdef __cplusplus 365 } 366 #endif 367 368 #endif 369