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

problemreductions/rules/
bottlenecktravelingsalesman_ilp.rs
