problemreductions/rules/sequencingwithdeadlinesandsetuptimes_ilp.rs
1//! Reduction from SequencingWithDeadlinesAndSetUpTimes to ILP<bool>.
2//!
3//! Position-assignment ILP with compiler-switch detection.
4//!
5//! Variables:
6//! - `x_{j,p}` binary: task j occupies position p (n*n variables)
7//! - `sw_p` binary: a compiler switch occurs before position p (n-1 variables, p >= 1)
8//! - `a_{j,p}` binary: x_{j,p} = 1 AND sw_p = 1 (n*(n-1) variables, p >= 1)
9//!
10//! The completion time of task j at position p equals the sum of all task
11//! lengths up to and including position p, plus the setup times for switches
12//! at each position 1..=p. Using the `a_{j,p}` linearisation, the setup
13//! contribution at position p is `sum_j s[k(j)] * a_{j,p}`.
14//!
15//! Deadline enforcement uses the standard big-M trick: for each (j, p),
16//! if `x_{j,p}=1` then the completion time at p must not exceed `d[j]`.
17
18use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
19use crate::models::misc::SequencingWithDeadlinesAndSetUpTimes;
20use crate::reduction;
21use crate::rules::ilp_helpers::one_hot_decode;
22use crate::rules::traits::{ReduceTo, ReductionResult};
23
24/// Result of reducing SequencingWithDeadlinesAndSetUpTimes to ILP<bool>.
25#[derive(Debug, Clone)]
26pub struct ReductionSWDSTToILP {
27 target: ILP<bool>,
28 num_tasks: usize,
29}
30
31impl ReductionResult for ReductionSWDSTToILP {
32 type Source = SequencingWithDeadlinesAndSetUpTimes;
33 type Target = ILP<bool>;
34
35 fn target_problem(&self) -> &ILP<bool> {
36 &self.target
37 }
38
39 fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
40 let n = self.num_tasks;
41 // x_{j,p} occupies the first n*n variables: decode the permutation.
42 one_hot_decode(target_solution, n, n, 0)
43 }
44}
45
46#[reduction(overhead = {
47 num_vars = "num_tasks * num_tasks + (num_tasks - 1) + num_tasks * (num_tasks - 1)",
48 num_constraints = "2 * num_tasks + num_tasks^2 * (num_tasks - 1) + 3 * num_tasks * (num_tasks - 1) + num_tasks * num_tasks",
49})]
50impl ReduceTo<ILP<bool>> for SequencingWithDeadlinesAndSetUpTimes {
51 type Result = ReductionSWDSTToILP;
52
53 fn reduce_to(&self) -> Self::Result {
54 let n = self.num_tasks();
55
56 // Handle empty case.
57 if n == 0 {
58 return ReductionSWDSTToILP {
59 target: ILP::new(0, vec![], vec![], ObjectiveSense::Minimize),
60 num_tasks: 0,
61 };
62 }
63
64 // Variable layout:
65 // x_{j,p} = j*n + p for j,p in 0..n → indices 0..n*n
66 // sw_p = n*n + (p-1) for p in 1..n → indices n*n .. n*n+(n-1)
67 // a_{j,p} = n*n+(n-1)+j*(n-1)+(p-1) for j in 0..n, p in 1..n
68 // → indices n*n+(n-1) .. n*n+(n-1)+n*(n-1)
69 let num_x = n * n;
70 let sw_offset = num_x;
71 let a_offset = sw_offset + (n - 1);
72 let num_vars = a_offset + n * (n - 1);
73
74 let x_var = |j: usize, p: usize| -> usize { j * n + p };
75 let sw_var = |p: usize| -> usize { sw_offset + (p - 1) }; // p >= 1
76 let a_var = |j: usize, p: usize| -> usize { a_offset + j * (n - 1) + (p - 1) }; // p >= 1
77
78 let lengths = self.lengths();
79 let deadlines = self.deadlines();
80 let compilers = self.compilers();
81 let setup_times = self.setup_times();
82
83 // Big-M: total processing time + worst-case total setup overhead.
84 let total_length: u64 = lengths.iter().copied().sum();
85 let max_setup: u64 = setup_times.iter().copied().max().unwrap_or(0);
86 let big_m = total_length as f64 + max_setup as f64 * (n as f64 - 1.0);
87
88 let mut constraints = Vec::new();
89
90 // 1. Each task assigned to exactly one position: sum_p x_{j,p} = 1 for all j.
91 for j in 0..n {
92 let terms: Vec<(usize, f64)> = (0..n).map(|p| (x_var(j, p), 1.0)).collect();
93 constraints.push(LinearConstraint::eq(terms, 1.0));
94 }
95
96 // 2. Each position has exactly one task: sum_j x_{j,p} = 1 for all p.
97 for p in 0..n {
98 let terms: Vec<(usize, f64)> = (0..n).map(|j| (x_var(j, p), 1.0)).collect();
99 constraints.push(LinearConstraint::eq(terms, 1.0));
100 }
101
102 // For each position p >= 1:
103 for p in 1..n {
104 // 3. Switch detection: sw_p >= x_{j,p} + x_{j',p-1} - 1
105 // whenever k(j) != k(j').
106 // This forces sw_p = 1 whenever the tasks at p-1 and p differ.
107 for j in 0..n {
108 for j_prev in 0..n {
109 if compilers[j] != compilers[j_prev] {
110 // sw_p - x_{j,p} - x_{j',p-1} >= -1
111 // i.e., x_{j,p} + x_{j',p-1} - sw_p <= 1
112 constraints.push(LinearConstraint::le(
113 vec![
114 (x_var(j, p), 1.0),
115 (x_var(j_prev, p - 1), 1.0),
116 (sw_var(p), -1.0),
117 ],
118 1.0,
119 ));
120 }
121 }
122 }
123
124 // 4. Linearisation of a_{j,p} = x_{j,p} * sw_p for each j:
125 // a_{j,p} <= x_{j,p}
126 // a_{j,p} <= sw_p
127 // a_{j,p} >= x_{j,p} + sw_p - 1
128 for j in 0..n {
129 // a_{j,p} <= x_{j,p}
130 constraints.push(LinearConstraint::le(
131 vec![(a_var(j, p), 1.0), (x_var(j, p), -1.0)],
132 0.0,
133 ));
134 // a_{j,p} <= sw_p
135 constraints.push(LinearConstraint::le(
136 vec![(a_var(j, p), 1.0), (sw_var(p), -1.0)],
137 0.0,
138 ));
139 // a_{j,p} >= x_{j,p} + sw_p - 1
140 // i.e. x_{j,p} + sw_p - a_{j,p} <= 1
141 constraints.push(LinearConstraint::le(
142 vec![(x_var(j, p), 1.0), (sw_var(p), 1.0), (a_var(j, p), -1.0)],
143 1.0,
144 ));
145 }
146 }
147
148 // 5. Deadline constraints: for each (j, p), if x_{j,p}=1, then
149 // the completion time at position p must be <= d[j].
150 //
151 // Completion time at position p =
152 // sum_{p'<=p} sum_{j''} l_{j''} * x_{j'',p'}
153 // + sum_{p'=1..=p} sum_{j''} s[k(j'')] * a_{j'',p'}
154 //
155 // Big-M form (only active when x_{j,p}=1):
156 // M * x_{j,p}
157 // + sum_{p'<p} sum_{j''} l_{j''} * x_{j'',p'}
158 // + sum_{p'=1..=p} sum_{j''} s[k(j'')] * a_{j'',p'}
159 // - M * x_{j,p} (cancels the activation term)
160 // <= d[j] - l[j] + M
161 //
162 // Simplifying (M * x_{j,p} - M * x_{j,p} vanishes):
163 // sum_{p'<p} sum_{j''} l_{j''} * x_{j'',p'}
164 // + sum_{p'=1..=p} sum_{j''} s[k(j'')] * a_{j'',p'}
165 // + M * x_{j,p}
166 // - M
167 // <= d[j] - l[j]
168 //
169 // i.e.:
170 // M * x_{j,p}
171 // + sum_{p'<p} sum_{j''} l_{j''} * x_{j'',p'}
172 // + sum_{p'=1..=p} sum_{j''} s[k(j'')] * a_{j'',p'}
173 // <= d[j] - l[j] + M
174 for j in 0..n {
175 for p in 0..n {
176 let mut terms: Vec<(usize, f64)> = Vec::new();
177 // Big-M activation term
178 terms.push((x_var(j, p), big_m));
179 // Processing time for positions 0..p (not including p itself)
180 for pp in 0..p {
181 for (jj, &len) in lengths.iter().enumerate() {
182 terms.push((x_var(jj, pp), len as f64));
183 }
184 }
185 // Setup time for positions 1..=p
186 for pp in 1..=p {
187 for jj in 0..n {
188 let s = setup_times[compilers[jj]] as f64;
189 if s > 0.0 {
190 terms.push((a_var(jj, pp), s));
191 }
192 }
193 }
194 let rhs = deadlines[j] as f64 - lengths[j] as f64 + big_m;
195 constraints.push(LinearConstraint::le(terms, rhs));
196 }
197 }
198
199 ReductionSWDSTToILP {
200 target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize),
201 num_tasks: n,
202 }
203 }
204}
205
206#[cfg(feature = "example-db")]
207pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
208 vec![crate::example_db::specs::RuleExampleSpec {
209 id: "sequencingwithdeadlinesandsetuptimes_to_ilp",
210 build: || {
211 let source = SequencingWithDeadlinesAndSetUpTimes::new(
212 vec![2, 3, 1, 2, 2],
213 vec![4, 11, 3, 16, 7],
214 vec![0, 1, 0, 1, 0],
215 vec![1, 2],
216 );
217 crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
218 },
219 }]
220}
221
222#[cfg(test)]
223#[path = "../unit_tests/rules/sequencingwithdeadlinesandsetuptimes_ilp.rs"]
224mod tests;