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::{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<i32>`) 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<i32>,
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<i32>;
34    type Target = ILP<i32>;
35
36    fn target_problem(&self) -> &ILP<i32> {
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(&self, target_solution: &[usize]) -> Vec<usize> {
45        target_solution[..self.num_arcs].to_vec()
46    }
47}
48
49#[reduction(
50    overhead = {
51        num_vars = "num_arcs + num_vertices",
52        num_constraints = "num_arcs + num_arcs + num_vertices",
53    }
54)]
55impl ReduceTo<ILP<i32>> for MinimumFeedbackArcSet<i32> {
56    type Result = ReductionFASToILP;
57
58    fn reduce_to(&self) -> Self::Result {
59        let n = self.num_vertices();
60        let m = self.num_arcs();
61        let arcs = self.graph().arcs();
62        let num_vars = m + n;
63
64        // Variable indices:
65        // y_a = a         (binary: arc a removed?)
66        // o_v = m + v     (integer: topological order of vertex v)
67
68        let mut constraints = Vec::new();
69
70        // Binary bounds: y_a <= 1 for a in 0..m
71        for a in 0..m {
72            constraints.push(LinearConstraint::le(vec![(a, 1.0)], 1.0));
73        }
74
75        // Order bounds: o_v <= n - 1 for v in 0..n
76        for v in 0..n {
77            constraints.push(LinearConstraint::le(vec![(m + v, 1.0)], (n - 1) as f64));
78        }
79
80        // Arc constraints: for each arc a = (u -> v):
81        //   o_v - o_u >= 1 - n * y_a
82        // Rearranged: o_v - o_u + n * y_a >= 1
83        let n_f64 = n as f64;
84        for (a, &(u, v)) in arcs.iter().enumerate() {
85            let terms = vec![
86                (m + v, 1.0),  // o_v
87                (m + u, -1.0), // -o_u
88                (a, n_f64),    // n * y_a
89            ];
90            constraints.push(LinearConstraint::ge(terms, 1.0));
91        }
92
93        // Objective: minimize sum w_a * y_a
94        let objective: Vec<(usize, f64)> = self
95            .weights()
96            .iter()
97            .enumerate()
98            .map(|(a, &w)| (a, w as f64))
99            .collect();
100
101        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
102
103        ReductionFASToILP {
104            target,
105            num_arcs: m,
106        }
107    }
108}
109
110#[cfg(feature = "example-db")]
111pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
112    use crate::topology::DirectedGraph;
113
114    vec![crate::example_db::specs::RuleExampleSpec {
115        id: "minimumfeedbackarcset_to_ilp",
116        build: || {
117            // Simple cycle: 0 -> 1 -> 2 -> 0 (FAS = 1 arc)
118            // 3 arcs, 3 vertices: 6 total variables
119            // Remove arc 2 (2->0): source_config = [0, 0, 1]
120            // ILP solution: y_0=0, y_1=0, y_2=1, o_0=0, o_1=1, o_2=2
121            let graph = DirectedGraph::new(3, vec![(0, 1), (1, 2), (2, 0)]);
122            let source = MinimumFeedbackArcSet::new(graph, vec![1i32; 3]);
123            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
124        },
125    }]
126}
127
128#[cfg(test)]
129#[path = "../unit_tests/rules/minimumfeedbackarcset_ilp.rs"]
130mod tests;
problemreductions/rules/minimumfeedbackarcset_ilp.rs

problemreductions/rules/
minimumfeedbackarcset_ilp.rs
