problemreductions/rules/
resourceconstrainedscheduling_ilp.rs

1//! Reduction from ResourceConstrainedScheduling to `ILP<bool>`.
2//!
3//! Time-indexed binary formulation: x_{j,t} = 1 iff task j runs in slot t.
4//! Each task in exactly one slot; processor capacity and resource bounds
5//! enforced per time slot.
6
7use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
8use crate::models::misc::ResourceConstrainedScheduling;
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11
12/// Result of reducing ResourceConstrainedScheduling to `ILP<bool>`.
13///
14/// Variable layout: x_{j,t} at index `j * D + t`
15/// for j in 0..n, t in 0..D.
16#[derive(Debug, Clone)]
17pub struct ReductionRCSToILP {
18    target: ILP<bool>,
19    num_tasks: usize,
20    deadline: usize,
21}
22
23impl ReductionResult for ReductionRCSToILP {
24    type Source = ResourceConstrainedScheduling;
25    type Target = ILP<bool>;
26
27    fn target_problem(&self) -> &ILP<bool> {
28        &self.target
29    }
30
31    /// Extract: for each task j, find the unique slot t with x_{j,t} = 1.
32    fn extract_solution(
33        &self,
34        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
35    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
36        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
37
38        crate::rules::ilp_helpers::one_hot_decode_rows(
39            target_solution,
40            self.num_tasks,
41            self.deadline,
42            0,
43        )
44    }
45}
46
47#[reduction(
48    transform = exact {
49        num_vars = "num_tasks * deadline",
50        num_constraints = "num_tasks + deadline + num_resources * deadline",
51    },
52    unavailable = {
53        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
54    }
55)]
56impl ReduceTo<ILP<bool>> for ResourceConstrainedScheduling {
57    type Result = ReductionRCSToILP;
58
59    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
60        let n = self.num_tasks();
61        let d =
62            usize::try_from(self.deadline()).map_err(|_| {
63                crate::rules::ReductionError::invalid_target::<
64                    ResourceConstrainedScheduling,
65                    ILP<bool>,
66                >("deadline does not fit the structural usize domain")
67            })?;
68        let r = self.num_resources();
69        let resource_requirements = self.resource_requirements();
70        let resource_bounds = self.resource_bounds();
71        let num_vars = n * d;
72
73        let var = |j: usize, t: usize| -> usize { j * d + t };
74        let processor_count =
75            Self::exact_i64(self.num_processors(), "encoding the processor capacity")?;
76
77        let mut constraints = Vec::new();
78
79        // 1. Each task in exactly one slot: Σ_t x_{j,t} = 1 for all j
80        for j in 0..n {
81            let terms: Vec<(usize, i64)> = (0..d).map(|t| (var(j, t), 1)).collect();
82            constraints.push(LinearConstraint::eq(terms, 1));
83        }
84
85        // 2. Processor capacity: Σ_j x_{j,t} <= m for each time slot t
86        for t in 0..d {
87            let terms: Vec<(usize, i64)> = (0..n).map(|j| (var(j, t), 1)).collect();
88            constraints.push(LinearConstraint::le(terms, processor_count));
89        }
90
91        // 3. Resource bounds: Σ_j r_{j,q} * x_{j,t} <= B_q for all q, t
92        for q in 0..r {
93            for t in 0..d {
94                let terms: Vec<(usize, i64)> = (0..n)
95                    .map(|j| (var(j, t), resource_requirements[j][q]))
96                    .collect();
97                constraints.push(LinearConstraint::le(terms, resource_bounds[q]));
98            }
99        }
100
101        Ok(ReductionRCSToILP {
102            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
103                .map_err(Self::target_construction)?,
104            num_tasks: n,
105            deadline: d,
106        })
107    }
108}
109
110#[cfg(feature = "example-db")]
111pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
112    vec![crate::example_db::specs::RuleExampleSpec {
113        id: "resourceconstrainedscheduling_to_ilp",
114        build: || {
115            // 6 tasks, 3 processors, 1 resource with bound 20, deadline 2
116            let source = ResourceConstrainedScheduling::new(
117                3,
118                vec![20],
119                vec![vec![6], vec![7], vec![7], vec![6], vec![8], vec![6]],
120                2,
121            )
122            .unwrap();
123            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
124        },
125    }]
126}
127
128#[cfg(test)]
129#[path = "../unit_tests/rules/resourceconstrainedscheduling_ilp.rs"]
130mod tests;
problemreductions/rules/resourceconstrainedscheduling_ilp.rs

problemreductions/rules/
resourceconstrainedscheduling_ilp.rs
