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::{Bounded, IntegerVariable, 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<i64, i64, Bounded>`, 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<i64, i64, Bounded>,
25    num_vertices: usize,
26}
27
28impl ReductionResult for ReductionOLAToILP {
29    type Source = OptimalLinearArrangement<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 + num_edges",
55        num_constraints = "2 * num_vertices + num_vertices^2 + num_vertices + num_vertices + 3 * num_edges",
56    },
57    upper_bound {
58        max_constraint_magnitude_bits = "num_vertices + 1",
59        num_nonzeros = "(num_vertices^2 + num_vertices + num_edges) * (2 * num_vertices + num_vertices^2 + num_vertices + num_vertices + 3 * num_edges)",
60    },
61})]
62impl ReduceTo<ILP<i64, i64, Bounded>> for OptimalLinearArrangement<SimpleGraph> {
63    type Result = ReductionOLAToILP;
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        let m = edges.len();
70
71        let num_x = n * n;
72        let num_vars = num_x + n + m;
73
74        let x_idx = |v: usize, p: usize| -> usize { v * n + p };
75        let p_idx = |v: usize| -> usize { num_x + v };
76        let z_idx = |e: usize| -> usize { num_x + n + e };
77
78        let mut constraints = Vec::new();
79        let n_i64 =
80            <Self as ReduceTo<ILP<i64, i64, Bounded>>>::exact_i64(n, "encoding a vertex position")?;
81
82        // Assignment: each vertex in exactly one position
83        for v in 0..n {
84            let terms: Vec<(usize, i64)> = (0..n).map(|p| (x_idx(v, p), 1)).collect();
85            constraints.push(LinearConstraint::eq(terms, 1));
86        }
87
88        // Assignment: each position has exactly one vertex
89        for p in 0..n {
90            let terms: Vec<(usize, i64)> = (0..n).map(|v| (x_idx(v, p), 1)).collect();
91            constraints.push(LinearConstraint::eq(terms, 1));
92        }
93
94        // Binary bounds for x variables (`ILP<i64, i64, Bounded>`)
95        for v in 0..n {
96            for p in 0..n {
97                constraints.push(LinearConstraint::le(vec![(x_idx(v, p), 1)], 1));
98            }
99        }
100
101        // Position variable linking: p_v = sum_p p * x_{v,p}
102        // Reformulated as: p_v - sum_p p * x_{v,p} = 0
103        for v in 0..n {
104            let mut terms: Vec<(usize, i64)> = vec![(p_idx(v), 1)];
105            for p in 0..n {
106                terms.push((
107                    x_idx(v, p),
108                    -<Self as ReduceTo<ILP<i64, i64, Bounded>>>::exact_i64(
109                        p,
110                        "encoding a vertex position",
111                    )?,
112                ));
113            }
114            constraints.push(LinearConstraint::eq(terms, 0));
115        }
116
117        // Position bounds: 0 <= p_v <= n-1
118        for v in 0..n {
119            constraints.push(LinearConstraint::le(vec![(p_idx(v), 1)], n_i64 - 1));
120        }
121
122        // Absolute value: z_e >= |p_u - p_v| for each edge e = {u, v}
123        for (e, &(u, v)) in edges.iter().enumerate() {
124            // z_e >= p_u - p_v
125            constraints.push(LinearConstraint::ge(
126                vec![(z_idx(e), 1), (p_idx(u), -1), (p_idx(v), 1)],
127                0,
128            ));
129            // z_e >= p_v - p_u
130            constraints.push(LinearConstraint::ge(
131                vec![(z_idx(e), 1), (p_idx(v), -1), (p_idx(u), 1)],
132                0,
133            ));
134            // z_e <= n-1 (max possible position difference)
135            constraints.push(LinearConstraint::le(vec![(z_idx(e), 1)], n_i64 - 1));
136        }
137
138        // Objective: minimize sum z_e
139        let objective: Vec<(usize, i64)> = (0..m).map(|e| (z_idx(e), 1)).collect();
140        let mut variables = vec![IntegerVariable::binary(); num_vars];
141        variables[num_x..].fill(
142            IntegerVariable::new(Some(0), Some((n_i64 - 1).max(0)))
143                .map_err(<Self as ReduceTo<ILP<i64, i64, Bounded>>>::target_construction)?,
144        );
145
146        let target =
147            ILP::with_variables(variables, constraints, objective, ObjectiveSense::Minimize)
148                .map_err(<Self as ReduceTo<ILP<i64, i64, Bounded>>>::target_construction)?;
149
150        Ok(ReductionOLAToILP {
151            target,
152            num_vertices: n,
153        })
154    }
155}
156
157#[cfg(feature = "example-db")]
158pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
159    vec![crate::example_db::specs::RuleExampleSpec {
160        id: "optimallineararrangement_to_ilp",
161        build: || {
162            // Path P4: 0-1-2-3 (identity permutation achieves cost 3)
163            let source =
164                OptimalLinearArrangement::new(SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]));
165            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
166        },
167    }]
168}
169
170#[cfg(test)]
171#[path = "../unit_tests/rules/optimallineararrangement_ilp.rs"]
172mod tests;
problemreductions/rules/optimallineararrangement_ilp.rs

problemreductions/rules/
optimallineararrangement_ilp.rs
