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

problemreductions/rules/
minimumfeedbackvertexset_ilp.rs
