problemreductions/rules/
optimallineararrangement_ilp.rs

1//! Reduction from OptimalLinearArrangement to ILP (Integer Linear Programming).
2//!
3//! Position-assignment with absolute-value auxiliaries:
4//! - Binary x_{v,p}: vertex v gets position p
5//! - Integer position variables p_v = sum_p p * x_{v,p}
6//! - Non-negative z_{u,v} per edge for |p_u - p_v|
7//! - abs_diff_le constraints: z_{u,v} >= p_u - p_v, z_{u,v} >= p_v - p_u
8//! - Minimize: sum z_{u,v}
9
10use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
11use crate::models::graph::OptimalLinearArrangement;
12use crate::reduction;
13use crate::rules::traits::{ReduceTo, ReductionResult};
14use crate::topology::{Graph, SimpleGraph};
15
16/// Result of reducing OptimalLinearArrangement 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/// - `p_v` at index `n^2 + v`, integer position in {0, ..., n-1}
21/// - `z_e` at index `n^2 + n + e`, non-negative integer for edge length
22#[derive(Debug, Clone)]
23pub struct ReductionOLAToILP {
24    target: ILP<i32>,
25    num_vertices: usize,
26}
27
28impl ReductionResult for ReductionOLAToILP {
29    type Source = OptimalLinearArrangement<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 + num_edges",
52        num_constraints = "2 * num_vertices + num_vertices^2 + num_vertices + num_vertices + 3 * num_edges",
53    }
54)]
55impl ReduceTo<ILP<i32>> for OptimalLinearArrangement<SimpleGraph> {
56    type Result = ReductionOLAToILP;
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        let m = edges.len();
63
64        let num_x = n * n;
65        let num_vars = num_x + n + m;
66
67        let x_idx = |v: usize, p: usize| -> usize { v * n + p };
68        let p_idx = |v: usize| -> usize { num_x + v };
69        let z_idx = |e: usize| -> usize { num_x + n + e };
70
71        let mut constraints = Vec::new();
72
73        // Assignment: each vertex in exactly one position
74        for v in 0..n {
75            let terms: Vec<(usize, f64)> = (0..n).map(|p| (x_idx(v, p), 1.0)).collect();
76            constraints.push(LinearConstraint::eq(terms, 1.0));
77        }
78
79        // Assignment: each position has exactly one vertex
80        for p in 0..n {
81            let terms: Vec<(usize, f64)> = (0..n).map(|v| (x_idx(v, p), 1.0)).collect();
82            constraints.push(LinearConstraint::eq(terms, 1.0));
83        }
84
85        // Binary bounds for x variables (ILP<i32>)
86        for v in 0..n {
87            for p in 0..n {
88                constraints.push(LinearConstraint::le(vec![(x_idx(v, p), 1.0)], 1.0));
89            }
90        }
91
92        // Position variable linking: p_v = sum_p p * x_{v,p}
93        // Reformulated as: p_v - sum_p p * x_{v,p} = 0
94        for v in 0..n {
95            let mut terms: Vec<(usize, f64)> = vec![(p_idx(v), 1.0)];
96            for p in 0..n {
97                terms.push((x_idx(v, p), -(p as f64)));
98            }
99            constraints.push(LinearConstraint::eq(terms, 0.0));
100        }
101
102        // Position bounds: 0 <= p_v <= n-1
103        for v in 0..n {
104            constraints.push(LinearConstraint::le(vec![(p_idx(v), 1.0)], (n - 1) as f64));
105        }
106
107        // Absolute value: z_e >= |p_u - p_v| for each edge e = {u, v}
108        for (e, &(u, v)) in edges.iter().enumerate() {
109            // z_e >= p_u - p_v
110            constraints.push(LinearConstraint::ge(
111                vec![(z_idx(e), 1.0), (p_idx(u), -1.0), (p_idx(v), 1.0)],
112                0.0,
113            ));
114            // z_e >= p_v - p_u
115            constraints.push(LinearConstraint::ge(
116                vec![(z_idx(e), 1.0), (p_idx(v), -1.0), (p_idx(u), 1.0)],
117                0.0,
118            ));
119            // z_e <= n-1 (max possible position difference)
120            constraints.push(LinearConstraint::le(vec![(z_idx(e), 1.0)], (n - 1) as f64));
121        }
122
123        // Objective: minimize sum z_e
124        let objective: Vec<(usize, f64)> = (0..m).map(|e| (z_idx(e), 1.0)).collect();
125        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
126
127        ReductionOLAToILP {
128            target,
129            num_vertices: n,
130        }
131    }
132}
133
134#[cfg(feature = "example-db")]
135pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
136    vec![crate::example_db::specs::RuleExampleSpec {
137        id: "optimallineararrangement_to_ilp",
138        build: || {
139            // Path P4: 0-1-2-3 (identity permutation achieves cost 3)
140            let source =
141                OptimalLinearArrangement::new(SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]));
142            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
143        },
144    }]
145}
146
147#[cfg(test)]
148#[path = "../unit_tests/rules/optimallineararrangement_ilp.rs"]
149mod tests;
problemreductions/rules/optimallineararrangement_ilp.rs

problemreductions/rules/
optimallineararrangement_ilp.rs
