problemreductions/rules/
minimumsummulticenter_ilp.rs

1//! Reduction from MinimumSumMulticenter to ILP (Integer Linear Programming).
2//!
3//! The p-median problem is formulated as a binary ILP.
4//!
5//! Variable layout (all binary):
6//! - `x_j` for each vertex j (1 if vertex j is selected as a center), indices `0..n`
7//! - `y_{i,j}` for each ordered pair (i, j), index `n + i*n + j`
8//!   (1 if vertex i is assigned to center j)
9//!
10//! Constraints:
11//! - Cardinality: Σ_j x_j = k (exactly k centers)
12//! - Assignment: ∀i: Σ_j y_{i,j} = 1 (each vertex assigned to exactly one center)
13//! - Assignment link: ∀i,j: if j is reachable from i then y_{i,j} ≤ x_j,
14//!   otherwise y_{i,j} = 0
15//!
16//! Objective: Minimize Σ_{i,j} w_i · d(i,j) · y_{i,j}
17//!
18//! Extraction: first n variables (x_j).
19//!
20//! Note: All-pairs shortest-path distances are computed using weighted shortest
21//! paths over `edge_lengths`. Unreachable assignment variables are forced to 0.
22
23use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
24use crate::models::graph::MinimumSumMulticenter;
25use crate::reduction;
26use crate::rules::traits::{ReduceTo, ReductionResult};
27use crate::topology::{Graph, SimpleGraph};
28
29/// Result of reducing MinimumSumMulticenter to ILP.
30#[derive(Debug, Clone)]
31pub struct ReductionMSMCToILP {
32    target: ILP<bool>,
33    num_vertices: usize,
34}
35
36impl ReductionResult for ReductionMSMCToILP {
37    type Source = MinimumSumMulticenter<SimpleGraph, i32>;
38    type Target = ILP<bool>;
39
40    fn target_problem(&self) -> &ILP<bool> {
41        &self.target
42    }
43
44    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
45        target_solution[..self.num_vertices].to_vec()
46    }
47}
48
49/// Compute weighted shortest-path distances from `source` in `graph`.
50///
51/// Returns a vector of length `n`; unreachable vertices remain `None`.
52fn weighted_distances_msmc(
53    graph: &SimpleGraph,
54    edge_lengths: &[i32],
55    source: usize,
56    n: usize,
57) -> Vec<Option<i64>> {
58    let mut adj: Vec<Vec<(usize, i64)>> = vec![Vec::new(); n];
59    for (idx, &(u, v)) in graph.edges().iter().enumerate() {
60        let len = i64::from(edge_lengths[idx]);
61        adj[u].push((v, len));
62        adj[v].push((u, len));
63    }
64
65    let mut dist = vec![None; n];
66    let mut visited = vec![false; n];
67    dist[source] = Some(0);
68
69    for _ in 0..n {
70        let mut next = None;
71        for vertex in 0..n {
72            if visited[vertex] {
73                continue;
74            }
75            let Some(dv) = dist[vertex] else {
76                continue;
77            };
78            match next {
79                None => next = Some(vertex),
80                Some(prev) => {
81                    if dv < dist[prev].expect("selected vertex must have a distance") {
82                        next = Some(vertex);
83                    }
84                }
85            }
86        }
87
88        let Some(u) = next else {
89            break;
90        };
91        visited[u] = true;
92        let du = dist[u].expect("selected vertex must have a distance");
93
94        for &(v, len) in &adj[u] {
95            if visited[v] {
96                continue;
97            }
98            let candidate = du + len;
99            let should_update = match dist[v] {
100                None => true,
101                Some(current) => candidate < current,
102            };
103            if should_update {
104                dist[v] = Some(candidate);
105            }
106        }
107    }
108
109    dist
110}
111
112#[reduction(
113    overhead = {
114        num_vars = "num_vertices + num_vertices^2",
115        num_constraints = "num_vertices^2 + 2 * num_vertices + 1",
116    }
117)]
118impl ReduceTo<ILP<bool>> for MinimumSumMulticenter<SimpleGraph, i32> {
119    type Result = ReductionMSMCToILP;
120
121    fn reduce_to(&self) -> Self::Result {
122        let n = self.num_vertices();
123        let k = self.k();
124        let vertex_weights = self.vertex_weights();
125        let edge_lengths = self.edge_lengths();
126
127        // Precompute all-pairs weighted shortest-path distances.
128        let all_dist: Vec<Vec<Option<i64>>> = (0..n)
129            .map(|s| weighted_distances_msmc(self.graph(), edge_lengths, s, n))
130            .collect();
131
132        // Index helpers.
133        let x_var = |j: usize| j;
134        let y_var = |i: usize, j: usize| n + i * n + j;
135
136        let num_vars = n + n * n;
137        // Capacity: n^2 + 2*n + 1
138        let mut constraints = Vec::with_capacity(n * n + 2 * n + 1);
139
140        // Cardinality constraint: Σ_j x_j = k
141        let center_terms: Vec<(usize, f64)> = (0..n).map(|j| (x_var(j), 1.0)).collect();
142        constraints.push(LinearConstraint::eq(center_terms, k as f64));
143
144        // Assignment constraints: ∀i: Σ_j y_{i,j} = 1
145        for i in 0..n {
146            let terms: Vec<(usize, f64)> = (0..n).map(|j| (y_var(i, j), 1.0)).collect();
147            constraints.push(LinearConstraint::eq(terms, 1.0));
148        }
149
150        // Assignment link constraints:
151        // reachable pairs use y_{i,j} ≤ x_j, unreachable pairs force y_{i,j} = 0.
152        for (i, distances) in all_dist.iter().enumerate() {
153            for (j, distance) in distances.iter().enumerate() {
154                if distance.is_some() {
155                    constraints.push(LinearConstraint::le(
156                        vec![(y_var(i, j), 1.0), (x_var(j), -1.0)],
157                        0.0,
158                    ));
159                } else {
160                    constraints.push(LinearConstraint::eq(vec![(y_var(i, j), 1.0)], 0.0));
161                }
162            }
163        }
164
165        // Objective: Minimize Σ_{i,j} w_i · d(i,j) · y_{i,j}
166        let mut objective: Vec<(usize, f64)> = Vec::new();
167        for (i, &w) in vertex_weights.iter().enumerate() {
168            let w_i = w as f64;
169            for (j, distance) in all_dist[i].iter().enumerate() {
170                if let Some(distance) = distance {
171                    let coeff = w_i * *distance as f64;
172                    if coeff != 0.0 {
173                        objective.push((y_var(i, j), coeff));
174                    }
175                }
176            }
177        }
178
179        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
180        ReductionMSMCToILP {
181            target,
182            num_vertices: n,
183        }
184    }
185}
186
187#[cfg(feature = "example-db")]
188pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
189    vec![crate::example_db::specs::RuleExampleSpec {
190        id: "minimumsummulticenter_to_ilp",
191        build: || {
192            // 3-vertex path: 0 - 1 - 2, unit weights, K=1
193            // Optimal center is vertex 1 with total distance 1+0+1 = 2.
194            let source = MinimumSumMulticenter::new(
195                SimpleGraph::new(3, vec![(0, 1), (1, 2)]),
196                vec![1i32; 3],
197                vec![1i32; 2],
198                1,
199            );
200            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
201        },
202    }]
203}
204
205#[cfg(test)]
206#[path = "../unit_tests/rules/minimumsummulticenter_ilp.rs"]
207mod tests;
problemreductions/rules/minimumsummulticenter_ilp.rs

problemreductions/rules/
minimumsummulticenter_ilp.rs
