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_witness(
37            self.target_problem(),
38            target_solution,
39            |value| value.value.is_some(),
40            "target ILP assignment is infeasible",
41        )?;
42
43        crate::rules::ilp_helpers::one_hot_decode_rows(
44            target_solution,
45            self.num_tasks,
46            self.deadline,
47            0,
48        )
49    }
50}
51
52#[crate::aggregate_reduction(ilp_feasibility)]
53impl crate::rules::AggregateReductionResult for ReductionRCSToILP {}
54
55#[reduction(transform = upper_bound {
56    max_constraint_magnitude_bits = "max_resource_bits + num_tasks",
57    num_vars = "num_tasks^2",
58    num_constraints = "num_tasks * (num_resources + 2)",
59    num_nonzeros = "num_tasks^3 * (num_resources + 2)",
60})]
61impl ReduceTo<ILP<bool>> for ResourceConstrainedScheduling {
62    type Result = ReductionRCSToILP;
63
64    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
65        let n = self.num_tasks();
66        // Unit tasks can pack occupied slots without gaps; at most n slots
67        // and n processors are needed, regardless of the numeric deadline.
68        let d = usize::try_from(self.deadline())
69            .map_err(|_| {
70                crate::rules::ReductionError::invalid_target::<
71                    ResourceConstrainedScheduling,
72                    ILP<bool>,
73                >("deadline does not fit the structural usize domain")
74            })?
75            .min(n);
76        let r = self.num_resources();
77        let resource_requirements = self.resource_requirements();
78        let resource_bounds = self.resource_bounds();
79        let num_vars = n * d;
80
81        let var = |j: usize, t: usize| -> usize { j * d + t };
82        let processor_count = Self::exact_i64(
83            self.num_processors().min(n),
84            "encoding the processor capacity",
85        )?;
86
87        let mut constraints = Vec::new();
88
89        // 1. Each task in exactly one slot: Σ_t x_{j,t} = 1 for all j
90        for j in 0..n {
91            let terms: Vec<(usize, i64)> = (0..d).map(|t| (var(j, t), 1)).collect();
92            constraints.push(LinearConstraint::eq(terms, 1));
93        }
94
95        // 2. Processor capacity: Σ_j x_{j,t} <= m for each time slot t
96        for t in 0..d {
97            let terms: Vec<(usize, i64)> = (0..n).map(|j| (var(j, t), 1)).collect();
98            constraints.push(LinearConstraint::le(terms, processor_count));
99        }
100
101        // 3. Resource bounds: Σ_j r_{j,q} * x_{j,t} <= B_q for all q, t
102        for q in 0..r {
103            for t in 0..d {
104                let terms: Vec<(usize, i64)> = (0..n)
105                    .map(|j| (var(j, t), resource_requirements[j][q]))
106                    .collect();
107                constraints.push(LinearConstraint::le(terms, resource_bounds[q]));
108            }
109        }
110
111        Ok(ReductionRCSToILP {
112            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
113                .map_err(Self::target_construction)?,
114            num_tasks: n,
115            deadline: d,
116        })
117    }
118}
119
120#[cfg(feature = "example-db")]
121pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
122    vec![crate::example_db::specs::RuleExampleSpec {
123        id: "resourceconstrainedscheduling_to_ilp",
124        build: || {
125            // 6 tasks, 3 processors, 1 resource with bound 20, deadline 2
126            let source = ResourceConstrainedScheduling::new(
127                3,
128                vec![20],
129                vec![vec![6], vec![7], vec![7], vec![6], vec![8], vec![6]],
130                2,
131            )
132            .unwrap();
133            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
134        },
135    }]
136}
137
138#[cfg(test)]
139#[path = "../unit_tests/rules/resourceconstrainedscheduling_ilp.rs"]
140mod tests;
problemreductions/rules/resourceconstrainedscheduling_ilp.rs

problemreductions/rules/
resourceconstrainedscheduling_ilp.rs
