Abstract
We are concerned with the exact solution of a graph optimization problem known as minimum linear arrangement (MinLA). Define the length of each edge of a graph with respect to a linear ordering of the graph vertices. Then, the MinLA problem asks for a vertex ordering that minimizes the sum of edge lengths. MinLA has several practical applications and is NP-Hard. We present a mixed 0-1 linear programming formulation of the problem, which led to fast optimal solutions for dense graphs of sizes up to n = 23.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Adams W.P., Sherali H.D.: Tight linearization and an algorithm for zero-one quadratic programming problems. Manage. Sci. 32, 1274–1290 (1986). doi:10.1287/mnsc.32.10.1274
Adams W.P., Guignard M., Hahn P.M., Hightower W.L.: A level-2 reformulation linearization technique bound for the quadratic assignment problem. Eur. J. Oper. Res. 180, 983–996 (2007). doi:10.1016/j.ejor.2006.03.051
Adolphson D., Hu T.C.: Optimal linear ordering. SIAM J. Appl. Math. 25(3), 403–423 (1973). doi:10.1137/0125042
Amaral A.R.S.: On the exact solution of a facility layout problem. Eur. J. Oper. Res. 173, 508–518 (2006). doi:10.1016/j.ejor.2004.12.021
Burkard R.E., Karisch S.E.: Rendl., F.: QAPLIB, A quadratic assignment problem library. J. Glob. Optim. 10, 391–403 (1997). doi:10.1023/A:1008293323270
Chung, F.R.K.: Labelings of graphs. In: Selected Topics in Graph Theory, vol. 3, pp. 151–168. Academic Press, San Diego (1988)
Díaz J., Petit J., Serna M.: A survey on graph layout problems. ACM Comput. Surv. 34(3), 313–356 (2002). doi:10.1145/568522.568523
Garey M.R., Johnson D.S.: Computers and Intractability: a Guide to the Theory of NP-Completeness. W.H. Freeman and Co, San Francisco (1979)
Goldberg M.K., Klipker I.A.: An algorithm for minimal numeration of tree vertices. Sakharth. SSR Mecn. Akad. Moambe 81(3), 553–556 (1976) [In Russian (English abstract at MathSciNet)]
Harper L.H.: Optimal assignments of numbers to vertices. J. SIAM 12(1), 131–135 (1964)
Horton, S.B.: The optimal linear arrangement problem: algorithms and approximation. Ph.D. Thesis, Georgia Institute of Technology (1997)
ILOG, Inc.: CPLEX 10.1 User Manual. Gentilly Cedex, France (2006)
Juvan M., Mohar B.: Optimal linear labelings and eigenvalues of graphs. Discrete Appl. Math. 36(2), 153–168 (1992). doi:10.1016/0166-218X(92)90229-4
Koren, Y., Harel, D.: A multi-scale algorithm for the linear arrangement problem. In: Kucera, L. (ed.) Revised Papers From the 28th international Workshop on Graph-theoretic Concepts in Computer Science (13–15 June 2002). Lecture Notes in Computer Science, vol. 2573, pp. 296–309. Springer, London (2002)
Lai Y., Williams K.: A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs. J. Graph Theory 31, 75–94 (1999). doi:10.1002/(SICI)1097-0118(199906)31:2<75::AID-JGT1>3.0.CO;2-S
Mitchison G., Durbin R.: Optimal numberings of an n × n array. SIAM J. Algebra. Discr. Methods. 7(4), 571–582 (1986). doi:10.1137/0607063
Muradyan D.O., Piliposjan T.E.: Minimal numberings of vertices of a rectangular lattice. Akad. Nauk. Armjan. SRR 1 70, 21–27 (1980) [In Russian (English abstract at MathSciNet)]
Nugent C.E., Vollmann T.E., Ruml J.: An experimental comparison of techniques for the assignment of facilities to locations. Oper. Res. 16, 150–173 (1968). doi:10.1287/opre.16.1.150
Petit, J.: Experiments on the minimum linear arrangement problem. ACM J. Exp. Algorithmics 8, article 2.3 (2003)
Poranen T.: A genetic hillclimbing algorithm for the optimal linear arrangement problem. Fund. Inf. 68, 333–356 (2005)
Ramakrishnan K.G., Resende M.C.G., Ramachandran B., Pekny J.F.: Tight QAP Bounds via Linear Programming. In: Pardalos, P.M., Migdalas, A., Burkard, R. (eds) Combinatorial and Global Optimization, pp. 297–303. World Scientific Publishing, Singapore (2002)
Resende M.G.C., Ramakrishnan K.G., Drezner Z.: Computing lower bounds for the quadratic assignment problem with an interior point algorithm for linear programming. Oper. Res. 43, 781–791 (1995). doi:10.1287/opre.43.5.781
Rodriguez-Tello E., Hao J.-K., Torres-Jimenez J.: Memetic algorithms for the MinLA problem. Lect. Notes Comput. Sci. 3871, 73–84 (2006). doi:10.1007/11740698_7
Rodriguez-Tello E., Hao J.-K., Torres-Jimenez J.: An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem. Comput. Oper. Res. 35(10), 3331–3346 (2008). doi:10.1016/j.cor.2007.03.001
Safro I., Ron D., Brandt A.: Graph minimum linear arrangement by multilevel weighted edge contractions. J. Algorithms 60(1), 24–41 (2006). doi:10.1016/j.jalgor.2004.10.004
Shahrokhi F., Sýkora O., Székely L.A., Vrto I.: On bipartite drawings and the linear arrangement problem. SIAM J. Comput. 30(6), 1773–1789 (2001). doi:10.1137/S0097539797331671
Shiloach Y.: A minimum linear arrangement algorithm for undirected trees. SIAM J. Comput. 8(1), 15–32 (1979). doi:10.1137/0208002
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Amaral, A.R.S. A mixed 0-1 linear programming formulation for the exact solution of the minimum linear arrangement problem. Optim Lett 3, 513–520 (2009). https://doi.org/10.1007/s11590-009-0130-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-009-0130-0