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(&self, target_solution: &[usize]) -> Vec<usize> {
38        let loc = self.num_locations;
39        (0..self.num_facilities)
40            .map(|i| {
41                (0..loc)
42                    .find(|&p| target_solution[i * loc + p] == 1)
43                    .unwrap_or(0)
44            })
45            .collect()
46    }
47}
48
49#[reduction(
50    overhead = {
51        num_vars = "num_facilities * num_locations + num_facilities^2 * num_locations^2",
52        num_constraints = "num_facilities + num_locations + 3 * num_facilities^2 * num_locations^2",
53    }
54)]
55impl ReduceTo<ILP<bool>> for QuadraticAssignment {
56    type Result = ReductionQAPToILP;
57
58    fn reduce_to(&self) -> Self::Result {
59        let n = self.num_facilities();
60        let loc = self.num_locations();
61        let cost = self.cost_matrix();
62        let dist = self.distance_matrix();
63
64        let num_x = n * loc;
65
66        let x_idx = |i: usize, p: usize| -> usize { i * loc + p };
67
68        // Enumerate z-variable pairs: (i, p, j, q) for i != j
69        let mut z_pairs = Vec::new();
70        for i in 0..n {
71            for j in 0..n {
72                if i == j {
73                    continue;
74                }
75                for p in 0..loc {
76                    for q in 0..loc {
77                        z_pairs.push((i, p, j, q));
78                    }
79                }
80            }
81        }
82
83        let num_z = z_pairs.len();
84        let num_vars = num_x + num_z;
85
86        let z_idx = |z_seq: usize| -> usize { num_x + z_seq };
87
88        let mut constraints = Vec::new();
89
90        // Assignment constraints
91        constraints.extend(one_hot_assignment_constraints(n, loc, 0));
92
93        // McCormick linearization for z variables
94        for (z_seq, &(i, p, j, q)) in z_pairs.iter().enumerate() {
95            constraints.extend(mccormick_product(z_idx(z_seq), x_idx(i, p), x_idx(j, q)));
96        }
97
98        // Objective: minimize sum_{i!=j,p,q} C[i][j] * D[p][q] * z_{(i,p),(j,q)}
99        let mut objective = Vec::new();
100        for (z_seq, &(i, p, j, q)) in z_pairs.iter().enumerate() {
101            let coeff = cost[i][j] as f64 * dist[p][q] as f64;
102            if coeff != 0.0 {
103                objective.push((z_idx(z_seq), coeff));
104            }
105        }
106
107        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
108
109        ReductionQAPToILP {
110            target,
111            num_facilities: n,
112            num_locations: loc,
113        }
114    }
115}
116
117#[cfg(feature = "example-db")]
118pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
119    vec![crate::example_db::specs::RuleExampleSpec {
120        id: "quadraticassignment_to_ilp",
121        build: || {
122            // 2x2 QAP: 2 facilities, 2 locations
123            let source = QuadraticAssignment::new(
124                vec![vec![0, 1], vec![1, 0]],
125                vec![vec![0, 2], vec![2, 0]],
126            );
127            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
128        },
129    }]
130}
131
132#[cfg(test)]
133#[path = "../unit_tests/rules/quadraticassignment_ilp.rs"]
134mod tests;
problemreductions/rules/quadraticassignment_ilp.rs

problemreductions/rules/
quadraticassignment_ilp.rs
