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#[reduction(
69    transform = exact {
70        num_vars = "num_vertices^2 + 2 * num_vertices * num_edges",
71        num_constraints = "num_vertices^3 + -1 * num_vertices^2 + 2 * num_vertices + 4 * num_vertices * num_edges",
72    },
73    unavailable = {
74        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
75    }
76)]
77impl ReduceTo<ILP<bool>> for TravelingSalesman<SimpleGraph, i64> {
78    type Result = ReductionTSPToILP;
79
80    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
81        let n = self.graph().num_vertices();
82        let graph = self.graph();
83        let edges_with_weights = self.edges();
84        let source_edges: Vec<(usize, usize)> =
85            edges_with_weights.iter().map(|&(u, v, _)| (u, v)).collect();
86        let edge_weights: Vec<i64> = edges_with_weights
87            .iter()
88            .map(|&(_, _, weight)| weight)
89            .collect();
90        let m = source_edges.len();
91
92        // Variable layout:
93        // [0, n²): x_{v,k} = vertex v at position k
94        // [n², n² + 2mn): auxiliary y variables for McCormick linearization
95        //   For edge_idx e and position k:
96        //     y_{forward} at n² + e * 2n + 2k      (x_{u,k} * x_{v,(k+1)%n})
97        //     y_{reverse} at n² + e * 2n + 2k + 1  (x_{v,k} * x_{u,(k+1)%n})
98        let num_x = n * n;
99        let num_y = 2 * m * n;
100        let num_vars = num_x + num_y;
101
102        let x_idx = |v: usize, k: usize| -> usize { v * n + k };
103        let y_idx =
104            |edge: usize, k: usize, dir: usize| -> usize { num_x + edge * 2 * n + 2 * k + dir };
105
106        let mut constraints = Vec::new();
107
108        // Constraint 1: Each vertex has exactly one position
109        for v in 0..n {
110            let terms: Vec<(usize, i64)> = (0..n).map(|k| (x_idx(v, k), 1)).collect();
111            constraints.push(LinearConstraint::eq(terms, 1));
112        }
113
114        // Constraint 2: Each position has exactly one vertex
115        for k in 0..n {
116            let terms: Vec<(usize, i64)> = (0..n).map(|v| (x_idx(v, k), 1)).collect();
117            constraints.push(LinearConstraint::eq(terms, 1));
118        }
119
120        // Constraint 3: Non-edge consecutive prohibition
121        // For each ordered pair (v, w) where {v, w} ∉ E and v ≠ w:
122        //   x_{v,k} + x_{w,(k+1) mod n} <= 1 for all k
123        for v in 0..n {
124            for w in 0..n {
125                if v == w {
126                    continue;
127                }
128                if graph.has_edge(v, w) {
129                    continue;
130                }
131                for k in 0..n {
132                    constraints.push(LinearConstraint::le(
133                        vec![(x_idx(v, k), 1), (x_idx(w, (k + 1) % n), 1)],
134                        1,
135                    ));
136                }
137            }
138        }
139
140        // Constraint 4: McCormick linearization for auxiliary variables
141        // For each edge (u, v) at index e:
142        //   Forward (dir=0): y = x_{u,k} * x_{v,(k+1)%n}
143        //   Reverse (dir=1): y = x_{v,k} * x_{u,(k+1)%n}
144        for (e, &(u, v)) in source_edges.iter().enumerate() {
145            for k in 0..n {
146                let k_next = (k + 1) % n;
147
148                // Forward: y_{e,k,0} = x_{u,k} * x_{v,k_next}
149                let y_fwd = y_idx(e, k, 0);
150                let xu = x_idx(u, k);
151                let xv_next = x_idx(v, k_next);
152                constraints.extend(mccormick_product(y_fwd, xu, xv_next));
153
154                // Reverse: y_{e,k,1} = x_{v,k} * x_{u,k_next}
155                let y_rev = y_idx(e, k, 1);
156                let xv = x_idx(v, k);
157                let xu_next = x_idx(u, k_next);
158                constraints.extend(mccormick_product(y_rev, xv, xu_next));
159            }
160        }
161
162        // Objective: minimize Σ_{e=(u,v)} w_e * Σ_k (y_{e,k,0} + y_{e,k,1})
163        let mut objective: Vec<(usize, i64)> = Vec::new();
164        for (e, &w) in edge_weights.iter().enumerate() {
165            for k in 0..n {
166                objective.push((y_idx(e, k, 0), w));
167                objective.push((y_idx(e, k, 1), w));
168            }
169        }
170
171        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
172            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
173
174        Ok(ReductionTSPToILP {
175            target,
176            num_vertices: n,
177            source_edges,
178        })
179    }
180}
181
182#[cfg(feature = "example-db")]
183pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
184    vec![crate::example_db::specs::RuleExampleSpec {
185        id: "travelingsalesman_to_ilp",
186        build: || {
187            let source = TravelingSalesman::new(
188                SimpleGraph::new(4, vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]),
189                vec![10, 15, 20, 35, 25, 30],
190            );
191            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
192        },
193    }]
194}
195
196#[cfg(test)]
197#[path = "../unit_tests/rules/travelingsalesman_ilp.rs"]
198mod tests;
problemreductions/rules/travelingsalesman_ilp.rs

problemreductions/rules/
travelingsalesman_ilp.rs
