problemreductions/rules/
sequencingtominimizeweightedtardiness_ilp.rs

1//! Reduction from SequencingToMinimizeWeightedTardiness to `ILP<i64>`.
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<i64>`.
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<i64>,
23    num_tasks: usize,
24    num_order_vars: usize,
25}
26
27impl ReductionResult for ReductionSTMWTToILP {
28    type Source = SequencingToMinimizeWeightedTardiness;
29    type Target = ILP<i64>;
30
31    fn target_problem(&self) -> &ILP<i64> {
32        &self.target
33    }
34
35    /// Extract by sorting jobs by completion time C_j.
36    fn extract_solution(
37        &self,
38        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
39    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
40        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
41
42        Ok({
43            let n = self.num_tasks;
44            let c_offset = self.num_order_vars;
45            let mut jobs: Vec<usize> = (0..n).collect();
46            jobs.sort_by_key(|&j| (target_solution[c_offset + j], j));
47            jobs
48        })
49    }
50}
51
52#[reduction(transform = upper_bound {
53    num_vars = "num_tasks^2 + 2 * num_tasks",
54    num_constraints = "2 * num_tasks^2 + 3 * num_tasks + 1",
55},
56    unavailable = {
57        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
58    }
59)]
60impl ReduceTo<ILP<i64>> for SequencingToMinimizeWeightedTardiness {
61    type Result = ReductionSTMWTToILP;
62
63    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
64        let n = self.num_tasks();
65        let num_order_vars = n * n.saturating_sub(1) / 2;
66        let num_vars = num_order_vars + 2 * n;
67
68        let order_var = |i: usize, j: usize| -> usize {
69            debug_assert!(i < j);
70            i * (2 * n - i - 1) / 2 + (j - i - 1)
71        };
72        let c_var = |j: usize| -> usize { num_order_vars + j };
73        let t_var = |j: usize| -> usize { num_order_vars + n + j };
74
75        let lengths = self.lengths();
76        let deadlines = self.deadlines();
77        let weights = self.weights();
78        let bound = self.bound();
79
80        // M = sum of all lengths (valid schedule-horizon bound)
81        let horizon = lengths
82            .iter()
83            .try_fold(0_i64, |total, &length| total.checked_add(length))
84            .ok_or_else(|| {
85                crate::rules::ReductionError::integer_overflow::<
86                    SequencingToMinimizeWeightedTardiness,
87                    ILP<i64>,
88                >("summing task processing times")
89            })?;
90        let big_m = horizon;
91
92        let mut constraints = Vec::new();
93
94        // 1. y_{i,j} in {0,1}: 0 <= y_{i,j} <= 1
95        for i in 0..n {
96            for j in (i + 1)..n {
97                constraints.push(LinearConstraint::le(vec![(order_var(i, j), 1)], 1));
98                constraints.push(LinearConstraint::ge(vec![(order_var(i, j), 1)], 0));
99            }
100        }
101
102        // 2. C_j >= l_j for all j
103        for (j, &l_j) in lengths.iter().enumerate() {
104            constraints.push(LinearConstraint::ge(vec![(c_var(j), 1)], l_j));
105        }
106
107        // 3. Disjunctive: C_j >= C_i + l_j - M*(1 - y_{i,j}) for i != j
108        for i in 0..n {
109            for (j, &l_j) in lengths.iter().enumerate() {
110                if i == j {
111                    continue;
112                }
113                if i < j {
114                    // y_{i,j} is the stored variable.
115                    // C_j >= C_i + l_j - M*(1 - y_{i,j})
116                    // => C_j - C_i - M*y_{i,j} >= l_j - M
117                    constraints.push(LinearConstraint::ge(
118                        vec![(c_var(j), 1), (c_var(i), -1), (order_var(i, j), -big_m)],
119                        l_j - big_m,
120                    ));
121                } else {
122                    // i > j: y_{j,i} is stored, y_{i,j} = 1 - y_{j,i}
123                    // C_j >= C_i + l_j - M*y_{j,i}
124                    // C_j - C_i + M*y_{j,i} >= l_j
125                    constraints.push(LinearConstraint::ge(
126                        vec![(c_var(j), 1), (c_var(i), -1), (order_var(j, i), big_m)],
127                        l_j,
128                    ));
129                }
130            }
131        }
132
133        // 4. T_j >= C_j - d_j for all j
134        for (j, &d_j) in deadlines.iter().enumerate() {
135            constraints.push(LinearConstraint::ge(
136                vec![(t_var(j), 1), (c_var(j), -1)],
137                -d_j,
138            ));
139        }
140
141        // 5. T_j >= 0 for all j
142        for j in 0..n {
143            constraints.push(LinearConstraint::ge(vec![(t_var(j), 1)], 0));
144        }
145
146        // 6. Σ_j w_j * T_j <= K
147        let terms: Vec<(usize, i64)> = (0..n).map(|j| (t_var(j), weights[j])).collect();
148        constraints.push(LinearConstraint::le(terms, bound));
149
150        Ok(ReductionSTMWTToILP {
151            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
152                .map_err(Self::target_construction)?,
153            num_tasks: n,
154            num_order_vars,
155        })
156    }
157}
158
159#[cfg(feature = "example-db")]
160pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
161    vec![crate::example_db::specs::RuleExampleSpec {
162        id: "sequencingtominimizeweightedtardiness_to_ilp",
163        build: || {
164            let source = SequencingToMinimizeWeightedTardiness::new(
165                vec![3, 4, 2],
166                vec![2, 3, 1],
167                vec![5, 8, 4],
168                10,
169            );
170            crate::example_db::specs::rule_example_via_ilp::<_, i64>(source)
171        },
172    }]
173}
174
175#[cfg(test)]
176#[path = "../unit_tests/rules/sequencingtominimizeweightedtardiness_ilp.rs"]
177mod tests;
problemreductions/rules/sequencingtominimizeweightedtardiness_ilp.rs

problemreductions/rules/
sequencingtominimizeweightedtardiness_ilp.rs
