pumpkin_constraints/constraints/
cumulative.rs

1use std::fmt::Debug;
2
3use pumpkin_core::Solver;
4use pumpkin_core::asserts::pumpkin_assert_simple;
5use pumpkin_core::constraints::Constraint;
6use pumpkin_core::proof::ConstraintTag;
7use pumpkin_core::variables::IntegerVariable;
8use pumpkin_core::variables::Literal;
9use pumpkin_propagators::cumulative::ArgTask;
10use pumpkin_propagators::cumulative::options::CumulativeOptions;
11use pumpkin_propagators::cumulative::options::CumulativePropagationMethod;
12use pumpkin_propagators::cumulative::time_table::TimeTableOverIntervalIncrementalPropagator;
13use pumpkin_propagators::cumulative::time_table::TimeTableOverIntervalPropagator;
14use pumpkin_propagators::cumulative::time_table::TimeTablePerPointIncrementalPropagator;
15use pumpkin_propagators::cumulative::time_table::TimeTablePerPointPropagator;
16
17/// Creates the [Cumulative](https://sofdem.github.io/gccat/gccat/Ccumulative.html) [`Constraint`].
18///
19/// This constraint ensures that at no point in time, the cumulative resource usage of the tasks
20/// exceeds `bound`.
21///
22/// The implementation uses a form of time-table reasoning (for an example of this type of
23/// reasoning, see \[1], note that it does **not** implement the specific algorithm in the paper
24/// but that the reasoning used is the same).
25///
26/// The length of `start_times`, `durations` and `resource_requirements` should be the same; if
27/// this is not the case then this method will panic.
28///
29/// It is possible to specify certain options for the cumulative (such as whether to allow holes in
30/// the domain or the type of explanation) using [`cumulative_with_options`].
31///
32/// # Example
33/// ```rust
34/// // We construct three tasks for a resource with capacity 2:
35/// // - Task 0: Start times: [0, 5], Processing time: 4, Resource usage: 1
36/// // - Task 1: Start times: [0, 5], Processing time: 2, Resource usage: 1
37/// // - Task 2: Start times: [0, 5], Processing time: 4, Resource usage: 2
38/// // We can infer that Task 0 and Task 1 execute at the same time
39/// // while Task 2 will start after them
40/// # use pumpkin_core::termination::Indefinite;
41/// # use pumpkin_core::Solver;
42/// # use pumpkin_core::results::SatisfactionResult;
43/// # use pumpkin_core::constraints;
44/// # use pumpkin_core::constraints::Constraint;
45/// # use pumpkin_core::results::ProblemSolution;
46/// let solver = Solver::default();
47///
48/// let mut solver = Solver::default();
49///
50/// let start_0 = solver.new_bounded_integer(0, 4);
51/// let start_1 = solver.new_bounded_integer(0, 4);
52/// let start_2 = solver.new_bounded_integer(0, 5);
53///
54/// let constraint_tag = solver.new_constraint_tag();
55///
56/// let start_times = [start_0, start_1, start_2];
57/// let durations = [5, 2, 5];
58/// let resource_requirements = [1, 1, 2];
59/// let resource_capacity = 2;
60///
61/// solver
62///     .add_constraint(pumpkin_constraints::cumulative(
63///         start_times.clone(),
64///         durations.clone(),
65///         resource_requirements.clone(),
66///         resource_capacity,
67///         constraint_tag,
68///     ))
69///     .post();
70///
71/// // ...
72/// ```
73///
74/// # Bibliography
75/// \[1\] S. Gay, R. Hartert, and P. Schaus, ‘Simple and scalable time-table filtering for the
76/// cumulative constraint’, in Principles and Practice of Constraint Programming: 21st
77/// International Conference, CP 2015, Cork, Ireland, August 31--September 4, 2015, Proceedings
78/// 21, 2015, pp. 149–157.
79pub fn cumulative<StartTimes, Durations, ResourceRequirements>(
80    start_times: StartTimes,
81    durations: Durations,
82    resource_requirements: ResourceRequirements,
83    resource_capacity: i32,
84    constraint_tag: ConstraintTag,
85) -> impl Constraint
86where
87    StartTimes: IntoIterator,
88    StartTimes::Item: IntegerVariable + Debug + 'static,
89    StartTimes::IntoIter: ExactSizeIterator,
90    Durations: IntoIterator<Item = i32>,
91    Durations::IntoIter: ExactSizeIterator,
92    ResourceRequirements: IntoIterator<Item = i32>,
93    ResourceRequirements::IntoIter: ExactSizeIterator,
94{
95    cumulative_with_options(
96        start_times,
97        durations,
98        resource_requirements,
99        resource_capacity,
100        CumulativeOptions::default(),
101        constraint_tag,
102    )
103}
104
105/// Creates the [Cumulative](https://sofdem.github.io/gccat/gccat/Ccumulative.html) [`Constraint`]
106/// with the provided [`CumulativeOptions`].
107///
108/// See the documentation of [`cumulative`] for more information about the constraint.
109pub fn cumulative_with_options<StartTimes, Durations, ResourceRequirements>(
110    start_times: StartTimes,
111    durations: Durations,
112    resource_requirements: ResourceRequirements,
113    resource_capacity: i32,
114    options: CumulativeOptions,
115    constraint_tag: ConstraintTag,
116) -> impl Constraint
117where
118    StartTimes: IntoIterator,
119    StartTimes::Item: IntegerVariable + Debug + 'static,
120    StartTimes::IntoIter: ExactSizeIterator,
121    Durations: IntoIterator<Item = i32>,
122    Durations::IntoIter: ExactSizeIterator,
123    ResourceRequirements: IntoIterator<Item = i32>,
124    ResourceRequirements::IntoIter: ExactSizeIterator,
125{
126    let start_times = start_times.into_iter();
127    let durations = durations.into_iter();
128    let resource_requirements = resource_requirements.into_iter();
129
130    pumpkin_assert_simple!(
131        start_times.len() == durations.len() && durations.len() == resource_requirements.len(),
132        "The number of start variables, durations and resource requirements should be the same!"
133    );
134
135    CumulativeConstraint::new(
136        &start_times
137            .zip(durations)
138            .zip(resource_requirements)
139            .map(|((start_time, duration), resource_requirement)| ArgTask {
140                start_time,
141                processing_time: duration,
142                resource_usage: resource_requirement,
143            })
144            .collect::<Vec<_>>(),
145        resource_capacity,
146        options,
147        constraint_tag,
148    )
149}
150
151struct CumulativeConstraint<Var> {
152    tasks: Vec<ArgTask<Var>>,
153    resource_capacity: i32,
154    options: CumulativeOptions,
155    constraint_tag: ConstraintTag,
156}
157
158impl<Var: IntegerVariable + 'static> CumulativeConstraint<Var> {
159    fn new(
160        tasks: &[ArgTask<Var>],
161        resource_capacity: i32,
162        options: CumulativeOptions,
163        constraint_tag: ConstraintTag,
164    ) -> Self {
165        Self {
166            tasks: tasks.into(),
167            resource_capacity,
168
169            options,
170            constraint_tag,
171        }
172    }
173}
174
175impl<Var: IntegerVariable + 'static + Debug> Constraint for CumulativeConstraint<Var> {
176    fn post(self, solver: &mut Solver) {
177        match self.options.propagation_method {
178            CumulativePropagationMethod::TimeTablePerPoint => TimeTablePerPointPropagator::new(
179                &self.tasks,
180                self.resource_capacity,
181                self.options.propagator_options,
182                self.constraint_tag,
183            )
184            .post(solver),
185
186            CumulativePropagationMethod::TimeTablePerPointIncremental => {
187                TimeTablePerPointIncrementalPropagator::<Var, false>::new(
188                    &self.tasks,
189                    self.resource_capacity,
190                    self.options.propagator_options,
191                    self.constraint_tag,
192                )
193                .post(solver)
194            }
195            CumulativePropagationMethod::TimeTablePerPointIncrementalSynchronised => {
196                TimeTablePerPointIncrementalPropagator::<Var, true>::new(
197                    &self.tasks,
198                    self.resource_capacity,
199                    self.options.propagator_options,
200                    self.constraint_tag,
201                )
202                .post(solver)
203            }
204            CumulativePropagationMethod::TimeTableOverInterval => {
205                TimeTableOverIntervalPropagator::new(
206                    &self.tasks,
207                    self.resource_capacity,
208                    self.options.propagator_options,
209                    self.constraint_tag,
210                )
211                .post(solver)
212            }
213            CumulativePropagationMethod::TimeTableOverIntervalIncremental => {
214                TimeTableOverIntervalIncrementalPropagator::<Var, false>::new(
215                    &self.tasks,
216                    self.resource_capacity,
217                    self.options.propagator_options,
218                    self.constraint_tag,
219                )
220                .post(solver)
221            }
222            CumulativePropagationMethod::TimeTableOverIntervalIncrementalSynchronised => {
223                TimeTableOverIntervalIncrementalPropagator::<Var, true>::new(
224                    &self.tasks,
225                    self.resource_capacity,
226                    self.options.propagator_options,
227                    self.constraint_tag,
228                )
229                .post(solver)
230            }
231        }
232    }
233
234    fn implied_by(self, solver: &mut Solver, reification_literal: Literal) {
235        match self.options.propagation_method {
236            CumulativePropagationMethod::TimeTablePerPoint => TimeTablePerPointPropagator::new(
237                &self.tasks,
238                self.resource_capacity,
239                self.options.propagator_options,
240                self.constraint_tag,
241            )
242            .implied_by(solver, reification_literal),
243            CumulativePropagationMethod::TimeTablePerPointIncremental => {
244                TimeTablePerPointIncrementalPropagator::<Var, false>::new(
245                    &self.tasks,
246                    self.resource_capacity,
247                    self.options.propagator_options,
248                    self.constraint_tag,
249                )
250                .implied_by(solver, reification_literal)
251            }
252            CumulativePropagationMethod::TimeTablePerPointIncrementalSynchronised => {
253                TimeTablePerPointIncrementalPropagator::<Var, true>::new(
254                    &self.tasks,
255                    self.resource_capacity,
256                    self.options.propagator_options,
257                    self.constraint_tag,
258                )
259                .implied_by(solver, reification_literal)
260            }
261            CumulativePropagationMethod::TimeTableOverInterval => {
262                TimeTableOverIntervalPropagator::new(
263                    &self.tasks,
264                    self.resource_capacity,
265                    self.options.propagator_options,
266                    self.constraint_tag,
267                )
268                .implied_by(solver, reification_literal)
269            }
270            CumulativePropagationMethod::TimeTableOverIntervalIncremental => {
271                TimeTableOverIntervalIncrementalPropagator::<Var, false>::new(
272                    &self.tasks,
273                    self.resource_capacity,
274                    self.options.propagator_options,
275                    self.constraint_tag,
276                )
277                .implied_by(solver, reification_literal)
278            }
279            CumulativePropagationMethod::TimeTableOverIntervalIncrementalSynchronised => {
280                TimeTableOverIntervalIncrementalPropagator::<Var, true>::new(
281                    &self.tasks,
282                    self.resource_capacity,
283                    self.options.propagator_options,
284                    self.constraint_tag,
285                )
286                .implied_by(solver, reification_literal)
287            }
288        }
289    }
290}
pumpkin_constraints/constraints/cumulative.rs

pumpkin_constraints/constraints/
cumulative.rs
