problemreductions/rules/
sequencingtominimizemaximumcumulativecost_ilp.rs

1//! Reduction from SequencingToMinimizeMaximumCumulativeCost to `ILP<i64, i64, Bounded>`.
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::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
8use crate::models::misc::SequencingToMinimizeMaximumCumulativeCost;
9use crate::reduction;
10use crate::rules::ilp_helpers::one_hot_decode;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12
13/// Result of reducing SequencingToMinimizeMaximumCumulativeCost to `ILP<i64, i64, Bounded>`.
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<i64, i64, Bounded>,
22    num_tasks: usize,
23}
24
25impl ReductionResult for ReductionSTMMCCToILP {
26    type Source = SequencingToMinimizeMaximumCumulativeCost;
27    type Target = ILP<i64, i64, Bounded>;
28
29    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
30        &self.target
31    }
32
33    /// Extract: decode position assignment → permutation → Lehmer code.
34    fn extract_solution(
35        &self,
36        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
37    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
38        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
39
40        Ok({
41            let n = self.num_tasks;
42
43            one_hot_decode(target_solution, n, n, 0)?
44        })
45    }
46}
47
48#[reduction(transform = {
49    exact {
50        num_vars = "num_tasks^2 + 1",
51        num_constraints = "num_tasks^2 + 3 * num_tasks + num_precedences + 1",
52    },
53    upper_bound {
54        max_constraint_magnitude_bits = "max_cost_bits + num_tasks",
55        num_nonzeros = "(num_tasks^2 + 1) * (num_tasks^2 + 3 * num_tasks + num_precedences + 1)",
56    },
57})]
58impl ReduceTo<ILP<i64, i64, Bounded>> for SequencingToMinimizeMaximumCumulativeCost {
59    type Result = ReductionSTMMCCToILP;
60
61    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
62        let n = self.num_tasks();
63        // n^2 position variables + 1 minimax variable z
64        let z_var = n * n;
65        let num_vars = n * n + 1;
66
67        let x_var = |j: usize, p: usize| -> usize { j * n + p };
68
69        let mut constraints = Vec::new();
70
71        // 1. Each task assigned to exactly one position: Σ_p x_{j,p} = 1 for all j
72        for j in 0..n {
73            let terms: Vec<(usize, i64)> = (0..n).map(|p| (x_var(j, p), 1)).collect();
74            constraints.push(LinearConstraint::eq(terms, 1));
75        }
76
77        // 2. Each position has exactly one task: Σ_j x_{j,p} = 1 for all p
78        for p in 0..n {
79            let terms: Vec<(usize, i64)> = (0..n).map(|j| (x_var(j, p), 1)).collect();
80            constraints.push(LinearConstraint::eq(terms, 1));
81        }
82
83        // 3. Precedence: Σ_p p*x_{i,p} + 1 <= Σ_p p*x_{j,p} for each (i,j)
84        for &(i, j) in self.precedences() {
85            let mut terms: Vec<(usize, i64)> = Vec::new();
86            for p in 0..n {
87                let p_i64 = Self::exact_i64(p, "encoding a task position")?;
88                terms.push((x_var(j, p), p_i64));
89                terms.push((x_var(i, p), -p_i64));
90            }
91            constraints.push(LinearConstraint::ge(terms, 1));
92        }
93
94        // Binary bounds for x variables (`ILP<i64, i64, Bounded>` allows any non-negative integer)
95        for j in 0..n {
96            for p in 0..n {
97                constraints.push(LinearConstraint::le(vec![(x_var(j, p), 1)], 1));
98            }
99        }
100
101        // 4. Prefix cumulative cost: Σ_j Σ_{p in 0..=q} c_j * x_{j,p} <= z for all q
102        //    (minimax linearization: z >= max_q cumulative_cost(q))
103        let costs = self.costs();
104        for q in 0..n {
105            let mut terms: Vec<(usize, i64)> = Vec::new();
106            for (j, &c_j) in costs.iter().enumerate() {
107                for p in 0..=q {
108                    terms.push((x_var(j, p), c_j));
109                }
110            }
111            terms.push((z_var, -1));
112            constraints.push(LinearConstraint::le(terms, 0));
113        }
114
115        // z upper bound: max cumulative cost ≤ sum of absolute costs
116        let z_upper = costs.iter().try_fold(0_i64, |total, &cost| {
117            let magnitude = cost.checked_abs().ok_or_else(|| {
118                crate::rules::ReductionError::integer_overflow::<
119                    SequencingToMinimizeMaximumCumulativeCost,
120                    ILP<i64, i64, Bounded>,
121                >("taking the absolute value of a task cost")
122            })?;
123            total.checked_add(magnitude).ok_or_else(|| {
124                crate::rules::ReductionError::integer_overflow::<
125                    SequencingToMinimizeMaximumCumulativeCost,
126                    ILP<i64, i64, Bounded>,
127                >("summing absolute task costs")
128            })
129        })?;
130        constraints.push(LinearConstraint::le(vec![(z_var, 1)], z_upper));
131
132        // Objective: minimize z (the maximum cumulative cost)
133        let objective = vec![(z_var, 1)];
134
135        let mut variables = vec![IntegerVariable::binary(); num_vars];
136        variables[z_var] =
137            IntegerVariable::new(Some(0), Some(z_upper)).map_err(Self::target_construction)?;
138
139        Ok(ReductionSTMMCCToILP {
140            target: ILP::with_variables(
141                variables,
142                constraints,
143                objective,
144                ObjectiveSense::Minimize,
145            )
146            .map_err(Self::target_construction)?,
147            num_tasks: n,
148        })
149    }
150}
151
152#[cfg(feature = "example-db")]
153pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
154    vec![crate::example_db::specs::RuleExampleSpec {
155        id: "sequencingtominimizemaximumcumulativecost_to_ilp",
156        build: || {
157            let source =
158                SequencingToMinimizeMaximumCumulativeCost::new(vec![2, -1, 3, -2], vec![(0, 2)]);
159            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
160        },
161    }]
162}
163
164#[cfg(test)]
165#[path = "../unit_tests/rules/sequencingtominimizemaximumcumulativecost_ilp.rs"]
166mod tests;
problemreductions/rules/sequencingtominimizemaximumcumulativecost_ilp.rs

problemreductions/rules/
sequencingtominimizemaximumcumulativecost_ilp.rs
