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