moptipyapps.qap package¶
The Quadratic Assignment Problem (QAP).
The quadratic assignment problem represents assignments of facilities to locations. Between each pair of facilities, there is a flow of goods. Between each two locations, there is a distance. The goal is to assign facilities to locations such that the overall sum of the products of distance and flow gets minimized. Each instance therefore presents a matrix with distances and a matrix with flows flows. The objective is then to minimize said product sum.
Eliane Maria Loiola, Nair Maria Maia de Abreu, Paulo Oswaldo Boaventura-Netto, Peter Hahn, and Tania Querido. A survey for the Quadratic Assignment Problem. European Journal of Operational Research. 176(2):657-690. January 2007. https://doi.org/10.1016/j.ejor.2005.09.032.
Rainer E. Burkard, Eranda Çela, Panos M. Pardalos, and Leonidas S. Pitsoulis. The Quadratic Assignment Problem. In Ding-Zhu Du, Panos M. Pardalos, eds., Handbook of Combinatorial Optimization, pages 1713-1809, 1998, Springer New York, NY, USA. https://doi.org/10.1007/978-1-4613-0303-9_27.
This is code is part of the research work of Mr. Jiayang Chen (陈嘉阳), a Master’s student at the Institute of Applied Optimization (应用优化研究所, http://iao.hfuu.edu.cn) of the School of Artificial Intelligence and Big Data (人工智能与大数据学院) at Hefei University (合肥大学) in Hefei, Anhui, China (中国安徽省合肥市) under the supervision of Prof. Dr. Thomas Weise (汤卫思教授). An instance of the Quadratic Assignment Problem. In this module, we provide the class Eliane Maria Loiola, Nair Maria Maia de Abreu, Paulo Oswaldo Boaventura-Netto, Peter Hahn, and Tania Querido. A survey for the Quadratic Assignment Problem. European Journal of Operational Research. 176(2):657-690. January 2007. https://doi.org/10.1016/j.ejor.2005.09.032. Rainer E. Burkard, Eranda Çela, Panos M. Pardalos, and Leonidas S. Pitsoulis. The Quadratic Assignment Problem. In Ding-Zhu Du, Panos M. Pardalos, eds., Handbook of Combinatorial Optimization, pages 1713-1809, 1998, Springer New York, NY, USA. https://doi.org/10.1007/978-1-4613-0303-9_27. We additionally provide access to several standard QAP benchmark instances via the QAPLIB - A Quadratic Assignment Problem Library. The Websites <https://qaplib.mgi.polymtl.ca/> (updated 2018) and <https://coral.ise.lehigh.edu/data-sets/qaplib/> (updated 2011), including the benchmark instances, on visited 2023-10-21. Rainer E. Burkard, Stefan E. Karisch, and Franz Rendl. QAPLIB - A Quadratic Assignment Problem Library. Journal of Global Optimization. 10:391-403, 1997. https://doi.org/10.1023/A:1008293323270. Bases: An instance of the Quadratic Assignment Problem. Get the best-known solution, if known, the optimum, or lower bound. A tuple with a string identifying the source of the value and a value corresponding to the best-known solution: (“OPT”, xxx): the problem instance has been solved to optimality and xxx is the objective value of the optimum (“LB”, xxx): neither the optimum nor a best-known solution are available for this instance, so we return the lower bound The data is based on https://qaplib.mgi.polymtl.ca/, visited on 2024-05-09. The following sources are included: “FF1993GHFTQAP”: Charles Fleurent and Jacques A. Ferland. Genetic Hybrids for the Quadratic Assignment Problem. In Panos M. Pardalos and Henry Wolkowicz, eds, Quadratic Assignment and Related Problems, Proceedings of a DIMACS Workshop, May 20-21, 1993. pages 173-187. Providence, RI, USA: American Mathematical Society. “M2003AMSAAFTQAP”: Alfonsas Misevičius, A Modified Simulated Annealing Algorithm for the Quadratic Assignment Problem. Informatica 14(4):497-514. January 2003. https://doi.org/10.15388/Informatica.2003.037. “M2005ATSAFTQAP”: Alfonsas Misevičius. A Tabu Search Algorithm for the Quadratic Assignment Problem. Computational Optimization and Applications 30(1):95-111. 2005. https://doi.org/10.1007/s10589-005-4562-x. “M2008AIOTITSAFTQAP”: Alfonsas Misevičius. An Implementation of the Iterated Tabu Search Algorithm for the Quadratic Assignment Problem. Working Paper. 2008. Kaunas, Lithuania: Kaunas University of Technology. “S1997MMASFQAP”: Thomas Stützle. MAX-MIN Ant System for Quadratic Assignment Problems. Research Report AIDA-97-04. 1997. Darmstadt, Germany: Department of Computer Schience, Darmstadt University of Technology. “T1991RTSFTQAP”: Éric Taillard. Robust Taboo Search for the Quadratic Assignment Problem. Parallel Computing. 17(4-5):443-455. July 1991. “T1995COISFTQAP”: Éric D. Taillard. Comparison of Iterative Searches for the Quadratic Assignment Problem. Location Science 3(2):87-105. 1995. “TB1994AISAAFTQAP”: Ulrich Wilhelm Thonemann and Andreas Bölte. An Improved Simulated Annealing Algorithm for the Quadratic Assignment Problem. Working Paper 1994. Paderborn, Germany: School of Business, Department of Production and Operations Research, University of Paderborn. “TG1997AMFTQAP”: Éric D. Taillard and Luca-Maria Gambardella. Adaptive Memories for the Quadratic Assignment Problem. 1997. Technical Report IDSIA-87-97. Lugano, Switzerland: IDSIA. Load an instance from a QAPLib-formatted stream. the instance Load a QAP-Lib instance from a resource. The original data can be found at <https://qaplib.mgi.polymtl.ca> and <https://coral.ise.lehigh.edu/data-sets/qaplib>. Get a tuple of all the QAP-lib instances available as resource. The original data can be found at <https://qaplib.mgi.polymtl.ca> and <https://coral.ise.lehigh.edu/data-sets/qaplib>. Log all parameters of this instance as key-value pairs. logger ( Compute the trivial bounds for the QAP objective. A trivial upper bound is to multiply the largest flow with the largest distance, the second-largest flow with the second-largest distance, the third-largest flow with the third-largest distance, and so on. A trivial lower bound is to multiply the largest flow with the shortest distance, the second-largest flow with the second-shortest distance, the third-largest flow with the third-shortest distance, and so on. the lower and upper bounds The objective function for the Quadratic Assignment Problem. The candidate solutions to the QAP are Eliane Maria Loiola, Nair Maria Maia de Abreu, Paulo Oswaldo Boaventura-Netto, Peter Hahn, and Tania Querido. A survey for the Quadratic Assignment Problem. European Journal of Operational Research. 176(2):657-690. January 2007. https://doi.org/10.1016/j.ejor.2005.09.032. Rainer E. Burkard, Eranda Çela, Panos M. Pardalos, and Leonidas S. Pitsoulis. The Quadratic Assignment Problem. In Ding-Zhu Du, Panos M. Pardalos, eds., Handbook of Combinatorial Optimization, pages 1713-1809, 1998, Springer New York, NY, USA. https://doi.org/10.1007/978-1-4613-0303-9_27. Bases: An objective function for the quadratic assignment problem. Compute the quadratic assignment problem objective value. x – the permutation of elements the sum of flows times distances Log all parameters of this component as key-value pairs. logger (Subpackages¶
Submodules¶
moptipyapps.qap.instance module¶
Instance that encapsulates all information of a problem instance of the Quadratic Assignment Problem (QAP). The QAP aims to locate facilities at locations such that the flow-distance product sum combining a flows of goods between instances with the distances of the locations becomes minimal. Each instance therefore presents a matrix with distances and a matrix with flows flows.from_resource() and list_resources() methods. The standard benchmark instances stem from QAPLIB, a library of QAP instances, which can be found at <https://qaplib.mgi.polymtl.ca> and <https://coral.ise.lehigh.edu/data-sets/qaplib>.Component>>> ins = Instance.from_qaplib_stream([
... "4", "",
... "1 2 3 4 5 6 7 8 9 10 11 12 13",
... " 14 15 16 ", "",
... "17 18 19 20 21 22 23 24 25 26 27",
... " 28 29 30 31 32"])
>>> ins.distances
array([[17, 18, 19, 20],
[21, 22, 23, 24],
[25, 26, 27, 28],
[29, 30, 31, 32]], dtype=int16)
>>> ins.flows
array([[ 1, 2, 3, 4],
[ 5, 6, 7, 8],
[ 9, 10, 11, 12],
[13, 14, 15, 16]], dtype=int16)
>>> ins.lower_bound
2992
>>> ins.upper_bound
3672
>>> ins.name
'qap4_2992_3672'
>>> insta = Instance.from_resource("chr25a")
>>> print(insta.n)
25
>>> print(insta.name)
chr25a
>>> print(insta.lower_bound)
3796
>>> print(insta.upper_bound)
50474
>>> len(Instance.list_resources())
134
KeyValueLogSection) – the logger for the parameters>>> dst = np.array([[0, 1, 2], [3, 0, 4], [5, 6, 0]])
>>> flws = np.array([[0, 95, 86], [23, 0, 55], [24, 43, 0]])
>>> 0*95 + 0*86 + 0*55 + 1*43 + 2*24 + 3*23 + 4*0 + 5*0 + 6*0
160
>>> 6*95 + 5*86 + 4*55 + 3*43 + 2*24 + 1*23 + 0*0 + 0*0 + 0*0
1420
>>> trivial_bounds(dst, flws)
(160, 1420)
moptipyapps.qap.objective module¶
permutations p of length n of the numbers 0, 1, …, n-1. An instance of the Quadratic Assignment Problem (QAP) presents a n*n matrix D with distances and a n*n matrix F with flows flows. The objective value, subject to minimization, is then the sum( F[i,j] * D[p[i], p[j]] for i, j in 0..n-1 ), i.e., the sum of the products of the flows between facilities and the distances of their assigned locations.>>> inst = Instance.from_resource("bur26a")
>>> QAPObjective(inst).evaluate(np.array([
... 25, 14, 10, 6, 3, 11, 12, 1, 5, 17, 0, 4, 8, 20,
... 7, 13, 2, 19, 18, 24, 16, 9, 15, 23, 22, 21]))
5426670
>>> inst = Instance.from_resource("nug12")
>>> QAPObjective(inst).evaluate(np.array([
... 11, 6, 8, 2, 3, 7, 10, 0, 4, 5, 9, 1]))
578
>>> inst = Instance.from_resource("tai12a")
>>> QAPObjective(inst).evaluate(np.array([
... 7, 0, 5, 1, 10, 9, 2, 4, 8, 6, 11, 3]))
224416
ObjectiveKeyValueLogSection) – the logger for the parameters