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, i64>;
38    type Target = ILP<bool>;
39
40    fn target_problem(&self) -> &ILP<bool> {
41        &self.target
42    }
43
44    fn extract_solution(
45        &self,
46        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
47    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
48        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
49
50        Ok(target_solution[..self.num_vertices]
51            .iter()
52            .map(|&value| value == 1)
53            .collect())
54    }
55}
56
57/// Compute weighted shortest-path distances from `source` in `graph`.
58///
59/// Returns a vector of length `n`; unreachable vertices remain `None`.
60fn weighted_distances_msmc(
61    graph: &SimpleGraph,
62    edge_lengths: &[i64],
63    source: usize,
64    n: usize,
65) -> Vec<Option<i64>> {
66    let mut adj: Vec<Vec<(usize, i64)>> = vec![Vec::new(); n];
67    for (idx, &(u, v)) in graph.edges().iter().enumerate() {
68        let len = edge_lengths[idx];
69        adj[u].push((v, len));
70        adj[v].push((u, len));
71    }
72
73    let mut dist = vec![None; n];
74    let mut visited = vec![false; n];
75    dist[source] = Some(0);
76
77    for _ in 0..n {
78        let mut next = None;
79        for vertex in 0..n {
80            if visited[vertex] {
81                continue;
82            }
83            let Some(dv) = dist[vertex] else {
84                continue;
85            };
86            match next {
87                None => next = Some(vertex),
88                Some(prev) => {
89                    if dv < dist[prev].expect("selected vertex must have a distance") {
90                        next = Some(vertex);
91                    }
92                }
93            }
94        }
95
96        let Some(u) = next else {
97            break;
98        };
99        visited[u] = true;
100        let du = dist[u].expect("selected vertex must have a distance");
101
102        for &(v, len) in &adj[u] {
103            if visited[v] {
104                continue;
105            }
106            let candidate = du + len;
107            let should_update = match dist[v] {
108                None => true,
109                Some(current) => candidate < current,
110            };
111            if should_update {
112                dist[v] = Some(candidate);
113            }
114        }
115    }
116
117    dist
118}
119
120#[reduction(
121    transform = upper_bound {
122        num_vars = "num_vertices + num_vertices^2",
123        num_constraints = "num_vertices^2 + 2 * num_vertices + 1",
124    },
125    unavailable = {
126        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
127    }
128)]
129impl ReduceTo<ILP<bool>> for MinimumSumMulticenter<SimpleGraph, i64> {
130    type Result = ReductionMSMCToILP;
131
132    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
133        let n = self.num_vertices();
134        let k = Self::exact_i64(self.k(), "encoding the number of centers")?;
135        let vertex_weights = self.vertex_weights();
136        let edge_lengths = self.edge_lengths();
137
138        // Precompute all-pairs weighted shortest-path distances.
139        let all_dist: Vec<Vec<Option<i64>>> = (0..n)
140            .map(|s| weighted_distances_msmc(self.graph(), edge_lengths, s, n))
141            .collect();
142
143        // Index helpers.
144        let x_var = |j: usize| j;
145        let y_var = |i: usize, j: usize| n + i * n + j;
146
147        let num_vars = n + n * n;
148        // Capacity: n^2 + 2*n + 1
149        let mut constraints = Vec::with_capacity(n * n + 2 * n + 1);
150
151        // Cardinality constraint: Σ_j x_j = k
152        let center_terms: Vec<(usize, i64)> = (0..n).map(|j| (x_var(j), 1)).collect();
153        constraints.push(LinearConstraint::eq(center_terms, k));
154
155        // Assignment constraints: ∀i: Σ_j y_{i,j} = 1
156        for i in 0..n {
157            let terms: Vec<(usize, i64)> = (0..n).map(|j| (y_var(i, j), 1)).collect();
158            constraints.push(LinearConstraint::eq(terms, 1));
159        }
160
161        // Assignment link constraints:
162        // reachable pairs use y_{i,j} ≤ x_j, unreachable pairs force y_{i,j} = 0.
163        for (i, distances) in all_dist.iter().enumerate() {
164            for (j, distance) in distances.iter().enumerate() {
165                if distance.is_some() {
166                    constraints.push(LinearConstraint::le(
167                        vec![(y_var(i, j), 1), (x_var(j), -1)],
168                        0,
169                    ));
170                } else {
171                    constraints.push(LinearConstraint::eq(vec![(y_var(i, j), 1)], 0));
172                }
173            }
174        }
175
176        // Objective: Minimize Σ_{i,j} w_i · d(i,j) · y_{i,j}
177        let mut objective: Vec<(usize, i64)> = Vec::new();
178        for (i, &w) in vertex_weights.iter().enumerate() {
179            for (j, distance) in all_dist[i].iter().enumerate() {
180                if let Some(distance) = distance {
181                    let weighted_distance = w.checked_mul(*distance).ok_or_else(|| {
182                        crate::rules::ReductionError::integer_overflow::<
183                            MinimumSumMulticenter<SimpleGraph, i64>,
184                            ILP<bool>,
185                        >(
186                            "multiplying a vertex weight by a shortest-path distance"
187                        )
188                    })?;
189                    let coeff = weighted_distance;
190                    if coeff != 0 {
191                        objective.push((y_var(i, j), coeff));
192                    }
193                }
194            }
195        }
196
197        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
198            .map_err(Self::target_construction)?;
199        Ok(ReductionMSMCToILP {
200            target,
201            num_vertices: n,
202        })
203    }
204}
205
206#[cfg(feature = "example-db")]
207pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
208    vec![crate::example_db::specs::RuleExampleSpec {
209        id: "minimumsummulticenter_to_ilp",
210        build: || {
211            // 3-vertex path: 0 - 1 - 2, unit weights, K=1
212            // Optimal center is vertex 1 with total distance 1+0+1 = 2.
213            let source = MinimumSumMulticenter::new(
214                SimpleGraph::new(3, vec![(0, 1), (1, 2)]),
215                vec![1i64; 3],
216                vec![1i64; 2],
217                1,
218            );
219            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
220        },
221    }]
222}
223
224#[cfg(test)]
225#[path = "../unit_tests/rules/minimumsummulticenter_ilp.rs"]
226mod tests;
problemreductions/rules/minimumsummulticenter_ilp.rs

problemreductions/rules/
minimumsummulticenter_ilp.rs
