problemreductions/rules/
openshopscheduling_ilp.rs

1//! Bounded disjunctive open-shop scheduling with identical-machine symmetry.
2use crate::models::algebraic::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
3use crate::models::misc::OpenShopScheduling;
4use crate::models::Decision;
5use crate::reduction;
6use crate::rules::traits::{ReduceTo, ReductionResult};
7
8#[derive(Debug, Clone)]
9pub struct ReductionOSSToILP {
10    target: ILP<i64, i64, Bounded>,
11    start_offset: usize,
12    num_operations: usize,
13}
14
15impl ReductionOSSToILP {
16    fn build(
17        source: &OpenShopScheduling,
18        bound: Option<i64>,
19    ) -> Result<Self, crate::rules::ReductionError> {
20        type Target = ILP<i64, i64, Bounded>;
21        let overflow = |operation| {
22            crate::rules::ReductionError::integer_overflow::<OpenShopScheduling, Target>(operation)
23        };
24        let construction = <OpenShopScheduling as ReduceTo<Target>>::target_construction;
25        let total = i64::try_from(source.schedule_horizon())
26            .map_err(|_| overflow("converting the schedule horizon"))?;
27        let horizon = bound.map_or(total, |b| b.min(total));
28        let p = source.processing_times();
29        if horizon < 0 || p.iter().flatten().any(|&duration| duration > horizon) {
30            return Ok(Self {
31                target: ILP::with_variables(
32                    vec![],
33                    vec![LinearConstraint::eq(vec![], 1)],
34                    vec![],
35                    ObjectiveSense::Minimize,
36                )
37                .map_err(construction)?,
38                start_offset: 0,
39                num_operations: 0,
40            });
41        }
42        let n = source.num_jobs();
43        let m = source.num_machines();
44        let pairs = |k: usize| {
45            if k.is_multiple_of(2) {
46                (k / 2).checked_mul(k.saturating_sub(1))
47            } else {
48                k.checked_mul(k / 2)
49            }
50        };
51        let machine_orders = if m == 0 {
52            0
53        } else {
54            pairs(n)
55                .and_then(|v| v.checked_mul(m))
56                .ok_or_else(|| overflow("counting machine order variables"))?
57        };
58        let job_orders = if n == 0 {
59            0
60        } else {
61            pairs(m)
62                .and_then(|v| v.checked_mul(n))
63                .ok_or_else(|| overflow("counting job order variables"))?
64        };
65        let operations = n
66            .checked_mul(m)
67            .ok_or_else(|| overflow("counting operations"))?;
68        let makespan = machine_orders
69            .checked_add(operations)
70            .and_then(|v| v.checked_add(job_orders))
71            .ok_or_else(|| overflow("counting scheduling variables"))?;
72        let count = makespan
73            .checked_add(usize::from(bound.is_none()))
74            .ok_or_else(|| overflow("counting scheduling variables"))?;
75        let mut variables = vec![IntegerVariable::binary(); count];
76        for (index, &duration) in p.iter().flatten().enumerate() {
77            variables[machine_orders + index] =
78                IntegerVariable::new(Some(0), Some(horizon - duration)).map_err(construction)?;
79        }
80        let start = |job: usize, machine: usize| machine_orders + job * m + machine;
81        let mut rows = Vec::new();
82        let mut disjunction = |a, b, bit, pa, pb| {
83            rows.push(LinearConstraint::ge(
84                vec![(b, 1), (a, -1), (bit, -horizon)],
85                pa - horizon,
86            ));
87            rows.push(LinearConstraint::ge(
88                vec![(a, 1), (b, -1), (bit, horizon)],
89                pb,
90            ));
91        };
92        let mut bit = 0;
93        for j in 0..n {
94            for k in j + 1..n {
95                for (i, (&left, &right)) in p[j].iter().zip(&p[k]).enumerate() {
96                    disjunction(start(j, i), start(k, i), bit, left, right);
97                    bit += 1;
98                }
99            }
100        }
101        bit = machine_orders + operations;
102        for (j, durations) in p.iter().enumerate() {
103            for i in 0..m {
104                for k in i + 1..m {
105                    disjunction(start(j, i), start(j, k), bit, durations[i], durations[k]);
106                    bit += 1;
107                }
108            }
109        }
110        let mut objective = Vec::new();
111        if bound.is_none() {
112            variables[makespan] =
113                IntegerVariable::new(Some(0), Some(horizon)).map_err(construction)?;
114            objective.push((makespan, 1));
115            for (index, &duration) in p.iter().flatten().enumerate() {
116                rows.push(LinearConstraint::ge(
117                    vec![(makespan, 1), (machine_orders + index, -1)],
118                    duration,
119                ));
120            }
121        }
122        // Relabel identical machines so one anchor job visits them in index order.
123        // Ordering every job this way would incorrectly impose a flow shop.
124        if n > 0 {
125            let mut groups = std::collections::BTreeMap::<Vec<i64>, Vec<usize>>::new();
126            for i in 0..m {
127                groups
128                    .entry(p.iter().map(|job| job[i]).collect())
129                    .or_default()
130                    .push(i);
131            }
132            for (column, machines) in groups {
133                let anchor = (0..n)
134                    .max_by_key(|&j| (column[j], std::cmp::Reverse(j)))
135                    .expect("nonempty jobs");
136                for pair in machines.windows(2) {
137                    rows.push(LinearConstraint::ge(
138                        vec![(start(anchor, pair[1]), 1), (start(anchor, pair[0]), -1)],
139                        column[anchor],
140                    ));
141                }
142            }
143        }
144        let target = ILP::with_variables(variables, rows, objective, ObjectiveSense::Minimize)
145            .map_err(construction)?;
146        crate::rules::ilp_helpers::validate_bounded_constraint_arithmetic::<OpenShopScheduling>(
147            &target,
148        )?;
149        Ok(Self {
150            target,
151            start_offset: machine_orders,
152            num_operations: operations,
153        })
154    }
155}
156
157impl ReductionResult for ReductionOSSToILP {
158    type Source = OpenShopScheduling;
159    type Target = ILP<i64, i64, Bounded>;
160    fn target_problem(&self) -> &Self::Target {
161        &self.target
162    }
163    fn extract_solution(&self, solution: &Vec<i64>) -> crate::rules::ExtractionResult<Vec<usize>> {
164        crate::rules::traits::validate_target_witness(
165            &self.target,
166            solution,
167            |value| value.value.is_some(),
168            "target ILP assignment is infeasible",
169        )?;
170        crate::rules::ilp_helpers::decode_usize_values(
171            &solution[self.start_offset..self.start_offset + self.num_operations],
172        )
173    }
174}
175
176#[reduction(transform = {
177    exact { num_vars = "num_jobs * (num_jobs - 1) / 2 * num_machines + num_jobs * num_machines + num_jobs * num_machines * (num_machines - 1) / 2 + 1", },
178    upper_bound {
179        num_constraints = "num_jobs * (num_jobs - 1) * num_machines + num_jobs * num_machines * (num_machines - 1) + num_jobs * num_machines + num_machines",
180        num_nonzeros = "3 * num_jobs * (num_jobs - 1) * num_machines + 3 * num_jobs * num_machines * (num_machines - 1) + 2 * num_jobs * num_machines + 2 * num_machines",
181        max_constraint_magnitude_bits = "schedule_horizon_bits",
182    },
183})]
184impl ReduceTo<ILP<i64, i64, Bounded>> for OpenShopScheduling {
185    type Result = ReductionOSSToILP;
186    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
187        ReductionOSSToILP::build(self, None)
188    }
189}
190
191#[derive(Debug, Clone)]
192pub struct ReductionDecisionOpenShopSchedulingToILP {
193    inner: ReductionOSSToILP,
194}
195impl ReductionResult for ReductionDecisionOpenShopSchedulingToILP {
196    type Source = Decision<OpenShopScheduling>;
197    type Target = ILP<i64, i64, Bounded>;
198    fn target_problem(&self) -> &Self::Target {
199        &self.inner.target
200    }
201    fn extract_solution(&self, solution: &Vec<i64>) -> crate::rules::ExtractionResult<Vec<usize>> {
202        self.inner.extract_solution(solution)
203    }
204}
205#[crate::aggregate_reduction(ilp_feasibility)]
206impl crate::rules::AggregateReductionResult for ReductionDecisionOpenShopSchedulingToILP {}
207#[reduction(transform = upper_bound {
208    num_vars = "num_jobs * (num_jobs - 1) / 2 * num_machines + num_jobs * num_machines + num_jobs * num_machines * (num_machines - 1) / 2",
209    num_constraints = "num_jobs * (num_jobs - 1) * num_machines + num_jobs * num_machines * (num_machines - 1) + num_machines + 1",
210    num_nonzeros = "3 * num_jobs * (num_jobs - 1) * num_machines + 3 * num_jobs * num_machines * (num_machines - 1) + 2 * num_machines",
211    max_constraint_magnitude_bits = "schedule_horizon_bits",
212})]
213impl ReduceTo<ILP<i64, i64, Bounded>> for Decision<OpenShopScheduling> {
214    type Result = ReductionDecisionOpenShopSchedulingToILP;
215    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
216        Ok(ReductionDecisionOpenShopSchedulingToILP {
217            inner: ReductionOSSToILP::build(self.inner(), Some(*self.bound()))?,
218        })
219    }
220}
221
222#[cfg(feature = "example-db")]
223pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
224    vec![
225        crate::example_db::specs::RuleExampleSpec {
226            id: "decisionopenshopscheduling_to_ilp",
227            build: || {
228                let source =
229                    Decision::new(OpenShopScheduling::new(2, vec![vec![1, 2], vec![2, 1]]), 3);
230                crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
231            },
232        },
233        crate::example_db::specs::RuleExampleSpec {
234            id: "openshopscheduling_to_ilp",
235            build: || {
236                // Small 2x2 instance for canonical example
237                let source = OpenShopScheduling::new(2, vec![vec![1, 2], vec![2, 1]]);
238                crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
239            },
240        },
241    ]
242}
243
244#[cfg(test)]
245#[path = "../unit_tests/rules/openshopscheduling_ilp.rs"]
246mod tests;
problemreductions/rules/openshopscheduling_ilp.rs

problemreductions/rules/
openshopscheduling_ilp.rs
