problemreductions/rules/
travelingsalesman_ilp.rs

1//! Reduction from TravelingSalesman to ILP (Integer Linear Programming).
2//!
3//! Uses position-based variables x_{v,k} with McCormick linearization.
4//! - Variables: x_{v,k} for vertex v at position k (binary), plus auxiliary y variables
5//! - Constraints: assignment, non-edge consecutive, McCormick
6//! - Objective: minimize total edge weight of the tour
7
8use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
9use crate::models::graph::TravelingSalesman;
10use crate::reduction;
11use crate::rules::ilp_helpers::{mccormick_product, one_hot_decode};
12use crate::rules::traits::{ReduceTo, ReductionResult};
13use crate::topology::{Graph, SimpleGraph};
14
15/// Result of reducing TravelingSalesman to ILP.
16#[derive(Debug, Clone)]
17pub struct ReductionTSPToILP {
18    target: ILP<bool>,
19    /// Number of vertices in the source graph.
20    num_vertices: usize,
21    /// Edges of the source graph (for solution extraction).
22    source_edges: Vec<(usize, usize)>,
23}
24
25impl ReductionResult for ReductionTSPToILP {
26    type Source = TravelingSalesman<SimpleGraph, i64>;
27    type Target = ILP<bool>;
28
29    fn target_problem(&self) -> &ILP<bool> {
30        &self.target
31    }
32
33    /// Extract solution: read tour permutation from x variables,
34    /// then map to edge selection for the source problem.
35    fn extract_solution(
36        &self,
37        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
38    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
39        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
40
41        Ok({
42            let n = self.num_vertices;
43
44            let tour = one_hot_decode(target_solution, n, n, 0)?;
45
46            // Map tour to edge selection
47            let mut edge_selection = vec![false; self.source_edges.len()];
48            for k in 0..n {
49                let u = tour[k];
50                let v = tour[(k + 1) % n];
51                let edge = self
52                    .source_edges
53                    .iter()
54                    .position(|&(a, b)| (a == u && b == v) || (a == v && b == u))
55                    .ok_or_else(|| {
56                        crate::rules::ExtractionError::invalid(format!(
57                            "target tour uses absent source edge ({u}, {v})"
58                        ))
59                    })?;
60                edge_selection[edge] = true;
61            }
62
63            edge_selection
64        })
65    }
66}
67
68// Assignment contributes 2n rows and 2n² coefficients. Absent ordered pairs
69// contribute at most n²(n-1) rows with two coefficients each. The 2nm products
70// each contribute three rows and at most seven normalized coefficients.
71// Edge occurrences cannot be subtracted from absent pairs: duplicates and
72// loops increase m without removing distinct non-loop pairs.
73#[reduction(transform = {
74    exact {
75        num_vars = "num_vertices^2 + 2 * num_vertices * num_edges",
76    },
77    upper_bound {
78        max_constraint_magnitude_bits = "2",
79        num_constraints = "num_vertices^2 * (num_vertices - 1) + 2 * num_vertices + 6 * num_vertices * num_edges",
80        num_nonzeros = "2 * num_vertices^3 + 14 * num_vertices * num_edges",
81    },
82})]
83impl ReduceTo<ILP<bool>> for TravelingSalesman<SimpleGraph, i64> {
84    type Result = ReductionTSPToILP;
85
86    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
87        let n = self.graph().num_vertices();
88        let graph = self.graph();
89        let edges_with_weights = self.edges();
90        let source_edges: Vec<(usize, usize)> =
91            edges_with_weights.iter().map(|&(u, v, _)| (u, v)).collect();
92        let edge_weights: Vec<i64> = edges_with_weights
93            .iter()
94            .map(|&(_, _, weight)| weight)
95            .collect();
96        let m = source_edges.len();
97
98        // Variable layout:
99        // [0, n²): x_{v,k} = vertex v at position k
100        // [n², n² + 2mn): auxiliary y variables for McCormick linearization
101        //   For edge_idx e and position k:
102        //     y_{forward} at n² + e * 2n + 2k      (x_{u,k} * x_{v,(k+1)%n})
103        //     y_{reverse} at n² + e * 2n + 2k + 1  (x_{v,k} * x_{u,(k+1)%n})
104        let num_x = n * n;
105        let num_y = 2 * m * n;
106        let num_vars = num_x + num_y;
107
108        let x_idx = |v: usize, k: usize| -> usize { v * n + k };
109        let y_idx =
110            |edge: usize, k: usize, dir: usize| -> usize { num_x + edge * 2 * n + 2 * k + dir };
111
112        let mut constraints = Vec::new();
113
114        // Constraint 1: Each vertex has exactly one position
115        for v in 0..n {
116            let terms: Vec<(usize, i64)> = (0..n).map(|k| (x_idx(v, k), 1)).collect();
117            constraints.push(LinearConstraint::eq(terms, 1));
118        }
119
120        // Constraint 2: Each position has exactly one vertex
121        for k in 0..n {
122            let terms: Vec<(usize, i64)> = (0..n).map(|v| (x_idx(v, k), 1)).collect();
123            constraints.push(LinearConstraint::eq(terms, 1));
124        }
125
126        // Constraint 3: Non-edge consecutive prohibition
127        // For each ordered pair (v, w) where {v, w} ∉ E and v ≠ w:
128        //   x_{v,k} + x_{w,(k+1) mod n} <= 1 for all k
129        for v in 0..n {
130            for w in 0..n {
131                if v == w {
132                    continue;
133                }
134                if graph.has_edge(v, w) {
135                    continue;
136                }
137                for k in 0..n {
138                    constraints.push(LinearConstraint::le(
139                        vec![(x_idx(v, k), 1), (x_idx(w, (k + 1) % n), 1)],
140                        1,
141                    ));
142                }
143            }
144        }
145
146        // Constraint 4: McCormick linearization for auxiliary variables
147        // For each edge (u, v) at index e:
148        //   Forward (dir=0): y = x_{u,k} * x_{v,(k+1)%n}
149        //   Reverse (dir=1): y = x_{v,k} * x_{u,(k+1)%n}
150        for (e, &(u, v)) in source_edges.iter().enumerate() {
151            for k in 0..n {
152                let k_next = (k + 1) % n;
153
154                // Forward: y_{e,k,0} = x_{u,k} * x_{v,k_next}
155                let y_fwd = y_idx(e, k, 0);
156                let xu = x_idx(u, k);
157                let xv_next = x_idx(v, k_next);
158                constraints.extend(mccormick_product(y_fwd, xu, xv_next));
159
160                // Reverse: y_{e,k,1} = x_{v,k} * x_{u,k_next}
161                let y_rev = y_idx(e, k, 1);
162                let xv = x_idx(v, k);
163                let xu_next = x_idx(u, k_next);
164                constraints.extend(mccormick_product(y_rev, xv, xu_next));
165            }
166        }
167
168        // Objective: minimize Σ_{e=(u,v)} w_e * Σ_k (y_{e,k,0} + y_{e,k,1})
169        let mut objective: Vec<(usize, i64)> = Vec::new();
170        for (e, &w) in edge_weights.iter().enumerate() {
171            for k in 0..n {
172                objective.push((y_idx(e, k, 0), w));
173                objective.push((y_idx(e, k, 1), w));
174            }
175        }
176
177        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
178            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
179
180        Ok(ReductionTSPToILP {
181            target,
182            num_vertices: n,
183            source_edges,
184        })
185    }
186}
187
188#[cfg(feature = "example-db")]
189pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
190    vec![crate::example_db::specs::RuleExampleSpec {
191        id: "travelingsalesman_to_ilp",
192        build: || {
193            let source = TravelingSalesman::new(
194                SimpleGraph::new(4, vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]),
195                vec![10, 15, 20, 35, 25, 30],
196            );
197            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
198        },
199    }]
200}
201
202#[cfg(test)]
203#[path = "../unit_tests/rules/travelingsalesman_ilp.rs"]
204mod tests;
problemreductions/rules/travelingsalesman_ilp.rs

problemreductions/rules/
travelingsalesman_ilp.rs
