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(transform = {
72    exact {
73        num_vars = "num_vertices + num_vertices^2",
74        num_constraints = "num_vertices^2 + num_vertices",
75    },
76    upper_bound {
77        max_constraint_magnitude_bits = "1",
78        num_nonzeros = "(num_vertices + num_vertices^2) * (num_vertices^2 + num_vertices)",
79    },
80})]
81impl ReduceTo<ILP<bool>> for MultipleCopyFileAllocation {
82    type Result = ReductionMCFAToILP;
83
84    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
85        let n = self.num_vertices();
86        let num_vars = n + n * n;
87        // Precompute all-pairs shortest-path distances using BFS. A negative
88        // distance marks an unreachable pair and is prohibited below.
89        let all_dist: Vec<Vec<i64>> = (0..n).map(|s| bfs_distances(self.graph(), s, n)).collect();
90
91        // Index helpers.
92        let x_var = |v: usize| v;
93        let y_var = |v: usize, u: usize| n + v * n + u;
94
95        let mut constraints = Vec::with_capacity(n * n + n);
96
97        // Assignment constraints: ∀v: Σ_u y_{v,u} = 1
98        for v in 0..n {
99            let terms: Vec<(usize, i64)> = (0..n).map(|u| (y_var(v, u), 1)).collect();
100            constraints.push(LinearConstraint::eq(terms, 1));
101        }
102
103        // Reachable assignments require a selected copy. Unreachable
104        // assignments are forbidden exactly rather than discouraged by a cost.
105        for (u, distances_from_u) in all_dist.iter().enumerate() {
106            for (v, &distance) in distances_from_u.iter().enumerate() {
107                if distance < 0 {
108                    constraints.push(LinearConstraint::eq(vec![(y_var(v, u), 1)], 0));
109                } else {
110                    constraints.push(LinearConstraint::le(
111                        vec![(y_var(v, u), 1), (x_var(u), -1)],
112                        0,
113                    ));
114                }
115            }
116        }
117
118        // Objective: minimize Σ_v s(v)·x_v + Σ_{v,u} usage(v)·dist(v,u)·y_{v,u}
119        let mut objective: Vec<(usize, i64)> = Vec::with_capacity(num_vars);
120        for v in 0..n {
121            let sc = self.storage()[v];
122            if sc != 0 {
123                objective.push((x_var(v), sc));
124            }
125        }
126        for (u, distances_from_u) in all_dist.iter().enumerate() {
127            for (v, &distance) in distances_from_u.iter().enumerate() {
128                if distance < 0 {
129                    continue;
130                }
131                let service_cost = self.usage()[v].checked_mul(distance).ok_or_else(|| {
132                    crate::rules::ReductionError::integer_overflow::<
133                        MultipleCopyFileAllocation,
134                        ILP<bool>,
135                    >("multiplying usage by service distance")
136                })?;
137                if service_cost != 0 {
138                    objective.push((y_var(v, u), service_cost));
139                }
140            }
141        }
142
143        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
144            .map_err(Self::target_construction)?;
145        Ok(ReductionMCFAToILP {
146            target,
147            num_vertices: n,
148        })
149    }
150}
151
152#[cfg(feature = "example-db")]
153pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
154    vec![crate::example_db::specs::RuleExampleSpec {
155        id: "multiplecopyfileallocation_to_ilp",
156        build: || {
157            // 3-vertex path: 0 - 1 - 2
158            // Place a copy at vertex 1 (center); all vertices reachable within
159            // distance 1.  storage = [5,5,5], usage = [1,1,1].
160            // Cost = 5 (storage at 1) + 1*1 + 1*0 + 1*1 = 7.
161            let source = MultipleCopyFileAllocation::new(
162                SimpleGraph::new(3, vec![(0, 1), (1, 2)]),
163                vec![1, 1, 1],
164                vec![5, 5, 5],
165            );
166            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
167        },
168    }]
169}
170
171#[cfg(test)]
172#[path = "../unit_tests/rules/multiplecopyfileallocation_ilp.rs"]
173mod tests;
problemreductions/rules/multiplecopyfileallocation_ilp.rs

problemreductions/rules/
multiplecopyfileallocation_ilp.rs
