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::{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>,
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>;
49
50    fn target_problem(&self) -> &ILP<i64> {
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(
66    transform = 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    unavailable = {
71        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
72    }
73)]
74impl ReduceTo<ILP<i64>> for SchedulingToMinimizeWeightedCompletionTime {
75    type Result = ReductionSMWCTToILP;
76
77    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
78        let n = self.num_tasks();
79        let m = self.num_processors();
80
81        let total_processing_time = self
82            .lengths()
83            .iter()
84            .try_fold(0_i64, |total, &length| total.checked_add(length))
85            .ok_or_else(|| {
86                crate::rules::ReductionError::integer_overflow::<
87                    SchedulingToMinimizeWeightedCompletionTime,
88                    ILP<i64>,
89                >("summing task processing times")
90            })?;
91        let lengths = self.lengths();
92        let weights = self.weights();
93        let big_m = total_processing_time;
94        let two_big_m = big_m.checked_mul(2).ok_or_else(|| {
95            crate::rules::ReductionError::integer_overflow::<
96                SchedulingToMinimizeWeightedCompletionTime,
97                ILP<i64>,
98            >("doubling the disjunctive scheduling bound")
99        })?;
100        let three_big_m = big_m.checked_mul(3).ok_or_else(|| {
101            crate::rules::ReductionError::integer_overflow::<
102                SchedulingToMinimizeWeightedCompletionTime,
103                ILP<i64>,
104            >("tripling the disjunctive scheduling bound")
105        })?;
106
107        let num_pairs = n * n.saturating_sub(1) / 2;
108        let num_vars = n * m + n + num_pairs;
109
110        let result = ReductionSMWCTToILP {
111            target: ILP::new(0, vec![], vec![], ObjectiveSense::Minimize)
112                .map_err(Self::target_construction)?,
113            num_tasks: n,
114            num_processors: m,
115        };
116
117        let mut constraints = Vec::new();
118
119        // 1. Assignment constraints: each task assigned to exactly one processor
120        // sum_p x_{t,p} = 1 for each t
121        for t in 0..n {
122            let terms: Vec<(usize, i64)> = (0..m).map(|p| (result.x_var(t, p), 1)).collect();
123            constraints.push(LinearConstraint::eq(terms, 1));
124        }
125
126        // 2. Binary bounds on x_{t,p}: 0 <= x_{t,p} <= 1
127        for t in 0..n {
128            for p in 0..m {
129                constraints.push(LinearConstraint::le(vec![(result.x_var(t, p), 1)], 1));
130            }
131        }
132
133        // 3. Completion time bounds: l_t <= C_t <= M
134        for (t, &length) in lengths.iter().enumerate() {
135            constraints.push(LinearConstraint::ge(vec![(result.c_var(t), 1)], length));
136            constraints.push(LinearConstraint::le(vec![(result.c_var(t), 1)], big_m));
137        }
138
139        // 4. Disjunctive constraints: for each pair (i,j) with i < j, on each processor p:
140        //    If both tasks are on processor p and y_{i,j}=1 (i before j):
141        //      C_j >= C_i + l_j - M*(2 - x_{i,p} - x_{j,p}) - M*(1 - y_{i,j})
142        //    If both on p and y_{i,j}=0 (j before i):
143        //      C_i >= C_j + l_i - M*(2 - x_{i,p} - x_{j,p}) - M*y_{i,j}
144        //
145        // Rearranged:
146        //   C_j - C_i + M*x_{i,p} + M*x_{j,p} + M*y_{i,j} >= l_j - 3M + M
147        //     => C_j - C_i + M*x_{i,p} + M*x_{j,p} + M*y_{i,j} >= l_j - 2M
148        //   C_i - C_j + M*x_{i,p} + M*x_{j,p} - M*y_{i,j} >= l_i - 2M - M + M
149        //     => C_i - C_j + M*x_{i,p} + M*x_{j,p} - M*y_{i,j} >= l_i - 3M
150
151        for i in 0..n {
152            for j in (i + 1)..n {
153                let y = result.y_var(i, j);
154                let ci = result.c_var(i);
155                let cj = result.c_var(j);
156                let li = lengths[i];
157                let lj = lengths[j];
158
159                for p in 0..m {
160                    let xip = result.x_var(i, p);
161                    let xjp = result.x_var(j, p);
162
163                    // If i before j on processor p: C_j >= C_i + l_j
164                    // C_j - C_i + M*(1-y) + M*(1-x_{i,p}) + M*(1-x_{j,p}) >= l_j
165                    // C_j - C_i - M*y - M*x_{i,p} - M*x_{j,p} >= l_j - 3M
166                    constraints.push(LinearConstraint::ge(
167                        vec![(cj, 1), (ci, -1), (y, -big_m), (xip, -big_m), (xjp, -big_m)],
168                        lj - three_big_m,
169                    ));
170
171                    // If j before i on processor p: C_i >= C_j + l_i
172                    // C_i - C_j + M*y + M*(1-x_{i,p}) + M*(1-x_{j,p}) >= l_i
173                    // C_i - C_j + M*y - M*x_{i,p} - M*x_{j,p} >= l_i - 2M
174                    constraints.push(LinearConstraint::ge(
175                        vec![(ci, 1), (cj, -1), (y, big_m), (xip, -big_m), (xjp, -big_m)],
176                        li - two_big_m,
177                    ));
178                }
179
180                // Binary bound on y_{i,j}: 0 <= y <= 1
181                constraints.push(LinearConstraint::le(vec![(y, 1)], 1));
182            }
183        }
184
185        // Objective: minimize sum_t w_t * C_t
186        let objective: Vec<(usize, i64)> = weights
187            .iter()
188            .copied()
189            .enumerate()
190            .map(|(task, weight)| (result.c_var(task), weight))
191            .collect();
192
193        Ok(ReductionSMWCTToILP {
194            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
195                .map_err(Self::target_construction)?,
196            num_tasks: n,
197            num_processors: m,
198        })
199    }
200}
201
202#[cfg(feature = "example-db")]
203pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
204    vec![crate::example_db::specs::RuleExampleSpec {
205        id: "schedulingtominimizeweightedcompletiontime_to_ilp",
206        build: || {
207            // 3 tasks, 2 processors: simple instance for canonical example
208            let source =
209                SchedulingToMinimizeWeightedCompletionTime::new(vec![1, 2, 3], vec![4, 2, 1], 2);
210            crate::example_db::specs::rule_example_via_ilp::<_, i64>(source)
211        },
212    }]
213}
214
215#[cfg(test)]
216#[path = "../unit_tests/rules/schedulingtominimizeweightedcompletiontime_ilp.rs"]
217mod tests;
problemreductions/rules/schedulingtominimizeweightedcompletiontime_ilp.rs

problemreductions/rules/
schedulingtominimizeweightedcompletiontime_ilp.rs
