Coverage for moptipyapps / qap / instance.py: 76%
131 statements
« prev ^ index » next coverage.py v7.13.0, created at 2025-12-11 04:40 +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", "tai12a", "tai12b", "tai15a", "tai15b",
124 "tai17a", "tai20a", "tai20b", "tai25a", "tai25b", "tai30a", "tai30b",
125 "tai35a", "tai35b", "tai40a", "tai40b", "tai50a", "tai50b", "tai60a",
126 "tai60b", "tai64c", "tai80a", "tai80b", "tai100a", "tai100b", "tai150b",
127 "tai256c", "tho30", "tho40", "tho150", "wil50", "wil100")
129#: the lower bounds provided at <https://qaplib.mgi.polymtl.ca/>
130_BOUNDS: Final[dict[str, int]] = {
131 "nug14": 1014, "nug15": 1150, "nug16a": 1610, "nug16b": 1240,
132 "nug17": 1732, "nug18": 1930, "nug20": 2570, "nug21": 2438, "nug22": 3596,
133 "nug24": 3488, "nug25": 3744, "nug27": 5234, "nug28": 5166, "nug30": 6124,
134 "rou12": 235528, "rou15": 354210, "rou20": 725522, "scr12": 31410,
135 "scr15": 51140, "scr20": 110030, "sko100a": 143846, "sko100b": 145522,
136 "sko100c": 139881, "sko100d": 141289, "sko100e": 140893, "sko100f": 140691,
137 "sko42": 15332, "sko49": 22650, "sko56": 33385, "sko64": 47017,
138 "sko72": 64455, "sko81": 88359, "sko90": 112423, "ste36a": 9526,
139 "ste36b": 15852, "ste36c": 8239110, "tai100a": 17853840,
140 "tai100b": 1151591000, "tai12a": 224416, "tai12b": 39464925,
141 "tai150b": 441786736, "tai15a": 388214, "tai15b": 51765268,
142 "tai17a": 491812, "tai20a": 703482, "tai20b": 122455319,
143 "tai256c": 44095032, "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, "tho150": 7620628, "tho30": 149936, "tho40": 226490,
149 "wil100": 268955, "wil50": 48121, "bur26a": 5426670, "bur26b": 3817852,
150 "bur26c": 5426795, "bur26d": 3821225, "bur26e": 5386879, "bur26f": 3782044,
151 "bur26g": 10117172, "bur26h": 7098658, "chr12a": 9552, "chr12b": 9742,
152 "chr12c": 11156, "chr15a": 9896, "chr15b": 7990, "chr15c": 9504,
153 "chr18a": 11098, "chr18b": 1534, "chr20a": 2192, "chr20b": 2298,
154 "chr20c": 14142, "chr22a": 6156, "chr22b": 6194, "chr25a": 3796,
155 "els19": 17212548, "esc128": 64, "esc16a": 68, "esc16b": 292,
156 "esc16c": 160, "esc16d": 16, "esc16e": 28, "esc16f": 0, "esc16g": 26,
157 "esc16h": 996, "esc16i": 14, "esc16j": 8, "esc32a": 130, "esc32b": 168,
158 "esc32c": 642, "esc32d": 200, "esc32e": 2, "esc32g": 6, "esc32h": 438,
159 "esc64a": 116, "had12": 1652, "had14": 2724, "had16": 3720, "had18": 5358,
160 "had20": 6922, "kra30a": 88900, "kra30b": 91420, "kra32": 88700,
161 "lipa20a": 3683, "lipa20b": 27076, "lipa30a": 13178, "lipa30b": 151426,
162 "lipa40a": 31538, "lipa40b": 476581, "lipa50a": 62093, "lipa50b": 1210244,
163 "lipa60a": 107218, "lipa60b": 2520135, "lipa70a": 169755,
164 "lipa70b": 4603200, "lipa80a": 253195, "lipa80b": 7763962,
165 "lipa90a": 360630, "lipa90b": 12490441, "nug12": 578}
167#: The best-known solutions of the QAPLIB instances that are not yet solved to
168#: optimality, as of 2024-05-09 on https://qaplib.mgi.polymtl.ca/
169_BKS: Final[dict[str, tuple[str, int]]] = {
170 "sko90": ("T1991RTSFTQAP,T1995COISFTQAP", 115534),
171 "sko100a": ("FF1993GHFTQAP", 152002),
172 "sko100b": ("FF1993GHFTQAP", 153890),
173 "sko100c": ("FF1993GHFTQAP", 147862),
174 "sko100d": ("FF1993GHFTQAP", 149576),
175 "sko100e": ("FF1993GHFTQAP", 149150),
176 "sko100f": ("FF1993GHFTQAP", 149036),
177 "tai30a": ("T1991RTSFTQAP,T1995COISFTQAP", 1818146),
178 "tai35a": ("T1991RTSFTQAP,T1995COISFTQAP", 2422002),
179 "tai35b": ("T1991RTSFTQAP,T1995COISFTQAP", 283315445),
180 "tai40a": ("T1991RTSFTQAP,T1995COISFTQAP", 3139370),
181 "tai40b": ("T1991RTSFTQAP,T1995COISFTQAP", 637250948),
182 "tai50a": ("M2008AIOTITSAFTQAP", 4938796),
183 "tai50b": ("T1991RTSFTQAP,T1995COISFTQAP", 458821517),
184 "tai60a": ("M2005ATSAFTQAP", 7205962),
185 "tai60b": ("T1991RTSFTQAP,T1995COISFTQAP", 608215054),
186 "tai80a": ("M2008AIOTITSAFTQAP", 13499184),
187 "tai80b": ("T1991RTSFTQAP,T1995COISFTQAP", 818415043),
188 "tai100a": ("M2008AIOTITSAFTQAP", 21044752),
189 "tai100b": ("T1991RTSFTQAP,T1995COISFTQAP", 1185996137),
190 "tai150b": ("TG1997AMFTQAP", 498896643),
191 "tai256c": ("S1997MMASFQAP", 44759294),
192 "tho40": ("TB1994AISAAFTQAP", 240516),
193 "tho150": ("M2003AMSAAFTQAP", 8133398),
194 "wil100": ("FF1993GHFTQAP", 273038),
195}
198class Instance(Component):
199 """An instance of the Quadratic Assignment Problem."""
201 def __init__(self, distances: np.ndarray, flows: np.ndarray,
202 lower_bound: int | None = None,
203 upper_bound: int | None = None,
204 name: str | None = None) -> None:
205 """
206 Create an instance of the quadratic assignment problem.
208 :param distances: the distance matrix
209 :param flows: the flow matrix
210 :param lower_bound: the optional lower bound
211 :param upper_bound: the optional upper bound
212 :param name: the name of this instance
213 """
214 super().__init__()
215 if not isinstance(distances, np.ndarray):
216 raise type_error(distances, "distances", np.ndarray)
217 if not isinstance(flows, np.ndarray):
218 raise type_error(flows, "flows", np.ndarray)
219 shape: tuple[int, ...] = distances.shape
220 if len(shape) != 2:
221 raise ValueError("distance matrix must have two dimensions, but "
222 f"has {len(shape)}, namely {shape}.")
223 if shape[0] != shape[1]:
224 raise ValueError(
225 f"distance matrix must be square, but has shape {shape}.")
226 if not is_np_int(distances.dtype):
227 raise ValueError("distance matrix must be integer, but has "
228 f"dtype {distances.dtype}.")
229 if shape != flows.shape:
230 raise ValueError(
231 f"flow matrix has shape {flows.shape} and distance matrix has"
232 f" shape {shape}, which are different.")
233 if not is_np_int(flows.dtype):
234 raise ValueError(
235 f"flow matrix must be integer, but has dtype {flows.dtype}.")
237 lb, ub = trivial_bounds(distances, flows)
238 if lower_bound is not None:
239 lb = max(lb, check_int_range(
240 lower_bound, "lower_bound", 0, 1_000_000_000_000_000))
241 if upper_bound is not None:
242 ub = min(ub, check_int_range(
243 upper_bound, "upper_bound", 0, 1_000_000_000_000_000))
244 if lb > ub:
245 raise ValueError(f"lower bound = {lb} > upper_bound = {ub}!")
246 dtype: Final[np.dtype] = int_range_to_dtype(min_value=0, max_value=ub)
247 #: the scale of the problem
248 self.n: Final[int] = shape[0]
249 if name is None:
250 name = f"qap{self.n}_{lb}_{ub}"
251 else:
252 sn: Final[str] = sanitize_name(name)
253 if name != sn:
254 raise ValueError(f"name={name!r} sanitizes to {sn!r}.")
255 #: the name of this instance
256 self.name: Final[str] = name
257 #: the distance matrix
258 self.distances: Final[np.ndarray] = \
259 distances.astype(dtype) if distances.dtype != dtype else distances
260 #: the flows
261 self.flows: Final[np.ndarray] = \
262 flows.astype(dtype) if flows.dtype != dtype else flows
263 #: the lower bound for the QAP objective
264 self.lower_bound: Final[int] = lb
265 #: the upper bound for the QAP objective
266 self.upper_bound: Final[int] = ub
268 def __str__(self):
269 """
270 Get the name of this instance.
272 :return: :attr:`~name`
273 """
274 return self.name
276 def bks(self) -> tuple[str, int]:
277 """
278 Get the best-known solution, if known, the optimum, or lower bound.
280 A tuple with a string identifying the source of the value and a value
281 corresponding to the best-known solution:
283 - `("OPT", xxx)`: the problem instance has been solved to optimality
284 and `xxx` is the objective value of the optimum
285 - `("LB", xxx)`: neither the optimum nor a best-known solution are
286 available for this instance, so we return the lower bound
288 The data is based on https://qaplib.mgi.polymtl.ca/, visited on
289 2024-05-09. The following sources are included:
291 - "FF1993GHFTQAP": Charles Fleurent and Jacques A. Ferland. Genetic
292 Hybrids for the Quadratic Assignment Problem. In Panos M. Pardalos
293 and Henry Wolkowicz, eds, *Quadratic Assignment and Related
294 Problems, Proceedings of a DIMACS Workshop,* May 20-21, 1993.
295 pages 173-187. Providence, RI, USA: American Mathematical Society.
296 - "M2003AMSAAFTQAP": Alfonsas Misevičius, A Modified Simulated
297 Annealing Algorithm for the Quadratic Assignment Problem.
298 *Informatica* 14(4):497-514. January 2003.
299 https://doi.org/10.15388/Informatica.2003.037.
300 - "M2005ATSAFTQAP": Alfonsas Misevičius. A Tabu Search Algorithm for
301 the Quadratic Assignment Problem.
302 *Computational Optimization and Applications* 30(1):95-111. 2005.
303 https://doi.org/10.1007/s10589-005-4562-x.
304 - "M2008AIOTITSAFTQAP": Alfonsas Misevičius. An Implementation of
305 the Iterated Tabu Search Algorithm for the Quadratic Assignment
306 Problem. Working Paper. 2008. Kaunas, Lithuania: Kaunas University
307 of Technology.
308 - "S1997MMASFQAP": Thomas Stützle. MAX-MIN Ant System for Quadratic
309 Assignment Problems. Research Report AIDA-97-04. 1997. Darmstadt,
310 Germany: Department of Computer Schience, Darmstadt University of
311 Technology.
312 - "T1991RTSFTQAP": Éric Taillard. Robust Taboo Search for the
313 Quadratic Assignment Problem. *Parallel Computing.*
314 17(4-5):443-455. July 1991.
315 - "T1995COISFTQAP": Éric D. Taillard. Comparison of Iterative
316 Searches for the Quadratic Assignment Problem. *Location Science*
317 3(2):87-105. 1995.
318 - "TB1994AISAAFTQAP": Ulrich Wilhelm Thonemann and Andreas Bölte.
319 An Improved Simulated Annealing Algorithm for the Quadratic
320 Assignment Problem. Working Paper 1994. Paderborn, Germany: School
321 of Business, Department of Production and Operations Research,
322 University of Paderborn.
323 - "TG1997AMFTQAP": Éric D. Taillard and Luca-Maria Gambardella.
324 Adaptive Memories for the Quadratic Assignment Problem. 1997.
325 Technical Report IDSIA-87-97. Lugano, Switzerland: IDSIA.
327 :return: a `tuple[str, int]` with the objective value of the
328 best-known (if any is available), the optimum, or the lower bound.
329 """
330 name: Final[str] = self.name
331 if name in _BKS:
332 return _BKS[name]
333 if name in _BOUNDS:
334 return "OPT", _BOUNDS[name]
335 return "LB", self.lower_bound
337 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
338 """
339 Log all parameters of this instance as key-value pairs.
341 :param logger: the logger for the parameters
342 """
343 super().log_parameters_to(logger)
344 logger.key_value("n", self.n)
345 logger.key_value("qapLowerBound", self.lower_bound)
346 logger.key_value("qapUpperBound", self.upper_bound)
348 @staticmethod
349 def from_qaplib_stream(stream: Iterable[str],
350 lower_bound: int | None = None,
351 upper_bound: int | None = None,
352 name: str | None = None) -> "Instance":
353 """
354 Load an instance from a QAPLib-formatted stream.
356 :param stream: the stream to load the data from
357 :param lower_bound: the optional lower bound
358 :param upper_bound: the optional upper bound
359 :param name: the name of this instance
360 :return: the instance
362 >>> ins = Instance.from_qaplib_stream([
363 ... "4", "",
364 ... "1 2 3 4 5 6 7 8 9 10 11 12 13",
365 ... " 14 15 16 ", "",
366 ... "17 18 19 20 21 22 23 24 25 26 27",
367 ... " 28 29 30 31 32"])
368 >>> ins.distances
369 array([[17, 18, 19, 20],
370 [21, 22, 23, 24],
371 [25, 26, 27, 28],
372 [29, 30, 31, 32]], dtype=int16)
373 >>> ins.flows
374 array([[ 1, 2, 3, 4],
375 [ 5, 6, 7, 8],
376 [ 9, 10, 11, 12],
377 [13, 14, 15, 16]], dtype=int16)
378 >>> ins.lower_bound
379 2992
380 >>> ins.upper_bound
381 3672
382 >>> ins.name
383 'qap4_2992_3672'
384 """
385 state: int = 0
386 n: int | None = None
387 n2: int = -1
388 flows: list[int] = []
389 dists: list[int] = []
390 for oline in stream:
391 line = oline.strip()
392 if len(line) <= 0:
393 continue
394 if state == 0:
395 n = check_to_int_range(line, "n", 1, 1_000_000)
396 n2 = n * n
397 state = 1
398 else:
399 row: Iterable[int] = map(_flow_or_dist_to_int, line.split())
400 if state == 1:
401 flows.extend(row)
402 if len(flows) >= n2:
403 state = 2
404 continue
405 dists.extend(row)
406 if len(dists) >= n2:
407 state = 3
408 break
410 if (n is None) or (n <= 0):
411 raise ValueError(f"Invalid or unspecified size n={n}.")
412 lll: int = len(flows)
413 if lll != n2:
414 raise ValueError(
415 f"Invalid number of flows {lll}, should be n²={n}²={n2}.")
416 lll = len(dists)
417 if lll != n2:
418 raise ValueError(
419 f"Invalid number of distances {lll}, should be n²={n}²={n2}.")
420 if state != 3:
421 raise ValueError(f"Stream is incomplete, state={state}.")
423 return Instance(np.array(dists, DEFAULT_UNSIGNED_INT).reshape((n, n)),
424 np.array(flows, DEFAULT_UNSIGNED_INT).reshape((n, n)),
425 lower_bound, upper_bound, name)
427 @staticmethod
428 def list_resources() -> tuple[str, ...]:
429 """
430 Get a tuple of all the QAP-lib instances available as resource.
432 The original data can be found at <https://qaplib.mgi.polymtl.ca> and
433 <https://coral.ise.lehigh.edu/data-sets/qaplib>.
435 :return: the tuple with the instance names
437 >>> len(Instance.list_resources())
438 134
439 """
440 return _INSTANCES
442 @staticmethod
443 def from_resource(name: str) -> "Instance":
444 """
445 Load a QAP-Lib instance from a resource.
447 The original data can be found at <https://qaplib.mgi.polymtl.ca> and
448 <https://coral.ise.lehigh.edu/data-sets/qaplib>.
450 :param name: the name string
451 :return: the instance
453 >>> insta = Instance.from_resource("chr25a")
454 >>> print(insta.n)
455 25
456 >>> print(insta.name)
457 chr25a
458 >>> print(insta.lower_bound)
459 3796
460 >>> print(insta.upper_bound)
461 50474
462 """
463 if not isinstance(name, str):
464 raise type_error(name, "name", str)
465 container: Final = Instance.from_resource
466 inst_attr: Final[str] = f"__inst_{name}"
467 if hasattr(container, inst_attr): # instance loaded?
468 return cast("Instance", getattr(container, inst_attr))
470 lb: int | None = _BOUNDS.get(name, None)
471 with open_resource_stream(f"{name}.dat") as stream:
472 inst: Final[Instance] = Instance.from_qaplib_stream(
473 stream, name=name, lower_bound=lb)
475 if inst.n <= 1000:
476 setattr(container, inst_attr, inst)
477 return inst