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(transform = {
108    exact {
109        num_vars = "num_tasks * num_tasks + num_tasks",
110        num_constraints = "2 * num_tasks + num_precedences + num_tasks",
111    },
112    upper_bound {
113        max_constraint_magnitude_bits = "num_tasks + 1",
114        num_nonzeros = "(num_tasks * num_tasks + num_tasks) * (2 * num_tasks + num_precedences + num_tasks)",
115    },
116})]
117impl ReduceTo<ILP<bool>> for MinimumTardinessSequencing<One> {
118    type Result = ReductionMTSToILP;
119
120    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
121        let n = self.num_tasks();
122        let num_x_vars = n * n;
123        let num_vars = num_x_vars + n;
124        let positions = (0..n)
125            .map(|position| Self::exact_i64(position, "representing a task position in ILP rows"))
126            .collect::<Result<Vec<_>, _>>()?;
127        let big_m = Self::exact_i64(n, "representing the number of tasks in ILP rows")?;
128
129        let x_var = |j: usize, p: usize| -> usize { j * n + p };
130        let u_var = |j: usize| -> usize { num_x_vars + j };
131
132        let mut constraints = build_common_constraints(n, &positions, self.precedences(), x_var);
133
134        // Tardy indicator (unit length: completion = p+1)
135        for j in 0..n {
136            let mut terms: Vec<(usize, i64)> =
137                (0..n).map(|p| (x_var(j, p), positions[p] + 1)).collect();
138            terms.push((u_var(j), -big_m));
139            // Completion times lie in [1, n]; outside deadlines have the same tardy status.
140            let deadline = self.deadlines()[j].clamp(0, big_m);
141            constraints.push(LinearConstraint::le(terms, deadline));
142        }
143
144        let objective: Vec<(usize, i64)> = (0..n).map(|j| (u_var(j), 1)).collect();
145
146        Ok(ReductionMTSToILP {
147            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
148                .map_err(Self::target_construction)?,
149            num_tasks: n,
150        })
151    }
152}
153
154// Arbitrary-length variant
155#[reduction(transform = {
156    exact {
157        num_vars = "num_tasks * num_tasks + num_tasks",
158        num_constraints = "2 * num_tasks + num_precedences + num_tasks * num_tasks",
159    },
160    upper_bound {
161        max_constraint_magnitude_bits = "max_processing_time_bits + num_tasks + 1",
162        num_nonzeros = "(num_tasks * num_tasks + num_tasks) * (2 * num_tasks + num_precedences + num_tasks * num_tasks)",
163    },
164})]
165impl ReduceTo<ILP<bool>> for MinimumTardinessSequencing<i64> {
166    type Result = ReductionMTSWeightedToILP;
167
168    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
169        let n = self.num_tasks();
170        let num_x_vars = n * n;
171        let num_vars = num_x_vars + n;
172        let total_length = self.lengths().iter().try_fold(0_i64, |total, &length| {
173            total.checked_add(length).ok_or_else(|| {
174                crate::rules::ReductionError::integer_overflow::<
175                    MinimumTardinessSequencing<i64>,
176                    ILP<bool>,
177                >("summing task lengths")
178            })
179        })?;
180        let big_m = total_length;
181        let positions = (0..n)
182            .map(|position| Self::exact_i64(position, "representing a task position in ILP rows"))
183            .collect::<Result<Vec<_>, _>>()?;
184
185        let x_var = |j: usize, p: usize| -> usize { j * n + p };
186        let u_var = |j: usize| -> usize { num_x_vars + j };
187
188        let mut constraints = build_common_constraints(n, &positions, self.precedences(), x_var);
189
190        // Tardy indicator for arbitrary lengths.
191        let lengths = self.lengths();
192        for j in 0..n {
193            // Positive lengths bound all completion times by total_length.
194            let rhs = self.deadlines()[j]
195                .clamp(0, total_length)
196                .checked_sub(lengths[j])
197                .and_then(|value| value.checked_add(total_length))
198                .ok_or_else(|| {
199                    crate::rules::ReductionError::integer_overflow::<
200                        MinimumTardinessSequencing<i64>,
201                        ILP<bool>,
202                    >("computing a tardiness constraint bound")
203                })?;
204            for p in 0..n {
205                let mut terms: Vec<(usize, i64)> = Vec::new();
206                terms.push((x_var(j, p), big_m));
207                for pp in 0..p {
208                    for (jj, &len) in lengths.iter().enumerate() {
209                        terms.push((x_var(jj, pp), len));
210                    }
211                }
212                terms.push((u_var(j), -big_m));
213                constraints.push(LinearConstraint::le(terms, rhs));
214            }
215        }
216
217        let objective: Vec<(usize, i64)> = (0..n).map(|j| (u_var(j), 1)).collect();
218
219        Ok(ReductionMTSWeightedToILP {
220            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
221                .map_err(Self::target_construction)?,
222            num_tasks: n,
223        })
224    }
225}
226
227#[cfg(feature = "example-db")]
228pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
229    vec![
230        crate::example_db::specs::RuleExampleSpec {
231            id: "minimumtardinesssequencing_to_ilp",
232            build: || {
233                let source = MinimumTardinessSequencing::<One>::new(3, vec![2, 3, 1], vec![(0, 2)]);
234                crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
235            },
236        },
237        crate::example_db::specs::RuleExampleSpec {
238            id: "minimumtardinesssequencing_weighted_to_ilp",
239            build: || {
240                let source = MinimumTardinessSequencing::<i64>::with_lengths(
241                    vec![2, 1, 3],
242                    vec![3, 4, 5],
243                    vec![(0, 2)],
244                );
245                crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
246            },
247        },
248    ]
249}
250
251#[cfg(test)]
252#[path = "../unit_tests/rules/minimumtardinesssequencing_ilp.rs"]
253mod tests;
problemreductions/rules/minimumtardinesssequencing_ilp.rs

problemreductions/rules/
minimumtardinesssequencing_ilp.rs
