problemreductions/rules/
longestcircuit_ilp.rs

1//! Reduction from LongestCircuit to ILP (Integer Linear Programming).
2//!
3//! Direct cycle-selection formulation:
4//! - Binary y_e for edge selection
5//! - Binary s_v for vertex on circuit
6//! - Degree: sum_{e : v in e} y_e = 2 s_v
7//! - At least 3 edges selected
8//! - Maximize: sum l_e y_e
9//! - Multi-commodity flow connectivity
10
11use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
12use crate::models::graph::LongestCircuit;
13use crate::reduction;
14use crate::rules::traits::{ReduceTo, ReductionResult};
15use crate::topology::{Graph, SimpleGraph};
16
17/// Result of reducing LongestCircuit to ILP.
18///
19/// Variable layout (all binary):
20/// - `y_e` for edge e, indices `0..m`
21/// - `s_v` for vertex v, indices `m..m+n`
22/// - `f^t_{e,dir}` flow for commodity t, indices `m+n..m+n+2m*(n-1)`
23#[derive(Debug, Clone)]
24pub struct ReductionLongestCircuitToILP {
25    target: ILP<bool>,
26    num_edges: usize,
27}
28
29impl ReductionResult for ReductionLongestCircuitToILP {
30    type Source = LongestCircuit<SimpleGraph, i32>;
31    type Target = ILP<bool>;
32
33    fn target_problem(&self) -> &ILP<bool> {
34        &self.target
35    }
36
37    /// Extract: output the binary edge-selection vector (y_e).
38    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
39        target_solution[..self.num_edges].to_vec()
40    }
41}
42
43#[reduction(
44    overhead = {
45        num_vars = "num_edges + num_vertices + 2 * num_edges * (num_vertices - 1)",
46        num_constraints = "1 + num_vertices^2 + 2 * num_edges * (num_vertices - 1)",
47    }
48)]
49impl ReduceTo<ILP<bool>> for LongestCircuit<SimpleGraph, i32> {
50    type Result = ReductionLongestCircuitToILP;
51
52    fn reduce_to(&self) -> Self::Result {
53        let n = self.num_vertices();
54        let m = self.num_edges();
55        let edges = self.graph().edges();
56        let lengths = self.edge_lengths();
57
58        let y_idx = |e: usize| -> usize { e };
59        let s_idx = |v: usize| -> usize { m + v };
60
61        // Multi-commodity flow for connectivity
62        let num_commodities = n.saturating_sub(1);
63        let num_flow = 2 * m * num_commodities;
64        let num_vars = m + n + num_flow;
65
66        let flow_idx = |commodity: usize, edge: usize, dir: usize| -> usize {
67            m + n + commodity * 2 * m + 2 * edge + dir
68        };
69
70        let mut constraints = Vec::new();
71
72        // Degree constraints: sum_{e : v in e} y_e = 2 s_v for all v
73        for v in 0..n {
74            let mut terms: Vec<(usize, f64)> = Vec::new();
75            for (e, &(u, w)) in edges.iter().enumerate() {
76                if u == v || w == v {
77                    terms.push((y_idx(e), 1.0));
78                }
79            }
80            terms.push((s_idx(v), -2.0));
81            constraints.push(LinearConstraint::eq(terms, 0.0));
82        }
83
84        // At least 3 edges selected
85        let all_edge_terms: Vec<(usize, f64)> = (0..m).map(|e| (y_idx(e), 1.0)).collect();
86        constraints.push(LinearConstraint::ge(all_edge_terms, 3.0));
87
88        // Multi-commodity flow for connectivity
89        // Root = vertex 0. For each non-root vertex t (commodity index = t-1):
90        for t in 1..n {
91            let commodity = t - 1;
92
93            // Flow conservation at each vertex v
94            for v in 0..n {
95                let mut terms = Vec::new();
96                for (e, &(u, w)) in edges.iter().enumerate() {
97                    // Forward dir: u->w, reverse dir: w->u
98                    if u == v {
99                        terms.push((flow_idx(commodity, e, 0), 1.0)); // outgoing
100                        terms.push((flow_idx(commodity, e, 1), -1.0)); // incoming
101                    }
102                    if w == v {
103                        terms.push((flow_idx(commodity, e, 0), -1.0)); // incoming
104                        terms.push((flow_idx(commodity, e, 1), 1.0)); // outgoing
105                    }
106                }
107
108                if v == 0 {
109                    // Root: outflow - inflow = s_t
110                    terms.push((s_idx(t), -1.0));
111                    constraints.push(LinearConstraint::eq(terms, 0.0));
112                } else if v == t {
113                    // Target: outflow - inflow = -s_t
114                    terms.push((s_idx(t), 1.0));
115                    constraints.push(LinearConstraint::eq(terms, 0.0));
116                } else {
117                    // Transit: outflow - inflow = 0
118                    constraints.push(LinearConstraint::eq(terms, 0.0));
119                }
120            }
121
122            // Capacity: f^t_{e,dir} <= y_e
123            for e in 0..m {
124                constraints.push(LinearConstraint::le(
125                    vec![(flow_idx(commodity, e, 0), 1.0), (y_idx(e), -1.0)],
126                    0.0,
127                ));
128                constraints.push(LinearConstraint::le(
129                    vec![(flow_idx(commodity, e, 1), 1.0), (y_idx(e), -1.0)],
130                    0.0,
131                ));
132            }
133        }
134
135        // Objective: maximize total edge length
136        let objective: Vec<(usize, f64)> = lengths
137            .iter()
138            .enumerate()
139            .map(|(e, &l)| (y_idx(e), l as f64))
140            .collect();
141        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize);
142
143        ReductionLongestCircuitToILP {
144            target,
145            num_edges: m,
146        }
147    }
148}
149
150#[cfg(feature = "example-db")]
151pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
152    vec![crate::example_db::specs::RuleExampleSpec {
153        id: "longestcircuit_to_ilp",
154        build: || {
155            // Triangle with unit lengths
156            let source = LongestCircuit::new(
157                SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]),
158                vec![1, 1, 1],
159            );
160            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
161        },
162    }]
163}
164
165#[cfg(test)]
166#[path = "../unit_tests/rules/longestcircuit_ilp.rs"]
167mod tests;
problemreductions/rules/longestcircuit_ilp.rs

problemreductions/rules/
longestcircuit_ilp.rs
