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

problemreductions/rules/
minimumfeedbackarcset_ilp.rs
