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 from a root chosen on the circuit
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/// - `r_v` for the chosen root, indices `m+n..m+2n`
23/// - `f^t_{e,dir}` flow to vertex t, indices `m+2n..m+2n+2mn`
24#[derive(Debug, Clone)]
25pub struct ReductionLongestCircuitToILP {
26    target: ILP<bool>,
27    num_edges: usize,
28}
29
30impl ReductionResult for ReductionLongestCircuitToILP {
31    type Source = LongestCircuit<SimpleGraph, i64>;
32    type Target = ILP<bool>;
33
34    fn target_problem(&self) -> &ILP<bool> {
35        &self.target
36    }
37
38    /// Extract: output the binary edge-selection vector (y_e).
39    fn extract_solution(
40        &self,
41        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
42    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
43        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
44
45        Ok(target_solution[..self.num_edges]
46            .iter()
47            .map(|&value| value == 1)
48            .collect())
49    }
50}
51
52#[reduction(
53    transform = exact {
54        num_vars = "num_edges + 2 * num_vertices + 2 * num_edges * num_vertices",
55        num_constraints = "2 + num_vertices + 2 * num_vertices^2 + 2 * num_edges * num_vertices",
56    },
57    unavailable = {
58        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
59    }
60)]
61impl ReduceTo<ILP<bool>> for LongestCircuit<SimpleGraph, i64> {
62    type Result = ReductionLongestCircuitToILP;
63
64    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
65        let n = self.num_vertices();
66        let m = self.num_edges();
67        let edges = self.graph().edges();
68        let lengths = self.edge_lengths();
69
70        let num_vars = m
71            .checked_mul(n)
72            .and_then(|flow| flow.checked_add(n))
73            .and_then(|flow_and_vertices| flow_and_vertices.checked_mul(2))
74            .and_then(|auxiliary| auxiliary.checked_add(m))
75            .ok_or_else(|| {
76                crate::rules::ReductionError::integer_overflow::<Self, ILP<bool>>(
77                    "computing the number of cycle and flow variables",
78                )
79            })?;
80
81        let y_idx = |e: usize| -> usize { e };
82        let s_idx = |v: usize| -> usize { m + v };
83        let r_idx = |v: usize| -> usize { m + n + v };
84        let flow_idx = |commodity: usize, edge: usize, dir: usize| -> usize {
85            m + 2 * n + commodity * 2 * m + 2 * edge + dir
86        };
87        let mut vertex_edges = vec![Vec::new(); n];
88        for (edge, &(u, v)) in edges.iter().enumerate() {
89            vertex_edges[u].push(edge);
90            vertex_edges[v].push(edge);
91        }
92
93        let mut constraints = Vec::new();
94
95        // Degree constraints: sum_{e : v in e} y_e = 2 s_v for all v
96        for (v, incident_edges) in vertex_edges.iter().enumerate() {
97            let mut terms: Vec<(usize, i64)> = Vec::new();
98            for &edge in incident_edges {
99                terms.push((y_idx(edge), 1));
100            }
101            terms.push((s_idx(v), -2));
102            constraints.push(LinearConstraint::eq(terms, 0));
103        }
104
105        // At least 3 edges selected
106        let all_edge_terms: Vec<(usize, i64)> = (0..m).map(|e| (y_idx(e), 1)).collect();
107        constraints.push(LinearConstraint::ge(all_edge_terms, 3));
108
109        // Choose exactly one root among the selected vertices.
110        constraints.push(LinearConstraint::eq(
111            (0..n).map(|v| (r_idx(v), 1)).collect(),
112            1,
113        ));
114        for v in 0..n {
115            constraints.push(LinearConstraint::le(vec![(r_idx(v), 1), (s_idx(v), -1)], 0));
116        }
117
118        // Each selected non-root vertex receives one unit from the chosen root.
119        for t in 0..n {
120            // Flow conservation at each vertex v
121            for (v, incident_edges) in vertex_edges.iter().enumerate() {
122                let mut terms = Vec::new();
123                for &edge in incident_edges {
124                    let (u, _) = edges[edge];
125                    // Forward dir: u->w, reverse dir: w->u
126                    if u == v {
127                        terms.push((flow_idx(t, edge, 0), 1)); // outgoing
128                        terms.push((flow_idx(t, edge, 1), -1)); // incoming
129                    } else {
130                        terms.push((flow_idx(t, edge, 0), -1)); // incoming
131                        terms.push((flow_idx(t, edge, 1), 1)); // outgoing
132                    }
133                }
134
135                if v == t {
136                    // Target: outflow - inflow = r_t - s_t.
137                    terms.push((s_idx(t), 1));
138                    terms.push((r_idx(t), -1));
139                    constraints.push(LinearConstraint::eq(terms, 0));
140                } else {
141                    // Only the root can supply flow: 0 <= outflow - inflow <= r_v.
142                    constraints.push(LinearConstraint::ge(terms.clone(), 0));
143                    terms.push((r_idx(v), -1));
144                    constraints.push(LinearConstraint::le(terms, 0));
145                }
146            }
147
148            // Capacity: f^t_{e,dir} <= y_e
149            for e in 0..m {
150                constraints.push(LinearConstraint::le(
151                    vec![(flow_idx(t, e, 0), 1), (y_idx(e), -1)],
152                    0,
153                ));
154                constraints.push(LinearConstraint::le(
155                    vec![(flow_idx(t, e, 1), 1), (y_idx(e), -1)],
156                    0,
157                ));
158            }
159        }
160
161        // Objective: maximize total edge length
162        let objective: Vec<(usize, i64)> = lengths
163            .iter()
164            .enumerate()
165            .map(|(e, &length)| (y_idx(e), length))
166            .collect();
167        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize)
168            .map_err(Self::target_construction)?;
169
170        Ok(ReductionLongestCircuitToILP {
171            target,
172            num_edges: m,
173        })
174    }
175}
176
177#[cfg(feature = "example-db")]
178pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
179    vec![crate::example_db::specs::RuleExampleSpec {
180        id: "longestcircuit_to_ilp",
181        build: || {
182            // Triangle with unit lengths
183            let source = LongestCircuit::new(
184                SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]),
185                vec![1, 1, 1],
186            );
187            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
188        },
189    }]
190}
191
192#[cfg(test)]
193#[path = "../unit_tests/rules/longestcircuit_ilp.rs"]
194mod tests;
problemreductions/rules/longestcircuit_ilp.rs

problemreductions/rules/
longestcircuit_ilp.rs
