problemreductions/rules/
minimumgraphbandwidth_ilp.rs

1//! Reduction from MinimumGraphBandwidth to ILP (Integer Linear Programming).
2//!
3//! Position-assignment formulation with bandwidth variable:
4//! - Binary x_{v,p}: vertex v gets position p
5//! - Integer position variables pos_v = sum_p p * x_{v,p}
6//! - Integer bandwidth variable B
7//! - For each edge (u,v): pos_u - pos_v <= B, pos_v - pos_u <= B
8//! - Objective: minimize B
9
10use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
11use crate::models::graph::MinimumGraphBandwidth;
12use crate::reduction;
13use crate::rules::traits::{ReduceTo, ReductionResult};
14use crate::topology::{Graph, SimpleGraph};
15
16/// Result of reducing MinimumGraphBandwidth to ILP.
17///
18/// Variable layout (ILP<i32>, non-negative integers):
19/// - `x_{v,p}` at index `v * n + p`, bounded to {0,1}
20/// - `pos_v` at index `n^2 + v`, integer position in {0, ..., n-1}
21/// - `B` (bandwidth) at index `n^2 + n`
22#[derive(Debug, Clone)]
23pub struct ReductionMGBToILP {
24    target: ILP<i32>,
25    num_vertices: usize,
26}
27
28impl ReductionResult for ReductionMGBToILP {
29    type Source = MinimumGraphBandwidth<SimpleGraph>;
30    type Target = ILP<i32>;
31
32    fn target_problem(&self) -> &ILP<i32> {
33        &self.target
34    }
35
36    /// Extract: for each vertex v, output its position p (the unique p with x_{v,p} = 1).
37    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
38        let n = self.num_vertices;
39        (0..n)
40            .map(|v| {
41                (0..n)
42                    .find(|&p| target_solution[v * n + p] == 1)
43                    .unwrap_or(0)
44            })
45            .collect()
46    }
47}
48
49#[reduction(
50    overhead = {
51        num_vars = "num_vertices^2 + num_vertices + 1",
52        num_constraints = "2 * num_vertices + num_vertices^2 + num_vertices + num_vertices + 1 + 2 * num_edges",
53    }
54)]
55impl ReduceTo<ILP<i32>> for MinimumGraphBandwidth<SimpleGraph> {
56    type Result = ReductionMGBToILP;
57
58    fn reduce_to(&self) -> Self::Result {
59        let n = self.num_vertices();
60        let graph = self.graph();
61        let edges = graph.edges();
62
63        let num_x = n * n;
64        let num_vars = num_x + n + 1;
65
66        let x_idx = |v: usize, p: usize| -> usize { v * n + p };
67        let pos_idx = |v: usize| -> usize { num_x + v };
68        let b_idx = num_x + n;
69
70        let mut constraints = Vec::new();
71
72        // Assignment: each vertex in exactly one position
73        for v in 0..n {
74            let terms: Vec<(usize, f64)> = (0..n).map(|p| (x_idx(v, p), 1.0)).collect();
75            constraints.push(LinearConstraint::eq(terms, 1.0));
76        }
77
78        // Assignment: each position has exactly one vertex
79        for p in 0..n {
80            let terms: Vec<(usize, f64)> = (0..n).map(|v| (x_idx(v, p), 1.0)).collect();
81            constraints.push(LinearConstraint::eq(terms, 1.0));
82        }
83
84        // Binary bounds for x variables (ILP<i32>)
85        for v in 0..n {
86            for p in 0..n {
87                constraints.push(LinearConstraint::le(vec![(x_idx(v, p), 1.0)], 1.0));
88            }
89        }
90
91        // Position variable linking: pos_v = sum_p p * x_{v,p}
92        for v in 0..n {
93            let mut terms: Vec<(usize, f64)> = vec![(pos_idx(v), 1.0)];
94            for p in 0..n {
95                terms.push((x_idx(v, p), -(p as f64)));
96            }
97            constraints.push(LinearConstraint::eq(terms, 0.0));
98        }
99
100        // Position bounds: 0 <= pos_v <= n-1
101        for v in 0..n {
102            constraints.push(LinearConstraint::le(
103                vec![(pos_idx(v), 1.0)],
104                (n - 1) as f64,
105            ));
106        }
107
108        // Bandwidth upper bound: B <= n-1 (max possible position difference)
109        constraints.push(LinearConstraint::le(vec![(b_idx, 1.0)], (n - 1) as f64));
110
111        // Bandwidth constraints: for each edge (u,v):
112        //   pos_u - pos_v <= B  =>  pos_u - pos_v - B <= 0
113        //   pos_v - pos_u <= B  =>  pos_v - pos_u - B <= 0
114        for &(u, v) in edges.iter() {
115            constraints.push(LinearConstraint::le(
116                vec![(pos_idx(u), 1.0), (pos_idx(v), -1.0), (b_idx, -1.0)],
117                0.0,
118            ));
119            constraints.push(LinearConstraint::le(
120                vec![(pos_idx(v), 1.0), (pos_idx(u), -1.0), (b_idx, -1.0)],
121                0.0,
122            ));
123        }
124
125        // Objective: minimize B
126        let objective = vec![(b_idx, 1.0)];
127        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
128
129        ReductionMGBToILP {
130            target,
131            num_vertices: n,
132        }
133    }
134}
135
136#[cfg(feature = "example-db")]
137pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
138    vec![crate::example_db::specs::RuleExampleSpec {
139        id: "minimumgraphbandwidth_to_ilp",
140        build: || {
141            // Star S4: center 0 connected to 1, 2, 3
142            let source =
143                MinimumGraphBandwidth::new(SimpleGraph::new(4, vec![(0, 1), (0, 2), (0, 3)]));
144            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
145        },
146    }]
147}
148
149#[cfg(test)]
150#[path = "../unit_tests/rules/minimumgraphbandwidth_ilp.rs"]
151mod tests;
problemreductions/rules/minimumgraphbandwidth_ilp.rs

problemreductions/rules/
minimumgraphbandwidth_ilp.rs
