problemreductions/rules/
precedenceconstrainedscheduling_ilp.rs

1//! Reduction from PrecedenceConstrainedScheduling to `ILP<bool>`.
2//!
3//! Uses a time-indexed binary formulation:
4//! - Variables: Binary x_{j,t} where x_{j,t} = 1 iff task j is scheduled at time slot t.
5//! - Variable index: j * deadline + t  for j in 0..num_tasks, t in 0..deadline
6//! - Constraints:
7//!   1. One-hot: Σ_t x_{j,t} = 1 for each task j
8//!   2. Capacity: Σ_j x_{j,t} ≤ m for each time slot t
9//!   3. Precedence: Σ_t t·x_{j,t} ≥ Σ_t t·x_{i,t} + 1 for each (i,j) in precedences
10//! - Objective: Minimize 0 (feasibility)
11//! - Extraction: For each task j, find argmax_t x_{j,t}
12
13use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
14use crate::models::misc::PrecedenceConstrainedScheduling;
15use crate::reduction;
16use crate::rules::traits::{ReduceTo, ReductionResult};
17
18/// Result of reducing PrecedenceConstrainedScheduling to `ILP<bool>`.
19///
20/// Variable layout: x_{j,t} at index j * deadline + t
21/// for j in 0..num_tasks, t in 0..deadline.
22#[derive(Debug, Clone)]
23pub struct ReductionPCSToILP {
24    target: ILP<bool>,
25    num_tasks: usize,
26    deadline: usize,
27}
28
29impl ReductionResult for ReductionPCSToILP {
30    type Source = PrecedenceConstrainedScheduling;
31    type Target = ILP<bool>;
32
33    fn target_problem(&self) -> &ILP<bool> {
34        &self.target
35    }
36
37    /// Extract schedule from ILP solution.
38    ///
39    /// For each task j, find the time slot t where x_{j,t} = 1.
40    /// Returns the time slot for each task (matching the `dims()` encoding of PCS).
41    fn extract_solution(
42        &self,
43        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
44    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
45        crate::rules::traits::validate_target_witness(
46            self.target_problem(),
47            target_solution,
48            |value| value.value.is_some(),
49            "target ILP assignment is infeasible",
50        )?;
51
52        crate::rules::ilp_helpers::one_hot_decode_rows(
53            target_solution,
54            self.num_tasks,
55            self.deadline,
56            0,
57        )
58    }
59}
60
61#[crate::aggregate_reduction(ilp_feasibility)]
62impl crate::rules::AggregateReductionResult for ReductionPCSToILP {}
63
64#[reduction(transform = {
65    exact {
66        num_vars = "num_tasks * deadline",
67        num_constraints = "num_tasks + deadline + num_precedences",
68    },
69    upper_bound {
70        max_constraint_magnitude_bits = "num_tasks + deadline + 1",
71        num_nonzeros = "(num_tasks * deadline) * (num_tasks + deadline + num_precedences)",
72    },
73})]
74impl ReduceTo<ILP<bool>> for PrecedenceConstrainedScheduling {
75    type Result = ReductionPCSToILP;
76
77    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
78        let n = self.num_tasks();
79        let d = usize::try_from(self.deadline()).map_err(|_| {
80            crate::rules::ReductionError::integer_overflow::<
81                PrecedenceConstrainedScheduling,
82                ILP<bool>,
83            >("validated deadline must fit usize")
84        })?;
85        let num_vars = n * d;
86
87        // x_{j,t} variable index
88        let var = |j: usize, t: usize| j * d + t;
89        // More processors than tasks cannot admit any additional schedules.
90        let processor_count = Self::exact_i64(
91            self.num_processors().min(n),
92            "encoding the processor capacity",
93        )?;
94
95        let mut constraints = Vec::new();
96
97        // 1. One-hot: Σ_t x_{j,t} = 1 for each task j
98        for j in 0..n {
99            let terms: Vec<(usize, i64)> = (0..d).map(|t| (var(j, t), 1)).collect();
100            constraints.push(LinearConstraint::eq(terms, 1));
101        }
102
103        // 2. Capacity: Σ_j x_{j,t} ≤ m for each time slot t
104        for t in 0..d {
105            let terms: Vec<(usize, i64)> = (0..n).map(|j| (var(j, t), 1)).collect();
106            constraints.push(LinearConstraint::le(terms, processor_count));
107        }
108
109        // 3. Precedence: Σ_t t·x_{j,t} ≥ Σ_t t·x_{i,t} + 1 for each (i,j)
110        // Rearranged: Σ_t t·x_{j,t} - Σ_t t·x_{i,t} ≥ 1
111        for &(i, j) in self.precedences() {
112            let mut terms: Vec<(usize, i64)> = Vec::new();
113            for t in 0..d {
114                let t_i64 = Self::exact_i64(t, "encoding a time slot")?;
115                terms.push((var(j, t), t_i64));
116                terms.push((var(i, t), -t_i64));
117            }
118            constraints.push(LinearConstraint::ge(terms, 1));
119        }
120
121        Ok(ReductionPCSToILP {
122            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
123                .map_err(Self::target_construction)?,
124            num_tasks: n,
125            deadline: d,
126        })
127    }
128}
129
130#[cfg(feature = "example-db")]
131pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
132    vec![crate::example_db::specs::RuleExampleSpec {
133        id: "precedenceconstrainedscheduling_to_ilp",
134        build: || {
135            // 3 tasks, 2 processors, deadline 2, with task 0 < task 2
136            let source = PrecedenceConstrainedScheduling::new(3, 2, 2, vec![(0, 2)]);
137            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
138        },
139    }]
140}
141
142#[cfg(test)]
143#[path = "../unit_tests/rules/precedenceconstrainedscheduling_ilp.rs"]
144mod tests;
problemreductions/rules/precedenceconstrainedscheduling_ilp.rs

problemreductions/rules/
precedenceconstrainedscheduling_ilp.rs
