problemreductions/rules/
schedulingtominimizeweightedcompletiontime_ilp.rs

1//! Reduction from SchedulingToMinimizeWeightedCompletionTime to ILP.
2//!
3//! The reduction uses binary assignment variables `x_{t,p}` (task t on
4//! processor p), integer completion-time variables `C_t`, and binary
5//! ordering variables `y_{i,j}` for each task pair. Big-M constraints
6//! enforce that tasks sharing a processor do not overlap.
7
8use crate::models::algebraic::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
9use crate::models::misc::SchedulingToMinimizeWeightedCompletionTime;
10use crate::reduction;
11use crate::rules::ilp_helpers::one_hot_decode_rows;
12use crate::rules::traits::{ReduceTo, ReductionResult};
13
14/// Result of reducing SchedulingToMinimizeWeightedCompletionTime to ILP.
15///
16/// Variable layout:
17/// - `x_{t,p}` at index `t * m + p` for t in 0..n, p in 0..m
18/// - `C_t` at index `n * m + t` for t in 0..n (completion times)
19/// - `y_{i,j}` at index `n * m + n + pair_index(i,j)` for i < j
20///   (1 if task i is before task j on their shared processor)
21///
22/// Total variables: n*m + n + n*(n-1)/2
23#[derive(Debug, Clone)]
24pub struct ReductionSMWCTToILP {
25    target: ILP<i64, i64, Bounded>,
26    num_tasks: usize,
27    num_processors: usize,
28}
29
30impl ReductionSMWCTToILP {
31    fn x_var(&self, task: usize, processor: usize) -> usize {
32        task * self.num_processors + processor
33    }
34
35    fn c_var(&self, task: usize) -> usize {
36        self.num_tasks * self.num_processors + task
37    }
38
39    fn y_var(&self, i: usize, j: usize) -> usize {
40        debug_assert!(i < j);
41        let base = self.num_tasks * self.num_processors + self.num_tasks;
42        base + i * (2 * self.num_tasks - i - 1) / 2 + (j - i - 1)
43    }
44}
45
46impl ReductionResult for ReductionSMWCTToILP {
47    type Source = SchedulingToMinimizeWeightedCompletionTime;
48    type Target = ILP<i64, i64, Bounded>;
49
50    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
51        &self.target
52    }
53
54    /// Extract solution: for each task, find the processor with x_{t,p} = 1.
55    fn extract_solution(
56        &self,
57        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
58    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
59        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
60
61        one_hot_decode_rows(target_solution, self.num_tasks, self.num_processors, 0)
62    }
63}
64
65#[reduction(transform = {
66    exact {
67        num_vars = "num_tasks * num_processors + num_tasks + num_tasks * (num_tasks - 1) / 2",
68        num_constraints = "num_tasks + num_tasks * num_processors + 2 * num_tasks + 2 * num_tasks * (num_tasks - 1) / 2 * num_processors + num_tasks * (num_tasks - 1) / 2",
69    },
70    upper_bound {
71        max_constraint_magnitude_bits = "max_processing_time_bits + num_tasks + 2",
72        num_nonzeros = "(num_tasks * num_processors + num_tasks + num_tasks * (num_tasks - 1) / 2) * (num_tasks + num_tasks * num_processors + 2 * num_tasks + 2 * num_tasks * (num_tasks - 1) / 2 * num_processors + num_tasks * (num_tasks - 1) / 2)",
73    },
74})]
75impl ReduceTo<ILP<i64, i64, Bounded>> for SchedulingToMinimizeWeightedCompletionTime {
76    type Result = ReductionSMWCTToILP;
77
78    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
79        let n = self.num_tasks();
80        let m = self.num_processors();
81
82        let total_processing_time = self
83            .lengths()
84            .iter()
85            .try_fold(0_i64, |total, &length| total.checked_add(length))
86            .ok_or_else(|| {
87                crate::rules::ReductionError::integer_overflow::<
88                    SchedulingToMinimizeWeightedCompletionTime,
89                    ILP<i64, i64, Bounded>,
90                >("summing task processing times")
91            })?;
92        let lengths = self.lengths();
93        let weights = self.weights();
94        let big_m = total_processing_time;
95        let two_big_m = big_m.checked_mul(2).ok_or_else(|| {
96            crate::rules::ReductionError::integer_overflow::<
97                SchedulingToMinimizeWeightedCompletionTime,
98                ILP<i64, i64, Bounded>,
99            >("doubling the disjunctive scheduling bound")
100        })?;
101        let three_big_m = big_m.checked_mul(3).ok_or_else(|| {
102            crate::rules::ReductionError::integer_overflow::<
103                SchedulingToMinimizeWeightedCompletionTime,
104                ILP<i64, i64, Bounded>,
105            >("tripling the disjunctive scheduling bound")
106        })?;
107
108        let num_pairs = n * n.saturating_sub(1) / 2;
109        let num_vars = n * m + n + num_pairs;
110
111        let result = ReductionSMWCTToILP {
112            target: ILP::new(0, vec![], vec![], ObjectiveSense::Minimize)
113                .map_err(Self::target_construction)?,
114            num_tasks: n,
115            num_processors: m,
116        };
117
118        let mut constraints = Vec::new();
119
120        // 1. Assignment constraints: each task assigned to exactly one processor
121        // sum_p x_{t,p} = 1 for each t
122        for t in 0..n {
123            let terms: Vec<(usize, i64)> = (0..m).map(|p| (result.x_var(t, p), 1)).collect();
124            constraints.push(LinearConstraint::eq(terms, 1));
125        }
126
127        // 2. Binary bounds on x_{t,p}: 0 <= x_{t,p} <= 1
128        for t in 0..n {
129            for p in 0..m {
130                constraints.push(LinearConstraint::le(vec![(result.x_var(t, p), 1)], 1));
131            }
132        }
133
134        // 3. Completion time bounds: l_t <= C_t <= M
135        for (t, &length) in lengths.iter().enumerate() {
136            constraints.push(LinearConstraint::ge(vec![(result.c_var(t), 1)], length));
137            constraints.push(LinearConstraint::le(vec![(result.c_var(t), 1)], big_m));
138        }
139
140        // 4. Disjunctive constraints: for each pair (i,j) with i < j, on each processor p:
141        //    If both tasks are on processor p and y_{i,j}=1 (i before j):
142        //      C_j >= C_i + l_j - M*(2 - x_{i,p} - x_{j,p}) - M*(1 - y_{i,j})
143        //    If both on p and y_{i,j}=0 (j before i):
144        //      C_i >= C_j + l_i - M*(2 - x_{i,p} - x_{j,p}) - M*y_{i,j}
145        //
146        // Rearranged:
147        //   C_j - C_i + M*x_{i,p} + M*x_{j,p} + M*y_{i,j} >= l_j - 3M + M
148        //     => C_j - C_i + M*x_{i,p} + M*x_{j,p} + M*y_{i,j} >= l_j - 2M
149        //   C_i - C_j + M*x_{i,p} + M*x_{j,p} - M*y_{i,j} >= l_i - 2M - M + M
150        //     => C_i - C_j + M*x_{i,p} + M*x_{j,p} - M*y_{i,j} >= l_i - 3M
151
152        for i in 0..n {
153            for j in (i + 1)..n {
154                let y = result.y_var(i, j);
155                let ci = result.c_var(i);
156                let cj = result.c_var(j);
157                let li = lengths[i];
158                let lj = lengths[j];
159
160                for p in 0..m {
161                    let xip = result.x_var(i, p);
162                    let xjp = result.x_var(j, p);
163
164                    // If i before j on processor p: C_j >= C_i + l_j
165                    // C_j - C_i + M*(1-y) + M*(1-x_{i,p}) + M*(1-x_{j,p}) >= l_j
166                    // C_j - C_i - M*y - M*x_{i,p} - M*x_{j,p} >= l_j - 3M
167                    constraints.push(LinearConstraint::ge(
168                        vec![(cj, 1), (ci, -1), (y, -big_m), (xip, -big_m), (xjp, -big_m)],
169                        lj - three_big_m,
170                    ));
171
172                    // If j before i on processor p: C_i >= C_j + l_i
173                    // C_i - C_j + M*y + M*(1-x_{i,p}) + M*(1-x_{j,p}) >= l_i
174                    // C_i - C_j + M*y - M*x_{i,p} - M*x_{j,p} >= l_i - 2M
175                    constraints.push(LinearConstraint::ge(
176                        vec![(ci, 1), (cj, -1), (y, big_m), (xip, -big_m), (xjp, -big_m)],
177                        li - two_big_m,
178                    ));
179                }
180
181                // Binary bound on y_{i,j}: 0 <= y <= 1
182                constraints.push(LinearConstraint::le(vec![(y, 1)], 1));
183            }
184        }
185
186        // Objective: minimize sum_t w_t * C_t
187        let objective: Vec<(usize, i64)> = weights
188            .iter()
189            .copied()
190            .enumerate()
191            .map(|(task, weight)| (result.c_var(task), weight))
192            .collect();
193
194        let mut variables = vec![IntegerVariable::binary(); num_vars];
195        variables[n * m..n * m + n].fill(
196            IntegerVariable::new(Some(0), Some(total_processing_time))
197                .map_err(Self::target_construction)?,
198        );
199
200        Ok(ReductionSMWCTToILP {
201            target: ILP::with_variables(
202                variables,
203                constraints,
204                objective,
205                ObjectiveSense::Minimize,
206            )
207            .map_err(Self::target_construction)?,
208            num_tasks: n,
209            num_processors: m,
210        })
211    }
212}
213
214#[cfg(feature = "example-db")]
215pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
216    vec![crate::example_db::specs::RuleExampleSpec {
217        id: "schedulingtominimizeweightedcompletiontime_to_ilp",
218        build: || {
219            // 3 tasks, 2 processors: simple instance for canonical example
220            let source =
221                SchedulingToMinimizeWeightedCompletionTime::new(vec![1, 2, 3], vec![4, 2, 1], 2);
222            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
223        },
224    }]
225}
226
227#[cfg(test)]
228#[path = "../unit_tests/rules/schedulingtominimizeweightedcompletiontime_ilp.rs"]
229mod tests;
problemreductions/rules/schedulingtominimizeweightedcompletiontime_ilp.rs

problemreductions/rules/
schedulingtominimizeweightedcompletiontime_ilp.rs
