problemreductions/rules/
minimumfeedbackarcset_ilp.rs

1//! Reduction from MinimumFeedbackArcSet to ILP (Integer Linear Programming).
2//!
3//! Uses MTZ-style topological ordering constraints on arcs:
4//! - Variables: |A| binary y_a (arc removal) + |V| integer o_v (topological order)
5//! - Constraints:
6//!   - For each arc a=(u→v): o_v - o_u + n*y_a >= 1
7//!   - Binary bounds: y_a <= 1 for all arcs
8//!   - Order bounds: o_v <= n-1 for all vertices
9//! - Objective: Minimize Σ w_a * y_a
10//! - Variable layout: first |A| are y_a, next |V| are o_v
11
12use crate::models::algebraic::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
13use crate::models::graph::MinimumFeedbackArcSet;
14use crate::reduction;
15use crate::rules::traits::{ReduceTo, ReductionResult};
16
17/// Result of reducing MinimumFeedbackArcSet to ILP.
18///
19/// The ILP uses integer variables (`ILP<i64, i64, Bounded>`) because it needs both
20/// binary arc-removal variables (y_a) and integer ordering variables (o_v).
21///
22/// Variable layout:
23/// - `y_a` at index `a` for `a in 0..m`: binary (0 or 1), arc removal indicator
24/// - `o_v` at index `m + v` for `v in 0..n`: integer in {0, ..., n-1}, topological order
25#[derive(Debug, Clone)]
26pub struct ReductionFASToILP {
27    target: ILP<i64, i64, Bounded>,
28    /// Number of arcs in the source graph (needed for solution extraction).
29    num_arcs: usize,
30}
31
32impl ReductionResult for ReductionFASToILP {
33    type Source = MinimumFeedbackArcSet<i64>;
34    type Target = ILP<i64, i64, Bounded>;
35
36    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
37        &self.target
38    }
39
40    /// Extract solution from ILP back to MinimumFeedbackArcSet.
41    ///
42    /// The first m variables of the ILP solution are the binary y_a values,
43    /// which directly correspond to the FAS configuration (1 = removed).
44    fn extract_solution(
45        &self,
46        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
47    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
48        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
49
50        Ok(target_solution[..self.num_arcs]
51            .iter()
52            .map(|&value| value == 1)
53            .collect())
54    }
55}
56
57#[reduction(transform = {
58    exact {
59        num_vars = "num_arcs + num_vertices",
60        num_constraints = "num_arcs + num_arcs + num_vertices",
61    },
62    upper_bound {
63        max_constraint_magnitude_bits = "num_vertices + 1",
64        num_nonzeros = "(num_arcs + num_vertices) * (num_arcs + num_arcs + num_vertices)",
65    },
66})]
67impl ReduceTo<ILP<i64, i64, Bounded>> for MinimumFeedbackArcSet<i64> {
68    type Result = ReductionFASToILP;
69
70    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
71        let n = self.num_vertices();
72        let m = self.num_arcs();
73        let arcs = self.graph().arcs();
74        let num_vars = m + n;
75
76        // Variable indices:
77        // y_a = a         (binary: arc a removed?)
78        // o_v = m + v     (integer: topological order of vertex v)
79
80        let mut constraints = Vec::new();
81        let n_i64 = Self::exact_i64(n, "encoding the topological order")?;
82
83        // Binary bounds: y_a <= 1 for a in 0..m
84        for a in 0..m {
85            constraints.push(LinearConstraint::le(vec![(a, 1)], 1));
86        }
87
88        // Order bounds: o_v <= n - 1 for v in 0..n
89        for v in 0..n {
90            constraints.push(LinearConstraint::le(vec![(m + v, 1)], n_i64 - 1));
91        }
92
93        // Arc constraints: for each arc a = (u -> v):
94        //   o_v - o_u >= 1 - n * y_a
95        // Rearranged: o_v - o_u + n * y_a >= 1
96        for (a, &(u, v)) in arcs.iter().enumerate() {
97            let terms = vec![
98                (m + v, 1),  // o_v
99                (m + u, -1), // -o_u
100                (a, n_i64),  // n * y_a
101            ];
102            constraints.push(LinearConstraint::ge(terms, 1));
103        }
104
105        // Objective: minimize sum w_a * y_a
106        let objective: Vec<(usize, i64)> = self
107            .weights()
108            .iter()
109            .enumerate()
110            .map(|(arc, &weight)| (arc, weight))
111            .collect();
112
113        let mut variables = vec![IntegerVariable::binary(); num_vars];
114        variables[m..].fill(
115            IntegerVariable::new(Some(0), Some((n_i64 - 1).max(0)))
116                .map_err(Self::target_construction)?,
117        );
118
119        let target =
120            ILP::with_variables(variables, constraints, objective, ObjectiveSense::Minimize)
121                .map_err(Self::target_construction)?;
122
123        Ok(ReductionFASToILP {
124            target,
125            num_arcs: m,
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: "minimumfeedbackarcset_to_ilp",
136        build: || {
137            // Simple cycle: 0 -> 1 -> 2 -> 0 (FAS = 1 arc)
138            // 3 arcs, 3 vertices: 6 total variables
139            // Remove arc 2 (2->0): source_config = [0, 0, 1]
140            // ILP solution: y_0=0, y_1=0, y_2=1, o_0=0, o_1=1, o_2=2
141            let graph = DirectedGraph::new(3, vec![(0, 1), (1, 2), (2, 0)]);
142            let source = MinimumFeedbackArcSet::new(graph, vec![1i64; 3]);
143            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
144        },
145    }]
146}
147
148#[cfg(test)]
149#[path = "../unit_tests/rules/minimumfeedbackarcset_ilp.rs"]
150mod tests;
problemreductions/rules/minimumfeedbackarcset_ilp.rs

problemreductions/rules/
minimumfeedbackarcset_ilp.rs
