problemreductions/rules/
minimumfeedbackvertexset_ilp.rs

1//! Reduction from MinimumFeedbackVertexSet to ILP (Integer Linear Programming).
2//!
3//! Uses MTZ-style topological ordering constraints:
4//! - Variables: n binary x_i (vertex removal) + n integer o_i (topological order) = 2n total
5//! - Constraints: For each arc (u->v): o_v - o_u >= 1 - n*(x_u + x_v)
6//!   Plus binary bounds (x_i <= 1) and order bounds (o_i <= n-1)
7//! - Objective: Minimize the weighted sum of removed vertices
8
9use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
10use crate::models::graph::MinimumFeedbackVertexSet;
11use crate::reduction;
12use crate::rules::traits::{ReduceTo, ReductionResult};
13
14/// Result of reducing MinimumFeedbackVertexSet to ILP.
15///
16/// The ILP uses integer variables (`ILP<i32>`) because it needs both
17/// binary selection variables (x_i) and integer ordering variables (o_i).
18///
19/// Variable layout:
20/// - `x_i` at index `i` for `i in 0..n`: binary (0 or 1), vertex removal indicator
21/// - `o_i` at index `n + i` for `i in 0..n`: integer in {0, ..., n-1}, topological order
22#[derive(Debug, Clone)]
23pub struct ReductionMFVSToILP {
24    target: ILP<i32>,
25    /// Number of vertices in the source graph (needed for solution extraction).
26    num_vertices: usize,
27}
28
29impl ReductionResult for ReductionMFVSToILP {
30    type Source = MinimumFeedbackVertexSet<i32>;
31    type Target = ILP<i32>;
32
33    fn target_problem(&self) -> &ILP<i32> {
34        &self.target
35    }
36
37    /// Extract solution from ILP back to MinimumFeedbackVertexSet.
38    ///
39    /// The first n variables of the ILP solution are the binary x_i values,
40    /// which directly correspond to the FVS configuration (1 = removed).
41    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
42        target_solution[..self.num_vertices].to_vec()
43    }
44}
45
46#[reduction(
47    overhead = {
48        num_vars = "2 * num_vertices",
49        num_constraints = "num_arcs + 2 * num_vertices",
50    }
51)]
52impl ReduceTo<ILP<i32>> for MinimumFeedbackVertexSet<i32> {
53    type Result = ReductionMFVSToILP;
54
55    fn reduce_to(&self) -> Self::Result {
56        let n = self.graph().num_vertices();
57        let arcs = self.graph().arcs();
58        let num_vars = 2 * n;
59
60        // Variable indices:
61        // x_i = i         (binary: vertex i removed?)
62        // o_i = n + i     (integer: topological order of vertex i)
63
64        let mut constraints = Vec::new();
65
66        // Binary bounds: x_i <= 1 for i in 0..n
67        for i in 0..n {
68            constraints.push(LinearConstraint::le(vec![(i, 1.0)], 1.0));
69        }
70
71        // Order bounds: o_i <= n - 1 for i in 0..n
72        for i in 0..n {
73            constraints.push(LinearConstraint::le(vec![(n + i, 1.0)], (n - 1) as f64));
74        }
75
76        // Arc constraints: for each arc (u -> v):
77        //   o_v - o_u >= 1 - n * (x_u + x_v)
78        // Rearranged: o_v - o_u + n*x_u + n*x_v >= 1
79        let n_f64 = n as f64;
80        for &(u, v) in &arcs {
81            let terms = vec![
82                (n + v, 1.0),  // o_v
83                (n + u, -1.0), // -o_u
84                (u, n_f64),    // n * x_u
85                (v, n_f64),    // n * x_v
86            ];
87            constraints.push(LinearConstraint::ge(terms, 1.0));
88        }
89
90        // Objective: minimize sum w_i * x_i
91        let objective: Vec<(usize, f64)> = self
92            .weights()
93            .iter()
94            .enumerate()
95            .map(|(i, &w)| (i, w as f64))
96            .collect();
97
98        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
99
100        ReductionMFVSToILP {
101            target,
102            num_vertices: n,
103        }
104    }
105}
106
107#[cfg(feature = "example-db")]
108pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
109    use crate::topology::DirectedGraph;
110
111    vec![crate::example_db::specs::RuleExampleSpec {
112        id: "minimumfeedbackvertexset_to_ilp",
113        build: || {
114            // Simple cycle: 0 -> 1 -> 2 -> 0 (FVS = 1 vertex)
115            let graph = DirectedGraph::new(3, vec![(0, 1), (1, 2), (2, 0)]);
116            let source = MinimumFeedbackVertexSet::new(graph, vec![1i32; 3]);
117            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
118        },
119    }]
120}
121
122#[cfg(test)]
123#[path = "../unit_tests/rules/minimumfeedbackvertexset_ilp.rs"]
124mod tests;
problemreductions/rules/minimumfeedbackvertexset_ilp.rs

problemreductions/rules/
minimumfeedbackvertexset_ilp.rs
