Scippy

SCIP

Solving Constraint Integer Programs

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