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)]
61#[serde(try_from = "QuadraticAssignmentData")]
62pub struct QuadraticAssignment {
63    /// Cost/flow matrix between facilities (n x n).
64    cost_matrix: Vec<Vec<i64>>,
65    /// Distance matrix between locations (m x m).
66    distance_matrix: Vec<Vec<i64>>,
67}
68
69#[derive(Deserialize)]
70struct QuadraticAssignmentData {
71    cost_matrix: Vec<Vec<i64>>,
72    distance_matrix: Vec<Vec<i64>>,
73}
74
75impl TryFrom<QuadraticAssignmentData> for QuadraticAssignment {
76    type Error = crate::registry::ConstructionError;
77
78    fn try_from(data: QuadraticAssignmentData) -> Result<Self, Self::Error> {
79        Self::try_new(data.cost_matrix, data.distance_matrix)
80    }
81}
82
83impl QuadraticAssignment {
84    /// Create a new Quadratic Assignment Problem.
85    ///
86    /// # Arguments
87    /// * `cost_matrix` - n x n matrix of flows/costs between facilities
88    /// * `distance_matrix` - m x m matrix of distances between locations
89    ///
90    /// # Panics
91    /// Panics if either matrix is not square, or if num_facilities > num_locations.
92    pub fn new(cost_matrix: Vec<Vec<i64>>, distance_matrix: Vec<Vec<i64>>) -> Self {
93        Self::try_new(cost_matrix, distance_matrix).unwrap_or_else(|error| panic!("{error}"))
94    }
95
96    fn try_new(
97        cost_matrix: Vec<Vec<i64>>,
98        distance_matrix: Vec<Vec<i64>>,
99    ) -> Result<Self, crate::registry::ConstructionError> {
100        let n = cost_matrix.len();
101        if cost_matrix.iter().any(|row| row.len() != n) {
102            return Err("cost_matrix must be square".into());
103        }
104        let m = distance_matrix.len();
105        if distance_matrix.iter().any(|row| row.len() != m) {
106            return Err("distance_matrix must be square".into());
107        }
108        if n > m {
109            return Err(format!("num_facilities ({n}) must be <= num_locations ({m})").into());
110        }
111        Ok(Self {
112            cost_matrix,
113            distance_matrix,
114        })
115    }
116
117    /// Get the cost/flow matrix.
118    pub fn cost_matrix(&self) -> &[Vec<i64>] {
119        &self.cost_matrix
120    }
121
122    /// Get the distance matrix.
123    pub fn distance_matrix(&self) -> &[Vec<i64>] {
124        &self.distance_matrix
125    }
126
127    /// Get the number of facilities.
128    pub fn num_facilities(&self) -> usize {
129        self.cost_matrix.len()
130    }
131
132    /// Get the number of locations.
133    pub fn num_locations(&self) -> usize {
134        self.distance_matrix.len()
135    }
136}
137
138impl Problem for QuadraticAssignment {
139    const NAME: &'static str = "QuadraticAssignment";
140    type Solution = Vec<usize>;
141    type Value = Min<i64>;
142
143    crate::problem_parameters![
144        ("num_facilities", num_facilities),
145        ("num_locations", num_locations),
146    ];
147
148    fn evaluate(
149        &self,
150        config: &Self::Solution,
151    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
152        Ok({
153            let n = self.num_facilities();
154            let m = self.num_locations();
155
156            // Check config length matches number of facilities
157            if config.len() != n {
158                return Err(crate::traits::EvaluationError::InvalidConfiguration(
159                    "assignment length does not match the number of facilities".into(),
160                ));
161            }
162
163            if config.iter().any(|&location| location >= m) {
164                return Err(crate::traits::EvaluationError::InvalidConfiguration(
165                    "assignment contains an out-of-range location".into(),
166                ));
167            }
168
169            // Check injectivity: no two facilities assigned to the same location
170            let mut used = vec![false; m];
171            for &loc in config {
172                if used[loc] {
173                    return Ok(Min(None));
174                }
175                used[loc] = true;
176            }
177
178            // Compute objective: sum_{i != j} cost_matrix[i][j] * distance_matrix[config[i]][config[j]]
179            let mut total: i64 = 0;
180            for i in 0..n {
181                for j in 0..n {
182                    if i != j {
183                        let term = self.cost_matrix[i][j]
184                            .checked_mul(self.distance_matrix[config[i]][config[j]])
185                            .ok_or_else(|| {
186                                crate::traits::EvaluationError::IntegerOverflow(
187                                    "multiplying quadratic assignment cost and distance"
188                                        .to_string(),
189                                )
190                            })?;
191                        total = total.checked_add(term).ok_or_else(|| {
192                            crate::traits::EvaluationError::IntegerOverflow(
193                                "summing quadratic assignment objective".to_string(),
194                            )
195                        })?;
196                    }
197                }
198            }
199
200            Min(Some(total))
201        })
202    }
203
204    fn variant() -> Vec<(&'static str, &'static str)> {
205        crate::variant_params![]
206    }
207}
208
209impl crate::solvers::BruteForceProblem for QuadraticAssignment {
210    fn dimensions(&self) -> Vec<usize> {
211        vec![self.num_locations(); self.num_facilities()]
212    }
213}
214
215crate::declare_variants! {
216    default QuadraticAssignment => "factorial(num_facilities)",
217}
218
219crate::register_brute_force! {
220    QuadraticAssignment,
221}
222
223#[cfg(feature = "example-db")]
224pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
225    vec![crate::example_db::specs::ModelExampleSpec {
226        id: "quadratic_assignment",
227        instance: Box::new(QuadraticAssignment::new(
228            vec![
229                vec![0, 5, 2, 0],
230                vec![5, 0, 0, 3],
231                vec![2, 0, 0, 4],
232                vec![0, 3, 4, 0],
233            ],
234            vec![
235                vec![0, 4, 1, 1],
236                vec![4, 0, 3, 4],
237                vec![1, 3, 0, 4],
238                vec![1, 4, 4, 0],
239            ],
240        )),
241        optimal_config: serde_json::json!(vec![3, 0, 1, 2]),
242        optimal_value: serde_json::json!(56),
243    }]
244}
245
246#[cfg(test)]
247#[path = "../../unit_tests/models/algebraic/quadratic_assignment.rs"]
248mod tests;
249
250crate::decision_problem_meta!(QuadraticAssignment, "DecisionQuadraticAssignment");
251crate::register_decision_variant!(
252    QuadraticAssignment, "DecisionQuadraticAssignment", "factorial(num_facilities)", &[],
253    "Does a feasible solution have objective value <= the bound?",
254    category: crate::registry::ProblemCategory::Algebraic,
255    dims: [],
256    fields: [
257        crate::registry::FieldInfo { name: "cost_matrix", type_name: "Vec<Vec<i64>>", description: "Flow/cost matrix between facilities" },
258        crate::registry::FieldInfo { name: "distance_matrix", type_name: "Vec<Vec<i64>>", description: "Distance matrix between locations" },
259        crate::registry::FieldInfo { name: "bound", type_name: "i64", description: "Accept objective values <= this bound" },
260    ],
261    decode: |_, indices: Vec<usize>| indices
262);
263
264#[cfg(feature = "example-db")]
265pub(crate) fn decision_canonical_rule_example_specs(
266) -> Vec<crate::example_db::specs::RuleExampleSpec> {
267    vec![crate::example_db::specs::RuleExampleSpec {
268        id: "decision_quadratic_assignment_to_quadratic_assignment",
269        build: || {
270            let source = crate::models::decision::Decision::new(
271                QuadraticAssignment::new(
272                    vec![
273                        vec![0, 5, 2, 0],
274                        vec![5, 0, 0, 3],
275                        vec![2, 0, 0, 4],
276                        vec![0, 3, 4, 0],
277                    ],
278                    vec![
279                        vec![0, 4, 1, 1],
280                        vec![4, 0, 3, 4],
281                        vec![1, 3, 0, 4],
282                        vec![1, 4, 4, 0],
283                    ],
284                ),
285                56,
286            );
287            let witness = serde_json::json!(vec![3, 0, 1, 2]);
288            crate::example_db::specs::rule_example_with_witness::<_, QuadraticAssignment>(
289                source,
290                crate::export::SolutionPair {
291                    source_config: witness.clone(),
292                    target_config: witness,
293                },
294            )
295        },
296    }]
297}
problemreductions/models/algebraic/quadratic_assignment.rs

problemreductions/models/algebraic/
quadratic_assignment.rs
