problemreductions/rules/
sequencingtominimizetardytaskweight_ilp.rs

1//! Reduction from SequencingToMinimizeTardyTaskWeight 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. A big-M constraint forces u_j = 1
5//! whenever the completion time at position p exceeds the deadline d_j.
6
7use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
8use crate::models::misc::SequencingToMinimizeTardyTaskWeight;
9use crate::reduction;
10use crate::rules::ilp_helpers::one_hot_decode;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12
13/// Result of reducing SequencingToMinimizeTardyTaskWeight to ILP<bool>.
14#[derive(Debug, Clone)]
15pub struct ReductionSTMTTWToILP {
16    target: ILP<bool>,
17    num_tasks: usize,
18}
19
20impl ReductionResult for ReductionSTMTTWToILP {
21    type Source = SequencingToMinimizeTardyTaskWeight;
22    type Target = ILP<bool>;
23
24    fn target_problem(&self) -> &ILP<bool> {
25        &self.target
26    }
27
28    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
29        let n = self.num_tasks;
30        // Decode the n*n block of x_{j,p} variables into a schedule permutation.
31        // The source uses direct permutation encoding (config = schedule directly),
32        // so return the schedule as-is (it is already a permutation of 0..n).
33        one_hot_decode(target_solution, n, n, 0)
34    }
35}
36
37#[reduction(overhead = {
38    num_vars = "num_tasks * num_tasks + num_tasks",
39    num_constraints = "2 * num_tasks + num_tasks * num_tasks",
40})]
41impl ReduceTo<ILP<bool>> for SequencingToMinimizeTardyTaskWeight {
42    type Result = ReductionSTMTTWToILP;
43
44    fn reduce_to(&self) -> Self::Result {
45        let n = self.num_tasks();
46        let num_x_vars = n * n;
47        let num_vars = num_x_vars + n;
48        let total_length: u64 = self.lengths().iter().copied().sum();
49        let big_m = total_length as f64;
50
51        let x_var = |j: usize, p: usize| -> usize { j * n + p };
52        let u_var = |j: usize| -> usize { num_x_vars + j };
53
54        let mut constraints = Vec::new();
55
56        // 1. Each task assigned to exactly one position
57        for j in 0..n {
58            let terms: Vec<(usize, f64)> = (0..n).map(|p| (x_var(j, p), 1.0)).collect();
59            constraints.push(LinearConstraint::eq(terms, 1.0));
60        }
61
62        // 2. Each position has exactly one task
63        for p in 0..n {
64            let terms: Vec<(usize, f64)> = (0..n).map(|j| (x_var(j, p), 1.0)).collect();
65            constraints.push(LinearConstraint::eq(terms, 1.0));
66        }
67
68        // 3. Tardy indicator: for each (j, p), if x_{j,p}=1 then
69        //    completion_time_at_p >= l_j + sum_{p' < p} sum_{j'} l_{j'} * x_{j',p'}
70        //    If completion > d_j then u_j must be 1.
71        //    Linearized as: big_m * x_{j,p} + sum_{p'<p} sum_{j'} l_{j'} * x_{j',p'} - big_m * u_j <= d_j - l_j + big_m
72        let lengths = self.lengths();
73        for j in 0..n {
74            for p in 0..n {
75                let mut terms: Vec<(usize, f64)> = Vec::new();
76                terms.push((x_var(j, p), big_m));
77                for pp in 0..p {
78                    for (jj, &len) in lengths.iter().enumerate() {
79                        terms.push((x_var(jj, pp), len as f64));
80                    }
81                }
82                terms.push((u_var(j), -big_m));
83                let rhs = self.deadlines()[j] as f64 - lengths[j] as f64 + big_m;
84                constraints.push(LinearConstraint::le(terms, rhs));
85            }
86        }
87
88        // Objective: minimize sum w_j * u_j
89        let weights = self.weights();
90        let objective: Vec<(usize, f64)> = (0..n).map(|j| (u_var(j), weights[j] as f64)).collect();
91
92        ReductionSTMTTWToILP {
93            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize),
94            num_tasks: n,
95        }
96    }
97}
98
99#[cfg(feature = "example-db")]
100pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
101    vec![crate::example_db::specs::RuleExampleSpec {
102        id: "sequencingtominimizetardytaskweight_to_ilp",
103        build: || {
104            let source = SequencingToMinimizeTardyTaskWeight::new(
105                vec![3, 2, 4, 1, 2],
106                vec![5, 3, 7, 2, 4],
107                vec![6, 4, 10, 2, 8],
108            );
109            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
110        },
111    }]
112}
113
114#[cfg(test)]
115#[path = "../unit_tests/rules/sequencingtominimizetardytaskweight_ilp.rs"]
116mod tests;
problemreductions/rules/sequencingtominimizetardytaskweight_ilp.rs

problemreductions/rules/
sequencingtominimizetardytaskweight_ilp.rs
