problemreductions/rules/
minmaxmulticenter_ilp.rs

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

problemreductions/rules/
minmaxmulticenter_ilp.rs
