Conditions for the effective solvability of the quadratic choice problem. Part 1

V. M. Demidenko

Journal of the Belarusian State University. Mathematics and Informatics, Tome 1 (2024), pp. 45-58.

Résumé

A class of four-index real matrices is described for which the effective solvability of the quadratic choice problem is guaranteed. This means achieving the extreme values of its functional on one of the permutations of a special kind, which are given in the classical theorem of Hardy, Littlewood and Polya on the permutation of three systems. The introduced conditions generalise all the previously proposed conditions imposed on the kind of matrices that guarantee strict solvability of the problems of minimising the bilinear form on the Cartesian product of the symmetric group (conditions of the theorem on the permutation of three systems), the quadratic form of the symmetric group, and also generalise the similar results obtained for the quadratic assignment problem.

Détail

Keywords: Combinatorial optimisation; quadratic assignment problem; substation optimisation; strict solvability of problems

Bibliographie

[1] G. Kh. Khardi, D. I. Litlvud, G. Polia, Neravenstva, Gosudarstvennoe izdatelstvo inostrannoi literatury, Moskva, 1948, 456 pp.

[2] B. B. Timofeev, V. A. Litvinov, “K voprosu ob organizatsii razmescheniya massivov informatsii v pamyati na magnitnykh lentakh”, Kibernetika, 4 (1969), 56–61

[3] V. R. Pratt, “An NlogN algorithm to distribute N records optimally in a sequential access file”, Complexity of computer computations, Proceedings of a symposium on the complexity of computer computations, held March 20–22, 1972, at the IBM Thomas J Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department, Plenum Press, New York, 1972, 111–118 | DOI

[4] E. L. Lawler, “The quadratic assignment problem: a brief review”, Combinatorial programming. methods and applications, Proceedings of the NATO advanced study institute held at the Palais des Congres (Versailles, France, 2–13 September, 1974), NATO Advanced Study Institutes Series, 19, D Reidel Publishing Company, Dordrecht, 1975, 351–360 | DOI

[5] R. G. Vickson, Xinjian. Lu, “Optimal product and server locations in one-dimensional storage racks”, European Journal of Operational Research, 105:1 (1998), 18–28 | DOI

[6] G. J. Woeginger, “Computational problems without computation”, Nieuw Archief voor Wiskunde. Vijfde Serie, 4:2 (2003), 140–147

[7] V. M. Demidenko, G. Finke, V. S. Gordon, “Well solvable cases of the quadratic assignment problem with monotone and bimonotone matrices”, Journal of Mathematical Modelling and Algorithms, 5:2 (2006), 167–187 | DOI

[8] V. M. Demidenko, “Quadratic assignment problem with additively monotone matrices and incomplete anti-Monge matrices: conditions for effective solvability”, Discrete Mathematics and Applications, 17:2 (2007), 105–133 | DOI

[9] V. M. Demidenko, A. Dolgii, “Effektivno razreshimye sluchai kvadratichnoi zadachi o naznacheniyakh s obobschenno monotonnymi i nepolnymi matritsami anti-Monzha”, Kibernetika i sistemnyi analiz, 1 (2007), 135–151

[10] R. E. Burkard, E. Cela, G. Rote, G. J. Woeginger, “The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: easy and hard cases”, Mathematical Programming, 82 (1998), 125–158 | DOI

[11] E. Cela, “Assignment problems”, Handbook of applied optimization, Oxford University Press, Oxford, 2002, 661–678

[12] R. Burkard, M. Dell’Amico, S. Martello, Assignment problems: revised reprint, Society for Industrial and Applied Mathematics, Philadelphia, 2009, XXII+393 pp. | DOI