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

problemreductions/rules/
capacityassignment_ilp.rs
