problemreductions/rules/
quadraticassignment_ilp.rs

1//! Reduction from QuadraticAssignment to ILP (Integer Linear Programming).
2//!
3//! Linearized assignment formulation:
4//! - Binary x_{i,p}: facility i at location p
5//! - Binary z_{(i,p),(j,q)}: product x_{i,p} * x_{j,q} for i != j
6//! - Assignment: each facility to exactly one location, each location at most one facility
7//! - McCormick linearization for z variables
8//! - Objective: minimize sum_{i!=j} C[i][j] * D[p][q] * z_{(i,p),(j,q)}
9
10use crate::models::algebraic::QuadraticAssignment;
11use crate::models::algebraic::{ObjectiveSense, ILP};
12use crate::reduction;
13use crate::rules::ilp_helpers::{mccormick_product, one_hot_assignment_constraints};
14use crate::rules::traits::{ReduceTo, ReductionResult};
15
16/// Result of reducing QuadraticAssignment to ILP.
17///
18/// Variable layout (all binary):
19/// - `x_{i,p}` at index `i * m + p` for facility i, location p
20/// - `z` variables for McCormick products, indexed sequentially after x
21#[derive(Debug, Clone)]
22pub struct ReductionQAPToILP {
23    target: ILP<bool>,
24    num_facilities: usize,
25    num_locations: usize,
26}
27
28impl ReductionResult for ReductionQAPToILP {
29    type Source = QuadraticAssignment;
30    type Target = ILP<bool>;
31
32    fn target_problem(&self) -> &ILP<bool> {
33        &self.target
34    }
35
36    /// Extract: for each facility i, output the unique location p with x_{i,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_facilities,
46            self.num_locations,
47            0,
48        )
49    }
50}
51
52#[reduction(transform = {
53    exact {
54        num_vars = "num_facilities * num_locations + num_facilities * (num_facilities - 1) * num_locations^2",
55        num_constraints = "num_facilities + num_locations + 3 * num_facilities * (num_facilities - 1) * num_locations^2",
56        num_nonzeros = "2 * num_facilities * num_locations + 7 * num_facilities * (num_facilities - 1) * num_locations^2",
57    },
58    upper_bound {
59        max_constraint_magnitude_bits = "2",
60    },
61})]
62impl ReduceTo<ILP<bool>> for QuadraticAssignment {
63    type Result = ReductionQAPToILP;
64
65    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
66        let n = self.num_facilities();
67        let loc = self.num_locations();
68        let cost = self.cost_matrix();
69        let dist = self.distance_matrix();
70
71        let num_x = n * loc;
72
73        let x_idx = |i: usize, p: usize| -> usize { i * loc + p };
74
75        // Enumerate z-variable pairs: (i, p, j, q) for i != j
76        let mut z_pairs = Vec::new();
77        for i in 0..n {
78            for j in 0..n {
79                if i == j {
80                    continue;
81                }
82                for p in 0..loc {
83                    for q in 0..loc {
84                        z_pairs.push((i, p, j, q));
85                    }
86                }
87            }
88        }
89
90        let num_z = z_pairs.len();
91        let num_vars = num_x + num_z;
92
93        let z_idx = |z_seq: usize| -> usize { num_x + z_seq };
94
95        let mut constraints = Vec::new();
96
97        // Assignment constraints
98        constraints.extend(one_hot_assignment_constraints(n, loc, 0));
99
100        // McCormick linearization for z variables
101        for (z_seq, &(i, p, j, q)) in z_pairs.iter().enumerate() {
102            constraints.extend(mccormick_product(z_idx(z_seq), x_idx(i, p), x_idx(j, q)));
103        }
104
105        // Objective: minimize sum_{i!=j,p,q} C[i][j] * D[p][q] * z_{(i,p),(j,q)}
106        let mut objective = Vec::new();
107        for (z_seq, &(i, p, j, q)) in z_pairs.iter().enumerate() {
108            let coefficient = cost[i][j].checked_mul(dist[p][q]).ok_or_else(|| {
109                crate::rules::ReductionError::integer_overflow::<QuadraticAssignment, ILP<bool>>(
110                    "multiplying a quadratic-assignment cost by a distance",
111                )
112            })?;
113            let coeff = coefficient;
114            if coeff != 0 {
115                objective.push((z_idx(z_seq), coeff));
116            }
117        }
118
119        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
120            .map_err(Self::target_construction)?;
121
122        Ok(ReductionQAPToILP {
123            target,
124            num_facilities: n,
125            num_locations: loc,
126        })
127    }
128}
129
130#[cfg(feature = "example-db")]
131pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
132    vec![crate::example_db::specs::RuleExampleSpec {
133        id: "quadraticassignment_to_ilp",
134        build: || {
135            // 2x2 QAP: 2 facilities, 2 locations
136            let source = QuadraticAssignment::new(
137                vec![vec![0, 1], vec![1, 0]],
138                vec![vec![0, 2], vec![2, 0]],
139            );
140            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
141        },
142    }]
143}
144
145#[cfg(test)]
146#[path = "../unit_tests/rules/quadraticassignment_ilp.rs"]
147mod tests;
problemreductions/rules/quadraticassignment_ilp.rs

problemreductions/rules/
quadraticassignment_ilp.rs
