problemreductions/rules/
multiprocessorscheduling_ilp.rs

1//! Reduction from MultiprocessorScheduling to ILP (Integer Linear Programming).
2//!
3//! The Multiprocessor Scheduling feasibility problem can be formulated as a binary ILP:
4//! - Variables: Binary x_{j,p} (task j assigned to processor p), one-hot per task
5//! - Constraints: Σ_p x_{j,p} = 1 for each task j (assignment); Σ_j len_j·x_{j,p} ≤ deadline for each p (load)
6//! - Objective: Minimize 0 (feasibility)
7//! - Extraction: argmax_p x_{j,p} for each task j
8
9use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
10use crate::models::misc::MultiprocessorScheduling;
11use crate::reduction;
12use crate::rules::traits::{ReduceTo, ReductionResult};
13
14/// Result of reducing MultiprocessorScheduling to ILP.
15///
16/// Variable layout: x_{j,p} at index j * num_processors + p.
17/// - j ∈ 0..num_tasks, p ∈ 0..num_processors
18///
19/// Total: num_tasks * num_processors variables.
20#[derive(Debug, Clone)]
21pub struct ReductionMSToILP {
22    target: ILP<bool>,
23    num_tasks: usize,
24    num_processors: usize,
25}
26
27impl ReductionResult for ReductionMSToILP {
28    type Source = MultiprocessorScheduling;
29    type Target = ILP<bool>;
30
31    fn target_problem(&self) -> &ILP<bool> {
32        &self.target
33    }
34
35    /// Extract solution: for each task j, find the unique processor p where x_{j,p} = 1.
36    fn extract_solution(
37        &self,
38        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
39    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
40        crate::rules::traits::validate_target_witness(
41            self.target_problem(),
42            target_solution,
43            |value| value.value.is_some(),
44            "target ILP assignment is infeasible",
45        )?;
46
47        crate::rules::ilp_helpers::one_hot_decode_rows(
48            target_solution,
49            self.num_tasks,
50            self.num_processors,
51            0,
52        )
53    }
54}
55
56#[crate::aggregate_reduction(ilp_feasibility)]
57impl crate::rules::AggregateReductionResult for ReductionMSToILP {}
58
59#[reduction(transform = {
60    exact {
61        max_constraint_magnitude_bits = "max_numeric_magnitude_bits",
62        num_vars = "num_tasks * num_processors",
63        num_constraints = "num_tasks + num_processors",
64    },
65    upper_bound {
66        num_nonzeros = "(num_tasks * num_processors) * (num_tasks + num_processors)",
67    },
68})]
69impl ReduceTo<ILP<bool>> for MultiprocessorScheduling {
70    type Result = ReductionMSToILP;
71
72    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
73        let num_tasks = self.num_tasks();
74        let num_processors = self.num_processors();
75        let num_vars = num_tasks * num_processors;
76        let lengths = self.lengths();
77        let deadline = self.deadline();
78
79        let mut constraints = Vec::with_capacity(num_tasks + num_processors);
80
81        // Assignment constraints: for each task j, Σ_p x_{j,p} = 1
82        for j in 0..num_tasks {
83            let terms: Vec<(usize, i64)> = (0..num_processors)
84                .map(|p| (j * num_processors + p, 1))
85                .collect();
86            constraints.push(LinearConstraint::eq(terms, 1));
87        }
88
89        // Load constraints: for each processor p, Σ_j len_j * x_{j,p} ≤ deadline
90        for p in 0..num_processors {
91            let terms: Vec<(usize, i64)> = (0..num_tasks)
92                .map(|j| (j * num_processors + p, lengths[j]))
93                .collect();
94            constraints.push(LinearConstraint::le(terms, deadline));
95        }
96
97        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
98            .map_err(Self::target_construction)?;
99
100        Ok(ReductionMSToILP {
101            target,
102            num_tasks,
103            num_processors,
104        })
105    }
106}
107
108#[cfg(feature = "example-db")]
109pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
110    vec![crate::example_db::specs::RuleExampleSpec {
111        id: "multiprocessorscheduling_to_ilp",
112        build: || {
113            // 3 tasks with lengths [4, 5, 3], 2 processors, deadline 7
114            // Assignment: task 0 → processor 0, task 1 → processor 1, task 2 → processor 1
115            // Loads: processor 0 = 4, processor 1 = 5+3 = 8 (wait, try different)
116            // Assignment: task 0 → processor 0, task 1 → processor 1, task 2 → processor 0
117            // Loads: processor 0 = 4+3=7, processor 1 = 5 ≤ 7. Feasible!
118            let source = MultiprocessorScheduling::new(vec![4, 5, 3], 2, 7);
119            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
120        },
121    }]
122}
123
124#[cfg(test)]
125#[path = "../unit_tests/rules/multiprocessorscheduling_ilp.rs"]
126mod tests;
problemreductions/rules/multiprocessorscheduling_ilp.rs

problemreductions/rules/
multiprocessorscheduling_ilp.rs
