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::{Bounded, IntegerVariable, 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<i64, i64, Bounded>`, 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<i64, i64, Bounded>,
25    num_vertices: usize,
26}
27
28impl ReductionResult for ReductionMGBToILP {
29    type Source = MinimumGraphBandwidth<SimpleGraph>;
30    type Target = ILP<i64, i64, Bounded>;
31
32    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
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(
38        &self,
39        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
40    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
41        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
42
43        crate::rules::ilp_helpers::one_hot_decode_rows(
44            target_solution,
45            self.num_vertices,
46            self.num_vertices,
47            0,
48        )
49    }
50}
51
52#[reduction(transform = {
53    exact {
54        num_vars = "num_vertices^2 + num_vertices + 1",
55        num_constraints = "2 * num_vertices + num_vertices^2 + num_vertices + num_vertices + 1 + 2 * num_edges",
56    },
57    upper_bound {
58        max_constraint_magnitude_bits = "num_vertices + 1",
59        num_nonzeros = "(num_vertices^2 + num_vertices + 1) * (2 * num_vertices + num_vertices^2 + num_vertices + num_vertices + 1 + 2 * num_edges)",
60    },
61})]
62impl ReduceTo<ILP<i64, i64, Bounded>> for MinimumGraphBandwidth<SimpleGraph> {
63    type Result = ReductionMGBToILP;
64
65    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
66        let n = self.num_vertices();
67        let graph = self.graph();
68        let edges = graph.edges();
69
70        let num_x = n * n;
71        let num_vars = num_x + n + 1;
72
73        let x_idx = |v: usize, p: usize| -> usize { v * n + p };
74        let pos_idx = |v: usize| -> usize { num_x + v };
75        let b_idx = num_x + n;
76
77        let mut constraints = Vec::new();
78        let n_i64 = Self::exact_i64(n, "encoding a vertex position")?;
79
80        // Assignment: each vertex in exactly one position
81        for v in 0..n {
82            let terms: Vec<(usize, i64)> = (0..n).map(|p| (x_idx(v, p), 1)).collect();
83            constraints.push(LinearConstraint::eq(terms, 1));
84        }
85
86        // Assignment: each position has exactly one vertex
87        for p in 0..n {
88            let terms: Vec<(usize, i64)> = (0..n).map(|v| (x_idx(v, p), 1)).collect();
89            constraints.push(LinearConstraint::eq(terms, 1));
90        }
91
92        // Binary bounds for x variables (`ILP<i64, i64, Bounded>`)
93        for v in 0..n {
94            for p in 0..n {
95                constraints.push(LinearConstraint::le(vec![(x_idx(v, p), 1)], 1));
96            }
97        }
98
99        // Position variable linking: pos_v = sum_p p * x_{v,p}
100        for v in 0..n {
101            let mut terms: Vec<(usize, i64)> = vec![(pos_idx(v), 1)];
102            for p in 0..n {
103                terms.push((
104                    x_idx(v, p),
105                    -Self::exact_i64(p, "encoding a vertex position")?,
106                ));
107            }
108            constraints.push(LinearConstraint::eq(terms, 0));
109        }
110
111        // Position bounds: 0 <= pos_v <= n-1
112        for v in 0..n {
113            constraints.push(LinearConstraint::le(vec![(pos_idx(v), 1)], n_i64 - 1));
114        }
115
116        // Bandwidth upper bound: B <= n-1 (max possible position difference)
117        constraints.push(LinearConstraint::le(vec![(b_idx, 1)], n_i64 - 1));
118
119        // Bandwidth constraints: for each edge (u,v):
120        //   pos_u - pos_v <= B  =>  pos_u - pos_v - B <= 0
121        //   pos_v - pos_u <= B  =>  pos_v - pos_u - B <= 0
122        for &(u, v) in edges.iter() {
123            constraints.push(LinearConstraint::le(
124                vec![(pos_idx(u), 1), (pos_idx(v), -1), (b_idx, -1)],
125                0,
126            ));
127            constraints.push(LinearConstraint::le(
128                vec![(pos_idx(v), 1), (pos_idx(u), -1), (b_idx, -1)],
129                0,
130            ));
131        }
132
133        // Objective: minimize B
134        let objective = vec![(b_idx, 1)];
135        let mut variables = vec![IntegerVariable::binary(); num_vars];
136        variables[num_x..].fill(
137            IntegerVariable::new(Some(0), Some((n_i64 - 1).max(0)))
138                .map_err(Self::target_construction)?,
139        );
140
141        let target =
142            ILP::with_variables(variables, constraints, objective, ObjectiveSense::Minimize)
143                .map_err(Self::target_construction)?;
144
145        Ok(ReductionMGBToILP {
146            target,
147            num_vertices: n,
148        })
149    }
150}
151
152#[cfg(feature = "example-db")]
153pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
154    vec![crate::example_db::specs::RuleExampleSpec {
155        id: "minimumgraphbandwidth_to_ilp",
156        build: || {
157            // Star S4: center 0 connected to 1, 2, 3
158            let source =
159                MinimumGraphBandwidth::new(SimpleGraph::new(4, vec![(0, 1), (0, 2), (0, 3)]));
160            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
161        },
162    }]
163}
164
165#[cfg(test)]
166#[path = "../unit_tests/rules/minimumgraphbandwidth_ilp.rs"]
167mod tests;
problemreductions/rules/minimumgraphbandwidth_ilp.rs

problemreductions/rules/
minimumgraphbandwidth_ilp.rs
