Coverage for moptipyapps/qap/instance.py: 76%
131 statements
« prev ^ index » next coverage.py v7.14.1, created at 2026-05-28 09:42 +0000
1"""
2An instance of the Quadratic Assignment Problem.
4In this module, we provide the class :class:`~Instance` that encapsulates all
5information of a problem instance of the Quadratic Assignment Problem (QAP).
6The QAP aims to locate facilities at locations such that the flow-distance
7product sum combining a flows of goods between instances with the distances of
8the locations becomes minimal. Each instance therefore presents a matrix with
9:attr:`~moptipyapps.qap.instance.Instance.distances` and a matrix with flows
10:attr:`~moptipyapps.qap.instance.Instance.flows`.
121. Eliane Maria Loiola, Nair Maria Maia de Abreu, Paulo Oswaldo
13 Boaventura-Netto, Peter Hahn, and Tania Querido. A survey for the
14 Quadratic Assignment Problem. European Journal of Operational Research.
15 176(2):657-690. January 2007. https://doi.org/10.1016/j.ejor.2005.09.032.
162. Rainer E. Burkard, Eranda Çela, Panos M. Pardalos, and
17 Leonidas S. Pitsoulis. The Quadratic Assignment Problem. In Ding-Zhu Du,
18 Panos M. Pardalos, eds., Handbook of Combinatorial Optimization,
19 pages 1713-1809, 1998, Springer New York, NY, USA.
20 https://doi.org/10.1007/978-1-4613-0303-9_27.
23We additionally provide access to several standard QAP benchmark instances
24via the :meth:`~Instance.from_resource` and :meth:`~Instance.list_resources`
25methods. The standard benchmark instances stem from QAPLIB, a library of QAP
26instances, which can be found at <https://qaplib.mgi.polymtl.ca> and
27<https://coral.ise.lehigh.edu/data-sets/qaplib>.
291. QAPLIB - A Quadratic Assignment Problem Library. The Websites
30 <https://qaplib.mgi.polymtl.ca/> (updated 2018) and
31 <https://coral.ise.lehigh.edu/data-sets/qaplib/> (updated 2011), including
32 the benchmark instances, on visited 2023-10-21.
332. Rainer E. Burkard, Stefan E. Karisch, and Franz Rendl. QAPLIB - A Quadratic
34 Assignment Problem Library. Journal of Global Optimization. 10:391-403,
35 1997. https://doi.org/10.1023/A:1008293323270.
36"""
39from typing import Final, Iterable, cast
41import numba # type: ignore
42import numpy as np
43from moptipy.api.component import Component
44from moptipy.utils.logger import KeyValueLogSection
45from moptipy.utils.nputils import (
46 DEFAULT_UNSIGNED_INT,
47 int_range_to_dtype,
48 is_np_int,
49)
50from moptipy.utils.strings import sanitize_name
51from pycommons.types import check_int_range, check_to_int_range, type_error
53from moptipyapps.qap.qaplib import open_resource_stream
56@numba.njit(cache=True, inline="always", fastmath=True, boundscheck=False)
57def trivial_bounds(distances: np.ndarray, flows: np.ndarray) \
58 -> tuple[int, int]:
59 """
60 Compute the trivial bounds for the QAP objective.
62 A trivial upper bound is to multiply the largest flow with the largest
63 distance, the second-largest flow with the second-largest distance, the
64 third-largest flow with the third-largest distance, and so on.
66 A trivial lower bound is to multiply the largest flow with the shortest
67 distance, the second-largest flow with the second-shortest distance, the
68 third-largest flow with the third-shortest distance, and so on.
70 :param distances: the distance matrix
71 :param flows: the flow matrix
72 :return: the lower and upper bounds
74 >>> dst = np.array([[0, 1, 2], [3, 0, 4], [5, 6, 0]])
75 >>> flws = np.array([[0, 95, 86], [23, 0, 55], [24, 43, 0]])
76 >>> 0*95 + 0*86 + 0*55 + 1*43 + 2*24 + 3*23 + 4*0 + 5*0 + 6*0
77 160
78 >>> 6*95 + 5*86 + 4*55 + 3*43 + 2*24 + 1*23 + 0*0 + 0*0 + 0*0
79 1420
80 >>> trivial_bounds(dst, flws)
81 (160, 1420)
82 """
83 n: int = len(distances)
84 n *= n
85 df_ub: Final[np.ndarray] = np.empty(n, DEFAULT_UNSIGNED_INT)
86 df_ub[:] = distances.flatten()
87 df_ub.sort()
88 df_lb: Final[np.ndarray] = np.empty(n, DEFAULT_UNSIGNED_INT)
89 df_lb[:] = df_ub[::-1]
90 ff: Final[np.ndarray] = np.empty(n, DEFAULT_UNSIGNED_INT)
91 ff[:] = flows.flatten()
92 ff.sort()
93 return (int(np.multiply(df_lb, ff, df_lb).sum()),
94 int(np.multiply(df_ub, ff, df_ub).sum()))
97def _flow_or_dist_to_int(val: str) -> int:
98 """
99 Convert a flow or distance string to an integer.
101 :param val: the value
102 :return: the integer
103 """
104 return check_to_int_range(val, "value", 0, 1_000_000_000_000_000)
107#: the instances of the QAPLib library
108_INSTANCES: Final[tuple[str, ...]] = (
109 "bur26a", "bur26b", "bur26c", "bur26d", "bur26e", "bur26f", "bur26g",
110 "bur26h", "chr12a", "chr12b", "chr12c", "chr15a", "chr15b", "chr15c",
111 "chr18a", "chr18b", "chr20a", "chr20b", "chr20c", "chr22a", "chr22b",
112 "chr25a", "els19", "esc16a", "esc16b", "esc16c", "esc16d", "esc16e",
113 "esc16f", "esc16g", "esc16h", "esc16i", "esc16j", "esc32a", "esc32b",
114 "esc32c", "esc32d", "esc32e", "esc32g", "esc32h", "esc64a", "esc128",
115 "had12", "had14", "had16", "had18", "had20", "kra30a", "kra30b", "kra32",
116 "lipa20a", "lipa20b", "lipa30a", "lipa30b", "lipa40a", "lipa40b",
117 "lipa50a", "lipa50b", "lipa60a", "lipa60b", "lipa70a", "lipa70b",
118 "lipa80a", "lipa80b", "lipa90a", "lipa90b", "nug12", "nug14", "nug15",
119 "nug16a", "nug16b", "nug17", "nug18", "nug20", "nug21", "nug22", "nug24",
120 "nug25", "nug27", "nug28", "nug30", "rou12", "rou15", "rou20", "scr12",
121 "scr15", "scr20", "sko42", "sko49", "sko56", "sko64", "sko72", "sko81",
122 "sko90", "sko100a", "sko100b", "sko100c", "sko100d", "sko100e", "sko100f",
123 "ste36a", "ste36b", "ste36c", "tai10a", "tai10b", "tai12a", "tai12b",
124 "tai15a", "tai15b", "tai17a", "tai20a", "tai20b", "tai25a", "tai25b",
125 "tai30a", "tai30b", "tai35a", "tai35b", "tai40a", "tai40b", "tai50a",
126 "tai50b", "tai60a", "tai60b", "tai64c", "tai80a", "tai80b", "tai100a",
127 "tai100b", "tai150b", "tai256c", "tho30", "tho40", "tho150", "wil50",
128 "wil100")
130#: the lower bounds provided at <https://qaplib.mgi.polymtl.ca/>
131_BOUNDS: Final[dict[str, int]] = {
132 "nug14": 1014, "nug15": 1150, "nug16a": 1610, "nug16b": 1240,
133 "nug17": 1732, "nug18": 1930, "nug20": 2570, "nug21": 2438, "nug22": 3596,
134 "nug24": 3488, "nug25": 3744, "nug27": 5234, "nug28": 5166, "nug30": 6124,
135 "rou12": 235528, "rou15": 354210, "rou20": 725522, "scr12": 31410,
136 "scr15": 51140, "scr20": 110030, "sko100a": 143846, "sko100b": 145522,
137 "sko100c": 139881, "sko100d": 141289, "sko100e": 140893, "sko100f": 140691,
138 "sko42": 15332, "sko49": 22650, "sko56": 33385, "sko64": 47017,
139 "sko72": 64455, "sko81": 88359, "sko90": 112423, "ste36a": 9526,
140 "ste36b": 15852, "ste36c": 8239110, "tai10a": 135028, "tai10b": 1183760,
141 "tai12a": 224416, "tai12b": 39464925, "tai150b": 441786736,
142 "tai15a": 388214, "tai15b": 51765268, "tai17a": 491812, "tai20a": 703482,
143 "tai20b": 122455319, "tai25a": 1167256, "tai25b": 344355646,
144 "tai30a": 1706855, "tai30b": 637117113, "tai35a": 2216627,
145 "tai35b": 269532400, "tai40a": 2843274, "tai40b": 608808400,
146 "tai50a": 4390920, "tai50b": 431090700, "tai60a": 6325978,
147 "tai60b": 592371800, "tai64c": 1855928, "tai80a": 11657010,
148 "tai80b": 786298800, "tai100a": 17853840, "tai100b": 1151591000,
149 "tai256c": 44095032, "tho150": 7620628, "tho30": 149936, "tho40": 226490,
150 "wil100": 268955, "wil50": 48121, "bur26a": 5426670, "bur26b": 3817852,
151 "bur26c": 5426795, "bur26d": 3821225, "bur26e": 5386879, "bur26f": 3782044,
152 "bur26g": 10117172, "bur26h": 7098658, "chr12a": 9552, "chr12b": 9742,
153 "chr12c": 11156, "chr15a": 9896, "chr15b": 7990, "chr15c": 9504,
154 "chr18a": 11098, "chr18b": 1534, "chr20a": 2192, "chr20b": 2298,
155 "chr20c": 14142, "chr22a": 6156, "chr22b": 6194, "chr25a": 3796,
156 "els19": 17212548, "esc128": 64, "esc16a": 68, "esc16b": 292,
157 "esc16c": 160, "esc16d": 16, "esc16e": 28, "esc16f": 0, "esc16g": 26,
158 "esc16h": 996, "esc16i": 14, "esc16j": 8, "esc32a": 130, "esc32b": 168,
159 "esc32c": 642, "esc32d": 200, "esc32e": 2, "esc32g": 6, "esc32h": 438,
160 "esc64a": 116, "had12": 1652, "had14": 2724, "had16": 3720, "had18": 5358,
161 "had20": 6922, "kra30a": 88900, "kra30b": 91420, "kra32": 88700,
162 "lipa20a": 3683, "lipa20b": 27076, "lipa30a": 13178, "lipa30b": 151426,
163 "lipa40a": 31538, "lipa40b": 476581, "lipa50a": 62093, "lipa50b": 1210244,
164 "lipa60a": 107218, "lipa60b": 2520135, "lipa70a": 169755,
165 "lipa70b": 4603200, "lipa80a": 253195, "lipa80b": 7763962,
166 "lipa90a": 360630, "lipa90b": 12490441, "nug12": 578}
168#: The best-known solutions of the QAPLIB instances that are not yet solved to
169#: optimality, as of 2024-05-09 on https://qaplib.mgi.polymtl.ca/
170_BKS: Final[dict[str, tuple[str, int]]] = {
171 "sko90": ("T1991RTSFTQAP,T1995COISFTQAP", 115534),
172 "sko100a": ("FF1993GHFTQAP", 152002),
173 "sko100b": ("FF1993GHFTQAP", 153890),
174 "sko100c": ("FF1993GHFTQAP", 147862),
175 "sko100d": ("FF1993GHFTQAP", 149576),
176 "sko100e": ("FF1993GHFTQAP", 149150),
177 "sko100f": ("FF1993GHFTQAP", 149036),
178 "tai30a": ("T1991RTSFTQAP,T1995COISFTQAP", 1818146),
179 "tai35a": ("T1991RTSFTQAP,T1995COISFTQAP", 2422002),
180 "tai35b": ("T1991RTSFTQAP,T1995COISFTQAP", 283315445),
181 "tai40a": ("T1991RTSFTQAP,T1995COISFTQAP", 3139370),
182 "tai40b": ("T1991RTSFTQAP,T1995COISFTQAP", 637250948),
183 "tai50a": ("M2008AIOTITSAFTQAP", 4938796),
184 "tai50b": ("T1991RTSFTQAP,T1995COISFTQAP", 458821517),
185 "tai60a": ("M2005ATSAFTQAP", 7205962),
186 "tai60b": ("T1991RTSFTQAP,T1995COISFTQAP", 608215054),
187 "tai80a": ("M2008AIOTITSAFTQAP", 13499184),
188 "tai80b": ("T1991RTSFTQAP,T1995COISFTQAP", 818415043),
189 "tai100a": ("M2008AIOTITSAFTQAP", 21044752),
190 "tai100b": ("T1991RTSFTQAP,T1995COISFTQAP", 1185996137),
191 "tai150b": ("TG1997AMFTQAP", 498896643),
192 "tai256c": ("S1997MMASFQAP", 44759294),
193 "tho40": ("TB1994AISAAFTQAP", 240516),
194 "tho150": ("M2003AMSAAFTQAP", 8133398),
195 "wil100": ("FF1993GHFTQAP", 273038),
196}
199class Instance(Component):
200 """An instance of the Quadratic Assignment Problem."""
202 def __init__(self, distances: np.ndarray, flows: np.ndarray,
203 lower_bound: int | None = None,
204 upper_bound: int | None = None,
205 name: str | None = None) -> None:
206 """
207 Create an instance of the quadratic assignment problem.
209 :param distances: the distance matrix
210 :param flows: the flow matrix
211 :param lower_bound: the optional lower bound
212 :param upper_bound: the optional upper bound
213 :param name: the name of this instance
214 """
215 super().__init__()
216 if not isinstance(distances, np.ndarray):
217 raise type_error(distances, "distances", np.ndarray)
218 if not isinstance(flows, np.ndarray):
219 raise type_error(flows, "flows", np.ndarray)
220 shape: tuple[int, ...] = distances.shape
221 if len(shape) != 2:
222 raise ValueError("distance matrix must have two dimensions, but "
223 f"has {len(shape)}, namely {shape}.")
224 if shape[0] != shape[1]:
225 raise ValueError(
226 f"distance matrix must be square, but has shape {shape}.")
227 if not is_np_int(distances.dtype):
228 raise ValueError("distance matrix must be integer, but has "
229 f"dtype {distances.dtype}.")
230 if shape != flows.shape:
231 raise ValueError(
232 f"flow matrix has shape {flows.shape} and distance matrix has"
233 f" shape {shape}, which are different.")
234 if not is_np_int(flows.dtype):
235 raise ValueError(
236 f"flow matrix must be integer, but has dtype {flows.dtype}.")
238 lb, ub = trivial_bounds(distances, flows)
239 if lower_bound is not None:
240 lb = max(lb, check_int_range(
241 lower_bound, "lower_bound", 0, 1_000_000_000_000_000))
242 if upper_bound is not None:
243 ub = min(ub, check_int_range(
244 upper_bound, "upper_bound", 0, 1_000_000_000_000_000))
245 if lb > ub:
246 raise ValueError(f"lower bound = {lb} > upper_bound = {ub}!")
247 dtype: Final[np.dtype] = int_range_to_dtype(min_value=0, max_value=ub)
248 #: the scale of the problem
249 self.n: Final[int] = shape[0]
250 if name is None:
251 name = f"qap{self.n}_{lb}_{ub}"
252 else:
253 sn: Final[str] = sanitize_name(name)
254 if name != sn:
255 raise ValueError(f"name={name!r} sanitizes to {sn!r}.")
256 #: the name of this instance
257 self.name: Final[str] = name
258 #: the distance matrix
259 self.distances: Final[np.ndarray] = \
260 distances.astype(dtype) if distances.dtype != dtype else distances
261 #: the flows
262 self.flows: Final[np.ndarray] = \
263 flows.astype(dtype) if flows.dtype != dtype else flows
264 #: the lower bound for the QAP objective
265 self.lower_bound: Final[int] = lb
266 #: the upper bound for the QAP objective
267 self.upper_bound: Final[int] = ub
269 def __str__(self):
270 """
271 Get the name of this instance.
273 :return: :attr:`~name`
274 """
275 return self.name
277 def bks(self) -> tuple[str, int]:
278 """
279 Get the best-known solution, if known, the optimum, or lower bound.
281 A tuple with a string identifying the source of the value and a value
282 corresponding to the best-known solution:
284 - `("OPT", xxx)`: the problem instance has been solved to optimality
285 and `xxx` is the objective value of the optimum
286 - `("LB", xxx)`: neither the optimum nor a best-known solution are
287 available for this instance, so we return the lower bound
289 The data is based on https://qaplib.mgi.polymtl.ca/, visited on
290 2024-05-09. The following sources are included:
292 - "FF1993GHFTQAP": Charles Fleurent and Jacques A. Ferland. Genetic
293 Hybrids for the Quadratic Assignment Problem. In Panos M. Pardalos
294 and Henry Wolkowicz, eds, *Quadratic Assignment and Related
295 Problems, Proceedings of a DIMACS Workshop,* May 20-21, 1993.
296 pages 173-187. Providence, RI, USA: American Mathematical Society.
297 - "M2003AMSAAFTQAP": Alfonsas Misevičius, A Modified Simulated
298 Annealing Algorithm for the Quadratic Assignment Problem.
299 *Informatica* 14(4):497-514. January 2003.
300 https://doi.org/10.15388/Informatica.2003.037.
301 - "M2005ATSAFTQAP": Alfonsas Misevičius. A Tabu Search Algorithm for
302 the Quadratic Assignment Problem.
303 *Computational Optimization and Applications* 30(1):95-111. 2005.
304 https://doi.org/10.1007/s10589-005-4562-x.
305 - "M2008AIOTITSAFTQAP": Alfonsas Misevičius. An Implementation of
306 the Iterated Tabu Search Algorithm for the Quadratic Assignment
307 Problem. Working Paper. 2008. Kaunas, Lithuania: Kaunas University
308 of Technology.
309 - "S1997MMASFQAP": Thomas Stützle. MAX-MIN Ant System for Quadratic
310 Assignment Problems. Research Report AIDA-97-04. 1997. Darmstadt,
311 Germany: Department of Computer Schience, Darmstadt University of
312 Technology.
313 - "T1991RTSFTQAP": Éric Taillard. Robust Taboo Search for the
314 Quadratic Assignment Problem. *Parallel Computing.*
315 17(4-5):443-455. July 1991.
316 - "T1995COISFTQAP": Éric D. Taillard. Comparison of Iterative
317 Searches for the Quadratic Assignment Problem. *Location Science*
318 3(2):87-105. 1995.
319 - "TB1994AISAAFTQAP": Ulrich Wilhelm Thonemann and Andreas Bölte.
320 An Improved Simulated Annealing Algorithm for the Quadratic
321 Assignment Problem. Working Paper 1994. Paderborn, Germany: School
322 of Business, Department of Production and Operations Research,
323 University of Paderborn.
324 - "TG1997AMFTQAP": Éric D. Taillard and Luca-Maria Gambardella.
325 Adaptive Memories for the Quadratic Assignment Problem. 1997.
326 Technical Report IDSIA-87-97. Lugano, Switzerland: IDSIA.
328 :return: a `tuple[str, int]` with the objective value of the
329 best-known (if any is available), the optimum, or the lower bound.
330 """
331 name: Final[str] = self.name
332 if name in _BKS:
333 return _BKS[name]
334 if name in _BOUNDS:
335 return "OPT", _BOUNDS[name]
336 return "LB", self.lower_bound
338 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
339 """
340 Log all parameters of this instance as key-value pairs.
342 :param logger: the logger for the parameters
343 """
344 super().log_parameters_to(logger)
345 logger.key_value("n", self.n)
346 logger.key_value("qapLowerBound", self.lower_bound)
347 logger.key_value("qapUpperBound", self.upper_bound)
349 @staticmethod
350 def from_qaplib_stream(stream: Iterable[str],
351 lower_bound: int | None = None,
352 upper_bound: int | None = None,
353 name: str | None = None) -> "Instance":
354 """
355 Load an instance from a QAPLib-formatted stream.
357 :param stream: the stream to load the data from
358 :param lower_bound: the optional lower bound
359 :param upper_bound: the optional upper bound
360 :param name: the name of this instance
361 :return: the instance
363 >>> ins = Instance.from_qaplib_stream([
364 ... "4", "",
365 ... "1 2 3 4 5 6 7 8 9 10 11 12 13",
366 ... " 14 15 16 ", "",
367 ... "17 18 19 20 21 22 23 24 25 26 27",
368 ... " 28 29 30 31 32"])
369 >>> ins.distances
370 array([[17, 18, 19, 20],
371 [21, 22, 23, 24],
372 [25, 26, 27, 28],
373 [29, 30, 31, 32]], dtype=int16)
374 >>> ins.flows
375 array([[ 1, 2, 3, 4],
376 [ 5, 6, 7, 8],
377 [ 9, 10, 11, 12],
378 [13, 14, 15, 16]], dtype=int16)
379 >>> ins.lower_bound
380 2992
381 >>> ins.upper_bound
382 3672
383 >>> ins.name
384 'qap4_2992_3672'
385 """
386 state: int = 0
387 n: int | None = None
388 n2: int = -1
389 flows: list[int] = []
390 dists: list[int] = []
391 for oline in stream:
392 line = oline.strip()
393 if len(line) <= 0:
394 continue
395 if state == 0:
396 n = check_to_int_range(line, "n", 1, 1_000_000)
397 n2 = n * n
398 state = 1
399 else:
400 row: Iterable[int] = map(_flow_or_dist_to_int, line.split())
401 if state == 1:
402 flows.extend(row)
403 if len(flows) >= n2:
404 state = 2
405 continue
406 dists.extend(row)
407 if len(dists) >= n2:
408 state = 3
409 break
411 if (n is None) or (n <= 0):
412 raise ValueError(f"Invalid or unspecified size n={n}.")
413 lll: int = len(flows)
414 if lll != n2:
415 raise ValueError(
416 f"Invalid number of flows {lll}, should be n²={n}²={n2}.")
417 lll = len(dists)
418 if lll != n2:
419 raise ValueError(
420 f"Invalid number of distances {lll}, should be n²={n}²={n2}.")
421 if state != 3:
422 raise ValueError(f"Stream is incomplete, state={state}.")
424 return Instance(np.array(dists, DEFAULT_UNSIGNED_INT).reshape((n, n)),
425 np.array(flows, DEFAULT_UNSIGNED_INT).reshape((n, n)),
426 lower_bound, upper_bound, name)
428 @staticmethod
429 def list_resources() -> tuple[str, ...]:
430 """
431 Get a tuple of all the QAP-lib instances available as resource.
433 The original data can be found at <https://qaplib.mgi.polymtl.ca> and
434 <https://coral.ise.lehigh.edu/data-sets/qaplib>.
436 :return: the tuple with the instance names
438 >>> len(Instance.list_resources())
439 136
440 """
441 return _INSTANCES
443 @staticmethod
444 def from_resource(name: str) -> "Instance":
445 """
446 Load a QAP-Lib instance from a resource.
448 The original data can be found at <https://qaplib.mgi.polymtl.ca> and
449 <https://coral.ise.lehigh.edu/data-sets/qaplib>.
451 :param name: the name string
452 :return: the instance
454 >>> insta = Instance.from_resource("chr25a")
455 >>> print(insta.n)
456 25
457 >>> print(insta.name)
458 chr25a
459 >>> print(insta.lower_bound)
460 3796
461 >>> print(insta.upper_bound)
462 50474
463 """
464 if not isinstance(name, str):
465 raise type_error(name, "name", str)
466 container: Final = Instance.from_resource
467 inst_attr: Final[str] = f"__inst_{name}"
468 if hasattr(container, inst_attr): # instance loaded?
469 return cast("Instance", getattr(container, inst_attr))
471 lb: int | None = _BOUNDS.get(name, None)
472 with open_resource_stream(f"{name}.dat") as stream:
473 inst: Final[Instance] = Instance.from_qaplib_stream(
474 stream, name=name, lower_bound=lb)
476 if inst.n <= 1000:
477 setattr(container, inst_attr, inst)
478 return inst