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(
38        &self,
39        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
40    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
41        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
42
43        crate::rules::ilp_helpers::one_hot_decode_rows(
44            target_solution,
45            self.num_links,
46            self.num_capacities,
47            0,
48        )
49    }
50}
51
52#[reduction(transform = {
53    exact {
54        max_constraint_magnitude_bits = "max_delay_bits",
55        num_vars = "num_links * num_capacities",
56        num_constraints = "num_links + 1",
57    },
58    upper_bound {
59        num_nonzeros = "(num_links * num_capacities) * (num_links + 1)",
60    },
61})]
62impl ReduceTo<ILP<bool>> for CapacityAssignment {
63    type Result = ReductionCAToILP;
64
65    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
66        let num_links = self.num_links();
67        let num_capacities = self.num_capacities();
68        let num_vars = num_links * num_capacities;
69        let delay = self.delay();
70        let cost = self.cost();
71        let delay_budget = self.delay_budget();
72
73        let mut constraints = Vec::with_capacity(num_links + 1);
74
75        // Assignment constraints: for each link l, Σ_c x_{l,c} = 1
76        for l in 0..num_links {
77            let terms: Vec<(usize, i64)> = (0..num_capacities)
78                .map(|c| (l * num_capacities + c, 1))
79                .collect();
80            constraints.push(LinearConstraint::eq(terms, 1));
81        }
82
83        // Delay budget constraint: Σ_{l,c} delay[l][c] * x_{l,c} ≤ delay_budget
84        let mut delay_terms = Vec::with_capacity(num_vars);
85        for (link, row) in delay.iter().enumerate() {
86            for (capacity, &value) in row.iter().enumerate() {
87                delay_terms.push((link * num_capacities + capacity, value));
88            }
89        }
90        constraints.push(LinearConstraint::le(delay_terms, delay_budget));
91
92        // Objective: minimize total cost
93        let mut objective = Vec::with_capacity(num_vars);
94        for (link, row) in cost.iter().enumerate() {
95            for (capacity, &value) in row.iter().enumerate() {
96                objective.push((link * num_capacities + capacity, value));
97            }
98        }
99
100        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
101            .map_err(Self::target_construction)?;
102
103        Ok(ReductionCAToILP {
104            target,
105            num_links,
106            num_capacities,
107        })
108    }
109}
110
111#[cfg(feature = "example-db")]
112pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
113    vec![crate::example_db::specs::RuleExampleSpec {
114        id: "capacityassignment_to_ilp",
115        build: || {
116            // 2 links, 2 capacity levels
117            // cost: [[1,3],[2,4]], delay: [[8,4],[7,3]]
118            // delay_budget=12
119            // Minimize cost subject to total_delay ≤ 12.
120            // link 0 → cap 0, link 1 → cap 0: cost=3, delay=15 > 12 — infeasible
121            // link 0 → cap 1, link 1 → cap 0: cost=5, delay=11 ≤ 12 — feasible
122            // link 0 → cap 0, link 1 → cap 1: cost=5, delay=11 ≤ 12 — feasible (tied)
123            // link 0 → cap 1, link 1 → cap 1: cost=7, delay=7 ≤ 12 — feasible
124            // Optimal: cost=5 at [1,0] or [0,1]
125            let source = CapacityAssignment::new(
126                vec![1, 2],
127                vec![vec![1, 3], vec![2, 4]],
128                vec![vec![8, 4], vec![7, 3]],
129                12,
130            );
131            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
132        },
133    }]
134}
135
136#[cfg(test)]
137#[path = "../unit_tests/rules/capacityassignment_ilp.rs"]
138mod tests;
problemreductions/rules/capacityassignment_ilp.rs

problemreductions/rules/
capacityassignment_ilp.rs
