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::{Bounded, IntegerVariable, 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, i64, Bounded>,
18    num_edges: usize,
19}
20
21impl ReductionResult for ReductionRPToILP {
22    type Source = RuralPostman<SimpleGraph, i64>;
23    type Target = ILP<i64, i64, Bounded>;
24
25    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
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// The nonempty-required-set branch allocates 4m+2n variables and 8m+4n+r rows;
44// the empty branch allocates none. Coefficients by block are bounded by:
45// linking 4m, required r, parity 2m+n, edge activation 4m, vertex activation
46// 2m+n, flow capacity 4m, conservation 4m+2n, and upper bounds 2m+n.
47#[reduction(transform = upper_bound {
48    max_constraint_magnitude_bits = "num_vertices + num_edges + 2",
49    num_vars = "4 * num_edges + 2 * num_vertices",
50    num_constraints = "8 * num_edges + 4 * num_vertices + num_required_edges",
51    num_nonzeros = "22 * num_edges + 5 * num_vertices + num_required_edges",
52})]
53impl ReduceTo<ILP<i64, i64, Bounded>> for RuralPostman<SimpleGraph, i64> {
54    type Result = ReductionRPToILP;
55
56    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
57        let m = self.num_edges();
58        let n = self.num_vertices();
59        let edges = self.graph().edges();
60
61        // If E' is empty, the empty circuit satisfies when B >= 0
62        if self.required_edges().is_empty() {
63            return Ok(ReductionRPToILP {
64                target: ILP::new(0, vec![], vec![], ObjectiveSense::Minimize)
65                    .map_err(Self::target_construction)?,
66                num_edges: m,
67            });
68        }
69
70        // Pick root vertex: first endpoint of first required edge
71        let root = edges[self.required_edges()[0]].0;
72
73        // Variable layout:
74        // t_e:    index e (0..m)         -- traversal multiplicity {0,1,2}
75        // q_v:    index m + v            -- parity variable (degree/2)
76        // y_e:    index m + n + e        -- binary edge activation
77        // z_v:    index m + n + m + v    -- binary vertex activity
78        // f_{e,0}: index m + n + m + n + 2*e     -- flow u->v
79        // f_{e,1}: index m + n + m + n + 2*e + 1 -- flow v->u
80        let t_idx = |e: usize| e;
81        let q_idx = |v: usize| m + v;
82        let y_idx = |e: usize| m + n + e;
83        let z_idx = |v: usize| m + n + m + v;
84        let f_idx = |e: usize, dir: usize| m + n + m + n + 2 * e + dir;
85
86        let num_vars = m + n + m + n + 2 * m;
87        let mut constraints = Vec::new();
88
89        // y_e <= t_e and t_e <= 2*y_e for each edge
90        for e in 0..m {
91            constraints.push(LinearConstraint::le(vec![(y_idx(e), 1), (t_idx(e), -1)], 0));
92            constraints.push(LinearConstraint::le(vec![(t_idx(e), 1), (y_idx(e), -2)], 0));
93        }
94
95        // t_e >= 1 for required edges
96        for &req_idx in self.required_edges() {
97            constraints.push(LinearConstraint::ge(vec![(t_idx(req_idx), 1)], 1));
98        }
99
100        // Even degree: sum_{e : v in e} t_e = 2 * q_v for all v
101        for v in 0..n {
102            let mut terms = Vec::new();
103            for (e, &(u, w)) in edges.iter().enumerate() {
104                if u == v || w == v {
105                    terms.push((t_idx(e), 1));
106                }
107            }
108            terms.push((q_idx(v), -2));
109            constraints.push(LinearConstraint::eq(terms, 0));
110        }
111
112        // y_e <= z_u and y_e <= z_v for each edge e = {u,v}
113        for (e, &(u, v)) in edges.iter().enumerate() {
114            constraints.push(LinearConstraint::le(vec![(y_idx(e), 1), (z_idx(u), -1)], 0));
115            constraints.push(LinearConstraint::le(vec![(y_idx(e), 1), (z_idx(v), -1)], 0));
116        }
117
118        // z_v <= sum_{e : v in e} y_e for all v
119        for v in 0..n {
120            let mut terms = vec![(z_idx(v), 1)];
121            for (e, &(u, w)) in edges.iter().enumerate() {
122                if u == v || w == v {
123                    terms.push((y_idx(e), -1));
124                }
125            }
126            constraints.push(LinearConstraint::le(terms, 0));
127        }
128
129        // Flow capacity: f_{u,v} <= (n-1)*y_e and f_{v,u} <= (n-1)*y_e
130        let big_m = Self::exact_i64(n, "encoding the connectivity-flow bound")? - 1;
131        for e in 0..m {
132            constraints.push(LinearConstraint::le(
133                vec![(f_idx(e, 0), 1), (y_idx(e), -big_m)],
134                0,
135            ));
136            constraints.push(LinearConstraint::le(
137                vec![(f_idx(e, 1), 1), (y_idx(e), -big_m)],
138                0,
139            ));
140        }
141
142        // Connectivity flow from root:
143        // Root: sum_{w: {r,w} in E} f_{r,w} - sum_{u: {u,r} in E} f_{u,r} = sum_v z_v - 1
144        // For non-root v: sum_{u: {u,v} in E} f_{u,v} - sum_{w: {v,w} in E} f_{v,w} = z_v
145
146        // Root conservation: outflow - inflow = sum_v z_v - 1
147        {
148            let mut terms = Vec::new();
149            for (e, &(u, v)) in edges.iter().enumerate() {
150                if u == root {
151                    terms.push((f_idx(e, 0), 1)); // outgoing from root via dir 0
152                    terms.push((f_idx(e, 1), -1)); // incoming to root via dir 1
153                }
154                if v == root {
155                    terms.push((f_idx(e, 1), 1)); // outgoing from root via dir 1
156                    terms.push((f_idx(e, 0), -1)); // incoming to root via dir 0
157                }
158            }
159            // rhs = sum_v z_v - 1, move z_v to left side
160            for v in 0..n {
161                terms.push((z_idx(v), -1));
162            }
163            constraints.push(LinearConstraint::eq(terms, -1));
164        }
165
166        // Non-root vertices: inflow - outflow = z_v
167        // The paper says: sum_{u: {u,v}} f_{u,v} - sum_{w: {v,w}} f_{v,w} = z_v
168        // This means: inflow - outflow = z_v (each non-root active vertex absorbs 1 unit)
169        for v in 0..n {
170            if v == root {
171                continue;
172            }
173            let mut terms = Vec::new();
174            for (e, &(u, w)) in edges.iter().enumerate() {
175                if u == v {
176                    // Edge e = {v, w}: dir 0 is v->w (outgoing), dir 1 is w->v (incoming)
177                    terms.push((f_idx(e, 0), -1)); // outgoing
178                    terms.push((f_idx(e, 1), 1)); // incoming
179                }
180                if w == v {
181                    // Edge e = {u, v}: dir 0 is u->v (incoming), dir 1 is v->u (outgoing)
182                    terms.push((f_idx(e, 0), 1)); // incoming
183                    terms.push((f_idx(e, 1), -1)); // outgoing
184                }
185            }
186            terms.push((z_idx(v), -1));
187            constraints.push(LinearConstraint::eq(terms, 0));
188        }
189
190        // Upper bound on t_e: t_e <= 2
191        for e in 0..m {
192            constraints.push(LinearConstraint::le(vec![(t_idx(e), 1)], 2));
193        }
194
195        // Upper bounds on binary variables: y_e <= 1, z_v <= 1
196        for e in 0..m {
197            constraints.push(LinearConstraint::le(vec![(y_idx(e), 1)], 1));
198        }
199        for v in 0..n {
200            constraints.push(LinearConstraint::le(vec![(z_idx(v), 1)], 1));
201        }
202
203        // Objective: minimize total route cost
204        let edge_lengths = self.edge_lengths();
205        let objective: Vec<(usize, i64)> = (0..m)
206            .map(|e| (t_idx(e), edge_lengths[e].to_sum()))
207            .collect();
208        let mut variables = vec![IntegerVariable::binary(); num_vars];
209        variables[..m]
210            .fill(IntegerVariable::new(Some(0), Some(2)).map_err(Self::target_construction)?);
211        variables[m..m + n].fill(
212            IntegerVariable::new(
213                Some(0),
214                Some(Self::exact_i64(m, "bounding half the traversal degree")?),
215            )
216            .map_err(Self::target_construction)?,
217        );
218        variables[2 * m + 2 * n..]
219            .fill(IntegerVariable::new(Some(0), Some(big_m)).map_err(Self::target_construction)?);
220
221        let target =
222            ILP::with_variables(variables, constraints, objective, ObjectiveSense::Minimize)
223                .map_err(Self::target_construction)?;
224
225        Ok(ReductionRPToILP {
226            target,
227            num_edges: m,
228        })
229    }
230}
231
232#[cfg(feature = "example-db")]
233pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
234    vec![crate::example_db::specs::RuleExampleSpec {
235        id: "ruralpostman_to_ilp",
236        build: || {
237            // Triangle: 3 vertices, 3 edges, require edge 0
238            let source = RuralPostman::new(
239                SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]),
240                vec![1, 1, 1],
241                vec![0],
242            );
243            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
244        },
245    }]
246}
247
248#[cfg(test)]
249#[path = "../unit_tests/rules/ruralpostman_ilp.rs"]
250mod tests;
problemreductions/rules/ruralpostman_ilp.rs

problemreductions/rules/
ruralpostman_ilp.rs
