problemreductions/rules/
longestpath_ilp.rs

1//! Reduction from LongestPath to ILP.
2//!
3//! The reduction uses one directed-arc variable for each orientation of each
4//! undirected edge, together with integer order variables for the selected
5//! path positions. Flow-balance constraints force a single directed `s-t` path,
6//! while MTZ-style ordering constraints eliminate detached cycles.
7
8use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
9use crate::models::graph::LongestPath;
10use crate::reduction;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12use crate::topology::{Graph, SimpleGraph};
13
14#[derive(Debug, Clone)]
15pub struct ReductionLongestPathToILP {
16    target: ILP<i32>,
17    num_edges: usize,
18}
19
20impl ReductionLongestPathToILP {
21    fn arc_var(edge_idx: usize, dir: usize) -> usize {
22        2 * edge_idx + dir
23    }
24}
25
26impl ReductionResult for ReductionLongestPathToILP {
27    type Source = LongestPath<SimpleGraph, i32>;
28    type Target = ILP<i32>;
29
30    fn target_problem(&self) -> &ILP<i32> {
31        &self.target
32    }
33
34    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
35        (0..self.num_edges)
36            .map(|edge_idx| {
37                usize::from(
38                    target_solution
39                        .get(Self::arc_var(edge_idx, 0))
40                        .copied()
41                        .unwrap_or(0)
42                        > 0
43                        || target_solution
44                            .get(Self::arc_var(edge_idx, 1))
45                            .copied()
46                            .unwrap_or(0)
47                            > 0,
48                )
49            })
50            .collect()
51    }
52}
53
54#[reduction(overhead = {
55    num_vars = "2 * num_edges + num_vertices",
56    num_constraints = "5 * num_edges + 4 * num_vertices + 1",
57})]
58impl ReduceTo<ILP<i32>> for LongestPath<SimpleGraph, i32> {
59    type Result = ReductionLongestPathToILP;
60
61    fn reduce_to(&self) -> Self::Result {
62        let edges = self.graph().edges();
63        let num_vertices = self.num_vertices();
64        let num_edges = self.num_edges();
65        let num_vars = 2 * num_edges + num_vertices;
66        let source = self.source_vertex();
67        let target = self.target_vertex();
68        let big_m = num_vertices as f64;
69
70        let order_var = |vertex: usize| 2 * num_edges + vertex;
71
72        let mut outgoing = vec![Vec::new(); num_vertices];
73        let mut incoming = vec![Vec::new(); num_vertices];
74
75        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
76            let forward = ReductionLongestPathToILP::arc_var(edge_idx, 0);
77            let reverse = ReductionLongestPathToILP::arc_var(edge_idx, 1);
78            outgoing[u].push((forward, 1.0));
79            incoming[v].push((forward, 1.0));
80            outgoing[v].push((reverse, 1.0));
81            incoming[u].push((reverse, 1.0));
82        }
83
84        let mut constraints = Vec::new();
85
86        // Directed arc variables are binary within ILP<i32>.
87        for edge_idx in 0..num_edges {
88            constraints.push(LinearConstraint::le(
89                vec![(ReductionLongestPathToILP::arc_var(edge_idx, 0), 1.0)],
90                1.0,
91            ));
92            constraints.push(LinearConstraint::le(
93                vec![(ReductionLongestPathToILP::arc_var(edge_idx, 1), 1.0)],
94                1.0,
95            ));
96        }
97
98        // Order variables stay within [0, |V|-1].
99        for vertex in 0..num_vertices {
100            constraints.push(LinearConstraint::le(
101                vec![(order_var(vertex), 1.0)],
102                num_vertices.saturating_sub(1) as f64,
103            ));
104        }
105
106        // Flow balance and degree bounds force one simple directed path.
107        for vertex in 0..num_vertices {
108            let mut balance_terms = outgoing[vertex].clone();
109            for &(var, coef) in &incoming[vertex] {
110                balance_terms.push((var, -coef));
111            }
112
113            let rhs = if source != target {
114                if vertex == source {
115                    1.0
116                } else if vertex == target {
117                    -1.0
118                } else {
119                    0.0
120                }
121            } else {
122                0.0
123            };
124            constraints.push(LinearConstraint::eq(balance_terms, rhs));
125            constraints.push(LinearConstraint::le(outgoing[vertex].clone(), 1.0));
126            constraints.push(LinearConstraint::le(incoming[vertex].clone(), 1.0));
127        }
128
129        // An undirected edge can be used in at most one direction.
130        for edge_idx in 0..num_edges {
131            constraints.push(LinearConstraint::le(
132                vec![
133                    (ReductionLongestPathToILP::arc_var(edge_idx, 0), 1.0),
134                    (ReductionLongestPathToILP::arc_var(edge_idx, 1), 1.0),
135                ],
136                1.0,
137            ));
138        }
139
140        // If arc u->v is selected then order(v) >= order(u) + 1.
141        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
142            constraints.push(LinearConstraint::ge(
143                vec![
144                    (order_var(v), 1.0),
145                    (order_var(u), -1.0),
146                    (ReductionLongestPathToILP::arc_var(edge_idx, 0), -big_m),
147                ],
148                1.0 - big_m,
149            ));
150            constraints.push(LinearConstraint::ge(
151                vec![
152                    (order_var(u), 1.0),
153                    (order_var(v), -1.0),
154                    (ReductionLongestPathToILP::arc_var(edge_idx, 1), -big_m),
155                ],
156                1.0 - big_m,
157            ));
158        }
159
160        constraints.push(LinearConstraint::eq(vec![(order_var(source), 1.0)], 0.0));
161
162        let mut objective = Vec::with_capacity(2 * num_edges);
163        for (edge_idx, length) in self.edge_lengths().iter().enumerate() {
164            let coeff = f64::from(*length);
165            objective.push((ReductionLongestPathToILP::arc_var(edge_idx, 0), coeff));
166            objective.push((ReductionLongestPathToILP::arc_var(edge_idx, 1), coeff));
167        }
168
169        ReductionLongestPathToILP {
170            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize),
171            num_edges,
172        }
173    }
174}
175
176#[cfg(feature = "example-db")]
177pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
178    vec![crate::example_db::specs::RuleExampleSpec {
179        id: "longestpath_to_ilp",
180        build: || {
181            let source =
182                LongestPath::new(SimpleGraph::new(3, vec![(0, 1), (1, 2)]), vec![2, 3], 0, 2);
183            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
184        },
185    }]
186}
187
188#[cfg(test)]
189#[path = "../unit_tests/rules/longestpath_ilp.rs"]
190mod tests;
problemreductions/rules/longestpath_ilp.rs

problemreductions/rules/
longestpath_ilp.rs
