problemreductions/rules/
minimumtardinesssequencing_ilp.rs

1//! Reduction from MinimumTardinessSequencing to `ILP<bool>`.
2//!
3//! Position-assignment ILP: binary x_{j,p} placing task j in position p,
4//! with binary tardy indicator u_j. Precedence constraints and a
5//! length-aware tardy indicator with big-M linearization.
6
7use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
8use crate::models::misc::MinimumTardinessSequencing;
9use crate::reduction;
10use crate::rules::ilp_helpers::one_hot_decode;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12use crate::types::One;
13
14/// Result of reducing MinimumTardinessSequencing<One> to `ILP<bool>`.
15#[derive(Debug, Clone)]
16pub struct ReductionMTSToILP {
17    target: ILP<bool>,
18    num_tasks: usize,
19}
20
21impl ReductionResult for ReductionMTSToILP {
22    type Source = MinimumTardinessSequencing<One>;
23    type Target = ILP<bool>;
24
25    fn target_problem(&self) -> &ILP<bool> {
26        &self.target
27    }
28
29    fn extract_solution(
30        &self,
31        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
32    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
33        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
34
35        Ok({
36            let n = self.num_tasks;
37
38            one_hot_decode(target_solution, n, n, 0)?
39        })
40    }
41}
42
43/// Result of reducing MinimumTardinessSequencing<i64> to `ILP<bool>`.
44#[derive(Debug, Clone)]
45pub struct ReductionMTSWeightedToILP {
46    target: ILP<bool>,
47    num_tasks: usize,
48}
49
50impl ReductionResult for ReductionMTSWeightedToILP {
51    type Source = MinimumTardinessSequencing<i64>;
52    type Target = ILP<bool>;
53
54    fn target_problem(&self) -> &ILP<bool> {
55        &self.target
56    }
57
58    fn extract_solution(
59        &self,
60        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
61    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
62        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
63
64        Ok({
65            let n = self.num_tasks;
66
67            one_hot_decode(target_solution, n, n, 0)?
68        })
69    }
70}
71
72/// Build task assignment + position filling + precedence constraints (shared).
73fn build_common_constraints(
74    n: usize,
75    positions: &[i64],
76    precedences: &[(usize, usize)],
77    x_var: impl Fn(usize, usize) -> usize,
78) -> Vec<LinearConstraint> {
79    let mut constraints = Vec::new();
80
81    // 1. Each task assigned to exactly one position
82    for j in 0..n {
83        let terms: Vec<(usize, i64)> = (0..n).map(|p| (x_var(j, p), 1)).collect();
84        constraints.push(LinearConstraint::eq(terms, 1));
85    }
86
87    // 2. Each position has exactly one task
88    for p in 0..n {
89        let terms: Vec<(usize, i64)> = (0..n).map(|j| (x_var(j, p), 1)).collect();
90        constraints.push(LinearConstraint::eq(terms, 1));
91    }
92
93    // 3. Precedence constraints
94    for &(i, j) in precedences {
95        let mut terms: Vec<(usize, i64)> = Vec::new();
96        for (p, &position) in positions.iter().enumerate() {
97            terms.push((x_var(j, p), position));
98            terms.push((x_var(i, p), -position));
99        }
100        constraints.push(LinearConstraint::ge(terms, 1));
101    }
102
103    constraints
104}
105
106// Unit-length variant
107#[reduction(
108    transform = exact {
109        num_vars = "num_tasks * num_tasks + num_tasks",
110        num_constraints = "2 * num_tasks + num_precedences + num_tasks",
111    },
112    unavailable = {
113        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
114    }
115)]
116impl ReduceTo<ILP<bool>> for MinimumTardinessSequencing<One> {
117    type Result = ReductionMTSToILP;
118
119    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
120        let n = self.num_tasks();
121        let num_x_vars = n * n;
122        let num_vars = num_x_vars + n;
123        let positions = (0..n)
124            .map(|position| Self::exact_i64(position, "representing a task position in ILP rows"))
125            .collect::<Result<Vec<_>, _>>()?;
126        let big_m = Self::exact_i64(n, "representing the number of tasks in ILP rows")?;
127
128        let x_var = |j: usize, p: usize| -> usize { j * n + p };
129        let u_var = |j: usize| -> usize { num_x_vars + j };
130
131        let mut constraints = build_common_constraints(n, &positions, self.precedences(), x_var);
132
133        // Tardy indicator (unit length: completion = p+1)
134        for j in 0..n {
135            let mut terms: Vec<(usize, i64)> =
136                (0..n).map(|p| (x_var(j, p), positions[p] + 1)).collect();
137            terms.push((u_var(j), -big_m));
138            let deadline = self.deadlines()[j];
139            constraints.push(LinearConstraint::le(terms, deadline));
140        }
141
142        let objective: Vec<(usize, i64)> = (0..n).map(|j| (u_var(j), 1)).collect();
143
144        Ok(ReductionMTSToILP {
145            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
146                .map_err(Self::target_construction)?,
147            num_tasks: n,
148        })
149    }
150}
151
152// Arbitrary-length variant
153#[reduction(
154    transform = exact {
155        num_vars = "num_tasks * num_tasks + num_tasks",
156        num_constraints = "2 * num_tasks + num_precedences + num_tasks * num_tasks",
157    },
158    unavailable = {
159        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
160    }
161)]
162impl ReduceTo<ILP<bool>> for MinimumTardinessSequencing<i64> {
163    type Result = ReductionMTSWeightedToILP;
164
165    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
166        let n = self.num_tasks();
167        let num_x_vars = n * n;
168        let num_vars = num_x_vars + n;
169        let total_length = self.lengths().iter().try_fold(0_i64, |total, &length| {
170            total.checked_add(length).ok_or_else(|| {
171                crate::rules::ReductionError::integer_overflow::<
172                    MinimumTardinessSequencing<i64>,
173                    ILP<bool>,
174                >("summing task lengths")
175            })
176        })?;
177        let big_m = total_length;
178        let positions = (0..n)
179            .map(|position| Self::exact_i64(position, "representing a task position in ILP rows"))
180            .collect::<Result<Vec<_>, _>>()?;
181
182        let x_var = |j: usize, p: usize| -> usize { j * n + p };
183        let u_var = |j: usize| -> usize { num_x_vars + j };
184
185        let mut constraints = build_common_constraints(n, &positions, self.precedences(), x_var);
186
187        // Tardy indicator for arbitrary lengths.
188        let lengths = self.lengths();
189        for j in 0..n {
190            for p in 0..n {
191                let mut terms: Vec<(usize, i64)> = Vec::new();
192                terms.push((x_var(j, p), big_m));
193                for pp in 0..p {
194                    for (jj, &len) in lengths.iter().enumerate() {
195                        terms.push((x_var(jj, pp), len));
196                    }
197                }
198                terms.push((u_var(j), -big_m));
199                let rhs = self.deadlines()[j]
200                    .checked_sub(lengths[j])
201                    .and_then(|value| value.checked_add(total_length))
202                    .ok_or_else(|| {
203                        crate::rules::ReductionError::integer_overflow::<
204                            MinimumTardinessSequencing<i64>,
205                            ILP<bool>,
206                        >("computing a tardiness constraint bound")
207                    })?;
208                constraints.push(LinearConstraint::le(terms, rhs));
209            }
210        }
211
212        let objective: Vec<(usize, i64)> = (0..n).map(|j| (u_var(j), 1)).collect();
213
214        Ok(ReductionMTSWeightedToILP {
215            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
216                .map_err(Self::target_construction)?,
217            num_tasks: n,
218        })
219    }
220}
221
222#[cfg(feature = "example-db")]
223pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
224    vec![
225        crate::example_db::specs::RuleExampleSpec {
226            id: "minimumtardinesssequencing_to_ilp",
227            build: || {
228                let source = MinimumTardinessSequencing::<One>::new(3, vec![2, 3, 1], vec![(0, 2)]);
229                crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
230            },
231        },
232        crate::example_db::specs::RuleExampleSpec {
233            id: "minimumtardinesssequencing_weighted_to_ilp",
234            build: || {
235                let source = MinimumTardinessSequencing::<i64>::with_lengths(
236                    vec![2, 1, 3],
237                    vec![3, 4, 5],
238                    vec![(0, 2)],
239                );
240                crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
241            },
242        },
243    ]
244}
245
246#[cfg(test)]
247#[path = "../unit_tests/rules/minimumtardinesssequencing_ilp.rs"]
248mod tests;
problemreductions/rules/minimumtardinesssequencing_ilp.rs

problemreductions/rules/
minimumtardinesssequencing_ilp.rs
