problemreductions/rules/
capacityassignment_ilp.rs

1//! Reduction from CapacityAssignment to ILP (Integer Linear Programming).
2//!
3//! The Capacity Assignment optimization problem can be formulated as a binary ILP:
4//! - Variables: Binary x_{l,c} (link l gets capacity c), one-hot per link
5//! - Constraints: Σ_c x_{l,c} = 1 for each link l (assignment);
6//!   Σ_{l,c} delay[l][c]·x_{l,c} ≤ delay_budget
7//! - Objective: Minimize Σ_{l,c} cost[l][c]·x_{l,c}
8//! - Extraction: argmax_c x_{l,c} for each link l
9
10use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
11use crate::models::misc::CapacityAssignment;
12use crate::reduction;
13use crate::rules::traits::{ReduceTo, ReductionResult};
14
15/// Result of reducing CapacityAssignment to ILP.
16///
17/// Variable layout: x_{l,c} at index l * num_capacities + c.
18/// - l ∈ 0..num_links, c ∈ 0..num_capacities
19///
20/// Total: num_links * num_capacities variables.
21#[derive(Debug, Clone)]
22pub struct ReductionCAToILP {
23    target: ILP<bool>,
24    num_links: usize,
25    num_capacities: usize,
26}
27
28impl ReductionResult for ReductionCAToILP {
29    type Source = CapacityAssignment;
30    type Target = ILP<bool>;
31
32    fn target_problem(&self) -> &ILP<bool> {
33        &self.target
34    }
35
36    /// Extract solution: for each link l, find the unique capacity c where x_{l,c} = 1.
37    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
38        let num_capacities = self.num_capacities;
39        (0..self.num_links)
40            .map(|l| {
41                (0..num_capacities)
42                    .find(|&c| target_solution[l * num_capacities + c] == 1)
43                    .unwrap_or(0)
44            })
45            .collect()
46    }
47}
48
49#[reduction(
50    overhead = {
51        num_vars = "num_links * num_capacities",
52        num_constraints = "num_links + 1",
53    }
54)]
55impl ReduceTo<ILP<bool>> for CapacityAssignment {
56    type Result = ReductionCAToILP;
57
58    fn reduce_to(&self) -> Self::Result {
59        let num_links = self.num_links();
60        let num_capacities = self.num_capacities();
61        let num_vars = num_links * num_capacities;
62
63        let mut constraints = Vec::with_capacity(num_links + 1);
64
65        // Assignment constraints: for each link l, Σ_c x_{l,c} = 1
66        for l in 0..num_links {
67            let terms: Vec<(usize, f64)> = (0..num_capacities)
68                .map(|c| (l * num_capacities + c, 1.0))
69                .collect();
70            constraints.push(LinearConstraint::eq(terms, 1.0));
71        }
72
73        // Delay budget constraint: Σ_{l,c} delay[l][c] * x_{l,c} ≤ delay_budget
74        let delay_terms: Vec<(usize, f64)> = (0..num_links)
75            .flat_map(|l| {
76                (0..num_capacities)
77                    .map(move |c| (l * num_capacities + c, self.delay()[l][c] as f64))
78            })
79            .collect();
80        constraints.push(LinearConstraint::le(
81            delay_terms,
82            self.delay_budget() as f64,
83        ));
84
85        // Objective: minimize total cost
86        let objective: Vec<(usize, f64)> = (0..num_links)
87            .flat_map(|l| {
88                (0..num_capacities).map(move |c| (l * num_capacities + c, self.cost()[l][c] as f64))
89            })
90            .collect();
91
92        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
93
94        ReductionCAToILP {
95            target,
96            num_links,
97            num_capacities,
98        }
99    }
100}
101
102#[cfg(feature = "example-db")]
103pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
104    vec![crate::example_db::specs::RuleExampleSpec {
105        id: "capacityassignment_to_ilp",
106        build: || {
107            // 2 links, 2 capacity levels
108            // cost: [[1,3],[2,4]], delay: [[8,4],[7,3]]
109            // delay_budget=12
110            // Minimize cost subject to total_delay ≤ 12.
111            // link 0 → cap 0, link 1 → cap 0: cost=3, delay=15 > 12 — infeasible
112            // link 0 → cap 1, link 1 → cap 0: cost=5, delay=11 ≤ 12 — feasible
113            // link 0 → cap 0, link 1 → cap 1: cost=5, delay=11 ≤ 12 — feasible (tied)
114            // link 0 → cap 1, link 1 → cap 1: cost=7, delay=7 ≤ 12 — feasible
115            // Optimal: cost=5 at [1,0] or [0,1]
116            let source = CapacityAssignment::new(
117                vec![1, 2],
118                vec![vec![1, 3], vec![2, 4]],
119                vec![vec![8, 4], vec![7, 3]],
120                12,
121            );
122            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
123        },
124    }]
125}
126
127#[cfg(test)]
128#[path = "../unit_tests/rules/capacityassignment_ilp.rs"]
129mod tests;
problemreductions/rules/capacityassignment_ilp.rs

problemreductions/rules/
capacityassignment_ilp.rs
