problemreductions/rules/
sequencingtominimizeweightedtardiness_ilp.rs

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

problemreductions/rules/
sequencingtominimizeweightedtardiness_ilp.rs
