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(&self, target_solution: &[usize]) -> Vec<usize> {
40        target_solution[..self.num_vertices].to_vec()
41    }
42}
43
44/// Compute BFS shortest-path distances from `source` in `graph`.
45///
46/// Returns a vector of length `n` where unreachable vertices get distance -1.
47fn bfs_distances(graph: &SimpleGraph, source: usize, n: usize) -> Vec<i64> {
48    let mut dist = vec![-1i64; n];
49    dist[source] = 0;
50    let mut queue = VecDeque::new();
51    queue.push_back(source);
52    while let Some(u) = queue.pop_front() {
53        for v in graph.neighbors(u) {
54            if dist[v] == -1 {
55                dist[v] = dist[u] + 1;
56                queue.push_back(v);
57            }
58        }
59    }
60    dist
61}
62
63#[reduction(
64    overhead = {
65        num_vars = "num_vertices + num_vertices^2",
66        num_constraints = "num_vertices^2 + num_vertices",
67    }
68)]
69impl ReduceTo<ILP<bool>> for MultipleCopyFileAllocation {
70    type Result = ReductionMCFAToILP;
71
72    fn reduce_to(&self) -> Self::Result {
73        let n = self.num_vertices();
74        let num_vars = n + n * n;
75        // Big-M penalty for unreachable pairs: use a value larger than any feasible
76        // total cost to make unreachable assignments infeasible.
77        let total_storage: i64 = self.storage().iter().sum();
78        let total_usage: i64 = self.usage().iter().sum();
79        let big_m = total_storage + total_usage * n as i64 + 1;
80
81        // Precompute all-pairs shortest-path distances using BFS.
82        let all_dist: Vec<Vec<i64>> = (0..n).map(|s| bfs_distances(self.graph(), s, n)).collect();
83
84        // Effective distance from v to u: use big_m when unreachable.
85        let eff_dist = |v: usize, u: usize| -> i64 {
86            let d = all_dist[u][v]; // distance from v to u = BFS from u, query v
87            if d < 0 {
88                big_m
89            } else {
90                d
91            }
92        };
93
94        // Index helpers.
95        let x_var = |v: usize| v;
96        let y_var = |v: usize, u: usize| n + v * n + u;
97
98        let mut constraints = Vec::with_capacity(n * n + n);
99
100        // Assignment constraints: ∀v: Σ_u y_{v,u} = 1
101        for v in 0..n {
102            let terms: Vec<(usize, f64)> = (0..n).map(|u| (y_var(v, u), 1.0)).collect();
103            constraints.push(LinearConstraint::eq(terms, 1.0));
104        }
105
106        // Capacity link constraints: ∀v,u: y_{v,u} ≤ x_u  →  y_{v,u} - x_u ≤ 0
107        for v in 0..n {
108            for u in 0..n {
109                constraints.push(LinearConstraint::le(
110                    vec![(y_var(v, u), 1.0), (x_var(u), -1.0)],
111                    0.0,
112                ));
113            }
114        }
115
116        // Objective: minimize Σ_v s(v)·x_v + Σ_{v,u} usage(v)·dist(v,u)·y_{v,u}
117        let mut objective: Vec<(usize, f64)> = Vec::with_capacity(num_vars);
118        for v in 0..n {
119            let sc = self.storage()[v] as f64;
120            if sc != 0.0 {
121                objective.push((x_var(v), sc));
122            }
123        }
124        for v in 0..n {
125            let u_v = self.usage()[v] as f64;
126            for u in 0..n {
127                let coeff = u_v * eff_dist(v, u) as f64;
128                if coeff != 0.0 {
129                    objective.push((y_var(v, u), coeff));
130                }
131            }
132        }
133
134        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
135        ReductionMCFAToILP {
136            target,
137            num_vertices: n,
138        }
139    }
140}
141
142#[cfg(feature = "example-db")]
143pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
144    vec![crate::example_db::specs::RuleExampleSpec {
145        id: "multiplecopyfileallocation_to_ilp",
146        build: || {
147            // 3-vertex path: 0 - 1 - 2
148            // Place a copy at vertex 1 (center); all vertices reachable within
149            // distance 1.  storage = [5,5,5], usage = [1,1,1].
150            // Cost = 5 (storage at 1) + 1*1 + 1*0 + 1*1 = 7.
151            let source = MultipleCopyFileAllocation::new(
152                SimpleGraph::new(3, vec![(0, 1), (1, 2)]),
153                vec![1, 1, 1],
154                vec![5, 5, 5],
155            );
156            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
157        },
158    }]
159}
160
161#[cfg(test)]
162#[path = "../unit_tests/rules/multiplecopyfileallocation_ilp.rs"]
163mod tests;
problemreductions/rules/multiplecopyfileallocation_ilp.rs

problemreductions/rules/
multiplecopyfileallocation_ilp.rs
