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(
53    transform = upper_bound {
54        num_vars = "num_facilities * num_locations + num_facilities^2 * num_locations^2",
55        num_constraints = "num_facilities + num_locations + 3 * num_facilities^2 * num_locations^2",
56    },
57    unavailable = {
58        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
59    }
60)]
61impl ReduceTo<ILP<bool>> for QuadraticAssignment {
62    type Result = ReductionQAPToILP;
63
64    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
65        let n = self.num_facilities();
66        let loc = self.num_locations();
67        let cost = self.cost_matrix();
68        let dist = self.distance_matrix();
69
70        let num_x = n * loc;
71
72        let x_idx = |i: usize, p: usize| -> usize { i * loc + p };
73
74        // Enumerate z-variable pairs: (i, p, j, q) for i != j
75        let mut z_pairs = Vec::new();
76        for i in 0..n {
77            for j in 0..n {
78                if i == j {
79                    continue;
80                }
81                for p in 0..loc {
82                    for q in 0..loc {
83                        z_pairs.push((i, p, j, q));
84                    }
85                }
86            }
87        }
88
89        let num_z = z_pairs.len();
90        let num_vars = num_x + num_z;
91
92        let z_idx = |z_seq: usize| -> usize { num_x + z_seq };
93
94        let mut constraints = Vec::new();
95
96        // Assignment constraints
97        constraints.extend(one_hot_assignment_constraints(n, loc, 0));
98
99        // McCormick linearization for z variables
100        for (z_seq, &(i, p, j, q)) in z_pairs.iter().enumerate() {
101            constraints.extend(mccormick_product(z_idx(z_seq), x_idx(i, p), x_idx(j, q)));
102        }
103
104        // Objective: minimize sum_{i!=j,p,q} C[i][j] * D[p][q] * z_{(i,p),(j,q)}
105        let mut objective = Vec::new();
106        for (z_seq, &(i, p, j, q)) in z_pairs.iter().enumerate() {
107            let coefficient = cost[i][j].checked_mul(dist[p][q]).ok_or_else(|| {
108                crate::rules::ReductionError::integer_overflow::<QuadraticAssignment, ILP<bool>>(
109                    "multiplying a quadratic-assignment cost by a distance",
110                )
111            })?;
112            let coeff = coefficient;
113            if coeff != 0 {
114                objective.push((z_idx(z_seq), coeff));
115            }
116        }
117
118        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
119            .map_err(Self::target_construction)?;
120
121        Ok(ReductionQAPToILP {
122            target,
123            num_facilities: n,
124            num_locations: loc,
125        })
126    }
127}
128
129#[cfg(feature = "example-db")]
130pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
131    vec![crate::example_db::specs::RuleExampleSpec {
132        id: "quadraticassignment_to_ilp",
133        build: || {
134            // 2x2 QAP: 2 facilities, 2 locations
135            let source = QuadraticAssignment::new(
136                vec![vec![0, 1], vec![1, 0]],
137                vec![vec![0, 2], vec![2, 0]],
138            );
139            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
140        },
141    }]
142}
143
144#[cfg(test)]
145#[path = "../unit_tests/rules/quadraticassignment_ilp.rs"]
146mod tests;
problemreductions/rules/quadraticassignment_ilp.rs

problemreductions/rules/
quadraticassignment_ilp.rs
