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::models::Decision;
14use crate::reduction;
15use crate::rules::traits::{ReduceTo, ReductionResult};
16use crate::topology::{Graph, SimpleGraph};
17
18/// Result of reducing LongestCircuit to ILP.
19///
20/// Variable layout (all binary):
21/// - `y_e` for edge e, indices `0..m`
22/// - `s_v` for vertex v, indices `m..m+n`
23/// - `r_v` for the chosen root, indices `m+n..m+2n`
24/// - `f^t_{e,dir}` flow to vertex t, indices `m+2n..m+2n+2mn`
25#[derive(Debug, Clone)]
26pub struct ReductionLongestCircuitToILP {
27    target: ILP<bool>,
28    num_edges: usize,
29}
30
31impl ReductionLongestCircuitToILP {
32    fn decode_edges(&self, solution: &[i64]) -> Vec<bool> {
33        solution[..self.num_edges]
34            .iter()
35            .map(|&value| value == 1)
36            .collect()
37    }
38}
39
40impl ReductionResult for ReductionLongestCircuitToILP {
41    type Source = LongestCircuit<SimpleGraph, i64>;
42    type Target = ILP<bool>;
43
44    fn target_problem(&self) -> &ILP<bool> {
45        &self.target
46    }
47
48    /// Extract: output the binary edge-selection vector (y_e).
49    fn extract_solution(
50        &self,
51        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
52    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
53        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
54
55        Ok(self.decode_edges(target_solution))
56    }
57}
58
59#[reduction(transform = {
60    exact {
61        num_vars = "num_edges + 2 * num_vertices + 2 * num_edges * num_vertices",
62        num_constraints = "2 + num_vertices + 2 * num_vertices^2 + 2 * num_edges * num_vertices",
63    },
64    upper_bound {
65        max_constraint_magnitude_bits = "2",
66        num_nonzeros = "(num_edges + 2 * num_vertices + 2 * num_edges * num_vertices) * (2 + num_vertices + 2 * num_vertices^2 + 2 * num_edges * num_vertices)",
67    },
68})]
69impl ReduceTo<ILP<bool>> for LongestCircuit<SimpleGraph, i64> {
70    type Result = ReductionLongestCircuitToILP;
71
72    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
73        let n = self.num_vertices();
74        let m = self.num_edges();
75        let edges = self.graph().edges();
76        let lengths = self.edge_lengths();
77
78        let num_vars = m
79            .checked_mul(n)
80            .and_then(|flow| flow.checked_add(n))
81            .and_then(|flow_and_vertices| flow_and_vertices.checked_mul(2))
82            .and_then(|auxiliary| auxiliary.checked_add(m))
83            .ok_or_else(|| {
84                crate::rules::ReductionError::integer_overflow::<Self, ILP<bool>>(
85                    "computing the number of cycle and flow variables",
86                )
87            })?;
88
89        let y_idx = |e: usize| -> usize { e };
90        let s_idx = |v: usize| -> usize { m + v };
91        let r_idx = |v: usize| -> usize { m + n + v };
92        let flow_idx = |commodity: usize, edge: usize, dir: usize| -> usize {
93            m + 2 * n + commodity * 2 * m + 2 * edge + dir
94        };
95        let mut vertex_edges = vec![Vec::new(); n];
96        for (edge, &(u, v)) in edges.iter().enumerate() {
97            vertex_edges[u].push(edge);
98            vertex_edges[v].push(edge);
99        }
100
101        let mut constraints = Vec::new();
102
103        // Degree constraints: sum_{e : v in e} y_e = 2 s_v for all v
104        for (v, incident_edges) in vertex_edges.iter().enumerate() {
105            let mut terms: Vec<(usize, i64)> = Vec::new();
106            for &edge in incident_edges {
107                terms.push((y_idx(edge), 1));
108            }
109            terms.push((s_idx(v), -2));
110            constraints.push(LinearConstraint::eq(terms, 0));
111        }
112
113        // At least 3 edges selected
114        let all_edge_terms: Vec<(usize, i64)> = (0..m).map(|e| (y_idx(e), 1)).collect();
115        constraints.push(LinearConstraint::ge(all_edge_terms, 3));
116
117        // Choose exactly one root among the selected vertices.
118        constraints.push(LinearConstraint::eq(
119            (0..n).map(|v| (r_idx(v), 1)).collect(),
120            1,
121        ));
122        for v in 0..n {
123            constraints.push(LinearConstraint::le(vec![(r_idx(v), 1), (s_idx(v), -1)], 0));
124        }
125
126        // Each selected non-root vertex receives one unit from the chosen root.
127        for t in 0..n {
128            // Flow conservation at each vertex v
129            for (v, incident_edges) in vertex_edges.iter().enumerate() {
130                let mut terms = Vec::new();
131                for &edge in incident_edges {
132                    let (u, _) = edges[edge];
133                    // Forward dir: u->w, reverse dir: w->u
134                    if u == v {
135                        terms.push((flow_idx(t, edge, 0), 1)); // outgoing
136                        terms.push((flow_idx(t, edge, 1), -1)); // incoming
137                    } else {
138                        terms.push((flow_idx(t, edge, 0), -1)); // incoming
139                        terms.push((flow_idx(t, edge, 1), 1)); // outgoing
140                    }
141                }
142
143                if v == t {
144                    // Target: outflow - inflow = r_t - s_t.
145                    terms.push((s_idx(t), 1));
146                    terms.push((r_idx(t), -1));
147                    constraints.push(LinearConstraint::eq(terms, 0));
148                } else {
149                    // Only the root can supply flow: 0 <= outflow - inflow <= r_v.
150                    constraints.push(LinearConstraint::ge(terms.clone(), 0));
151                    terms.push((r_idx(v), -1));
152                    constraints.push(LinearConstraint::le(terms, 0));
153                }
154            }
155
156            // Capacity: f^t_{e,dir} <= y_e
157            for e in 0..m {
158                constraints.push(LinearConstraint::le(
159                    vec![(flow_idx(t, e, 0), 1), (y_idx(e), -1)],
160                    0,
161                ));
162                constraints.push(LinearConstraint::le(
163                    vec![(flow_idx(t, e, 1), 1), (y_idx(e), -1)],
164                    0,
165                ));
166            }
167        }
168
169        // Objective: maximize total edge length
170        let objective: Vec<(usize, i64)> = lengths
171            .iter()
172            .enumerate()
173            .map(|(e, &length)| (y_idx(e), length))
174            .collect();
175        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize)
176            .map_err(Self::target_construction)?;
177
178        Ok(ReductionLongestCircuitToILP {
179            target,
180            num_edges: m,
181        })
182    }
183}
184
185/// Feasibility encoding of the circuit-length bound, with the existing edge decoder.
186#[derive(Debug, Clone)]
187pub struct ReductionDecisionLongestCircuitToILP {
188    inner: ReductionLongestCircuitToILP,
189}
190
191impl ReductionResult for ReductionDecisionLongestCircuitToILP {
192    type Source = Decision<LongestCircuit<SimpleGraph, i64>>;
193    type Target = ILP<bool>;
194
195    fn target_problem(&self) -> &Self::Target {
196        self.inner.target_problem()
197    }
198
199    fn extract_solution(&self, solution: &Vec<i64>) -> crate::rules::ExtractionResult<Vec<bool>> {
200        crate::rules::traits::validate_target_witness(
201            self.target_problem(),
202            solution,
203            |value| value.value.is_some(),
204            "ILP assignment does not satisfy the bounded circuit constraints",
205        )?;
206        Ok(self.inner.decode_edges(solution))
207    }
208}
209
210#[crate::aggregate_reduction(ilp_feasibility)]
211impl crate::rules::AggregateReductionResult for ReductionDecisionLongestCircuitToILP {}
212
213#[reduction(transform = {
214    exact {
215        num_vars = "num_edges + 2 * num_vertices + 2 * num_edges * num_vertices",
216        num_constraints = "3 + num_vertices + 2 * num_vertices^2 + 2 * num_edges * num_vertices",
217    },
218    upper_bound {
219        max_constraint_magnitude_bits = "max_length_bits + num_edges + 1",
220        num_nonzeros = "(num_edges + 2 * num_vertices + 2 * num_edges * num_vertices) * (3 + num_vertices + 2 * num_vertices^2 + 2 * num_edges * num_vertices)",
221    },
222})]
223impl ReduceTo<ILP<bool>> for Decision<LongestCircuit<SimpleGraph, i64>> {
224    type Result = ReductionDecisionLongestCircuitToILP;
225
226    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
227        let mut inner = ReduceTo::<ILP<bool>>::reduce_to(self.inner())?;
228        let mut constraints = inner.target.constraints().to_vec();
229        // Positive edge lengths bound every circuit by their total. Normalize
230        // thresholds outside that range while retaining one acceptance row.
231        let total_length: i128 = self
232            .inner()
233            .edge_lengths()
234            .iter()
235            .map(|&length| i128::from(length))
236            .sum();
237        let acceptance = if *self.bound() <= 0 {
238            LinearConstraint::ge(vec![], 0)
239        } else if i128::from(*self.bound()) > total_length {
240            LinearConstraint::ge(vec![], 1)
241        } else {
242            LinearConstraint::ge(inner.target.objective().to_vec(), *self.bound())
243        };
244        constraints.push(acceptance);
245        inner.target = ILP::with_variables(
246            inner.target.variables().to_vec(),
247            constraints,
248            vec![],
249            ObjectiveSense::Minimize,
250        )
251        .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
252        Ok(ReductionDecisionLongestCircuitToILP { inner })
253    }
254}
255
256#[cfg(feature = "example-db")]
257pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
258    vec![
259        crate::example_db::specs::RuleExampleSpec {
260            id: "decisionlongestcircuit_to_ilp",
261            build: || {
262                let source =
263                    Decision::new(LongestCircuit::new(SimpleGraph::cycle(3), vec![1i64; 3]), 3);
264                crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
265            },
266        },
267        crate::example_db::specs::RuleExampleSpec {
268            id: "longestcircuit_to_ilp",
269            build: || {
270                // Triangle with unit lengths
271                let source = LongestCircuit::new(
272                    SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]),
273                    vec![1, 1, 1],
274                );
275                crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
276            },
277        },
278    ]
279}
280
281#[cfg(test)]
282#[path = "../unit_tests/rules/longestcircuit_ilp.rs"]
283mod tests;
problemreductions/rules/longestcircuit_ilp.rs

problemreductions/rules/
longestcircuit_ilp.rs
