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(&self, target_solution: &[usize]) -> Vec<usize> {
37        let num_processors = self.num_processors;
38        (0..self.num_tasks)
39            .map(|j| {
40                (0..num_processors)
41                    .find(|&p| target_solution[j * num_processors + p] == 1)
42                    .unwrap_or(0)
43            })
44            .collect()
45    }
46}
47
48#[reduction(
49    overhead = {
50        num_vars = "num_tasks * num_processors",
51        num_constraints = "num_tasks + num_processors",
52    }
53)]
54impl ReduceTo<ILP<bool>> for MultiprocessorScheduling {
55    type Result = ReductionMSToILP;
56
57    fn reduce_to(&self) -> Self::Result {
58        let num_tasks = self.num_tasks();
59        let num_processors = self.num_processors();
60        let num_vars = num_tasks * num_processors;
61
62        let mut constraints = Vec::with_capacity(num_tasks + num_processors);
63
64        // Assignment constraints: for each task j, Σ_p x_{j,p} = 1
65        for j in 0..num_tasks {
66            let terms: Vec<(usize, f64)> = (0..num_processors)
67                .map(|p| (j * num_processors + p, 1.0))
68                .collect();
69            constraints.push(LinearConstraint::eq(terms, 1.0));
70        }
71
72        // Load constraints: for each processor p, Σ_j len_j * x_{j,p} ≤ deadline
73        let deadline = self.deadline() as f64;
74        for p in 0..num_processors {
75            let terms: Vec<(usize, f64)> = (0..num_tasks)
76                .map(|j| (j * num_processors + p, self.lengths()[j] as f64))
77                .collect();
78            constraints.push(LinearConstraint::le(terms, deadline));
79        }
80
81        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize);
82
83        ReductionMSToILP {
84            target,
85            num_tasks,
86            num_processors,
87        }
88    }
89}
90
91#[cfg(feature = "example-db")]
92pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
93    vec![crate::example_db::specs::RuleExampleSpec {
94        id: "multiprocessorscheduling_to_ilp",
95        build: || {
96            // 3 tasks with lengths [4, 5, 3], 2 processors, deadline 7
97            // Assignment: task 0 → processor 0, task 1 → processor 1, task 2 → processor 1
98            // Loads: processor 0 = 4, processor 1 = 5+3 = 8 (wait, try different)
99            // Assignment: task 0 → processor 0, task 1 → processor 1, task 2 → processor 0
100            // Loads: processor 0 = 4+3=7, processor 1 = 5 ≤ 7. Feasible!
101            let source = MultiprocessorScheduling::new(vec![4, 5, 3], 2, 7);
102            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
103        },
104    }]
105}
106
107#[cfg(test)]
108#[path = "../unit_tests/rules/multiprocessorscheduling_ilp.rs"]
109mod tests;
problemreductions/rules/multiprocessorscheduling_ilp.rs

problemreductions/rules/
multiprocessorscheduling_ilp.rs
