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