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, permutation_to_lehmer};
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(&self, target_solution: &[usize]) -> Vec<usize> {
30        let n = self.num_tasks;
31        let schedule = one_hot_decode(target_solution, n, n, 0);
32        permutation_to_lehmer(&schedule)
33    }
34}
35
36/// Result of reducing MinimumTardinessSequencing<i32> to ILP<bool>.
37#[derive(Debug, Clone)]
38pub struct ReductionMTSWeightedToILP {
39    target: ILP<bool>,
40    num_tasks: usize,
41}
42
43impl ReductionResult for ReductionMTSWeightedToILP {
44    type Source = MinimumTardinessSequencing<i32>;
45    type Target = ILP<bool>;
46
47    fn target_problem(&self) -> &ILP<bool> {
48        &self.target
49    }
50
51    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
52        let n = self.num_tasks;
53        let schedule = one_hot_decode(target_solution, n, n, 0);
54        permutation_to_lehmer(&schedule)
55    }
56}
57
58/// Build task assignment + position filling + precedence constraints (shared).
59fn build_common_constraints(
60    n: usize,
61    precedences: &[(usize, usize)],
62    x_var: impl Fn(usize, usize) -> usize,
63) -> Vec<LinearConstraint> {
64    let mut constraints = Vec::new();
65
66    // 1. Each task assigned to exactly one position
67    for j in 0..n {
68        let terms: Vec<(usize, f64)> = (0..n).map(|p| (x_var(j, p), 1.0)).collect();
69        constraints.push(LinearConstraint::eq(terms, 1.0));
70    }
71
72    // 2. Each position has exactly one task
73    for p in 0..n {
74        let terms: Vec<(usize, f64)> = (0..n).map(|j| (x_var(j, p), 1.0)).collect();
75        constraints.push(LinearConstraint::eq(terms, 1.0));
76    }
77
78    // 3. Precedence constraints
79    for &(i, j) in precedences {
80        let mut terms: Vec<(usize, f64)> = Vec::new();
81        for p in 0..n {
82            terms.push((x_var(j, p), p as f64));
83            terms.push((x_var(i, p), -(p as f64)));
84        }
85        constraints.push(LinearConstraint::ge(terms, 1.0));
86    }
87
88    constraints
89}
90
91// Unit-length variant
92#[reduction(overhead = {
93    num_vars = "num_tasks * num_tasks + num_tasks",
94    num_constraints = "2 * num_tasks + num_precedences + num_tasks",
95})]
96impl ReduceTo<ILP<bool>> for MinimumTardinessSequencing<One> {
97    type Result = ReductionMTSToILP;
98
99    fn reduce_to(&self) -> Self::Result {
100        let n = self.num_tasks();
101        let num_x_vars = n * n;
102        let num_vars = num_x_vars + n;
103        let big_m = n as f64;
104
105        let x_var = |j: usize, p: usize| -> usize { j * n + p };
106        let u_var = |j: usize| -> usize { num_x_vars + j };
107
108        let mut constraints = build_common_constraints(n, self.precedences(), x_var);
109
110        // Tardy indicator (unit length: completion = p+1)
111        for j in 0..n {
112            let mut terms: Vec<(usize, f64)> =
113                (0..n).map(|p| (x_var(j, p), (p + 1) as f64)).collect();
114            terms.push((u_var(j), -big_m));
115            constraints.push(LinearConstraint::le(terms, self.deadlines()[j] as f64));
116        }
117
118        let objective: Vec<(usize, f64)> = (0..n).map(|j| (u_var(j), 1.0)).collect();
119
120        ReductionMTSToILP {
121            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize),
122            num_tasks: n,
123        }
124    }
125}
126
127// Arbitrary-length variant
128#[reduction(overhead = {
129    num_vars = "num_tasks * num_tasks + num_tasks",
130    num_constraints = "2 * num_tasks + num_precedences + num_tasks * num_tasks",
131})]
132impl ReduceTo<ILP<bool>> for MinimumTardinessSequencing<i32> {
133    type Result = ReductionMTSWeightedToILP;
134
135    fn reduce_to(&self) -> Self::Result {
136        let n = self.num_tasks();
137        let num_x_vars = n * n;
138        let num_vars = num_x_vars + n;
139        let total_length: i32 = self.lengths().iter().copied().sum();
140        let big_m = total_length as f64;
141
142        let x_var = |j: usize, p: usize| -> usize { j * n + p };
143        let u_var = |j: usize| -> usize { num_x_vars + j };
144
145        let mut constraints = build_common_constraints(n, self.precedences(), x_var);
146
147        // Tardy indicator for arbitrary lengths.
148        let lengths = self.lengths();
149        for j in 0..n {
150            for p in 0..n {
151                let mut terms: Vec<(usize, f64)> = Vec::new();
152                terms.push((x_var(j, p), big_m));
153                for pp in 0..p {
154                    for (jj, &len) in lengths.iter().enumerate() {
155                        terms.push((x_var(jj, pp), len as f64));
156                    }
157                }
158                terms.push((u_var(j), -big_m));
159                let rhs = self.deadlines()[j] as f64 - lengths[j] as f64 + big_m;
160                constraints.push(LinearConstraint::le(terms, rhs));
161            }
162        }
163
164        let objective: Vec<(usize, f64)> = (0..n).map(|j| (u_var(j), 1.0)).collect();
165
166        ReductionMTSWeightedToILP {
167            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize),
168            num_tasks: n,
169        }
170    }
171}
172
173#[cfg(feature = "example-db")]
174pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
175    vec![
176        crate::example_db::specs::RuleExampleSpec {
177            id: "minimumtardinesssequencing_to_ilp",
178            build: || {
179                let source = MinimumTardinessSequencing::<One>::new(3, vec![2, 3, 1], vec![(0, 2)]);
180                crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
181            },
182        },
183        crate::example_db::specs::RuleExampleSpec {
184            id: "minimumtardinesssequencing_weighted_to_ilp",
185            build: || {
186                let source = MinimumTardinessSequencing::<i32>::with_lengths(
187                    vec![2, 1, 3],
188                    vec![3, 4, 5],
189                    vec![(0, 2)],
190                );
191                crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
192            },
193        },
194    ]
195}
196
197#[cfg(test)]
198#[path = "../unit_tests/rules/minimumtardinesssequencing_ilp.rs"]
199mod tests;
problemreductions/rules/minimumtardinesssequencing_ilp.rs

problemreductions/rules/
minimumtardinesssequencing_ilp.rs
