problemreductions/rules/
ruralpostman_ilp.rs

1//! Reduction from RuralPostman to ILP.
2//!
3//! Uses traversal multiplicity variables, parity variables, activation and
4//! connectivity flow constraints to encode an Eulerian connected subgraph
5//! covering all required edges within the length bound.
6
7use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
8use crate::models::graph::RuralPostman;
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11use crate::topology::{Graph, SimpleGraph};
12use crate::types::WeightElement;
13
14/// Result of reducing RuralPostman to ILP.
15#[derive(Debug, Clone)]
16pub struct ReductionRPToILP {
17    target: ILP<i32>,
18    num_edges: usize,
19}
20
21impl ReductionResult for ReductionRPToILP {
22    type Source = RuralPostman<SimpleGraph, i32>;
23    type Target = ILP<i32>;
24
25    fn target_problem(&self) -> &ILP<i32> {
26        &self.target
27    }
28
29    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
30        // Output the traversal multiplicities t_e
31        target_solution[..self.num_edges].to_vec()
32    }
33}
34
35#[reduction(
36    overhead = {
37        num_vars = "num_edges + num_vertices + num_edges + num_vertices + 2 * num_edges",
38        num_constraints = "2 * num_edges + num_required_edges + num_vertices + 2 * num_edges + num_vertices + 2 * num_edges + num_vertices + num_edges + num_edges + num_vertices",
39    }
40)]
41impl ReduceTo<ILP<i32>> for RuralPostman<SimpleGraph, i32> {
42    type Result = ReductionRPToILP;
43
44    fn reduce_to(&self) -> Self::Result {
45        let m = self.num_edges();
46        let n = self.num_vertices();
47        let edges = self.graph().edges();
48
49        // If E' is empty, the empty circuit satisfies when B >= 0
50        if self.required_edges().is_empty() {
51            return ReductionRPToILP {
52                target: ILP::new(0, vec![], vec![], ObjectiveSense::Minimize),
53                num_edges: 0,
54            };
55        }
56
57        // Pick root vertex: first endpoint of first required edge
58        let root = edges[self.required_edges()[0]].0;
59
60        // Variable layout:
61        // t_e:    index e (0..m)         -- traversal multiplicity {0,1,2}
62        // q_v:    index m + v            -- parity variable (degree/2)
63        // y_e:    index m + n + e        -- binary edge activation
64        // z_v:    index m + n + m + v    -- binary vertex activity
65        // f_{e,0}: index m + n + m + n + 2*e     -- flow u->v
66        // f_{e,1}: index m + n + m + n + 2*e + 1 -- flow v->u
67        let t_idx = |e: usize| e;
68        let q_idx = |v: usize| m + v;
69        let y_idx = |e: usize| m + n + e;
70        let z_idx = |v: usize| m + n + m + v;
71        let f_idx = |e: usize, dir: usize| m + n + m + n + 2 * e + dir;
72
73        let num_vars = m + n + m + n + 2 * m;
74        let mut constraints = Vec::new();
75
76        // y_e <= t_e and t_e <= 2*y_e for each edge
77        for e in 0..m {
78            constraints.push(LinearConstraint::le(
79                vec![(y_idx(e), 1.0), (t_idx(e), -1.0)],
80                0.0,
81            ));
82            constraints.push(LinearConstraint::le(
83                vec![(t_idx(e), 1.0), (y_idx(e), -2.0)],
84                0.0,
85            ));
86        }
87
88        // t_e >= 1 for required edges
89        for &req_idx in self.required_edges() {
90            constraints.push(LinearConstraint::ge(vec![(t_idx(req_idx), 1.0)], 1.0));
91        }
92
93        // Even degree: sum_{e : v in e} t_e = 2 * q_v for all v
94        for v in 0..n {
95            let mut terms = Vec::new();
96            for (e, &(u, w)) in edges.iter().enumerate() {
97                if u == v || w == v {
98                    terms.push((t_idx(e), 1.0));
99                }
100            }
101            terms.push((q_idx(v), -2.0));
102            constraints.push(LinearConstraint::eq(terms, 0.0));
103        }
104
105        // y_e <= z_u and y_e <= z_v for each edge e = {u,v}
106        for (e, &(u, v)) in edges.iter().enumerate() {
107            constraints.push(LinearConstraint::le(
108                vec![(y_idx(e), 1.0), (z_idx(u), -1.0)],
109                0.0,
110            ));
111            constraints.push(LinearConstraint::le(
112                vec![(y_idx(e), 1.0), (z_idx(v), -1.0)],
113                0.0,
114            ));
115        }
116
117        // z_v <= sum_{e : v in e} y_e for all v
118        for v in 0..n {
119            let mut terms = vec![(z_idx(v), 1.0)];
120            for (e, &(u, w)) in edges.iter().enumerate() {
121                if u == v || w == v {
122                    terms.push((y_idx(e), -1.0));
123                }
124            }
125            constraints.push(LinearConstraint::le(terms, 0.0));
126        }
127
128        // Flow capacity: f_{u,v} <= (n-1)*y_e and f_{v,u} <= (n-1)*y_e
129        let big_m = (n - 1) as f64;
130        for e in 0..m {
131            constraints.push(LinearConstraint::le(
132                vec![(f_idx(e, 0), 1.0), (y_idx(e), -big_m)],
133                0.0,
134            ));
135            constraints.push(LinearConstraint::le(
136                vec![(f_idx(e, 1), 1.0), (y_idx(e), -big_m)],
137                0.0,
138            ));
139        }
140
141        // Connectivity flow from root:
142        // Root: sum_{w: {r,w} in E} f_{r,w} - sum_{u: {u,r} in E} f_{u,r} = sum_v z_v - 1
143        // For non-root v: sum_{u: {u,v} in E} f_{u,v} - sum_{w: {v,w} in E} f_{v,w} = z_v
144
145        // Root conservation: outflow - inflow = sum_v z_v - 1
146        {
147            let mut terms = Vec::new();
148            for (e, &(u, v)) in edges.iter().enumerate() {
149                if u == root {
150                    terms.push((f_idx(e, 0), 1.0)); // outgoing from root via dir 0
151                    terms.push((f_idx(e, 1), -1.0)); // incoming to root via dir 1
152                }
153                if v == root {
154                    terms.push((f_idx(e, 1), 1.0)); // outgoing from root via dir 1
155                    terms.push((f_idx(e, 0), -1.0)); // incoming to root via dir 0
156                }
157            }
158            // rhs = sum_v z_v - 1, move z_v to left side
159            for v in 0..n {
160                terms.push((z_idx(v), -1.0));
161            }
162            constraints.push(LinearConstraint::eq(terms, -1.0));
163        }
164
165        // Non-root vertices: inflow - outflow = z_v
166        // The paper says: sum_{u: {u,v}} f_{u,v} - sum_{w: {v,w}} f_{v,w} = z_v
167        // This means: inflow - outflow = z_v (each non-root active vertex absorbs 1 unit)
168        for v in 0..n {
169            if v == root {
170                continue;
171            }
172            let mut terms = Vec::new();
173            for (e, &(u, w)) in edges.iter().enumerate() {
174                if u == v {
175                    // Edge e = {v, w}: dir 0 is v->w (outgoing), dir 1 is w->v (incoming)
176                    terms.push((f_idx(e, 0), -1.0)); // outgoing
177                    terms.push((f_idx(e, 1), 1.0)); // incoming
178                }
179                if w == v {
180                    // Edge e = {u, v}: dir 0 is u->v (incoming), dir 1 is v->u (outgoing)
181                    terms.push((f_idx(e, 0), 1.0)); // incoming
182                    terms.push((f_idx(e, 1), -1.0)); // outgoing
183                }
184            }
185            terms.push((z_idx(v), -1.0));
186            constraints.push(LinearConstraint::eq(terms, 0.0));
187        }
188
189        // Upper bound on t_e: t_e <= 2
190        for e in 0..m {
191            constraints.push(LinearConstraint::le(vec![(t_idx(e), 1.0)], 2.0));
192        }
193
194        // Upper bounds on binary variables: y_e <= 1, z_v <= 1
195        for e in 0..m {
196            constraints.push(LinearConstraint::le(vec![(y_idx(e), 1.0)], 1.0));
197        }
198        for v in 0..n {
199            constraints.push(LinearConstraint::le(vec![(z_idx(v), 1.0)], 1.0));
200        }
201
202        // Objective: minimize total route cost
203        let edge_lengths = self.edge_lengths();
204        let objective: Vec<(usize, f64)> = (0..m)
205            .map(|e| (t_idx(e), edge_lengths[e].to_sum() as f64))
206            .collect();
207        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
208
209        ReductionRPToILP {
210            target,
211            num_edges: m,
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: "ruralpostman_to_ilp",
220        build: || {
221            // Triangle: 3 vertices, 3 edges, require edge 0
222            let source = RuralPostman::new(
223                SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]),
224                vec![1, 1, 1],
225                vec![0],
226            );
227            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
228        },
229    }]
230}
231
232#[cfg(test)]
233#[path = "../unit_tests/rules/ruralpostman_ilp.rs"]
234mod tests;
problemreductions/rules/ruralpostman_ilp.rs

problemreductions/rules/
ruralpostman_ilp.rs
