problemreductions/rules/
bottlenecktravelingsalesman_ilp.rs

1//! Bottleneck TSP to ILP using cyclic positions and a selected maximum edge.
2
3use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
4use crate::models::graph::BottleneckTravelingSalesman;
5use crate::reduction;
6use crate::rules::traits::{ReduceTo, ReductionResult};
7use crate::topology::Graph;
8
9/// A tour is encoded by positions and distinct directed uses of source edges.
10/// One selected maximum-weight edge carries the exact objective coefficient.
11#[derive(Debug, Clone)]
12pub struct ReductionBTSPToILP {
13    target: ILP<bool>,
14    num_vertices: usize,
15    num_edges: usize,
16}
17
18impl ReductionResult for ReductionBTSPToILP {
19    type Source = BottleneckTravelingSalesman;
20    type Target = ILP<bool>;
21
22    fn target_problem(&self) -> &ILP<bool> {
23        &self.target
24    }
25
26    fn extract_solution(
27        &self,
28        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
29    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
30        crate::rules::traits::validate_target_witness(
31            self.target_problem(),
32            target_solution,
33            |value| value.is_valid(),
34            "target ILP assignment is infeasible",
35        )?;
36        let n = self.num_vertices;
37        Ok((0..self.num_edges)
38            .map(|edge| {
39                (0..2 * n).any(|offset| target_solution[n * n + 2 * n * edge + offset] == 1)
40            })
41            .collect())
42    }
43}
44
45impl ReductionBTSPToILP {
46    fn dimensions(
47        n: usize,
48        m: usize,
49    ) -> Result<(usize, usize, usize, usize), crate::rules::ReductionError> {
50        let overflow = || {
51            crate::rules::ReductionError::integer_overflow::<BottleneckTravelingSalesman, ILP<bool>>(
52                "sizing the cyclic edge-selection formulation",
53            )
54        };
55        let x = n.checked_mul(n).ok_or_else(overflow)?;
56        let z = n
57            .checked_mul(m)
58            .and_then(|v| v.checked_mul(2))
59            .ok_or_else(overflow)?;
60        let vars = x
61            .checked_add(z)
62            .and_then(|v| v.checked_add(m))
63            .ok_or_else(overflow)?;
64        let constraints = vars
65            .checked_add(z)
66            .and_then(|v| v.checked_add(z))
67            .and_then(|v| {
68                n.checked_add(m)
69                    .and_then(|extra| extra.checked_mul(3))
70                    .and_then(|extra| v.checked_add(extra))
71            })
72            .and_then(|v| v.checked_add(1))
73            .ok_or_else(overflow)?;
74        <BottleneckTravelingSalesman as ReduceTo<ILP<bool>>>::exact_i64(
75            vars,
76            "bounding binary constraint accumulation",
77        )?;
78        Ok((x, z, vars, constraints))
79    }
80}
81
82// Binary/assignment/implication/selection rows contribute 3n^2+18mn+3m
83// terms. Weight-threshold selectors add at most m^2 terms, including ties.
84// Loop orientations and parallel edges remain separate variables.
85#[reduction(transform = {
86    exact {
87        num_vars = "num_vertices^2 + 2 * num_edges * num_vertices + num_edges",
88        num_constraints = "num_vertices^2 + 6 * num_edges * num_vertices + 4 * num_edges + 3 * num_vertices + 1",
89    },
90    upper_bound {
91        max_constraint_magnitude_bits = "2",
92        num_nonzeros = "3 * num_vertices^2 + 18 * num_edges * num_vertices + num_edges^2 + 3 * num_edges",
93    },
94})]
95impl ReduceTo<ILP<bool>> for BottleneckTravelingSalesman {
96    type Result = ReductionBTSPToILP;
97
98    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
99        let n = self.num_vertices();
100        let edges = self.graph().edges();
101        let m = edges.len();
102        let weights = self.weights();
103        let (num_x, num_z, num_vars, num_constraints) = ReductionBTSPToILP::dimensions(n, m)?;
104        let x = |vertex: usize, position: usize| vertex * n + position;
105        let z = |edge: usize, position: usize, direction: usize| {
106            num_x + 2 * (edge * n + position) + direction
107        };
108        let q = |edge: usize| num_x + num_z + edge;
109        let uses = |edge: usize| {
110            (0..n)
111                .flat_map(move |p| [(z(edge, p, 0), 1), (z(edge, p, 1), 1)])
112                .collect::<Vec<_>>()
113        };
114        let mut constraints = Vec::with_capacity(num_constraints);
115        // ILP<bool> variables are nonnegative. Check binary bounds before sums.
116        for variable in 0..num_vars {
117            constraints.push(LinearConstraint::le(vec![(variable, 1)], 1));
118        }
119        for vertex in 0..n {
120            constraints.push(LinearConstraint::eq(
121                (0..n).map(|p| (x(vertex, p), 1)).collect(),
122                1,
123            ));
124        }
125        for p in 0..n {
126            constraints.push(LinearConstraint::eq(
127                (0..n).map(|vertex| (x(vertex, p), 1)).collect(),
128                1,
129            ));
130        }
131        // Choose one actual edge at each cyclic step. Parallel edges remain
132        // independent choices, and the two orientations of a loop are choices.
133        for (edge, &(u, v)) in edges.iter().enumerate() {
134            for p in 0..n {
135                for (direction, a, b) in [(0, u, v), (1, v, u)] {
136                    constraints.push(LinearConstraint::le(
137                        vec![(z(edge, p, direction), 1), (x(a, p), -1)],
138                        0,
139                    ));
140                    constraints.push(LinearConstraint::le(
141                        vec![(z(edge, p, direction), 1), (x(b, (p + 1) % n), -1)],
142                        0,
143                    ));
144                }
145            }
146        }
147        for p in 0..n {
148            constraints.push(LinearConstraint::eq(
149                (0..m)
150                    .flat_map(|edge| [(z(edge, p, 0), 1), (z(edge, p, 1), 1)])
151                    .collect(),
152                1,
153            ));
154        }
155        for edge in 0..m {
156            constraints.push(LinearConstraint::le(uses(edge), 1));
157        }
158        // The selector is a used edge whose weight dominates every used edge.
159        // We compare weights without subtraction or negation, including MIN.
160        constraints.push(LinearConstraint::eq(
161            (0..m).map(|edge| (q(edge), 1)).collect(),
162            1,
163        ));
164        for edge in 0..m {
165            let mut threshold = uses(edge);
166            threshold.extend(
167                (0..m)
168                    .filter(|&other| weights[other] >= weights[edge])
169                    .map(|other| (q(other), -1)),
170            );
171            constraints.push(LinearConstraint::le(threshold, 0));
172            let mut selected = vec![(q(edge), 1)];
173            selected.extend(uses(edge).into_iter().map(|(var, _)| (var, -1)));
174            constraints.push(LinearConstraint::le(selected, 0));
175        }
176        let objective = weights
177            .into_iter()
178            .enumerate()
179            .map(|(edge, weight)| (q(edge), weight))
180            .collect();
181        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
182            .map_err(Self::target_construction)?;
183        Ok(ReductionBTSPToILP {
184            target,
185            num_vertices: n,
186            num_edges: m,
187        })
188    }
189}
190
191#[cfg(feature = "example-db")]
192pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
193    vec![crate::example_db::specs::RuleExampleSpec {
194        id: "bottlenecktravelingsalesman_to_ilp",
195        build: || {
196            // C4 with varying weights
197            let source = BottleneckTravelingSalesman::new(
198                crate::topology::SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3), (3, 0)]),
199                vec![1, 2, 3, 4],
200            );
201            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
202        },
203    }]
204}
205
206#[cfg(test)]
207#[path = "../unit_tests/rules/bottlenecktravelingsalesman_ilp.rs"]
208mod tests;
problemreductions/rules/bottlenecktravelingsalesman_ilp.rs

problemreductions/rules/
bottlenecktravelingsalesman_ilp.rs
