problemreductions/rules/
bottlenecktravelingsalesman_ilp.rs

1//! Reduction from BottleneckTravelingSalesman to ILP (Integer Linear Programming).
2//!
3//! Cyclic position-assignment formulation with bottleneck variable:
4//! - Binary x_{v,p}: vertex v at position p (cyclic tour)
5//! - Binary z_{e,p,dir}: linearized consecutive-pair products
6//! - Integer bottleneck variable b >= w_e * z_{e,p,dir}
7//! - Objective: minimize b
8
9use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
10use crate::models::graph::BottleneckTravelingSalesman;
11use crate::reduction;
12use crate::rules::ilp_helpers::mccormick_product;
13use crate::rules::traits::{ReduceTo, ReductionResult};
14use crate::topology::Graph;
15
16/// Result of reducing BottleneckTravelingSalesman to ILP.
17///
18/// Variable layout (ILP<i32>, all non-negative):
19/// - `x_{v,p}` at index `v * n + p`, bounded to {0,1}
20/// - `z_{e,p,dir}` at index `n^2 + 2*(e*n + p) + dir`, bounded to {0,1}
21/// - `b` (bottleneck) at index `n^2 + 2*m*n`
22#[derive(Debug, Clone)]
23pub struct ReductionBTSPToILP {
24    target: ILP<i32>,
25    num_vertices: usize,
26    source_edges: Vec<(usize, usize)>,
27}
28
29impl ReductionResult for ReductionBTSPToILP {
30    type Source = BottleneckTravelingSalesman;
31    type Target = ILP<i32>;
32
33    fn target_problem(&self) -> &ILP<i32> {
34        &self.target
35    }
36
37    /// Extract: decode tour from x variables, then mark selected edges.
38    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
39        let n = self.num_vertices;
40
41        // Decode tour: for each position p, find vertex v with x_{v,p} = 1
42        let mut tour = vec![0usize; n];
43        for p in 0..n {
44            for v in 0..n {
45                if target_solution[v * n + p] == 1 {
46                    tour[p] = v;
47                    break;
48                }
49            }
50        }
51
52        // Map tour to edge selection
53        let mut edge_selection = vec![0usize; self.source_edges.len()];
54        for p in 0..n {
55            let u = tour[p];
56            let v = tour[(p + 1) % n];
57            for (idx, &(a, b)) in self.source_edges.iter().enumerate() {
58                if (a == u && b == v) || (a == v && b == u) {
59                    edge_selection[idx] = 1;
60                    break;
61                }
62            }
63        }
64
65        edge_selection
66    }
67}
68
69#[reduction(
70    overhead = {
71        num_vars = "num_vertices^2 + 2 * num_edges * num_vertices + 1",
72        num_constraints = "2 * num_vertices + num_vertices^2 + 2 * num_edges * num_vertices + 6 * num_edges * num_vertices + num_vertices + 2 * num_edges * num_vertices",
73    }
74)]
75impl ReduceTo<ILP<i32>> for BottleneckTravelingSalesman {
76    type Result = ReductionBTSPToILP;
77
78    fn reduce_to(&self) -> Self::Result {
79        let n = self.num_vertices();
80        let graph = self.graph();
81        let edges = graph.edges();
82        let m = edges.len();
83        let weights = self.weights();
84
85        let num_x = n * n;
86        let num_z = 2 * m * n;
87        let b_idx = num_x + num_z;
88        let num_vars = num_x + num_z + 1;
89
90        let x_idx = |v: usize, p: usize| -> usize { v * n + p };
91        let z_fwd_idx = |e: usize, p: usize| -> usize { num_x + 2 * (e * n + p) };
92        let z_rev_idx = |e: usize, p: usize| -> usize { num_x + 2 * (e * n + p) + 1 };
93
94        let mut constraints = Vec::new();
95
96        // Assignment: each vertex in exactly one position
97        for v in 0..n {
98            let terms: Vec<(usize, f64)> = (0..n).map(|p| (x_idx(v, p), 1.0)).collect();
99            constraints.push(LinearConstraint::eq(terms, 1.0));
100        }
101
102        // Assignment: each position has exactly one vertex
103        for p in 0..n {
104            let terms: Vec<(usize, f64)> = (0..n).map(|v| (x_idx(v, p), 1.0)).collect();
105            constraints.push(LinearConstraint::eq(terms, 1.0));
106        }
107
108        // Binary bounds for x variables (ILP<i32> is non-negative integer)
109        for idx in 0..num_x {
110            constraints.push(LinearConstraint::le(vec![(idx, 1.0)], 1.0));
111        }
112
113        // Binary bounds for z variables
114        for idx in 0..num_z {
115            constraints.push(LinearConstraint::le(vec![(num_x + idx, 1.0)], 1.0));
116        }
117
118        // McCormick linearization for z variables (cyclic: position (p+1) mod n)
119        for (e, &(u, v)) in edges.iter().enumerate() {
120            for p in 0..n {
121                let p_next = (p + 1) % n;
122                // Forward: z_fwd = x_{u,p} * x_{v,p_next}
123                constraints.extend(mccormick_product(
124                    z_fwd_idx(e, p),
125                    x_idx(u, p),
126                    x_idx(v, p_next),
127                ));
128                // Reverse: z_rev = x_{v,p} * x_{u,p_next}
129                constraints.extend(mccormick_product(
130                    z_rev_idx(e, p),
131                    x_idx(v, p),
132                    x_idx(u, p_next),
133                ));
134            }
135        }
136
137        // Adjacency: for each position p, exactly one edge in either direction
138        for p in 0..n {
139            let mut terms = Vec::new();
140            for e in 0..m {
141                terms.push((z_fwd_idx(e, p), 1.0));
142                terms.push((z_rev_idx(e, p), 1.0));
143            }
144            constraints.push(LinearConstraint::eq(terms, 1.0));
145        }
146
147        // Bottleneck: b >= w_e * z_{e,p,dir} for all e, p, dir
148        for (e, &w) in weights.iter().enumerate() {
149            let w_f64 = w as f64;
150            for p in 0..n {
151                constraints.push(LinearConstraint::ge(
152                    vec![(b_idx, 1.0), (z_fwd_idx(e, p), -w_f64)],
153                    0.0,
154                ));
155                constraints.push(LinearConstraint::ge(
156                    vec![(b_idx, 1.0), (z_rev_idx(e, p), -w_f64)],
157                    0.0,
158                ));
159            }
160        }
161
162        // Objective: minimize b
163        let objective = vec![(b_idx, 1.0)];
164
165        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
166
167        ReductionBTSPToILP {
168            target,
169            num_vertices: n,
170            source_edges: edges,
171        }
172    }
173}
174
175#[cfg(feature = "example-db")]
176pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
177    vec![crate::example_db::specs::RuleExampleSpec {
178        id: "bottlenecktravelingsalesman_to_ilp",
179        build: || {
180            // C4 with varying weights
181            let source = BottleneckTravelingSalesman::new(
182                crate::topology::SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3), (3, 0)]),
183                vec![1, 2, 3, 4],
184            );
185            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
186        },
187    }]
188}
189
190#[cfg(test)]
191#[path = "../unit_tests/rules/bottlenecktravelingsalesman_ilp.rs"]
192mod tests;
problemreductions/rules/bottlenecktravelingsalesman_ilp.rs

problemreductions/rules/
bottlenecktravelingsalesman_ilp.rs
