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_cumulative.h 26 * @ingroup CONSHDLRS 27 * @brief constraint handler for cumulative constraints 28 * @author Timo Berthold 29 * @author Stefan Heinz 30 * @author Jens Schulz 31 * 32 */ 33 34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 35 36 #ifndef __SCIP_CONS_CUMULATIVE_H__ 37 #define __SCIP_CONS_CUMULATIVE_H__ 38 39 40 #include "scip/def.h" 41 #include "scip/type_cons.h" 42 #include "scip/type_lp.h" 43 #include "scip/type_misc.h" 44 #include "scip/type_result.h" 45 #include "scip/type_retcode.h" 46 #include "scip/type_scip.h" 47 #include "scip/type_sol.h" 48 #include "scip/type_timing.h" 49 #include "scip/type_var.h" 50 51 #ifdef __cplusplus 52 extern "C" { 53 #endif 54 55 56 /** creates the constraint handler for cumulative constraints and includes it in SCIP 57 * 58 * @ingroup ConshdlrIncludes 59 */ 60 SCIP_EXPORT 61 SCIP_RETCODE SCIPincludeConshdlrCumulative( 62 SCIP* scip /**< SCIP data structure */ 63 ); 64 65 /**@addtogroup CONSHDLRS 66 * 67 * @{ 68 * 69 * @name Cumulative Constraints 70 * 71 * Given: 72 * - a set of jobs, represented by their integer start time variables \f$S_j\f$, their array of processing times \f$p_j\f$ and of 73 * their demands \f$d_j\f$. 74 * - an integer resource capacity \f$C\f$ 75 * 76 * The cumulative constraint ensures that for each point in time \f$t\f$ \f$\sum_{j: S_j \leq t < S_j + p_j} d_j \leq C\f$ holds. 77 * 78 * @par 79 * Separation: 80 * - can be done using binary start time model, see Pritskers, Watters and Wolfe 81 * - or by just separating relatively weak cuts on the start time variables 82 * 83 * @par 84 * Propagation: 85 * - time tabling, Klein & Scholl (1999) 86 * - Edge-finding from Petr Vilim, adjusted and simplified for dynamic repropagation 87 * (2009) 88 * - energetic reasoning, see Baptiste, Le Pape, Nuijten (2001) 89 * 90 * @{ 91 */ 92 93 /** creates and captures a cumulative constraint */ 94 SCIP_EXPORT 95 SCIP_RETCODE SCIPcreateConsCumulative( 96 SCIP* scip, /**< SCIP data structure */ 97 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 98 const char* name, /**< name of constraint */ 99 int nvars, /**< number of variables (jobs) */ 100 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */ 101 int* durations, /**< array containing corresponding durations */ 102 int* demands, /**< array containing corresponding demands */ 103 int capacity, /**< available cumulative capacity */ 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 seperated 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 an absolute power constraint 130 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the 131 * method SCIPcreateConsCumulative(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h 132 * 133 * @see SCIPcreateConsCumulative() for information about the basic 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 SCIPcreateConsBasicCumulative( 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 (jobs) */ 143 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */ 144 int* durations, /**< array containing corresponding durations */ 145 int* demands, /**< array containing corresponding demands */ 146 int capacity /**< available cumulative capacity */ 147 ); 148 149 /** set the left bound of effective horizon */ 150 SCIP_EXPORT 151 SCIP_RETCODE SCIPsetHminCumulative( 152 SCIP* scip, /**< SCIP data structure */ 153 SCIP_CONS* cons, /**< constraint data */ 154 int hmin /**< left bound of time axis to be considered */ 155 ); 156 157 /** returns the left bound of the effective horizon */ 158 SCIP_EXPORT 159 int SCIPgetHminCumulative( 160 SCIP* scip, /**< SCIP data structure */ 161 SCIP_CONS* cons /**< constraint */ 162 ); 163 164 165 /** set the right bound of the effective horizon */ 166 SCIP_EXPORT 167 SCIP_RETCODE SCIPsetHmaxCumulative( 168 SCIP* scip, /**< SCIP data structure */ 169 SCIP_CONS* cons, /**< constraint data */ 170 int hmax /**< right bound of time axis to be considered */ 171 ); 172 173 /** returns the right bound of effective horizon */ 174 SCIP_EXPORT 175 int SCIPgetHmaxCumulative( 176 SCIP* scip, /**< SCIP data structure */ 177 SCIP_CONS* cons /**< constraint */ 178 ); 179 180 /** returns the start time variables of the cumulative constraint */ 181 SCIP_EXPORT 182 SCIP_VAR** SCIPgetVarsCumulative( 183 SCIP* scip, /**< SCIP data structure */ 184 SCIP_CONS* cons /**< constraint data */ 185 ); 186 187 /** returns the number of start time variables of the cumulative constraint */ 188 SCIP_EXPORT 189 int SCIPgetNVarsCumulative( 190 SCIP* scip, /**< SCIP data structure */ 191 SCIP_CONS* cons /**< constraint data */ 192 ); 193 194 /** returns the capacity of the cumulative constraint */ 195 SCIP_EXPORT 196 int SCIPgetCapacityCumulative( 197 SCIP* scip, /**< SCIP data structure */ 198 SCIP_CONS* cons /**< constraint data */ 199 ); 200 201 /** returns the durations of the cumulative constraint */ 202 SCIP_EXPORT 203 int* SCIPgetDurationsCumulative( 204 SCIP* scip, /**< SCIP data structure */ 205 SCIP_CONS* cons /**< constraint data */ 206 ); 207 208 /** returns the demands of the cumulative constraint */ 209 SCIP_EXPORT 210 int* SCIPgetDemandsCumulative( 211 SCIP* scip, /**< SCIP data structure */ 212 SCIP_CONS* cons /**< constraint data */ 213 ); 214 215 /** check for the given starting time variables with their demands and durations if the cumulative conditions for the 216 * given solution is satisfied 217 */ 218 SCIP_EXPORT 219 SCIP_RETCODE SCIPcheckCumulativeCondition( 220 SCIP* scip, /**< SCIP data structure */ 221 SCIP_SOL* sol, /**< primal solution, or NULL for current LP/pseudo solution */ 222 int nvars, /**< number of variables (jobs) */ 223 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */ 224 int* durations, /**< array containing corresponding durations */ 225 int* demands, /**< array containing corresponding demands */ 226 int capacity, /**< available cumulative capacity */ 227 int hmin, /**< left bound of time axis to be considered */ 228 int hmax, /**< right bound of time axis to be considered */ 229 SCIP_Bool* violated, /**< pointer to store if the cumulative condition is violated */ 230 SCIP_CONS* cons, /**< constraint which is checked */ 231 SCIP_Bool printreason /**< should the reason for the violation be printed? */ 232 ); 233 234 /** normalize cumulative condition */ 235 SCIP_EXPORT 236 SCIP_RETCODE SCIPnormalizeCumulativeCondition( 237 SCIP* scip, /**< SCIP data structure */ 238 int nvars, /**< number of start time variables (activities) */ 239 SCIP_VAR** vars, /**< array of start time variables */ 240 int* durations, /**< array of durations */ 241 int* demands, /**< array of demands */ 242 int* capacity, /**< pointer to store the changed cumulative capacity */ 243 int* nchgcoefs, /**< pointer to count total number of changed coefficients */ 244 int* nchgsides /**< pointer to count number of side changes */ 245 ); 246 247 /** searches for a time point within the cumulative condition were the cumulative condition can be split */ 248 SCIP_EXPORT 249 SCIP_RETCODE SCIPsplitCumulativeCondition( 250 SCIP* scip, /**< SCIP data structure */ 251 int nvars, /**< number of variables (jobs) */ 252 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */ 253 int* durations, /**< array containing corresponding durations */ 254 int* demands, /**< array containing corresponding demands */ 255 int capacity, /**< available cumulative capacity */ 256 int* hmin, /**< pointer to store the left bound of the effective horizon */ 257 int* hmax, /**< pointer to store the right bound of the effective horizon */ 258 int* split /**< point were the cumulative condition can be split */ 259 ); 260 261 /** presolve cumulative condition w.r.t. effective horizon by detecting irrelevant variables */ 262 SCIP_EXPORT 263 SCIP_RETCODE SCIPpresolveCumulativeCondition( 264 SCIP* scip, /**< SCIP data structure */ 265 int nvars, /**< number of start time variables (activities) */ 266 SCIP_VAR** vars, /**< array of start time variables */ 267 int* durations, /**< array of durations */ 268 int hmin, /**< left bound of time axis to be considered */ 269 int hmax, /**< right bound of time axis to be considered (not including hmax) */ 270 SCIP_Bool* downlocks, /**< array storing if the variable has a down lock, or NULL */ 271 SCIP_Bool* uplocks, /**< array storing if the variable has an up lock, or NULL */ 272 SCIP_CONS* cons, /**< constraint which gets propagated, or NULL */ 273 SCIP_Bool* delvars, /**< array storing the variable which can be deleted from the constraint */ 274 int* nfixedvars, /**< pointer to store the number of fixed variables */ 275 int* nchgsides, /**< pointer to store the number of changed sides */ 276 SCIP_Bool* cutoff /**< buffer to store whether a cutoff is detected */ 277 ); 278 279 /** propagate the given cumulative condition */ 280 SCIP_EXPORT 281 SCIP_RETCODE SCIPpropCumulativeCondition( 282 SCIP* scip, /**< SCIP data structure */ 283 SCIP_PRESOLTIMING presoltiming, /**< current presolving timing */ 284 int nvars, /**< number of variables (jobs) */ 285 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */ 286 int* durations, /**< array containing corresponding durations */ 287 int* demands, /**< array containing corresponding demands */ 288 int capacity, /**< available cumulative capacity */ 289 int hmin, /**< left bound of time axis to be considered */ 290 int hmax, /**< right bound of time axis to be considered */ 291 SCIP_CONS* cons, /**< constraint which gets propagated */ 292 int* nchgbds, /**< pointer to store the number of variable bound changes */ 293 SCIP_Bool* initialized, /**< was conflict analysis initialized */ 294 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 295 SCIP_Bool* cutoff /**< pointer to store if the cumulative condition is violated */ 296 ); 297 298 /** resolve propagation w.r.t. the cumulative condition */ 299 SCIP_EXPORT 300 SCIP_RETCODE SCIPrespropCumulativeCondition( 301 SCIP* scip, /**< SCIP data structure */ 302 int nvars, /**< number of start time variables (activities) */ 303 SCIP_VAR** vars, /**< array of start time variables */ 304 int* durations, /**< array of durations */ 305 int* demands, /**< array of demands */ 306 int capacity, /**< cumulative capacity */ 307 int hmin, /**< left bound of time axis to be considered (including hmin) */ 308 int hmax, /**< right bound of time axis to be considered (not including hmax) */ 309 SCIP_VAR* infervar, /**< the conflict variable whose bound change has to be resolved */ 310 int inferinfo, /**< the user information */ 311 SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */ 312 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */ 313 SCIP_Real relaxedbd, /**< the relaxed bound which is sufficient to be explained */ 314 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 315 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */ 316 ); 317 318 /** this method visualizes the cumulative structure in GML format */ 319 SCIP_EXPORT 320 SCIP_RETCODE SCIPvisualizeConsCumulative( 321 SCIP* scip, /**< SCIP data structure */ 322 SCIP_CONS* cons /**< cumulative constraint */ 323 ); 324 325 /** solves given cumulative condition as independent sub problem 326 * 327 * @note The time and memory limit should be respected. 328 * 329 * @note If the problem was solved to the earliest start times (ests) and latest start times (lsts) array contain the 330 * solution values; If the problem was not solved these two arrays contain the global bounds at the time the sub 331 * solver was interrupted. 332 * 333 * input: 334 * - njobs : number of jobs (activities) 335 * - objvals : array of objective coefficients for each job (linear objective function), or NULL if none 336 * - durations : array of durations 337 * - demands : array of demands 338 * - capacity : cumulative capacity 339 * - hmin : left bound of time axis to be considered (including hmin) 340 * - hmax : right bound of time axis to be considered (not including hmax) 341 * - timelimit : time limit for solving in seconds 342 * - memorylimit : memory limit for solving in mega bytes (MB) 343 * - maxnodes : maximum number of branch-and-bound nodes to solve the single cumulative constraint (-1: no limit) 344 * 345 * input/output: 346 * - ests : array of earliest start times for each job 347 * - lsts : array of latest start times for each job 348 * 349 * output: 350 * - solved : pointer to store if the problem is solved (to optimality) 351 * - infeasible : pointer to store if the problem is infeasible 352 * - unbounded : pointer to store if the problem is unbounded 353 * - error : pointer to store if an error occurred 354 * 355 */ 356 #define SCIP_DECL_SOLVECUMULATIVE(x) SCIP_RETCODE x (int njobs, SCIP_Real* ests, SCIP_Real* lsts, SCIP_Real* objvals, \ 357 int* durations, int* demands, int capacity, int hmin, int hmax, \ 358 SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Longint maxnodes, \ 359 SCIP_Bool* solved, SCIP_Bool* infeasible, SCIP_Bool* unbounded, SCIP_Bool* error) 360 361 /** sets method to solve an individual cumulative condition */ 362 SCIP_EXPORT 363 SCIP_RETCODE SCIPsetSolveCumulative( 364 SCIP* scip, /**< SCIP data structure */ 365 SCIP_DECL_SOLVECUMULATIVE((*solveCumulative)) /**< method to use an individual cumulative condition */ 366 ); 367 368 /** solves given cumulative condition as independent sub problem 369 * 370 * @note If the problem was solved to the earliest start times (ests) and latest start times (lsts) array contain the 371 * solution values; If the problem was not solved these two arrays contain the global bounds at the time the sub 372 * solver was interrupted. 373 */ 374 SCIP_EXPORT 375 SCIP_RETCODE SCIPsolveCumulative( 376 SCIP* scip, /**< SCIP data structure */ 377 int njobs, /**< number of jobs (activities) */ 378 SCIP_Real* ests, /**< array with the earlier start time for each job */ 379 SCIP_Real* lsts, /**< array with the latest start time for each job */ 380 SCIP_Real* objvals, /**< array of objective coefficients for each job (linear objective function), or NULL if none */ 381 int* durations, /**< array of durations */ 382 int* demands, /**< array of demands */ 383 int capacity, /**< cumulative capacity */ 384 int hmin, /**< left bound of time axis to be considered (including hmin) */ 385 int hmax, /**< right bound of time axis to be considered (not including hmax) */ 386 SCIP_Real timelimit, /**< time limit for solving in seconds */ 387 SCIP_Real memorylimit, /**< memory limit for solving in mega bytes (MB) */ 388 SCIP_Longint maxnodes, /**< maximum number of branch-and-bound nodes to solve the single cumulative constraint (-1: no limit) */ 389 SCIP_Bool* solved, /**< pointer to store if the problem is solved (to optimality) */ 390 SCIP_Bool* infeasible, /**< pointer to store if the problem is infeasible */ 391 SCIP_Bool* unbounded, /**< pointer to store if the problem is unbounded */ 392 SCIP_Bool* error /**< pointer to store if an error occurred */ 393 ); 394 395 /** creates the worst case resource profile, that is, all jobs are inserted with the earliest start and latest 396 * completion time 397 */ 398 SCIP_EXPORT 399 SCIP_RETCODE SCIPcreateWorstCaseProfile( 400 SCIP* scip, /**< SCIP data structure */ 401 SCIP_PROFILE* profile, /**< resource profile */ 402 int nvars, /**< number of variables (jobs) */ 403 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */ 404 int* durations, /**< array containing corresponding durations */ 405 int* demands /**< array containing corresponding demands */ 406 ); 407 408 /** computes w.r.t. the given worst case resource profile the first time point where the given capacity can be violated */ 409 SCIP_EXPORT 410 int SCIPcomputeHmin( 411 SCIP* scip, /**< SCIP data structure */ 412 SCIP_PROFILE* profile, /**< worst case resource profile */ 413 int capacity /**< capacity to check */ 414 ); 415 416 /** computes w.r.t. the given worst case resource profile the first time point where the given capacity is satisfied for sure */ 417 SCIP_EXPORT 418 int SCIPcomputeHmax( 419 SCIP* scip, /**< SCIP data structure */ 420 SCIP_PROFILE* profile, /**< worst case profile */ 421 int capacity /**< capacity to check */ 422 ); 423 424 425 /** @} */ 426 427 /** @} */ 428 429 #ifdef __cplusplus 430 } 431 #endif 432 433 #endif 434