problemreductions/rules/
sequencingtominimizeweightedtardiness_ilp.rs

1//! Reduction from SequencingToMinimizeWeightedTardiness to ILP<i32>.
2//!
3//! Pairwise order variables y_{i,j}, integer completion times C_j,
4//! and nonnegative tardiness variables T_j. Big-M disjunctive constraints
5//! force a single-machine order; the weighted tardiness sum is bounded by K.
6
7use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
8use crate::models::misc::SequencingToMinimizeWeightedTardiness;
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11
12/// Result of reducing SequencingToMinimizeWeightedTardiness to ILP<i32>.
13///
14/// Variable layout:
15/// - `y_{i,j}` for i < j: pairwise order bits (n*(n-1)/2 vars)
16/// - `C_j` for j in 0..n: completion times (n vars)
17/// - `T_j` for j in 0..n: tardiness (n vars)
18///
19/// Total: n*(n-1)/2 + 2*n variables.
20#[derive(Debug, Clone)]
21pub struct ReductionSTMWTToILP {
22    target: ILP<i32>,
23    num_tasks: usize,
24    num_order_vars: usize,
25}
26
27impl ReductionSTMWTToILP {
28    fn encode_schedule_as_lehmer(schedule: &[usize]) -> Vec<usize> {
29        let mut available: Vec<usize> = (0..schedule.len()).collect();
30        let mut config = Vec::with_capacity(schedule.len());
31        for &task in schedule {
32            let digit = available
33                .iter()
34                .position(|&c| c == task)
35                .expect("schedule must be a permutation");
36            config.push(digit);
37            available.remove(digit);
38        }
39        config
40    }
41}
42
43impl ReductionResult for ReductionSTMWTToILP {
44    type Source = SequencingToMinimizeWeightedTardiness;
45    type Target = ILP<i32>;
46
47    fn target_problem(&self) -> &ILP<i32> {
48        &self.target
49    }
50
51    /// Extract: sort jobs by completion time C_j, convert to Lehmer code.
52    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
53        let n = self.num_tasks;
54        let c_offset = self.num_order_vars;
55        let mut jobs: Vec<usize> = (0..n).collect();
56        jobs.sort_by_key(|&j| (target_solution.get(c_offset + j).copied().unwrap_or(0), j));
57        Self::encode_schedule_as_lehmer(&jobs)
58    }
59}
60
61#[reduction(overhead = {
62    num_vars = "num_tasks * (num_tasks - 1) / 2 + 2 * num_tasks",
63    num_constraints = "num_tasks * (num_tasks - 1) / 2 + num_tasks + num_tasks * (num_tasks - 1) + 2 * num_tasks + 1",
64})]
65impl ReduceTo<ILP<i32>> for SequencingToMinimizeWeightedTardiness {
66    type Result = ReductionSTMWTToILP;
67
68    fn reduce_to(&self) -> Self::Result {
69        let n = self.num_tasks();
70        let num_order_vars = n * n.saturating_sub(1) / 2;
71        let num_vars = num_order_vars + 2 * n;
72
73        let order_var = |i: usize, j: usize| -> usize {
74            debug_assert!(i < j);
75            i * (2 * n - i - 1) / 2 + (j - i - 1)
76        };
77        let c_var = |j: usize| -> usize { num_order_vars + j };
78        let t_var = |j: usize| -> usize { num_order_vars + n + j };
79
80        let lengths = self.lengths();
81        let deadlines = self.deadlines();
82        let weights = self.weights();
83        let bound = self.bound();
84
85        // M = sum of all lengths (valid schedule-horizon bound)
86        let big_m: f64 = lengths.iter().sum::<u64>() as f64;
87
88        let mut constraints = Vec::new();
89
90        // 1. y_{i,j} in {0,1}: 0 <= y_{i,j} <= 1
91        for i in 0..n {
92            for j in (i + 1)..n {
93                constraints.push(LinearConstraint::le(vec![(order_var(i, j), 1.0)], 1.0));
94                constraints.push(LinearConstraint::ge(vec![(order_var(i, j), 1.0)], 0.0));
95            }
96        }
97
98        // 2. C_j >= l_j for all j
99        for (j, &l_j) in lengths.iter().enumerate() {
100            constraints.push(LinearConstraint::ge(vec![(c_var(j), 1.0)], l_j as f64));
101        }
102
103        // 3. Disjunctive: C_j >= C_i + l_j - M*(1 - y_{i,j}) for i != j
104        for i in 0..n {
105            for (j, &l_j) in lengths.iter().enumerate() {
106                if i == j {
107                    continue;
108                }
109                if i < j {
110                    // y_{i,j} is the stored variable.
111                    // C_j >= C_i + l_j - M*(1 - y_{i,j})
112                    // => C_j - C_i - M*y_{i,j} >= l_j - M
113                    constraints.push(LinearConstraint::ge(
114                        vec![(c_var(j), 1.0), (c_var(i), -1.0), (order_var(i, j), -big_m)],
115                        l_j as f64 - big_m,
116                    ));
117                } else {
118                    // i > j: y_{j,i} is stored, y_{i,j} = 1 - y_{j,i}
119                    // C_j >= C_i + l_j - M*y_{j,i}
120                    // C_j - C_i + M*y_{j,i} >= l_j
121                    constraints.push(LinearConstraint::ge(
122                        vec![(c_var(j), 1.0), (c_var(i), -1.0), (order_var(j, i), big_m)],
123                        l_j as f64,
124                    ));
125                }
126            }
127        }
128
129        // 4. T_j >= C_j - d_j for all j
130        for (j, &d_j) in deadlines.iter().enumerate() {
131            constraints.push(LinearConstraint::ge(
132                vec![(t_var(j), 1.0), (c_var(j), -1.0)],
133                -(d_j as f64),
134            ));
135        }
136
137        // 5. T_j >= 0 for all j
138        for j in 0..n {
139            constraints.push(LinearConstraint::ge(vec![(t_var(j), 1.0)], 0.0));
140        }
141
142        // 6. Σ_j w_j * T_j <= K
143        let terms: Vec<(usize, f64)> = (0..n).map(|j| (t_var(j), weights[j] as f64)).collect();
144        constraints.push(LinearConstraint::le(terms, bound as f64));
145
146        ReductionSTMWTToILP {
147            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize),
148            num_tasks: n,
149            num_order_vars,
150        }
151    }
152}
153
154#[cfg(feature = "example-db")]
155pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
156    vec![crate::example_db::specs::RuleExampleSpec {
157        id: "sequencingtominimizeweightedtardiness_to_ilp",
158        build: || {
159            let source = SequencingToMinimizeWeightedTardiness::new(
160                vec![3, 4, 2],
161                vec![2, 3, 1],
162                vec![5, 8, 4],
163                10,
164            );
165            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
166        },
167    }]
168}
169
170#[cfg(test)]
171#[path = "../unit_tests/rules/sequencingtominimizeweightedtardiness_ilp.rs"]
172mod tests;
problemreductions/rules/sequencingtominimizeweightedtardiness_ilp.rs

problemreductions/rules/
sequencingtominimizeweightedtardiness_ilp.rs
