problemreductions/rules/
multiplecopyfileallocation_ilp.rs

1//! Reduction from MultipleCopyFileAllocation to ILP (Integer Linear Programming).
2//!
3//! Binary variable x_v (1 if a file copy is placed at vertex v) and binary
4//! variable y_{v,u} (1 if vertex v is served by the copy at vertex u).
5//!
6//! Variable layout (all binary):
7//! - `x_v` for each vertex v, indices `0..n`
8//! - `y_{v,u}` for each ordered pair (v, u), index `n + v*n + u`
9//!
10//! Constraints:
11//! - Assignment: ∀v: Σ_u y_{v,u} = 1 (each vertex assigned to exactly one server)
12//! - Capacity link: ∀v,u: y_{v,u} ≤ x_u (can only assign to a vertex with a copy)
13//!
14//! Objective: minimize Σ_v s(v)·x_v + Σ_{v,u} u(v)·d(v,u)·y_{v,u}.
15//! Extraction: first n variables (x_v).
16
17use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
18use crate::models::graph::MultipleCopyFileAllocation;
19use crate::reduction;
20use crate::rules::traits::{ReduceTo, ReductionResult};
21use crate::topology::{Graph, SimpleGraph};
22use std::collections::VecDeque;
23
24/// Result of reducing MultipleCopyFileAllocation to ILP.
25#[derive(Debug, Clone)]
26pub struct ReductionMCFAToILP {
27    target: ILP<bool>,
28    num_vertices: usize,
29}
30
31impl ReductionResult for ReductionMCFAToILP {
32    type Source = MultipleCopyFileAllocation;
33    type Target = ILP<bool>;
34
35    fn target_problem(&self) -> &ILP<bool> {
36        &self.target
37    }
38
39    fn extract_solution(
40        &self,
41        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
42    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
43        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
44
45        Ok(target_solution[..self.num_vertices]
46            .iter()
47            .map(|&value| value == 1)
48            .collect())
49    }
50}
51
52/// Compute BFS shortest-path distances from `source` in `graph`.
53///
54/// Returns a vector of length `n` where unreachable vertices get distance -1.
55fn bfs_distances(graph: &SimpleGraph, source: usize, n: usize) -> Vec<i64> {
56    let mut dist = vec![-1i64; n];
57    dist[source] = 0;
58    let mut queue = VecDeque::new();
59    queue.push_back(source);
60    while let Some(u) = queue.pop_front() {
61        for v in graph.neighbors(u) {
62            if dist[v] == -1 {
63                dist[v] = dist[u] + 1;
64                queue.push_back(v);
65            }
66        }
67    }
68    dist
69}
70
71#[reduction(
72    transform = exact {
73        num_vars = "num_vertices + num_vertices^2",
74        num_constraints = "num_vertices^2 + num_vertices",
75    },
76    unavailable = {
77        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
78    }
79)]
80impl ReduceTo<ILP<bool>> for MultipleCopyFileAllocation {
81    type Result = ReductionMCFAToILP;
82
83    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
84        let n = self.num_vertices();
85        let num_vars = n + n * n;
86        // Precompute all-pairs shortest-path distances using BFS. A negative
87        // distance marks an unreachable pair and is prohibited below.
88        let all_dist: Vec<Vec<i64>> = (0..n).map(|s| bfs_distances(self.graph(), s, n)).collect();
89
90        // Index helpers.
91        let x_var = |v: usize| v;
92        let y_var = |v: usize, u: usize| n + v * n + u;
93
94        let mut constraints = Vec::with_capacity(n * n + n);
95
96        // Assignment constraints: ∀v: Σ_u y_{v,u} = 1
97        for v in 0..n {
98            let terms: Vec<(usize, i64)> = (0..n).map(|u| (y_var(v, u), 1)).collect();
99            constraints.push(LinearConstraint::eq(terms, 1));
100        }
101
102        // Reachable assignments require a selected copy. Unreachable
103        // assignments are forbidden exactly rather than discouraged by a cost.
104        for (u, distances_from_u) in all_dist.iter().enumerate() {
105            for (v, &distance) in distances_from_u.iter().enumerate() {
106                if distance < 0 {
107                    constraints.push(LinearConstraint::eq(vec![(y_var(v, u), 1)], 0));
108                } else {
109                    constraints.push(LinearConstraint::le(
110                        vec![(y_var(v, u), 1), (x_var(u), -1)],
111                        0,
112                    ));
113                }
114            }
115        }
116
117        // Objective: minimize Σ_v s(v)·x_v + Σ_{v,u} usage(v)·dist(v,u)·y_{v,u}
118        let mut objective: Vec<(usize, i64)> = Vec::with_capacity(num_vars);
119        for v in 0..n {
120            let sc = self.storage()[v];
121            if sc != 0 {
122                objective.push((x_var(v), sc));
123            }
124        }
125        for (u, distances_from_u) in all_dist.iter().enumerate() {
126            for (v, &distance) in distances_from_u.iter().enumerate() {
127                if distance < 0 {
128                    continue;
129                }
130                let service_cost = self.usage()[v].checked_mul(distance).ok_or_else(|| {
131                    crate::rules::ReductionError::integer_overflow::<
132                        MultipleCopyFileAllocation,
133                        ILP<bool>,
134                    >("multiplying usage by service distance")
135                })?;
136                if service_cost != 0 {
137                    objective.push((y_var(v, u), service_cost));
138                }
139            }
140        }
141
142        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
143            .map_err(Self::target_construction)?;
144        Ok(ReductionMCFAToILP {
145            target,
146            num_vertices: n,
147        })
148    }
149}
150
151#[cfg(feature = "example-db")]
152pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
153    vec![crate::example_db::specs::RuleExampleSpec {
154        id: "multiplecopyfileallocation_to_ilp",
155        build: || {
156            // 3-vertex path: 0 - 1 - 2
157            // Place a copy at vertex 1 (center); all vertices reachable within
158            // distance 1.  storage = [5,5,5], usage = [1,1,1].
159            // Cost = 5 (storage at 1) + 1*1 + 1*0 + 1*1 = 7.
160            let source = MultipleCopyFileAllocation::new(
161                SimpleGraph::new(3, vec![(0, 1), (1, 2)]),
162                vec![1, 1, 1],
163                vec![5, 5, 5],
164            );
165            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
166        },
167    }]
168}
169
170#[cfg(test)]
171#[path = "../unit_tests/rules/multiplecopyfileallocation_ilp.rs"]
172mod tests;
problemreductions/rules/multiplecopyfileallocation_ilp.rs

problemreductions/rules/
multiplecopyfileallocation_ilp.rs
