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), 0 <= k <= 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 = max(0, d_i - r_i - l_i + 1) counts 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 (0 = 1 for an empty start domain).
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 = max(0, 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(
47        &self,
48        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
49    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
50        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
51
52        self.task_layout
53            .iter()
54            .enumerate()
55            .map(|(task, &(base, count))| {
56                let mut selected = (0..count).filter(|&offset| target_solution[base + offset] == 1);
57                match (selected.next(), selected.next()) {
58                    (Some(offset), None) => Ok(offset),
59                    (None, _) => Err(crate::rules::ExtractionError::invalid(format!(
60                        "task {task} has no selected start time"
61                    ))),
62                    (Some(_), Some(_)) => Err(crate::rules::ExtractionError::invalid(format!(
63                        "task {task} has multiple selected start times"
64                    ))),
65                }
66            })
67            .collect()
68    }
69}
70
71#[reduction(
72    transform = upper_bound {
73        num_vars = "num_start_slots",
74        num_constraints = "num_start_slots^2 + num_tasks",
75    },
76    unavailable = {
77        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
78    }
79)]
80impl ReduceTo<ILP<bool>> for SequencingWithinIntervals {
81    type Result = ReductionSWIToILP;
82
83    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
84        let n = self.num_tasks();
85        let release = self.release_times();
86        let lengths = self.lengths();
87
88        // Compute per-task variable layout: how many start slots each task has
89        let overflow = |operation| {
90            crate::rules::ReductionError::integer_overflow::<Self, ILP<bool>>(operation)
91        };
92        let slot_counts: Vec<usize> = self.start_slot_counts().collect();
93
94        let mut bases = vec![0usize; n];
95        for j in 1..n {
96            bases[j] = bases[j - 1]
97                .checked_add(slot_counts[j - 1])
98                .ok_or_else(|| overflow("computing task variable offsets"))?;
99        }
100        let num_vars = bases
101            .last()
102            .copied()
103            .unwrap_or(0)
104            .checked_add(slot_counts.last().copied().unwrap_or(0))
105            .ok_or_else(|| overflow("computing the ILP variable count"))?;
106
107        let task_layout: Vec<(usize, usize)> = (0..n).map(|j| (bases[j], slot_counts[j])).collect();
108
109        let mut constraints = Vec::new();
110
111        // 1. One-hot per task
112        for j in 0..n {
113            let terms: Vec<(usize, i64)> = (0..slot_counts[j]).map(|k| (bases[j] + k, 1)).collect();
114            constraints.push(LinearConstraint::eq(terms, 1));
115        }
116
117        // 2. Non-overlap for each pair (i, j) with i < j
118        // For each (k1, k2) where task i at offset k1 overlaps task j at offset k2:
119        // x_{i,k1} + x_{j,k2} <= 1
120        for i in 0..n {
121            for j in (i + 1)..n {
122                for k1 in 0..slot_counts[i] {
123                    let offset_i = Self::exact_i64(k1, "converting a task start offset to i64")?;
124                    let start_i = release[i]
125                        .checked_add(offset_i)
126                        .ok_or_else(|| overflow("computing a task start time"))?;
127                    let end_i = start_i
128                        .checked_add(lengths[i])
129                        .ok_or_else(|| overflow("computing a task end time"))?;
130                    for k2 in 0..slot_counts[j] {
131                        let offset_j =
132                            Self::exact_i64(k2, "converting a task start offset to i64")?;
133                        let start_j = release[j]
134                            .checked_add(offset_j)
135                            .ok_or_else(|| overflow("computing a task start time"))?;
136                        let end_j = start_j
137                            .checked_add(lengths[j])
138                            .ok_or_else(|| overflow("computing a task end time"))?;
139                        // Overlap if neither ends before the other starts
140                        if !(end_i <= start_j || end_j <= start_i) {
141                            constraints.push(LinearConstraint::le(
142                                vec![(bases[i] + k1, 1), (bases[j] + k2, 1)],
143                                1,
144                            ));
145                        }
146                    }
147                }
148            }
149        }
150
151        Ok(ReductionSWIToILP {
152            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
153                .map_err(Self::target_construction)?,
154            task_layout,
155        })
156    }
157}
158
159#[cfg(feature = "example-db")]
160pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
161    use crate::export::SolutionPair;
162
163    vec![crate::example_db::specs::RuleExampleSpec {
164        id: "sequencingwithinintervals_to_ilp",
165        build: || {
166            // 2 tasks: task 0 [r=0, d=3, l=2], task 1 [r=2, d=5, l=2]
167            // Task 0 can start at offset 0 or 1, task 1 can start at offset 0 or 1
168            // No overlap when both at offset 0: [0,2) and [2,4)
169            let source =
170                SequencingWithinIntervals::new(vec![0, 2], vec![3, 5], vec![2, 2]).unwrap();
171            let reduction: ReductionSWIToILP =
172                ReduceTo::<ILP<bool>>::reduce_to(&source).expect("reduction should succeed");
173            let solver = crate::solvers::ILPSolver::new();
174            let target_config = solver
175                .solve(reduction.target_problem())
176                .expect("canonical example should be feasible");
177            let source_config = reduction.extract_solution(&target_config).unwrap();
178            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
179                source,
180                SolutionPair {
181                    source_config: serde_json::to_value(source_config)
182                        .expect("solution serialization must succeed"),
183                    target_config: serde_json::to_value(target_config)
184                        .expect("solution serialization must succeed"),
185                },
186            )
187        },
188    }]
189}
190
191#[cfg(test)]
192#[path = "../unit_tests/rules/sequencingwithinintervals_ilp.rs"]
193mod tests;
problemreductions/rules/sequencingwithinintervals_ilp.rs

problemreductions/rules/
sequencingwithinintervals_ilp.rs
