problemreductions/rules/
shortestweightconstrainedpath_ilp.rs

1//! Reduction from ShortestWeightConstrainedPath to ILP (Integer Linear Programming).
2//!
3//! Uses directed-arc variables for each orientation of each undirected edge,
4//! together with integer order variables for MTZ-style subtour elimination.
5//! Flow-balance constraints force a single directed s-t path, the weight
6//! bound constraint enforces the weight limit, and the objective minimizes
7//! total path length.
8
9use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
10use crate::models::graph::ShortestWeightConstrainedPath;
11use crate::reduction;
12use crate::rules::traits::{ReduceTo, ReductionResult};
13use crate::topology::{Graph, SimpleGraph};
14use crate::types::WeightElement;
15
16/// Result of reducing ShortestWeightConstrainedPath to ILP.
17///
18/// Variable layout (within `ILP<i32>`):
19/// - Arc variables: `a_{e,0}` and `a_{e,1}` for each undirected edge `e`
20///   (indices `0..2m`), bounded to {0, 1}
21/// - Order variables: `o_v` for each vertex `v` (indices `2m..2m+n`),
22///   bounded to `[0, n-1]`
23#[derive(Debug, Clone)]
24pub struct ReductionSWCPToILP {
25    target: ILP<i32>,
26    num_edges: usize,
27}
28
29impl ReductionSWCPToILP {
30    fn arc_var(edge_idx: usize, dir: usize) -> usize {
31        2 * edge_idx + dir
32    }
33}
34
35impl ReductionResult for ReductionSWCPToILP {
36    type Source = ShortestWeightConstrainedPath<SimpleGraph, i32>;
37    type Target = ILP<i32>;
38
39    fn target_problem(&self) -> &ILP<i32> {
40        &self.target
41    }
42
43    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
44        (0..self.num_edges)
45            .map(|edge_idx| {
46                usize::from(
47                    target_solution
48                        .get(Self::arc_var(edge_idx, 0))
49                        .copied()
50                        .unwrap_or(0)
51                        > 0
52                        || target_solution
53                            .get(Self::arc_var(edge_idx, 1))
54                            .copied()
55                            .unwrap_or(0)
56                            > 0,
57                )
58            })
59            .collect()
60    }
61}
62
63#[reduction(overhead = {
64    num_vars = "2 * num_edges + num_vertices",
65    num_constraints = "5 * num_edges + 4 * num_vertices + 2",
66})]
67impl ReduceTo<ILP<i32>> for ShortestWeightConstrainedPath<SimpleGraph, i32> {
68    type Result = ReductionSWCPToILP;
69
70    fn reduce_to(&self) -> Self::Result {
71        let edges = self.graph().edges();
72        let num_vertices = self.num_vertices();
73        let num_edges = self.num_edges();
74        let num_vars = 2 * num_edges + num_vertices;
75        let source = self.source_vertex();
76        let target = self.target_vertex();
77        let big_m = num_vertices as f64;
78
79        let order_var = |vertex: usize| 2 * num_edges + vertex;
80
81        // Build adjacency: outgoing[v] and incoming[v] collect arc variable
82        // references for arcs leaving / entering vertex v.
83        let mut outgoing: Vec<Vec<(usize, f64)>> = vec![Vec::new(); num_vertices];
84        let mut incoming: Vec<Vec<(usize, f64)>> = vec![Vec::new(); num_vertices];
85
86        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
87            let forward = ReductionSWCPToILP::arc_var(edge_idx, 0); // u -> v
88            let reverse = ReductionSWCPToILP::arc_var(edge_idx, 1); // v -> u
89            outgoing[u].push((forward, 1.0));
90            incoming[v].push((forward, 1.0));
91            outgoing[v].push((reverse, 1.0));
92            incoming[u].push((reverse, 1.0));
93        }
94
95        let mut constraints = Vec::new();
96
97        // --- Arc variables are binary within ILP<i32>: 0 <= a_{e,d} <= 1 ---
98        for edge_idx in 0..num_edges {
99            constraints.push(LinearConstraint::le(
100                vec![(ReductionSWCPToILP::arc_var(edge_idx, 0), 1.0)],
101                1.0,
102            ));
103            constraints.push(LinearConstraint::le(
104                vec![(ReductionSWCPToILP::arc_var(edge_idx, 1), 1.0)],
105                1.0,
106            ));
107        }
108
109        // --- Order variables stay within [0, |V|-1] ---
110        for vertex in 0..num_vertices {
111            constraints.push(LinearConstraint::le(
112                vec![(order_var(vertex), 1.0)],
113                num_vertices.saturating_sub(1) as f64,
114            ));
115        }
116
117        // --- Flow balance and degree bounds ---
118        for vertex in 0..num_vertices {
119            // net flow: out - in
120            let mut balance_terms = outgoing[vertex].clone();
121            for &(var, coef) in &incoming[vertex] {
122                balance_terms.push((var, -coef));
123            }
124
125            let rhs = if source != target {
126                if vertex == source {
127                    1.0
128                } else if vertex == target {
129                    -1.0
130                } else {
131                    0.0
132                }
133            } else {
134                0.0
135            };
136            constraints.push(LinearConstraint::eq(balance_terms, rhs));
137            constraints.push(LinearConstraint::le(outgoing[vertex].clone(), 1.0));
138            constraints.push(LinearConstraint::le(incoming[vertex].clone(), 1.0));
139        }
140
141        // --- At most one direction per undirected edge ---
142        for edge_idx in 0..num_edges {
143            constraints.push(LinearConstraint::le(
144                vec![
145                    (ReductionSWCPToILP::arc_var(edge_idx, 0), 1.0),
146                    (ReductionSWCPToILP::arc_var(edge_idx, 1), 1.0),
147                ],
148                1.0,
149            ));
150        }
151
152        // --- MTZ ordering: if arc u->v is selected then order(v) >= order(u) + 1 ---
153        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
154            // o_v - o_u - M * a_{e,0} >= 1 - M
155            constraints.push(LinearConstraint::ge(
156                vec![
157                    (order_var(v), 1.0),
158                    (order_var(u), -1.0),
159                    (ReductionSWCPToILP::arc_var(edge_idx, 0), -big_m),
160                ],
161                1.0 - big_m,
162            ));
163            // o_u - o_v - M * a_{e,1} >= 1 - M
164            constraints.push(LinearConstraint::ge(
165                vec![
166                    (order_var(u), 1.0),
167                    (order_var(v), -1.0),
168                    (ReductionSWCPToILP::arc_var(edge_idx, 1), -big_m),
169                ],
170                1.0 - big_m,
171            ));
172        }
173
174        // --- Fix source order to 0 ---
175        constraints.push(LinearConstraint::eq(vec![(order_var(source), 1.0)], 0.0));
176
177        // --- Weight bound: Σ wt_e * (a_{e,0} + a_{e,1}) <= weight_bound ---
178        let weight_terms: Vec<(usize, f64)> = edges
179            .iter()
180            .enumerate()
181            .flat_map(|(edge_idx, _)| {
182                let coeff = self.edge_weights()[edge_idx].to_sum() as f64;
183                [
184                    (ReductionSWCPToILP::arc_var(edge_idx, 0), coeff),
185                    (ReductionSWCPToILP::arc_var(edge_idx, 1), coeff),
186                ]
187            })
188            .collect();
189        constraints.push(LinearConstraint::le(
190            weight_terms,
191            *self.weight_bound() as f64,
192        ));
193
194        // --- Objective: minimize total path length ---
195        let objective: Vec<(usize, f64)> = edges
196            .iter()
197            .enumerate()
198            .flat_map(|(edge_idx, _)| {
199                let coeff = self.edge_lengths()[edge_idx].to_sum() as f64;
200                [
201                    (ReductionSWCPToILP::arc_var(edge_idx, 0), coeff),
202                    (ReductionSWCPToILP::arc_var(edge_idx, 1), coeff),
203                ]
204            })
205            .collect();
206        let target_ilp = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
207
208        ReductionSWCPToILP {
209            target: target_ilp,
210            num_edges,
211        }
212    }
213}
214
215#[cfg(feature = "example-db")]
216pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
217    vec![crate::example_db::specs::RuleExampleSpec {
218        id: "shortestweightconstrainedpath_to_ilp",
219        build: || {
220            // 3-vertex path: 0 -- 1 -- 2, s=0, t=2
221            // edge_lengths = [2, 3], edge_weights = [1, 2]
222            // weight_bound = 4
223            // The only s-t path uses both edges: length=5, weight=3 <= 4 => feasible
224            let source = ShortestWeightConstrainedPath::new(
225                SimpleGraph::new(3, vec![(0, 1), (1, 2)]),
226                vec![2, 3],
227                vec![1, 2],
228                0,
229                2,
230                4,
231            );
232            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
233        },
234    }]
235}
236
237#[cfg(test)]
238#[path = "../unit_tests/rules/shortestweightconstrainedpath_ilp.rs"]
239mod tests;
problemreductions/rules/shortestweightconstrainedpath_ilp.rs

problemreductions/rules/
shortestweightconstrainedpath_ilp.rs
