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<i64>,
18    num_edges: usize,
19}
20
21impl ReductionResult for ReductionRPToILP {
22    type Source = RuralPostman<SimpleGraph, i64>;
23    type Target = ILP<i64>;
24
25    fn target_problem(&self) -> &ILP<i64> {
26        &self.target
27    }
28
29    fn extract_solution(
30        &self,
31        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
32    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
33        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
34
35        if self.target.num_vars() == 0 {
36            Ok(vec![0; self.num_edges])
37        } else {
38            crate::rules::ilp_helpers::decode_usize_values(&target_solution[..self.num_edges])
39        }
40    }
41}
42
43#[reduction(
44    transform = exact {
45        num_vars = "num_edges + num_vertices + num_edges + num_vertices + 2 * num_edges",
46        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",
47    },
48    unavailable = {
49        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
50    }
51)]
52impl ReduceTo<ILP<i64>> for RuralPostman<SimpleGraph, i64> {
53    type Result = ReductionRPToILP;
54
55    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
56        let m = self.num_edges();
57        let n = self.num_vertices();
58        let edges = self.graph().edges();
59
60        // If E' is empty, the empty circuit satisfies when B >= 0
61        if self.required_edges().is_empty() {
62            return Ok(ReductionRPToILP {
63                target: ILP::new(0, vec![], vec![], ObjectiveSense::Minimize)
64                    .map_err(Self::target_construction)?,
65                num_edges: m,
66            });
67        }
68
69        // Pick root vertex: first endpoint of first required edge
70        let root = edges[self.required_edges()[0]].0;
71
72        // Variable layout:
73        // t_e:    index e (0..m)         -- traversal multiplicity {0,1,2}
74        // q_v:    index m + v            -- parity variable (degree/2)
75        // y_e:    index m + n + e        -- binary edge activation
76        // z_v:    index m + n + m + v    -- binary vertex activity
77        // f_{e,0}: index m + n + m + n + 2*e     -- flow u->v
78        // f_{e,1}: index m + n + m + n + 2*e + 1 -- flow v->u
79        let t_idx = |e: usize| e;
80        let q_idx = |v: usize| m + v;
81        let y_idx = |e: usize| m + n + e;
82        let z_idx = |v: usize| m + n + m + v;
83        let f_idx = |e: usize, dir: usize| m + n + m + n + 2 * e + dir;
84
85        let num_vars = m + n + m + n + 2 * m;
86        let mut constraints = Vec::new();
87
88        // y_e <= t_e and t_e <= 2*y_e for each edge
89        for e in 0..m {
90            constraints.push(LinearConstraint::le(vec![(y_idx(e), 1), (t_idx(e), -1)], 0));
91            constraints.push(LinearConstraint::le(vec![(t_idx(e), 1), (y_idx(e), -2)], 0));
92        }
93
94        // t_e >= 1 for required edges
95        for &req_idx in self.required_edges() {
96            constraints.push(LinearConstraint::ge(vec![(t_idx(req_idx), 1)], 1));
97        }
98
99        // Even degree: sum_{e : v in e} t_e = 2 * q_v for all v
100        for v in 0..n {
101            let mut terms = Vec::new();
102            for (e, &(u, w)) in edges.iter().enumerate() {
103                if u == v || w == v {
104                    terms.push((t_idx(e), 1));
105                }
106            }
107            terms.push((q_idx(v), -2));
108            constraints.push(LinearConstraint::eq(terms, 0));
109        }
110
111        // y_e <= z_u and y_e <= z_v for each edge e = {u,v}
112        for (e, &(u, v)) in edges.iter().enumerate() {
113            constraints.push(LinearConstraint::le(vec![(y_idx(e), 1), (z_idx(u), -1)], 0));
114            constraints.push(LinearConstraint::le(vec![(y_idx(e), 1), (z_idx(v), -1)], 0));
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)];
120            for (e, &(u, w)) in edges.iter().enumerate() {
121                if u == v || w == v {
122                    terms.push((y_idx(e), -1));
123                }
124            }
125            constraints.push(LinearConstraint::le(terms, 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 = Self::exact_i64(n, "encoding the connectivity-flow bound")? - 1;
130        for e in 0..m {
131            constraints.push(LinearConstraint::le(
132                vec![(f_idx(e, 0), 1), (y_idx(e), -big_m)],
133                0,
134            ));
135            constraints.push(LinearConstraint::le(
136                vec![(f_idx(e, 1), 1), (y_idx(e), -big_m)],
137                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)); // outgoing from root via dir 0
151                    terms.push((f_idx(e, 1), -1)); // incoming to root via dir 1
152                }
153                if v == root {
154                    terms.push((f_idx(e, 1), 1)); // outgoing from root via dir 1
155                    terms.push((f_idx(e, 0), -1)); // 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));
161            }
162            constraints.push(LinearConstraint::eq(terms, -1));
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)); // outgoing
177                    terms.push((f_idx(e, 1), 1)); // 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)); // incoming
182                    terms.push((f_idx(e, 1), -1)); // outgoing
183                }
184            }
185            terms.push((z_idx(v), -1));
186            constraints.push(LinearConstraint::eq(terms, 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)], 2));
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)], 1));
197        }
198        for v in 0..n {
199            constraints.push(LinearConstraint::le(vec![(z_idx(v), 1)], 1));
200        }
201
202        // Objective: minimize total route cost
203        let edge_lengths = self.edge_lengths();
204        let objective: Vec<(usize, i64)> = (0..m)
205            .map(|e| (t_idx(e), edge_lengths[e].to_sum()))
206            .collect();
207        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
208            .map_err(Self::target_construction)?;
209
210        Ok(ReductionRPToILP {
211            target,
212            num_edges: m,
213        })
214    }
215}
216
217#[cfg(feature = "example-db")]
218pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
219    vec![crate::example_db::specs::RuleExampleSpec {
220        id: "ruralpostman_to_ilp",
221        build: || {
222            // Triangle: 3 vertices, 3 edges, require edge 0
223            let source = RuralPostman::new(
224                SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]),
225                vec![1, 1, 1],
226                vec![0],
227            );
228            crate::example_db::specs::rule_example_via_ilp::<_, i64>(source)
229        },
230    }]
231}
232
233#[cfg(test)]
234#[path = "../unit_tests/rules/ruralpostman_ilp.rs"]
235mod tests;
problemreductions/rules/ruralpostman_ilp.rs

problemreductions/rules/
ruralpostman_ilp.rs
