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::{Bounded, IntegerVariable, 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<i64, i64, Bounded>,
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, i64>;
28    type Target = ILP<i64, i64, Bounded>;
29
30    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
31        &self.target
32    }
33
34    fn extract_solution(
35        &self,
36        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
37    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
38        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
39
40        Ok({
41            (0..self.num_edges)
42                .map(|edge_idx| {
43                    target_solution[Self::arc_var(edge_idx, 0)] > 0
44                        || target_solution[Self::arc_var(edge_idx, 1)] > 0
45                })
46                .collect()
47        })
48    }
49}
50
51#[reduction(transform = {
52    exact {
53        num_vars = "2 * num_edges + num_vertices",
54        num_constraints = "5 * num_edges + 4 * num_vertices + 1",
55    },
56    upper_bound {
57        max_constraint_magnitude_bits = "num_vertices + 1",
58        num_nonzeros = "(2 * num_edges + num_vertices) * (5 * num_edges + 4 * num_vertices + 1)",
59    },
60})]
61impl ReduceTo<ILP<i64, i64, Bounded>> for LongestPath<SimpleGraph, i64> {
62    type Result = ReductionLongestPathToILP;
63
64    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
65        let edges = self.graph().edges();
66        let num_vertices = self.num_vertices();
67        let num_edges = self.num_edges();
68        let num_vars = 2 * num_edges + num_vertices;
69        let source = self.source_vertex();
70        let target = self.target_vertex();
71        let big_m = Self::exact_i64(num_vertices, "encoding the vertex order")?;
72        let max_order = Self::exact_i64(
73            num_vertices.saturating_sub(1),
74            "encoding the maximum vertex order",
75        )?;
76
77        let order_var = |vertex: usize| 2 * num_edges + vertex;
78
79        let mut outgoing = vec![Vec::new(); num_vertices];
80        let mut incoming = vec![Vec::new(); num_vertices];
81
82        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
83            let forward = ReductionLongestPathToILP::arc_var(edge_idx, 0);
84            let reverse = ReductionLongestPathToILP::arc_var(edge_idx, 1);
85            outgoing[u].push((forward, 1));
86            incoming[v].push((forward, 1));
87            outgoing[v].push((reverse, 1));
88            incoming[u].push((reverse, 1));
89        }
90
91        let mut constraints = Vec::new();
92
93        // Directed arc variables are binary within `ILP<i64, i64, Bounded>`.
94        for edge_idx in 0..num_edges {
95            constraints.push(LinearConstraint::le(
96                vec![(ReductionLongestPathToILP::arc_var(edge_idx, 0), 1)],
97                1,
98            ));
99            constraints.push(LinearConstraint::le(
100                vec![(ReductionLongestPathToILP::arc_var(edge_idx, 1), 1)],
101                1,
102            ));
103        }
104
105        // Order variables stay within [0, |V|-1].
106        for vertex in 0..num_vertices {
107            constraints.push(LinearConstraint::le(
108                vec![(order_var(vertex), 1)],
109                max_order,
110            ));
111        }
112
113        // Flow balance and degree bounds force one simple directed path.
114        for vertex in 0..num_vertices {
115            let mut balance_terms = outgoing[vertex].clone();
116            for &(var, coef) in &incoming[vertex] {
117                balance_terms.push((var, -coef));
118            }
119
120            let rhs = if source != target {
121                if vertex == source {
122                    1
123                } else if vertex == target {
124                    -1
125                } else {
126                    0
127                }
128            } else {
129                0
130            };
131            constraints.push(LinearConstraint::eq(balance_terms, rhs));
132            constraints.push(LinearConstraint::le(outgoing[vertex].clone(), 1));
133            constraints.push(LinearConstraint::le(incoming[vertex].clone(), 1));
134        }
135
136        // An undirected edge can be used in at most one direction.
137        for edge_idx in 0..num_edges {
138            constraints.push(LinearConstraint::le(
139                vec![
140                    (ReductionLongestPathToILP::arc_var(edge_idx, 0), 1),
141                    (ReductionLongestPathToILP::arc_var(edge_idx, 1), 1),
142                ],
143                1,
144            ));
145        }
146
147        // If arc u->v is selected then order(v) >= order(u) + 1.
148        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
149            constraints.push(LinearConstraint::ge(
150                vec![
151                    (order_var(v), 1),
152                    (order_var(u), -1),
153                    (ReductionLongestPathToILP::arc_var(edge_idx, 0), -big_m),
154                ],
155                1 - big_m,
156            ));
157            constraints.push(LinearConstraint::ge(
158                vec![
159                    (order_var(u), 1),
160                    (order_var(v), -1),
161                    (ReductionLongestPathToILP::arc_var(edge_idx, 1), -big_m),
162                ],
163                1 - big_m,
164            ));
165        }
166
167        constraints.push(LinearConstraint::eq(vec![(order_var(source), 1)], 0));
168
169        let mut objective = Vec::with_capacity(2 * num_edges);
170        for (edge_idx, length) in self.edge_lengths().iter().enumerate() {
171            let coeff = *length;
172            objective.push((ReductionLongestPathToILP::arc_var(edge_idx, 0), coeff));
173            objective.push((ReductionLongestPathToILP::arc_var(edge_idx, 1), coeff));
174        }
175
176        let mut variables = vec![IntegerVariable::binary(); num_vars];
177        variables[2 * num_edges..].fill(
178            IntegerVariable::new(Some(0), Some(max_order)).map_err(Self::target_construction)?,
179        );
180
181        Ok(ReductionLongestPathToILP {
182            target: ILP::with_variables(
183                variables,
184                constraints,
185                objective,
186                ObjectiveSense::Maximize,
187            )
188            .map_err(Self::target_construction)?,
189            num_edges,
190        })
191    }
192}
193
194#[cfg(feature = "example-db")]
195pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
196    vec![crate::example_db::specs::RuleExampleSpec {
197        id: "longestpath_to_ilp",
198        build: || {
199            let source =
200                LongestPath::new(SimpleGraph::new(3, vec![(0, 1), (1, 2)]), vec![2, 3], 0, 2);
201            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
202        },
203    }]
204}
205
206#[cfg(test)]
207#[path = "../unit_tests/rules/longestpath_ilp.rs"]
208mod tests;
problemreductions/rules/longestpath_ilp.rs

problemreductions/rules/
longestpath_ilp.rs
