problemreductions/rules/
sequencingtominimizeweightedcompletiontime_ilp.rs

1//! Strict linear ordering with exact signed completion-time equations.
2//! Triangle inequalities rule out cyclic orders even for zero-duration jobs.
3
4use crate::models::algebraic::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
5use crate::models::misc::SequencingToMinimizeWeightedCompletionTime;
6use crate::reduction;
7use crate::rules::traits::{ReduceTo, ReductionResult};
8
9#[derive(Debug, Clone)]
10pub struct ReductionSTMWCTToILP {
11    target: ILP<i64, i64, Bounded>,
12    num_tasks: usize,
13}
14
15impl ReductionResult for ReductionSTMWCTToILP {
16    type Source = SequencingToMinimizeWeightedCompletionTime;
17    type Target = ILP<i64, i64, Bounded>;
18
19    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
20        &self.target
21    }
22
23    fn extract_solution(
24        &self,
25        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
26    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
27        crate::rules::traits::validate_target_witness(
28            self.target_problem(),
29            target_solution,
30            |value| value.value.is_some(),
31            "target ILP assignment is infeasible",
32        )?;
33
34        let mut ranks = vec![0; self.num_tasks];
35        let mut pair = self.num_tasks;
36        for i in 0..self.num_tasks {
37            for j in i + 1..self.num_tasks {
38                ranks[if target_solution[pair] == 1 { j } else { i }] += 1;
39                pair += 1;
40            }
41        }
42        let mut order: Vec<_> = (0..self.num_tasks).collect();
43        order.sort_by_key(|&j| ranks[j]);
44        Ok(order)
45    }
46}
47
48#[reduction(transform = {
49    exact {
50        num_vars = "num_tasks + num_tasks * (num_tasks - 1) / 2",
51        num_constraints = "num_tasks * (num_tasks - 1) * (num_tasks - 2) / 3 + num_tasks + num_precedences",
52    },
53    upper_bound {
54        max_constraint_magnitude_bits = "max_processing_time_bits + num_tasks",
55        num_nonzeros = "num_tasks * (num_tasks - 1) * (num_tasks - 2) + num_tasks^2 + num_precedences",
56    },
57})]
58impl ReduceTo<ILP<i64, i64, Bounded>> for SequencingToMinimizeWeightedCompletionTime {
59    type Result = ReductionSTMWCTToILP;
60
61    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
62        let overflow = |operation: &str| {
63            crate::rules::ReductionError::integer_overflow::<Self, ILP<i64, i64, Bounded>>(
64                operation,
65            )
66        };
67        let integer = |value: i128| {
68            i64::try_from(value).map_err(|_| overflow("representing an exact completion equation"))
69        };
70        let n = self.num_tasks();
71        let pairs = n
72            .checked_mul(n.saturating_sub(1))
73            .ok_or_else(|| overflow("counting ordering variables"))?
74            / 2;
75        let num_vars = n
76            .checked_add(pairs)
77            .ok_or_else(|| overflow("counting sequencing variables"))?;
78        let rows = pairs
79            .checked_mul(n.saturating_sub(2))
80            .and_then(|x| (x / 3).checked_mul(2))
81            .and_then(|x| x.checked_add(n))
82            .and_then(|x| x.checked_add(self.num_precedences()))
83            .ok_or_else(|| overflow("counting sequencing constraints"))?;
84        let lengths = self.lengths();
85        // Any permutation prefix lies between the sums of negative and positive lengths.
86        let lower: i128 = lengths.iter().map(|&p| i128::from(p.min(0))).sum();
87        let upper: i128 = lengths.iter().map(|&p| i128::from(p.max(0))).sum();
88        integer(lower)?;
89        integer(upper)?;
90        let mut variables = Vec::with_capacity(num_vars);
91        for &p in lengths {
92            let low = integer(i128::from(p) + lower - i128::from(p.min(0)))?;
93            let high = integer(i128::from(p) + upper - i128::from(p.max(0)))?;
94            variables.push(
95                IntegerVariable::new(Some(low), Some(high)).map_err(Self::target_construction)?,
96            );
97        }
98        variables.resize(num_vars, IntegerVariable::binary());
99        let pair = |i: usize, j: usize| n + i * (2 * n - i - 1) / 2 + j - i - 1;
100        let mut constraints = Vec::with_capacity(rows);
101        for i in 0..n {
102            for j in i + 1..n {
103                for k in j + 1..n {
104                    let terms = vec![(pair(i, j), 1), (pair(j, k), 1), (pair(i, k), -1)];
105                    constraints.push(LinearConstraint::ge(terms.clone(), 0));
106                    constraints.push(LinearConstraint::le(terms, 1));
107                }
108            }
109        }
110        for &(a, b) in self.precedences() {
111            let terms = if a == b {
112                vec![]
113            } else {
114                vec![(pair(a.min(b), a.max(b)), 1)]
115            };
116            constraints.push(LinearConstraint::eq(terms, i64::from(a <= b)));
117        }
118        for j in 0..n {
119            let mut terms = vec![(j, 1)];
120            for (i, &p) in lengths.iter().enumerate().take(j) {
121                terms.push((pair(i, j), integer(-i128::from(p))?));
122            }
123            for (i, &p) in lengths.iter().enumerate().skip(j + 1) {
124                terms.push((pair(j, i), p));
125            }
126            let rhs = integer(lengths[j..].iter().map(|&p| i128::from(p)).sum())?;
127            constraints.push(LinearConstraint::eq(terms, rhs));
128        }
129        // Keep the source's coefficients and task-index accumulation order exactly.
130        let objective = self.weights().iter().copied().enumerate().collect();
131        let target =
132            ILP::with_variables(variables, constraints, objective, ObjectiveSense::Minimize)
133                .map_err(Self::target_construction)?;
134        crate::rules::ilp_helpers::validate_bounded_constraint_arithmetic::<Self>(&target)?;
135        Ok(Self::Result {
136            target,
137            num_tasks: n,
138        })
139    }
140}
141
142#[cfg(feature = "example-db")]
143pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
144    vec![crate::example_db::specs::RuleExampleSpec {
145        id: "sequencingtominimizeweightedcompletiontime_to_ilp",
146        build: || {
147            let source =
148                SequencingToMinimizeWeightedCompletionTime::new(vec![2, 1], vec![3, 5], vec![]);
149            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
150        },
151    }]
152}
153
154#[cfg(test)]
155#[path = "../unit_tests/rules/sequencingtominimizeweightedcompletiontime_ilp.rs"]
156mod tests;
problemreductions/rules/sequencingtominimizeweightedcompletiontime_ilp.rs

problemreductions/rules/
sequencingtominimizeweightedcompletiontime_ilp.rs
