problemreductions/rules/
openshopscheduling_ilp.rs

1//! Reduction from OpenShopScheduling to `ILP<i64>`.
2//!
3//! Disjunctive formulation with binary ordering variables and integer start times:
4//!
5//! **Variables:**
6//! - `x_{j,k,i}` for j < k, all machines i: binary, 1 if job j precedes job k on machine i.
7//!   Index: pair index * m + i, where pair index = `j*(2n-j-1)/2 + (k-j-1)`.
8//!   Count: n*(n-1)/2 * m variables.
9//! - `s_{j,i}` for all (j, i): integer start time of job j on machine i.
10//!   Index: num_order_vars + j * m + i.
11//!   Count: n * m variables.
12//! - `C` (makespan): integer, index num_order_vars + n * m.
13//!
14//! **Constraints:**
15//! 1. Binary bounds: 0 ≤ x_{j,k,i} ≤ 1 for all j < k, i.
16//! 2. Machine non-overlap for each pair (j, k) and machine i:
17//!    - s_{k,i} ≥ s_{j,i} + p_{j,i} - M*(1 - x_{j,k,i})  →  s_{k,i} - s_{j,i} + M*x_{j,k,i} ≥ p_{j,i}
18//!    - s_{j,i} ≥ s_{k,i} + p_{k,i} - M*x_{j,k,i}         →  s_{j,i} - s_{k,i} - M*x_{j,k,i} ≥ p_{k,i} - M
19//! 3. Job non-overlap for each job j and each pair of machines (i, i'):
20//!    Uses separate binary variable y_{j,i,i'} for i < i' to decide which task runs first.
21//!    Variables y_{j,i,i'}: appended after s variables.
22//!    - s_{j,i'} ≥ s_{j,i} + p_{j,i} - M*(1 - y_{j,i,i'})
23//!    - s_{j,i} ≥ s_{j,i'} + p_{j,i'} - M*y_{j,i,i'}
24//! 4. Makespan: C ≥ s_{j,i} + p_{j,i} for all (j, i).
25//! 5. Non-negativity of start times: s_{j,i} ≥ 0 (implied by ILP non-negativity).
26//!
27//! **Objective:** Minimize C.
28
29use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
30use crate::models::misc::OpenShopScheduling;
31use crate::reduction;
32use crate::rules::traits::{ReduceTo, ReductionResult};
33
34/// Result of reducing OpenShopScheduling to `ILP<i64>`.
35///
36/// Variable layout:
37/// - `x_{j,k,i}` at index `pair_idx(j,k) * m + i`    (num_pairs * m vars)
38/// - `s_{j,i}`   at index `num_order_vars + j * m + i`  (n * m vars)
39/// - `y_{j,i,i'}` for i < i': at `num_order_vars + n*m + j * num_machine_pairs + machine_pair_idx(i,i')`
40///   (n * m*(m-1)/2 vars)
41/// - `C`: at index `num_order_vars + n * m + n * m*(m-1)/2` (1 var)
42#[derive(Debug, Clone)]
43pub struct ReductionOSSToILP {
44    target: ILP<i64>,
45    num_jobs: usize,
46    num_machines: usize,
47    /// n*(n-1)/2 * m — start index of s_{j,i} variables
48    num_order_vars: usize,
49}
50
51impl ReductionOSSToILP {
52    fn pair_idx(&self, j: usize, k: usize) -> usize {
53        debug_assert!(j < k);
54        let n = self.num_jobs;
55        j * (2 * n - j - 1) / 2 + (k - j - 1)
56    }
57
58    fn x_var(&self, j: usize, k: usize, i: usize) -> usize {
59        self.pair_idx(j, k) * self.num_machines + i
60    }
61
62    fn s_var(&self, j: usize, i: usize) -> usize {
63        self.num_order_vars + j * self.num_machines + i
64    }
65
66    fn machine_pair_idx(&self, i: usize, ip: usize) -> usize {
67        debug_assert!(i < ip);
68        let m = self.num_machines;
69        i * (2 * m - i - 1) / 2 + (ip - i - 1)
70    }
71
72    fn y_var(&self, j: usize, i: usize, ip: usize) -> usize {
73        let num_machine_pairs = self.num_machines * self.num_machines.saturating_sub(1) / 2;
74        self.num_order_vars
75            + self.num_jobs * self.num_machines
76            + j * num_machine_pairs
77            + self.machine_pair_idx(i, ip)
78    }
79}
80
81impl ReductionResult for ReductionOSSToILP {
82    type Source = OpenShopScheduling;
83    type Target = ILP<i64>;
84
85    fn target_problem(&self) -> &ILP<i64> {
86        &self.target
87    }
88
89    /// Extract the job-major operation start times from the ILP solution.
90    fn extract_solution(
91        &self,
92        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
93    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
94        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
95        let start = self.num_order_vars;
96        let end = start + self.num_jobs * self.num_machines;
97        crate::rules::ilp_helpers::decode_usize_values(&target_solution[start..end])
98    }
99}
100
101#[reduction(
102    transform = exact {
103        num_vars = "num_jobs * (num_jobs - 1) / 2 * num_machines + num_jobs * num_machines + num_jobs * num_machines * (num_machines - 1) / 2 + 1",
104        num_constraints = "num_jobs * (num_jobs - 1) / 2 * num_machines + num_jobs * num_machines + 1 + 2 * num_jobs * (num_jobs - 1) / 2 * num_machines + num_jobs * num_machines * (num_machines - 1) / 2 + 2 * num_jobs * num_machines * (num_machines - 1) / 2 + num_jobs * num_machines",
105    },
106    unavailable = {
107        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
108    }
109)]
110impl ReduceTo<ILP<i64>> for OpenShopScheduling {
111    type Result = ReductionOSSToILP;
112
113    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
114        let n = self.num_jobs();
115        let m = self.num_machines();
116        let p = self.processing_times();
117
118        let num_pairs = n * n.saturating_sub(1) / 2;
119        let num_machine_pairs = m * m.saturating_sub(1) / 2;
120
121        // Variable counts
122        let num_order_vars = num_pairs * m; // x_{j,k,i}: binary
123        let num_start_vars = n * m; // s_{j,i}: integer
124        let num_job_pair_vars = n * num_machine_pairs; // y_{j,i,i'}: binary
125        let num_vars = num_order_vars + num_start_vars + num_job_pair_vars + 1; // +1 for C
126
127        let result = ReductionOSSToILP {
128            target: ILP::new(0, vec![], vec![], ObjectiveSense::Minimize)
129                .map_err(Self::target_construction)?,
130            num_jobs: n,
131            num_machines: m,
132            num_order_vars,
133        };
134
135        // Big-M: sum of all processing times (loose upper bound on makespan)
136        let total_p = p
137            .iter()
138            .flat_map(|row| row.iter())
139            .try_fold(0_i64, |total, &time| total.checked_add(time))
140            .ok_or_else(|| {
141                crate::rules::ReductionError::integer_overflow::<OpenShopScheduling, ILP<i64>>(
142                    "summing open-shop processing times",
143                )
144            })?;
145        let big_m = total_p;
146        let processing_times = p;
147
148        let c_var = num_order_vars + num_start_vars + num_job_pair_vars;
149
150        let mut constraints = Vec::new();
151
152        // 1. Binary bounds on x_{j,k,i}: 0 ≤ x ≤ 1
153        for j in 0..n {
154            for k in (j + 1)..n {
155                for i in 0..m {
156                    let x = result.x_var(j, k, i);
157                    constraints.push(LinearConstraint::le(vec![(x, 1)], 1));
158                }
159            }
160        }
161
162        // Upper bounds on start time variables: s_{j,i} ≤ total_p
163        // (no task can start after all tasks have finished)
164        for j in 0..n {
165            for i in 0..m {
166                let sji = result.s_var(j, i);
167                constraints.push(LinearConstraint::le(vec![(sji, 1)], big_m));
168            }
169        }
170
171        // Upper bound on makespan C ≤ total_p
172        constraints.push(LinearConstraint::le(vec![(c_var, 1)], big_m));
173
174        // 2. Machine non-overlap: for each pair (j,k) with j<k, each machine i
175        //    x_{j,k,i}=1 means j precedes k on machine i:
176        //      s_{k,i} ≥ s_{j,i} + p_{j,i}  →  s_{k,i} - s_{j,i} + M*x_{j,k,i} ≥ p_{j,i} (active when x=0)
177        //    Actually: s_{k,i} ≥ s_{j,i} + p_{j,i} - M*(1 - x_{j,k,i})
178        //              ⟺ s_{k,i} - s_{j,i} - M*x_{j,k,i} ≥ p_{j,i} - M
179        //    And:    s_{j,i} ≥ s_{k,i} + p_{k,i} - M*x_{j,k,i}
180        //              ⟺ s_{j,i} - s_{k,i} + M*x_{j,k,i} ≥ p_{k,i}  (active when x=1, i.e. k before j)
181        //    Wait, let's be careful. x=1 means j before k.
182        //      (a) if j before k: s_k ≥ s_j + p_{j,i}  →  when x=1 this is active, when x=0 inactive
183        //      (b) if k before j (x=0): s_j ≥ s_k + p_{k,i}
184        //
185        //    Linearization:
186        //      (a) s_{k,i} - s_{j,i} + M*(1-x) ≥ p_{j,i}
187        //          s_{k,i} - s_{j,i} - M*x ≥ p_{j,i} - M
188        //      (b) s_{j,i} - s_{k,i} + M*x ≥ p_{k,i}
189        for j in 0..n {
190            for k in (j + 1)..n {
191                for (i, (&pji, &pki)) in processing_times[j]
192                    .iter()
193                    .zip(processing_times[k].iter())
194                    .enumerate()
195                {
196                    let x = result.x_var(j, k, i);
197                    let sj = result.s_var(j, i);
198                    let sk = result.s_var(k, i);
199                    // (a) s_{k,i} - s_{j,i} - M*x_{j,k,i} >= p_{j,i} - M
200                    constraints.push(LinearConstraint::ge(
201                        vec![(sk, 1), (sj, -1), (x, -big_m)],
202                        pji - big_m,
203                    ));
204
205                    // (b) s_{j,i} - s_{k,i} + M*x_{j,k,i} >= p_{k,i}
206                    constraints.push(LinearConstraint::ge(
207                        vec![(sj, 1), (sk, -1), (x, big_m)],
208                        pki,
209                    ));
210                }
211            }
212        }
213
214        // 3. Binary bounds on y_{j,i,i'}: 0 ≤ y ≤ 1
215        for j in 0..n {
216            for i in 0..m {
217                for ip in (i + 1)..m {
218                    let y = result.y_var(j, i, ip);
219                    constraints.push(LinearConstraint::le(vec![(y, 1)], 1));
220                }
221            }
222        }
223
224        // 4. Job non-overlap: for each job j and each pair (i, i') with i < i'
225        //    y_{j,i,i'}=1 means machine i is scheduled before machine i' for job j:
226        //      (a) s_{j,i'} ≥ s_{j,i} + p_{j,i} - M*(1-y)
227        //          s_{j,i'} - s_{j,i} - M*y ≥ p_{j,i} - M
228        //      (b) s_{j,i} ≥ s_{j,i'} + p_{j,i'} - M*y
229        //          s_{j,i} - s_{j,i'} + M*y ≥ p_{j,i'}
230        for (j, pj) in processing_times.iter().enumerate() {
231            for i in 0..m {
232                for ip in (i + 1)..m {
233                    let y = result.y_var(j, i, ip);
234                    let sji = result.s_var(j, i);
235                    let sjip = result.s_var(j, ip);
236                    let pji = pj[i];
237                    let pjip = pj[ip];
238
239                    // (a) s_{j,i'} - s_{j,i} - M*y >= p_{j,i} - M
240                    constraints.push(LinearConstraint::ge(
241                        vec![(sjip, 1), (sji, -1), (y, -big_m)],
242                        pji - big_m,
243                    ));
244
245                    // (b) s_{j,i} - s_{j,i'} + M*y >= p_{j,i'}
246                    constraints.push(LinearConstraint::ge(
247                        vec![(sji, 1), (sjip, -1), (y, big_m)],
248                        pjip,
249                    ));
250                }
251            }
252        }
253
254        // 5. Makespan: C ≥ s_{j,i} + p_{j,i}  ⟺  C - s_{j,i} ≥ p_{j,i}
255        for (j, pj) in processing_times.iter().enumerate() {
256            for (i, &pji) in pj.iter().enumerate() {
257                let sji = result.s_var(j, i);
258                constraints.push(LinearConstraint::ge(vec![(c_var, 1), (sji, -1)], pji));
259            }
260        }
261
262        // Objective: minimize C
263        let objective = vec![(c_var, 1)];
264
265        Ok(ReductionOSSToILP {
266            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
267                .map_err(Self::target_construction)?,
268            num_jobs: n,
269            num_machines: m,
270            num_order_vars,
271        })
272    }
273}
274
275#[cfg(feature = "example-db")]
276pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
277    vec![crate::example_db::specs::RuleExampleSpec {
278        id: "openshopscheduling_to_ilp",
279        build: || {
280            // Small 2x2 instance for canonical example
281            let source = OpenShopScheduling::new(2, vec![vec![1, 2], vec![2, 1]]);
282            crate::example_db::specs::rule_example_via_ilp::<_, i64>(source)
283        },
284    }]
285}
286
287#[cfg(test)]
288#[path = "../unit_tests/rules/openshopscheduling_ilp.rs"]
289mod tests;
problemreductions/rules/openshopscheduling_ilp.rs

problemreductions/rules/
openshopscheduling_ilp.rs
