problemreductions/models/algebraic/
quadratic_assignment.rs

1//! Quadratic Assignment Problem (QAP) implementation.
2//!
3//! The QAP assigns facilities to locations to minimize the total cost,
4//! where cost depends on both inter-facility flows and inter-location distances.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry};
7use crate::traits::Problem;
8use crate::types::Min;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "QuadraticAssignment",
14        display_name: "Quadratic Assignment",
15        aliases: &["QAP"],
16        dimensions: &[],
17        category: crate::registry::ProblemCategory::Algebraic,
18        module_path: module_path!(),
19        description: "Minimize total cost of assigning facilities to locations",
20        fields: &[
21            FieldInfo { name: "cost_matrix", type_name: "Vec<Vec<i64>>", description: "Flow/cost matrix between facilities" },
22            FieldInfo { name: "distance_matrix", type_name: "Vec<Vec<i64>>", description: "Distance matrix between locations" },
23        ],
24    }
25}
26
27/// The Quadratic Assignment Problem (QAP).
28///
29/// Given n facilities and m locations, a cost matrix C (n x n) representing
30/// flows between facilities, and a distance matrix D (m x m) representing
31/// distances between locations, find an injective assignment of facilities
32/// to locations that minimizes:
33///
34/// `f(p) = sum_{i != j} C[i][j] * D[p(i)][p(j)]`
35///
36/// where p is an injective mapping from facilities to locations (a permutation when n == m).
37///
38/// # Example
39///
40/// ```
41/// use problemreductions::models::algebraic::QuadraticAssignment;
42/// use problemreductions::{Problem, BruteForce};
43///
44/// let cost_matrix = vec![
45///     vec![0, 1, 2],
46///     vec![1, 0, 3],
47///     vec![2, 3, 0],
48/// ];
49/// let distance_matrix = vec![
50///     vec![0, 5, 8],
51///     vec![5, 0, 3],
52///     vec![8, 3, 0],
53/// ];
54/// let problem = QuadraticAssignment::new(cost_matrix, distance_matrix);
55///
56/// let solver = BruteForce::new();
57/// let best = solver.solve(&problem).unwrap();
58/// assert!(best.is_some());
59/// ```
60#[derive(Debug, Clone, Serialize, Deserialize)]
61pub struct QuadraticAssignment {
62    /// Cost/flow matrix between facilities (n x n).
63    cost_matrix: Vec<Vec<i64>>,
64    /// Distance matrix between locations (m x m).
65    distance_matrix: Vec<Vec<i64>>,
66}
67
68impl QuadraticAssignment {
69    /// Create a new Quadratic Assignment Problem.
70    ///
71    /// # Arguments
72    /// * `cost_matrix` - n x n matrix of flows/costs between facilities
73    /// * `distance_matrix` - m x m matrix of distances between locations
74    ///
75    /// # Panics
76    /// Panics if either matrix is not square, or if num_facilities > num_locations.
77    pub fn new(cost_matrix: Vec<Vec<i64>>, distance_matrix: Vec<Vec<i64>>) -> Self {
78        let n = cost_matrix.len();
79        for row in &cost_matrix {
80            assert_eq!(row.len(), n, "cost_matrix must be square");
81        }
82        let m = distance_matrix.len();
83        for row in &distance_matrix {
84            assert_eq!(row.len(), m, "distance_matrix must be square");
85        }
86        assert!(
87            n <= m,
88            "num_facilities ({n}) must be <= num_locations ({m})"
89        );
90        Self {
91            cost_matrix,
92            distance_matrix,
93        }
94    }
95
96    /// Get the cost/flow matrix.
97    pub fn cost_matrix(&self) -> &[Vec<i64>] {
98        &self.cost_matrix
99    }
100
101    /// Get the distance matrix.
102    pub fn distance_matrix(&self) -> &[Vec<i64>] {
103        &self.distance_matrix
104    }
105
106    /// Get the number of facilities.
107    pub fn num_facilities(&self) -> usize {
108        self.cost_matrix.len()
109    }
110
111    /// Get the number of locations.
112    pub fn num_locations(&self) -> usize {
113        self.distance_matrix.len()
114    }
115}
116
117impl Problem for QuadraticAssignment {
118    const NAME: &'static str = "QuadraticAssignment";
119    type Solution = Vec<usize>;
120    type Value = Min<i64>;
121
122    crate::problem_parameters![
123        ("num_facilities", num_facilities),
124        ("num_locations", num_locations),
125    ];
126
127    fn evaluate(
128        &self,
129        config: &Self::Solution,
130    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
131        Ok({
132            let n = self.num_facilities();
133            let m = self.num_locations();
134
135            // Check config length matches number of facilities
136            if config.len() != n {
137                return Err(crate::traits::EvaluationError::InvalidConfiguration(
138                    "assignment length does not match the number of facilities".into(),
139                ));
140            }
141
142            if config.iter().any(|&location| location >= m) {
143                return Err(crate::traits::EvaluationError::InvalidConfiguration(
144                    "assignment contains an out-of-range location".into(),
145                ));
146            }
147
148            // Check injectivity: no two facilities assigned to the same location
149            let mut used = vec![false; m];
150            for &loc in config {
151                if used[loc] {
152                    return Ok(Min(None));
153                }
154                used[loc] = true;
155            }
156
157            // Compute objective: sum_{i != j} cost_matrix[i][j] * distance_matrix[config[i]][config[j]]
158            let mut total: i64 = 0;
159            for i in 0..n {
160                for j in 0..n {
161                    if i != j {
162                        let term = self.cost_matrix[i][j]
163                            .checked_mul(self.distance_matrix[config[i]][config[j]])
164                            .ok_or_else(|| {
165                                crate::traits::EvaluationError::IntegerOverflow(
166                                    "multiplying quadratic assignment cost and distance"
167                                        .to_string(),
168                                )
169                            })?;
170                        total = total.checked_add(term).ok_or_else(|| {
171                            crate::traits::EvaluationError::IntegerOverflow(
172                                "summing quadratic assignment objective".to_string(),
173                            )
174                        })?;
175                    }
176                }
177            }
178
179            Min(Some(total))
180        })
181    }
182
183    fn variant() -> Vec<(&'static str, &'static str)> {
184        crate::variant_params![]
185    }
186}
187
188impl crate::solvers::BruteForceProblem for QuadraticAssignment {
189    fn dimensions(&self) -> Vec<usize> {
190        vec![self.num_locations(); self.num_facilities()]
191    }
192}
193
194crate::declare_variants! {
195    default QuadraticAssignment => "factorial(num_facilities)",
196}
197
198crate::register_brute_force! {
199    QuadraticAssignment,
200}
201
202#[cfg(feature = "example-db")]
203pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
204    vec![crate::example_db::specs::ModelExampleSpec {
205        id: "quadratic_assignment",
206        instance: Box::new(QuadraticAssignment::new(
207            vec![
208                vec![0, 5, 2, 0],
209                vec![5, 0, 0, 3],
210                vec![2, 0, 0, 4],
211                vec![0, 3, 4, 0],
212            ],
213            vec![
214                vec![0, 4, 1, 1],
215                vec![4, 0, 3, 4],
216                vec![1, 3, 0, 4],
217                vec![1, 4, 4, 0],
218            ],
219        )),
220        optimal_config: serde_json::json!(vec![3, 0, 1, 2]),
221        optimal_value: serde_json::json!(56),
222    }]
223}
224
225#[cfg(test)]
226#[path = "../../unit_tests/models/algebraic/quadratic_assignment.rs"]
227mod tests;
problemreductions/models/algebraic/quadratic_assignment.rs

problemreductions/models/algebraic/
quadratic_assignment.rs
