problemreductions/rules/
preemptivescheduling_ilp.rs

1//! Reduction from PreemptiveScheduling to `ILP<i64>`.
2//!
3//! Time-indexed formulation with an auxiliary integer makespan variable:
4//! - Variables: binary x_{t,u} for t in 0..n, u in 0..D_max (task t processed at slot u),
5//!   plus integer M (the makespan), indexed at position n*D_max.
6//! - Variable index for x_{t,u}: t * D_max + u.
7//! - Variable index for M: n * D_max.
8//! - Constraints:
9//!   1. Work: Σ_u x_{t,u} = l(t) for each task t
10//!   2. Capacity: Σ_t x_{t,u} ≤ m for each time slot u
11//!   3. Precedence: for each (pred, succ) and each slot u,
12//!      `l(pred) * x_{succ,u} ≤ Σ_{v=0}^{u-1} x_{pred,v}`
13//!      This ensures succ can only be active at slot u if pred has already
14//!      completed all l(pred) units of work in slots 0..u-1.
15//!   4. Makespan lower bound: M ≥ (u+1) when x_{t,u}=1:
16//!      `M - (u+1)*x_{t,u} ≥ 0` for all t,u
17//!   5. Binary bounds: x_{t,u} ≤ 1 for each t,u
18//!      (since `ILP<i64>` uses non-negative integer domain)
19//! - Objective: Minimize M.
20//!
21//! Note: `ILP<i64>` treats all variables as non-negative integers. Binary constraints
22//! on x_{t,u} are enforced by x_{t,u} ≤ 1.
23
24use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
25use crate::models::misc::PreemptiveScheduling;
26use crate::reduction;
27use crate::rules::traits::{ReduceTo, ReductionResult};
28
29/// Result of reducing PreemptiveScheduling to `ILP<i64>`.
30///
31/// Variable layout:
32/// - x_{t,u} at index t * D_max + u for t in 0..n, u in 0..D_max  (n*D_max vars)
33/// - M at index n * D_max  (1 integer var)
34///
35/// Total: n * D_max + 1 variables.
36#[derive(Debug, Clone)]
37pub struct ReductionPSToILP {
38    target: ILP<i64>,
39    num_tasks: usize,
40    d_max: usize,
41}
42
43impl ReductionResult for ReductionPSToILP {
44    type Source = PreemptiveScheduling;
45    type Target = ILP<i64>;
46
47    fn target_problem(&self) -> &ILP<i64> {
48        &self.target
49    }
50
51    /// Extract schedule from ILP solution.
52    ///
53    /// Returns a binary config of length n * D_max: `config[t * D_max + u] = x_{t,u}`.
54    fn extract_solution(
55        &self,
56        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
57    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
58        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
59
60        Ok((0..self.num_tasks)
61            .map(|task| {
62                (0..self.d_max)
63                    .map(|time| target_solution[task * self.d_max + time] == 1)
64                    .collect()
65            })
66            .collect())
67    }
68}
69
70#[reduction(
71    transform = exact {
72        num_vars = "num_tasks * d_max + 1",
73        num_constraints = "num_tasks + d_max + num_precedences * d_max + 2 * num_tasks * d_max",
74    },
75    unavailable = {
76        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
77    }
78)]
79impl ReduceTo<ILP<i64>> for PreemptiveScheduling {
80    type Result = ReductionPSToILP;
81
82    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
83        let n = self.num_tasks();
84        let d = self.d_max();
85        let num_task_vars = n * d;
86        let m_var = num_task_vars; // index of the makespan variable M
87        let num_vars = num_task_vars + 1;
88        let lengths = self.lengths();
89        let processor_count =
90            Self::exact_i64(self.num_processors(), "encoding the processor capacity")?;
91
92        let x = |t: usize, u: usize| t * d + u;
93
94        let mut constraints = Vec::new();
95
96        // 1. Work constraints: Σ_u x_{t,u} = l(t) for each task t
97        for (t, &length) in lengths.iter().enumerate() {
98            let terms: Vec<(usize, i64)> = (0..d).map(|u| (x(t, u), 1)).collect();
99            constraints.push(LinearConstraint::eq(terms, length));
100        }
101
102        // 2. Capacity constraints: Σ_t x_{t,u} ≤ m for each time slot u
103        for u in 0..d {
104            let terms: Vec<(usize, i64)> = (0..n).map(|t| (x(t, u), 1)).collect();
105            constraints.push(LinearConstraint::le(terms, processor_count));
106        }
107
108        // 3. Precedence constraints: for each (pred, succ) and each slot u:
109        //    l(pred) * x_{succ,u} ≤ Σ_{v=0}^{u-1} x_{pred,v}
110        //    i.e. l(pred) * x_{succ,u} - Σ_{v=0}^{u-1} x_{pred,v} ≤ 0
111        //
112        //    Interpretation: succ can only be active at slot u once pred has
113        //    accumulated all l(pred) units of work in strictly earlier slots.
114        for &(pred, succ) in self.precedences() {
115            let l_pred = lengths[pred];
116            for u in 0..d {
117                // Σ_{v=0}^{u-1} x_{pred,v} - l(pred)*x_{succ,u} ≥ 0
118                // i.e. l(pred)*x_{succ,u} - Σ_{v<u} x_{pred,v} ≤ 0
119                let mut terms: Vec<(usize, i64)> = Vec::new();
120                // Cumulative pred work up to u-1
121                for v in 0..u {
122                    terms.push((x(pred, v), -1));
123                }
124                terms.push((x(succ, u), l_pred));
125                constraints.push(LinearConstraint::le(terms, 0));
126            }
127        }
128
129        // 4. Makespan lower bound: M - (u+1)*x_{t,u} ≥ 0 for all t,u
130        for t in 0..n {
131            for u in 0..d {
132                constraints.push(LinearConstraint::ge(
133                    vec![
134                        (m_var, 1),
135                        (x(t, u), -Self::exact_i64(u + 1, "encoding a time slot")?),
136                    ],
137                    0,
138                ));
139            }
140        }
141
142        // 5. Binary upper bound: x_{t,u} ≤ 1 for all t,u
143        for t in 0..n {
144            for u in 0..d {
145                constraints.push(LinearConstraint::le(vec![(x(t, u), 1)], 1));
146            }
147        }
148
149        // Objective: minimize M
150        let objective = vec![(m_var, 1)];
151
152        Ok(ReductionPSToILP {
153            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
154                .map_err(Self::target_construction)?,
155            num_tasks: n,
156            d_max: d,
157        })
158    }
159}
160
161#[cfg(feature = "example-db")]
162pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
163    vec![crate::example_db::specs::RuleExampleSpec {
164        id: "preemptivescheduling_to_ilp",
165        build: || {
166            // 3 tasks, lengths [2,1,2], 2 processors, precedence (0,2)
167            let source = PreemptiveScheduling::new(vec![2, 1, 2], 2, vec![(0, 2)]).unwrap();
168            crate::example_db::specs::rule_example_via_ilp::<_, i64>(source)
169        },
170    }]
171}
172
173#[cfg(test)]
174#[path = "../unit_tests/rules/preemptivescheduling_ilp.rs"]
175mod tests;
problemreductions/rules/preemptivescheduling_ilp.rs

problemreductions/rules/
preemptivescheduling_ilp.rs
