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

problemreductions/rules/
longestpath_ilp.rs
