problemreductions/rules/
sequencingtominimizemaximumcumulativecost_ilp.rs

1//! Reduction from SequencingToMinimizeMaximumCumulativeCost to ILP<i32>.
2//!
3//! Position-assignment ILP: binary x_{j,p} placing task j in position p.
4//! Permutation constraints, precedence constraints, and prefix cumulative-cost
5//! bounds at every position.
6
7use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
8use crate::models::misc::SequencingToMinimizeMaximumCumulativeCost;
9use crate::reduction;
10use crate::rules::ilp_helpers::{one_hot_decode, permutation_to_lehmer};
11use crate::rules::traits::{ReduceTo, ReductionResult};
12
13/// Result of reducing SequencingToMinimizeMaximumCumulativeCost to ILP<i32>.
14///
15/// Variable layout:
16/// - x_{j,p} for j in 0..n, p in 0..n: index `j*n + p`
17///
18/// Total: n^2 variables.
19#[derive(Debug, Clone)]
20pub struct ReductionSTMMCCToILP {
21    target: ILP<i32>,
22    num_tasks: usize,
23}
24
25impl ReductionResult for ReductionSTMMCCToILP {
26    type Source = SequencingToMinimizeMaximumCumulativeCost;
27    type Target = ILP<i32>;
28
29    fn target_problem(&self) -> &ILP<i32> {
30        &self.target
31    }
32
33    /// Extract: decode position assignment → permutation → Lehmer code.
34    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
35        let n = self.num_tasks;
36        let schedule = one_hot_decode(target_solution, n, n, 0);
37        permutation_to_lehmer(&schedule)
38    }
39}
40
41#[reduction(overhead = {
42    num_vars = "num_tasks * num_tasks + 1",
43    num_constraints = "2 * num_tasks + num_precedences + num_tasks + num_tasks * num_tasks",
44})]
45impl ReduceTo<ILP<i32>> for SequencingToMinimizeMaximumCumulativeCost {
46    type Result = ReductionSTMMCCToILP;
47
48    fn reduce_to(&self) -> Self::Result {
49        let n = self.num_tasks();
50        // n^2 position variables + 1 minimax variable z
51        let z_var = n * n;
52        let num_vars = n * n + 1;
53
54        let x_var = |j: usize, p: usize| -> usize { j * n + p };
55
56        let mut constraints = Vec::new();
57
58        // 1. Each task assigned to exactly one position: Σ_p x_{j,p} = 1 for all j
59        for j in 0..n {
60            let terms: Vec<(usize, f64)> = (0..n).map(|p| (x_var(j, p), 1.0)).collect();
61            constraints.push(LinearConstraint::eq(terms, 1.0));
62        }
63
64        // 2. Each position has exactly one task: Σ_j x_{j,p} = 1 for all p
65        for p in 0..n {
66            let terms: Vec<(usize, f64)> = (0..n).map(|j| (x_var(j, p), 1.0)).collect();
67            constraints.push(LinearConstraint::eq(terms, 1.0));
68        }
69
70        // 3. Precedence: Σ_p p*x_{i,p} + 1 <= Σ_p p*x_{j,p} for each (i,j)
71        for &(i, j) in self.precedences() {
72            let mut terms: Vec<(usize, f64)> = Vec::new();
73            for p in 0..n {
74                terms.push((x_var(j, p), p as f64));
75                terms.push((x_var(i, p), -(p as f64)));
76            }
77            constraints.push(LinearConstraint::ge(terms, 1.0));
78        }
79
80        // Binary bounds for x variables (ILP<i32> allows any non-negative integer)
81        for j in 0..n {
82            for p in 0..n {
83                constraints.push(LinearConstraint::le(vec![(x_var(j, p), 1.0)], 1.0));
84            }
85        }
86
87        // 4. Prefix cumulative cost: Σ_j Σ_{p in 0..=q} c_j * x_{j,p} <= z for all q
88        //    (minimax linearization: z >= max_q cumulative_cost(q))
89        let costs = self.costs();
90        for q in 0..n {
91            let mut terms: Vec<(usize, f64)> = Vec::new();
92            for (j, &c_j) in costs.iter().enumerate() {
93                for p in 0..=q {
94                    terms.push((x_var(j, p), c_j as f64));
95                }
96            }
97            terms.push((z_var, -1.0));
98            constraints.push(LinearConstraint::le(terms, 0.0));
99        }
100
101        // z upper bound: max cumulative cost ≤ sum of absolute costs
102        let z_upper: f64 = costs.iter().map(|&c| (c as f64).abs()).sum();
103        constraints.push(LinearConstraint::le(vec![(z_var, 1.0)], z_upper));
104
105        // Objective: minimize z (the maximum cumulative cost)
106        let objective = vec![(z_var, 1.0)];
107
108        ReductionSTMMCCToILP {
109            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize),
110            num_tasks: n,
111        }
112    }
113}
114
115#[cfg(feature = "example-db")]
116pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
117    vec![crate::example_db::specs::RuleExampleSpec {
118        id: "sequencingtominimizemaximumcumulativecost_to_ilp",
119        build: || {
120            let source =
121                SequencingToMinimizeMaximumCumulativeCost::new(vec![2, -1, 3, -2], vec![(0, 2)]);
122            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
123        },
124    }]
125}
126
127#[cfg(test)]
128#[path = "../unit_tests/rules/sequencingtominimizemaximumcumulativecost_ilp.rs"]
129mod tests;
problemreductions/rules/sequencingtominimizemaximumcumulativecost_ilp.rs

problemreductions/rules/
sequencingtominimizemaximumcumulativecost_ilp.rs
