pumpkin_constraints/constraints/
cumulative.rs

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

pumpkin_constraints/constraints/
cumulative.rs
