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::{Bounded, IntegerVariable, 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<i64, i64, Bounded>`) 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<i64, i64, Bounded>,
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<i64>;
31    type Target = ILP<i64, i64, Bounded>;
32
33    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
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(
42        &self,
43        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
44    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
45        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
46
47        Ok(target_solution[..self.num_vertices]
48            .iter()
49            .map(|&value| value == 1)
50            .collect())
51    }
52}
53
54#[reduction(transform = {
55    exact {
56        num_vars = "2 * num_vertices",
57        num_constraints = "num_arcs + 2 * num_vertices",
58    },
59    upper_bound {
60        max_constraint_magnitude_bits = "2 * num_vertices + 1",
61        num_nonzeros = "(2 * num_vertices) * (num_arcs + 2 * num_vertices)",
62    },
63})]
64impl ReduceTo<ILP<i64, i64, Bounded>> for MinimumFeedbackVertexSet<i64> {
65    type Result = ReductionMFVSToILP;
66
67    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
68        let n = self.graph().num_vertices();
69        let arcs = self.graph().arcs();
70        let num_vars = 2 * n;
71
72        // Variable indices:
73        // x_i = i         (binary: vertex i removed?)
74        // o_i = n + i     (integer: topological order of vertex i)
75
76        let mut constraints = Vec::new();
77        let n_i64 = <Self as ReduceTo<ILP<i64, i64, Bounded>>>::exact_i64(
78            n,
79            "encoding the topological order",
80        )?;
81
82        // Binary bounds: x_i <= 1 for i in 0..n
83        for i in 0..n {
84            constraints.push(LinearConstraint::le(vec![(i, 1)], 1));
85        }
86
87        // Order bounds: o_i <= n - 1 for i in 0..n
88        for i in 0..n {
89            constraints.push(LinearConstraint::le(vec![(n + i, 1)], n_i64 - 1));
90        }
91
92        // Arc constraints: for each arc (u -> v):
93        //   o_v - o_u >= 1 - n * (x_u + x_v)
94        // Rearranged: o_v - o_u + n*x_u + n*x_v >= 1
95        for &(u, v) in &arcs {
96            let terms = vec![
97                (n + v, 1),  // o_v
98                (n + u, -1), // -o_u
99                (u, n_i64),  // n * x_u
100                (v, n_i64),  // n * x_v
101            ];
102            constraints.push(LinearConstraint::ge(terms, 1));
103        }
104
105        // Objective: minimize sum w_i * x_i
106        let objective: Vec<(usize, i64)> = self
107            .weights()
108            .iter()
109            .enumerate()
110            .map(|(vertex, &weight)| (vertex, weight))
111            .collect();
112
113        let mut variables = vec![IntegerVariable::binary(); num_vars];
114        variables[n..].fill(
115            IntegerVariable::new(Some(0), Some((n_i64 - 1).max(0)))
116                .map_err(<Self as ReduceTo<ILP<i64, i64, Bounded>>>::target_construction)?,
117        );
118
119        let target =
120            ILP::with_variables(variables, constraints, objective, ObjectiveSense::Minimize)
121                .map_err(<Self as ReduceTo<ILP<i64, i64, Bounded>>>::target_construction)?;
122
123        Ok(ReductionMFVSToILP {
124            target,
125            num_vertices: n,
126        })
127    }
128}
129
130#[cfg(feature = "example-db")]
131pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
132    use crate::topology::DirectedGraph;
133
134    vec![crate::example_db::specs::RuleExampleSpec {
135        id: "minimumfeedbackvertexset_to_ilp",
136        build: || {
137            // Simple cycle: 0 -> 1 -> 2 -> 0 (FVS = 1 vertex)
138            let graph = DirectedGraph::new(3, vec![(0, 1), (1, 2), (2, 0)]);
139            let source = MinimumFeedbackVertexSet::new(graph, vec![1i64; 3]);
140            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
141        },
142    }]
143}
144
145#[cfg(test)]
146#[path = "../unit_tests/rules/minimumfeedbackvertexset_ilp.rs"]
147mod tests;
problemreductions/rules/minimumfeedbackvertexset_ilp.rs

problemreductions/rules/
minimumfeedbackvertexset_ilp.rs
