problemreductions/rules/
sequencingwithinintervals_ilp.rs

1//! Reduction from SequencingWithinIntervals to ILP<bool>.
2//!
3//! Uses a time-indexed binary formulation:
4//! - Variables: Binary x_{j,k} where x_{j,k} = 1 iff task j starts at offset k
5//!   from its release time (actual start = r_j + k), k in 0..(d_j - r_j - l_j).
6//! - Variable index: task j at offset k has global index: Σ_{i<j} slot_count_i + k,
7//!   where slot_count_i = d_i - r_i - l_i + 1 is the number of valid start offsets.
8//!   For simplicity we use a flat layout: each task j occupies slot_count[j] variables.
9//! - Constraints:
10//!   1. One-hot: Σ_k x_{j,k} = 1 for each task j
11//!   2. Non-overlap: for each pair (i, j), they cannot be active at the same time.
12//!      Active time of task j starting at r_j+k: [r_j+k, r_j+k+l_j).
13//!      Non-overlap: no shared time. Modeled with: for each pair (i,j) with i<j,
14//!      Σ_{(k1,k2): windows overlap} (x_{i,k1} + x_{j,k2}) ≤ 1.
15//! - Objective: Minimize 0 (feasibility)
16//! - Extraction: For task j, find offset k where x_{j,k}=1; config[j] = k.
17
18use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
19use crate::models::misc::SequencingWithinIntervals;
20use crate::reduction;
21use crate::rules::traits::{ReduceTo, ReductionResult};
22
23/// Result of reducing SequencingWithinIntervals to ILP<bool>.
24///
25/// Variable layout: task j occupies variables at offsets [base_j, base_j + slot_count_j).
26/// where base_j = Σ_{i<j} slot_count_i and slot_count_j = d_j - r_j - l_j + 1.
27#[derive(Debug, Clone)]
28pub struct ReductionSWIToILP {
29    target: ILP<bool>,
30    /// For each task: (base variable index, number of start offsets).
31    task_layout: Vec<(usize, usize)>,
32}
33
34impl ReductionResult for ReductionSWIToILP {
35    type Source = SequencingWithinIntervals;
36    type Target = ILP<bool>;
37
38    fn target_problem(&self) -> &ILP<bool> {
39        &self.target
40    }
41
42    /// Extract schedule from ILP solution.
43    ///
44    /// For each task j, find the offset k where x_{j,k} = 1.
45    /// Returns config[j] = k (start time offset from release time).
46    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
47        self.task_layout
48            .iter()
49            .map(|&(base, count)| {
50                (0..count)
51                    .find(|&k| target_solution.get(base + k).copied().unwrap_or(0) == 1)
52                    .unwrap_or(0)
53            })
54            .collect()
55    }
56}
57
58#[reduction(
59    overhead = {
60        num_vars = "num_tasks^2",
61        num_constraints = "num_tasks^2 + num_tasks",
62    }
63)]
64impl ReduceTo<ILP<bool>> for SequencingWithinIntervals {
65    type Result = ReductionSWIToILP;
66
67    fn reduce_to(&self) -> Self::Result {
68        let n = self.num_tasks();
69        let release = self.release_times();
70        let deadlines = self.deadlines();
71        let lengths = self.lengths();
72
73        // Compute per-task variable layout: how many start slots each task has
74        let slot_counts: Vec<usize> = (0..n)
75            .map(|j| (deadlines[j] - release[j] - lengths[j] + 1) as usize)
76            .collect();
77
78        let mut bases = vec![0usize; n];
79        for j in 1..n {
80            bases[j] = bases[j - 1] + slot_counts[j - 1];
81        }
82        let num_vars =
83            bases.last().copied().unwrap_or(0) + slot_counts.last().copied().unwrap_or(0);
84
85        let task_layout: Vec<(usize, usize)> = (0..n).map(|j| (bases[j], slot_counts[j])).collect();
86
87        let mut constraints = Vec::new();
88
89        // 1. One-hot per task
90        for j in 0..n {
91            let terms: Vec<(usize, f64)> =
92                (0..slot_counts[j]).map(|k| (bases[j] + k, 1.0)).collect();
93            constraints.push(LinearConstraint::eq(terms, 1.0));
94        }
95
96        // 2. Non-overlap for each pair (i, j) with i < j
97        // For each (k1, k2) where task i at offset k1 overlaps task j at offset k2:
98        // x_{i,k1} + x_{j,k2} <= 1
99        for i in 0..n {
100            for j in (i + 1)..n {
101                for k1 in 0..slot_counts[i] {
102                    let start_i = release[i] + k1 as u64;
103                    let end_i = start_i + lengths[i];
104                    for k2 in 0..slot_counts[j] {
105                        let start_j = release[j] + k2 as u64;
106                        let end_j = start_j + lengths[j];
107                        // Overlap if neither ends before the other starts
108                        if !(end_i <= start_j || end_j <= start_i) {
109                            constraints.push(LinearConstraint::le(
110                                vec![(bases[i] + k1, 1.0), (bases[j] + k2, 1.0)],
111                                1.0,
112                            ));
113                        }
114                    }
115                }
116            }
117        }
118
119        ReductionSWIToILP {
120            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize),
121            task_layout,
122        }
123    }
124}
125
126#[cfg(feature = "example-db")]
127pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
128    use crate::export::SolutionPair;
129
130    vec![crate::example_db::specs::RuleExampleSpec {
131        id: "sequencingwithinintervals_to_ilp",
132        build: || {
133            // 2 tasks: task 0 [r=0, d=3, l=2], task 1 [r=2, d=5, l=2]
134            // Task 0 can start at offset 0 or 1, task 1 can start at offset 0 or 1
135            // No overlap when both at offset 0: [0,2) and [2,4)
136            let source = SequencingWithinIntervals::new(vec![0, 2], vec![3, 5], vec![2, 2]);
137            let reduction: ReductionSWIToILP = ReduceTo::<ILP<bool>>::reduce_to(&source);
138            let solver = crate::solvers::ILPSolver::new();
139            let target_config = solver
140                .solve(reduction.target_problem())
141                .expect("canonical example should be feasible");
142            let source_config = reduction.extract_solution(&target_config);
143            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
144                source,
145                SolutionPair {
146                    source_config,
147                    target_config,
148                },
149            )
150        },
151    }]
152}
153
154#[cfg(test)]
155#[path = "../unit_tests/rules/sequencingwithinintervals_ilp.rs"]
156mod tests;
problemreductions/rules/sequencingwithinintervals_ilp.rs

problemreductions/rules/
sequencingwithinintervals_ilp.rs
