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 exact binary tardy indicators. Position-specific prefix bounds give
5//! both implications of the deadline comparison, including signed model inputs.
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(
29        &self,
30        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
31    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
32        let value =
33            crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
34        if !value.is_valid() {
35            return Err(crate::rules::ExtractionError::invalid(
36                "target ILP assignment is infeasible",
37            ));
38        }
39
40        Ok({
41            let n = self.num_tasks;
42            // Decode the n*n block of x_{j,p} variables into a schedule permutation.
43            // The source uses direct permutation encoding (config = schedule directly),
44            // so return the schedule as-is (it is already a permutation of 0..n).
45            one_hot_decode(target_solution, n, n, 0)?
46        })
47    }
48}
49
50#[reduction(
51    transform = exact {
52        num_vars = "num_tasks * num_tasks + num_tasks",
53        num_constraints = "2 * num_tasks + 2 * num_tasks * num_tasks",
54    },
55    unavailable = {
56        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
57    }
58)]
59impl ReduceTo<ILP<bool>> for SequencingToMinimizeTardyTaskWeight {
60    type Result = ReductionSTMTTWToILP;
61
62    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
63        let overflow = |operation: &str| {
64            crate::rules::ReductionError::integer_overflow::<Self, ILP<bool>>(operation)
65        };
66        let integer = |value: i128| {
67            i64::try_from(value).map_err(|_| overflow("representing exact tardiness constraints"))
68        };
69        let n = self.num_tasks();
70        let num_x_vars = n
71            .checked_mul(n)
72            .ok_or_else(|| overflow("assignment count"))?;
73        let num_vars = num_x_vars
74            .checked_add(n)
75            .ok_or_else(|| overflow("variable count"))?;
76        let num_constraints = num_vars
77            .checked_mul(2)
78            .ok_or_else(|| overflow("constraint count"))?;
79        // Upper bound: 2*n^2 assignment entries and two (n*p + 2)-term
80        // inequalities for each task and position. The preceding count bound
81        // also makes n^2 - n + 6 representable.
82        num_x_vars
83            .checked_mul(num_x_vars - n + 6)
84            .ok_or_else(|| overflow("constraint nonzero count"))?;
85
86        let lengths = self.lengths();
87        let deadlines = self.deadlines();
88        let weights = self.weights();
89        let mut sorted = lengths.to_vec();
90        sorted.sort_unstable();
91        let mut lower = vec![0i128; n + 1];
92        let mut upper = vec![0i128; n + 1];
93        let mut partial_lower = vec![0i128; n + 1];
94        let mut partial_upper = vec![0i128; n + 1];
95        // Checked polynomial dimensions bound n, so summing n i64 values and
96        // the subsequent constant arithmetic fit i128 before checked narrowing.
97        for p in 0..n {
98            lower[p + 1] = lower[p] + i128::from(sorted[p]);
99            upper[p + 1] = upper[p] + i128::from(sorted[n - 1 - p]);
100            partial_lower[p + 1] = partial_lower[p].min(lower[p + 1]);
101            partial_upper[p + 1] = partial_upper[p].max(upper[p + 1]);
102        }
103        // All source completion times and objective accumulation partial sums
104        // must be representable, including when lengths or weights are signed.
105        integer(partial_lower[n])?;
106        integer(partial_upper[n])?;
107        integer(weights.iter().map(|&w| i128::from(w.min(0))).sum())?;
108        integer(weights.iter().map(|&w| i128::from(w.max(0))).sum())?;
109
110        let x_var = |j: usize, p: usize| j * n + p;
111        let u_var = |j: usize| num_x_vars + j;
112        let mut constraints = Vec::with_capacity(num_constraints);
113        // Keep assignment constraints first: only permutation matrices reach
114        // the prefix inequalities in the target's formal sequential evaluator.
115        for j in 0..n {
116            constraints.push(LinearConstraint::eq(
117                (0..n).map(|p| (x_var(j, p), 1)).collect(),
118                1,
119            ));
120        }
121        for p in 0..n {
122            constraints.push(LinearConstraint::eq(
123                (0..n).map(|j| (x_var(j, p), 1)).collect(),
124                1,
125            ));
126        }
127
128        for j in 0..n {
129            for p in 0..n {
130                // P_p lies in [lower[p], upper[p]]. Replacing the integer
131                // comparison cutoff by its projection onto [lower[p]-1,
132                // upper[p]] preserves P_p > deadline[j]-length[j] exactly.
133                let cutoff = (i128::from(deadlines[j]) - i128::from(lengths[j]))
134                    .clamp(lower[p] - 1, upper[p]);
135                let on_time_m = upper[p] - cutoff;
136                let tardy_m = cutoff + 1 - lower[p];
137                // Bounds cover every sparse dot-product partial sum for a
138                // permutation matrix and every indicator vector, not just the
139                // final sum of feasible target witnesses.
140                integer(partial_lower[p] - on_time_m)?;
141                integer(partial_upper[p] + on_time_m)?;
142                integer(partial_lower[p] - 2 * tardy_m)?;
143                let on_time_m = integer(on_time_m)?;
144                let tardy_m = integer(tardy_m)?;
145                let mut on_time_terms = Vec::with_capacity(n * p + 2);
146                let mut tardy_terms = Vec::with_capacity(n * p + 2);
147                for pp in 0..p {
148                    for (task, &length) in lengths.iter().enumerate() {
149                        on_time_terms.push((x_var(task, pp), length));
150                        tardy_terms.push((x_var(task, pp), length));
151                    }
152                }
153                on_time_terms.push((x_var(j, p), on_time_m));
154                on_time_terms.push((u_var(j), -on_time_m));
155                tardy_terms.push((x_var(j, p), -tardy_m));
156                tardy_terms.push((u_var(j), -tardy_m));
157                // x=1,u=0 forces P_p <= cutoff; x=1,u=1 forces
158                // P_p >= cutoff+1. With x=0 both rows are redundant.
159                constraints.push(LinearConstraint::le(on_time_terms, integer(upper[p])?));
160                constraints.push(LinearConstraint::ge(
161                    tardy_terms,
162                    integer(lower[p] - i128::from(tardy_m))?,
163                ));
164            }
165        }
166
167        // Objective: minimize sum w_j * u_j
168        let objective: Vec<(usize, i64)> =
169            (0..n).map(|task| (u_var(task), weights[task])).collect();
170
171        Ok(ReductionSTMTTWToILP {
172            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
173                .map_err(Self::target_construction)?,
174            num_tasks: n,
175        })
176    }
177}
178
179#[cfg(feature = "example-db")]
180pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
181    vec![crate::example_db::specs::RuleExampleSpec {
182        id: "sequencingtominimizetardytaskweight_to_ilp",
183        build: || {
184            let source = SequencingToMinimizeTardyTaskWeight::new(
185                vec![3, 2, 4, 1, 2],
186                vec![5, 3, 7, 2, 4],
187                vec![6, 4, 10, 2, 8],
188            );
189            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
190        },
191    }]
192}
193
194#[cfg(test)]
195#[path = "../unit_tests/rules/sequencingtominimizetardytaskweight_ilp.rs"]
196mod tests;
problemreductions/rules/sequencingtominimizetardytaskweight_ilp.rs

problemreductions/rules/
sequencingtominimizetardytaskweight_ilp.rs
