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-2017 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 email to scip@zib.de. */
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/scip.h"
32 
33 #ifdef __cplusplus
34 extern "C" {
35 #endif
36 
37 
38 /** creates the constraint handler for cumulative constraints and includes it in SCIP
39  *
40  * @ingroup ConshdlrIncludes
41  * */
42 extern
44  SCIP* scip /**< SCIP data structure */
45  );
46 
47 /**@addtogroup CONSHDLRS
48  *
49  * @{
50  *
51  * @name Cumulative Constraints
52  *
53  * Given:
54  * - 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
55  * their demands \f$d_j\f$.
56  * - an integer resource capacity \f$C\f$
57  *
58  * 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.
59  *
60  * @par
61  * Separation:
62  * - can be done using binary start time model, see Pritskers, Watters and Wolfe
63  * - or by just separating relatively weak cuts on the start time variables
64  *
65  * @par
66  * Propagation:
67  * - time tabling, Klein & Scholl (1999)
68  * - Edge-finding from Petr Vilim, adjusted and simplified for dynamic repropagation
69  * (2009)
70  * - energetic reasoning, see Baptiste, Le Pape, Nuijten (2001)
71  *
72  * @{
73  */
74 
75 /** creates and captures a cumulative constraint */
76 extern
78  SCIP* scip, /**< SCIP data structure */
79  SCIP_CONS** cons, /**< pointer to hold the created constraint */
80  const char* name, /**< name of constraint */
81  int nvars, /**< number of variables (jobs) */
82  SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
83  int* durations, /**< array containing corresponding durations */
84  int* demands, /**< array containing corresponding demands */
85  int capacity, /**< available cumulative capacity */
86  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
87  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
88  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
89  * Usually set to TRUE. */
90  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
91  * TRUE for model constraints, FALSE for additional, redundant constraints. */
92  SCIP_Bool check, /**< should the constraint be checked for feasibility?
93  * TRUE for model constraints, FALSE for additional, redundant constraints. */
94  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
95  * Usually set to TRUE. */
96  SCIP_Bool local, /**< is constraint only valid locally?
97  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
98  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
99  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
100  * adds coefficients to this constraint. */
101  SCIP_Bool dynamic, /**< is constraint subject to aging?
102  * Usually set to FALSE. Set to TRUE for own cuts which
103  * are seperated as constraints. */
104  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
105  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
106  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
107  * if it may be moved to a more global node?
108  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
109  );
110 
111 /** creates and captures an absolute power constraint
112  * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
113  * method SCIPcreateConsCumulative(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
114  *
115  * @see SCIPcreateConsCumulative() for information about the basic constraint flag configuration
116  *
117  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
118  */
119 extern
121  SCIP* scip, /**< SCIP data structure */
122  SCIP_CONS** cons, /**< pointer to hold the created constraint */
123  const char* name, /**< name of constraint */
124  int nvars, /**< number of variables (jobs) */
125  SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
126  int* durations, /**< array containing corresponding durations */
127  int* demands, /**< array containing corresponding demands */
128  int capacity /**< available cumulative capacity */
129  );
130 
131 /** set the left bound of effective horizon */
132 extern
134  SCIP* scip, /**< SCIP data structure */
135  SCIP_CONS* cons, /**< constraint data */
136  int hmin /**< left bound of time axis to be considered */
137  );
138 
139 /** returns the left bound of the effective horizon */
140 extern
142  SCIP* scip, /**< SCIP data structure */
143  SCIP_CONS* cons /**< constraint */
144  );
145 
146 
147 /** set the right bound of the effective horizon */
148 extern
150  SCIP* scip, /**< SCIP data structure */
151  SCIP_CONS* cons, /**< constraint data */
152  int hmax /**< right bound of time axis to be considered */
153  );
154 
155 /** returns the right bound of effective horizon */
156 extern
158  SCIP* scip, /**< SCIP data structure */
159  SCIP_CONS* cons /**< constraint */
160  );
161 
162 /** returns the start time variables of the cumulative constraint */
163 extern
165  SCIP* scip, /**< SCIP data structure */
166  SCIP_CONS* cons /**< constraint data */
167  );
168 
169 /** returns the number of start time variables of the cumulative constraint */
170 extern
172  SCIP* scip, /**< SCIP data structure */
173  SCIP_CONS* cons /**< constraint data */
174  );
175 
176 /** returns the capacity of the cumulative constraint */
177 extern
179  SCIP* scip, /**< SCIP data structure */
180  SCIP_CONS* cons /**< constraint data */
181  );
182 
183 /** returns the durations of the cumulative constraint */
184 extern
186  SCIP* scip, /**< SCIP data structure */
187  SCIP_CONS* cons /**< constraint data */
188  );
189 
190 /** returns the demands of the cumulative constraint */
191 extern
193  SCIP* scip, /**< SCIP data structure */
194  SCIP_CONS* cons /**< constraint data */
195  );
196 
197 /** check for the given starting time variables with their demands and durations if the cumulative conditions for the
198  * given solution is satisfied
199  */
200 extern
202  SCIP* scip, /**< SCIP data structure */
203  SCIP_SOL* sol, /**< primal solution, or NULL for current LP/pseudo solution */
204  int nvars, /**< number of variables (jobs) */
205  SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
206  int* durations, /**< array containing corresponding durations */
207  int* demands, /**< array containing corresponding demands */
208  int capacity, /**< available cumulative capacity */
209  int hmin, /**< left bound of time axis to be considered */
210  int hmax, /**< right bound of time axis to be considered */
211  SCIP_Bool* violated, /**< pointer to store if the cumulative condition is violated */
212  SCIP_CONS* cons, /**< constraint which is checked */
213  SCIP_Bool printreason /**< should the reason for the violation be printed? */
214  );
215 
216 /** normalize cumulative condition */
217 extern
219  SCIP* scip, /**< SCIP data structure */
220  int nvars, /**< number of start time variables (activities) */
221  SCIP_VAR** vars, /**< array of start time variables */
222  int* durations, /**< array of durations */
223  int* demands, /**< array of demands */
224  int* capacity, /**< pointer to store the changed cumulative capacity */
225  int* nchgcoefs, /**< pointer to count total number of changed coefficients */
226  int* nchgsides /**< pointer to count number of side changes */
227  );
228 
229 /** searches for a time point within the cumulative condition were the cumulative condition can be split */
230 extern
232  SCIP* scip, /**< SCIP data structure */
233  int nvars, /**< number of variables (jobs) */
234  SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
235  int* durations, /**< array containing corresponding durations */
236  int* demands, /**< array containing corresponding demands */
237  int capacity, /**< available cumulative capacity */
238  int* hmin, /**< pointer to store the left bound of the effective horizon */
239  int* hmax, /**< pointer to store the right bound of the effective horizon */
240  int* split /**< point were the cumulative condition can be split */
241  );
242 
243 /** presolve cumulative condition w.r.t. effective horizon by detecting irrelevant variables */
244 extern
246  SCIP* scip, /**< SCIP data structure */
247  int nvars, /**< number of start time variables (activities) */
248  SCIP_VAR** vars, /**< array of start time variables */
249  int* durations, /**< array of durations */
250  int hmin, /**< left bound of time axis to be considered */
251  int hmax, /**< right bound of time axis to be considered (not including hmax) */
252  SCIP_Bool* downlocks, /**< array storing if the variable has a down lock, or NULL */
253  SCIP_Bool* uplocks, /**< array storing if the variable has an up lock, or NULL */
254  SCIP_CONS* cons, /**< constraint which gets propagated, or NULL */
255  SCIP_Bool* delvars, /**< array storing the variable which can be deleted from the constraint */
256  int* nfixedvars, /**< pointer to store the number of fixed variables */
257  int* nchgsides, /**< pointer to store the number of changed sides */
258  SCIP_Bool* cutoff /**< buffer to store whether a cutoff is detected */
259  );
260 
261 /** propagate the given cumulative condition */
262 extern
264  SCIP* scip, /**< SCIP data structure */
265  SCIP_PRESOLTIMING presoltiming, /**< current presolving timing */
266  int nvars, /**< number of variables (jobs) */
267  SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
268  int* durations, /**< array containing corresponding durations */
269  int* demands, /**< array containing corresponding demands */
270  int capacity, /**< available cumulative capacity */
271  int hmin, /**< left bound of time axis to be considered */
272  int hmax, /**< right bound of time axis to be considered */
273  SCIP_CONS* cons, /**< constraint which gets propagated */
274  int* nchgbds, /**< pointer to store the number of variable bound changes */
275  SCIP_Bool* initialized, /**< was conflict analysis initialized */
276  SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
277  SCIP_Bool* cutoff /**< pointer to store if the cumulative condition is violated */
278  );
279 
280 /** resolve propagation w.r.t. the cumulative condition */
281 extern
283  SCIP* scip, /**< SCIP data structure */
284  int nvars, /**< number of start time variables (activities) */
285  SCIP_VAR** vars, /**< array of start time variables */
286  int* durations, /**< array of durations */
287  int* demands, /**< array of demands */
288  int capacity, /**< cumulative capacity */
289  int hmin, /**< left bound of time axis to be considered (including hmin) */
290  int hmax, /**< right bound of time axis to be considered (not including hmax) */
291  SCIP_VAR* infervar, /**< the conflict variable whose bound change has to be resolved */
292  int inferinfo, /**< the user information */
293  SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
294  SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
295  SCIP_Real relaxedbd, /**< the relaxed bound which is sufficient to be explained */
296  SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
297  SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
298  );
299 
300 /** this method visualizes the cumulative structure in GML format */
301 extern
303  SCIP* scip, /**< SCIP data structure */
304  SCIP_CONS* cons /**< cumulative constraint */
305  );
306 
307 /** solves given cumulative condition as independent sub problem
308  *
309  * @note The time and memory limit should be respected.
310  *
311  * @note If the problem was solved to the earliest start times (ests) and latest start times (lsts) array contain the
312  * solution values; If the problem was not solved these two arrays contain the global bounds at the time the sub
313  * solver was interrupted.
314  *
315  * input:
316  * - njobs : number of jobs (activities)
317  * - objvals : array of objective coefficients for each job (linear objective function), or NULL if none
318  * - durations : array of durations
319  * - demands : array of demands
320  * - capacity : cumulative capacity
321  * - hmin : left bound of time axis to be considered (including hmin)
322  * - hmax : right bound of time axis to be considered (not including hmax)
323  * - timelimit : time limit for solving in seconds
324  * - memorylimit : memory limit for solving in mega bytes (MB)
325  * - maxnodes : maximum number of branch-and-bound nodes to solve the single cumulative constraint (-1: no limit)
326  *
327  * input/output:
328  * - ests : array of earliest start times for each job
329  * - lsts : array of latest start times for each job
330  *
331  * output:
332  * - solved : pointer to store if the problem is solved (to optimality)
333  * - infeasible : pointer to store if the problem is infeasible
334  * - unbounded : pointer to store if the problem is unbounded
335  * - error : pointer to store if an error occurred
336  *
337  */
338 #define SCIP_DECL_SOLVECUMULATIVE(x) SCIP_RETCODE x (int njobs, SCIP_Real* ests, SCIP_Real* lsts, SCIP_Real* objvals, \
339  int* durations, int* demands, int capacity, int hmin, int hmax, \
340  SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Longint maxnodes, \
341  SCIP_Bool* solved, SCIP_Bool* infeasible, SCIP_Bool* unbounded, SCIP_Bool* error)
342 
343 /** sets method to solve an individual cumulative condition */
344 extern
346  SCIP* scip, /**< SCIP data structure */
347  SCIP_DECL_SOLVECUMULATIVE((*solveCumulative)) /**< method to use an individual cumulative condition */
348  );
349 
350 /** solves given cumulative condition as independent sub problem
351  *
352  * @note If the problem was solved to the earliest start times (ests) and latest start times (lsts) array contain the
353  * solution values; If the problem was not solved these two arrays contain the global bounds at the time the sub
354  * solver was interrupted.
355  */
356 extern
358  SCIP* scip, /**< SCIP data structure */
359  int njobs, /**< number of jobs (activities) */
360  SCIP_Real* ests, /**< array with the earlier start time for each job */
361  SCIP_Real* lsts, /**< array with the latest start time for each job */
362  SCIP_Real* objvals, /**< array of objective coefficients for each job (linear objective function), or NULL if none */
363  int* durations, /**< array of durations */
364  int* demands, /**< array of demands */
365  int capacity, /**< cumulative capacity */
366  int hmin, /**< left bound of time axis to be considered (including hmin) */
367  int hmax, /**< right bound of time axis to be considered (not including hmax) */
368  SCIP_Real timelimit, /**< time limit for solving in seconds */
369  SCIP_Real memorylimit, /**< memory limit for solving in mega bytes (MB) */
370  SCIP_Longint maxnodes, /**< maximum number of branch-and-bound nodes to solve the single cumulative constraint (-1: no limit) */
371  SCIP_Bool* solved, /**< pointer to store if the problem is solved (to optimality) */
372  SCIP_Bool* infeasible, /**< pointer to store if the problem is infeasible */
373  SCIP_Bool* unbounded, /**< pointer to store if the problem is unbounded */
374  SCIP_Bool* error /**< pointer to store if an error occurred */
375  );
376 
377 /** creates the worst case resource profile, that is, all jobs are inserted with the earliest start and latest
378  * completion time
379  */
380 extern
382  SCIP* scip, /**< SCIP data structure */
383  SCIP_PROFILE* profile, /**< resource profile */
384  int nvars, /**< number of variables (jobs) */
385  SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
386  int* durations, /**< array containing corresponding durations */
387  int* demands /**< array containing corresponding demands */
388  );
389 
390 /** computes w.r.t. the given worst case resource profile the first time point where the given capacity can be violated */
391 extern
392 int SCIPcomputeHmin(
393  SCIP* scip, /**< SCIP data structure */
394  SCIP_PROFILE* profile, /**< worst case resource profile */
395  int capacity /**< capacity to check */
396  );
397 
398 /** computes w.r.t. the given worst case resource profile the first time point where the given capacity is satisfied for sure */
399 extern
400 int SCIPcomputeHmax(
401  SCIP* scip, /**< SCIP data structure */
402  SCIP_PROFILE* profile, /**< worst case profile */
403  int capacity /**< capacity to check */
404  );
405 
406 
407 /* @} */
408 
409 /* @} */
410 
411 #ifdef __cplusplus
412 }
413 #endif
414 
415 #endif
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
#define SCIP_DECL_SOLVECUMULATIVE(x)
int SCIPgetNVarsCumulative(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPincludeConshdlrCumulative(SCIP *scip)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPsetSolveCumulative(SCIP *scip, SCIP_DECL_SOLVECUMULATIVE((*solveCumulative)))
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_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)
int SCIPgetHmaxCumulative(SCIP *scip, SCIP_CONS *cons)
int SCIPcomputeHmin(SCIP *scip, SCIP_PROFILE *profile, int capacity)
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)
int SCIPcomputeHmax(SCIP *scip, SCIP_PROFILE *profile, int capacity)
unsigned int SCIP_PRESOLTIMING
Definition: type_timing.h:52
SCIP_RETCODE SCIPcreateWorstCaseProfile(SCIP *scip, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands)
int * SCIPgetDurationsCumulative(SCIP *scip, SCIP_CONS *cons)
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_RETCODE SCIPsetHminCumulative(SCIP *scip, SCIP_CONS *cons, int hmin)
SCIP_RETCODE SCIPsplitCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int *hmin, int *hmax, int *split)
#define SCIP_Bool
Definition: def.h:61
SCIP_RETCODE SCIPnormalizeCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int *capacity, int *nchgcoefs, int *nchgsides)
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)
int * SCIPgetDemandsCumulative(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPsetHmaxCumulative(SCIP *scip, SCIP_CONS *cons, int hmax)
int SCIPgetHminCumulative(SCIP *scip, SCIP_CONS *cons)
#define SCIP_Real
Definition: def.h:145
#define SCIP_Longint
Definition: def.h:130
int SCIPgetCapacityCumulative(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsBasicCumulative(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity)
SCIP_VAR ** SCIPgetVarsCumulative(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPvisualizeConsCumulative(SCIP *scip, SCIP_CONS *cons)
SCIP callable library.
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)