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

  • Vitaliy M. Demidenko Belarusian State Economic University, 26 Partyzanski Avenue, Minsk 220070, Belarus

Abstract

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 Pólya 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.

Author Biography

Vitaliy M. Demidenko, Belarusian State Economic University, 26 Partyzanski Avenue, Minsk 220070, Belarus

doctor of science (physics and mathematics), docent; professor at the department of higher mathematics, faculty of digital economy

 

References

  1. Hardy GH, Littlewood JE, Pólya G. Inequalities. Cambridge: Cambridge University Press; 1934. XII, 314 p. Russian edition: Hardy GH, Littlewood JE, Pólya G. Neravenstva. Levin VI, translator. Moscow: Gosudarstvennoe izdatel’stvo inostrannoi literatury; 1948. 456 p.
  2. Timofeev BB, Litvinov VA. [On the problem of organizing the disposition of information files on magnetic tapes]. Kibernetika. 1969;4:56–61. Russian.
  3. Pratt VR. An Nlog N algorithm to distribute N records optimally in a sequential access file. In: Miller RE, Thatcher JW, editors. 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. New York: Plenum Press; 1972. p. 111–118 (The IBM research symposia series). DOI: 10.1007/978-1-4684-2001-2_11.
  4. Lawler EL. The quadratic assignment problem: a brief review. In: Roy B, editor. Combinatorial programming: methods and applications. Proceedings of the NATO advanced study institute held at the Palais des Congrès, Versailles, France, 2–13 September, 1974. Dordrecht: D. Reidel Publishing Company; 1975. p. 351–360 (NATO advanced study institutes series. Series C, Mathematical and physical sciences; volume 19). DOI: 10.1007/978-94-011-7557-9_20.
  5. Vickson RG, Lu Xinjian. Optimal product and server locations in one-dimensional storage racks. European Journal of Operational Research. 1998;105(1):18–28. DOI: 10.1016/S0377-2217(97)00023-4.
  6. Woeginger GJ. Computational problems without computation. Nieuw Archief voor Wiskunde. Vijfde Serie. 2003;4(2):140–147.
  7. Demidenko VM, Finke G, Gordon VS. Well solvable cases of the quadratic assignment problem with monotone and bimonotone matrices. Journal of Mathematical Modelling and Algorithms. 2006;5(2):167–187. DOI: 10.1007/s10852-005-9013-2.
  8. Demidenko VM. Quadratic assignment problem with additively monotone matrices and incomplete anti-Monge matrices: conditions for effective solvability. Discrete Mathematics and Applications. 2007;17(2):105–133. DOI: 10.1515/dma.2007.011.
  9. Demidenko VM, Dolgiy A. [Efficiently solvable cases of a quadratic assignment problem with generalized monotonic and incomplete anti-Monge matrices]. Kibernetika i sistemnyi analiz. 2007;1:135–151. Russian.
  10. Burkard RE, Çela E, Rote G, Woeginger GJ. The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: easy and hard cases. Mathematical Programming. 1998;82:125–158. DOI: 10.1007/BF01585868.
  11. Çela E. Assignment problems. In: Pardalos PM, Resende MGC, editors. Handbook of applied optimization. Oxford: Oxford University Press; 2002. p. 661–678.
  12. Burkard R, Dell’Amico M, Martello S. Assignment problems: revised reprint. Philadelphia: Society for Industrial and Applied Mathematics; 2009. XXII, 393 p. (Other titles in applied mathematics). DOI: 10.1137/1.9781611972238.
Published
2024-04-15
Keywords: combinatorial optimisation, quadratic assignment problem, substation optimisation, strict solvability of problems
Supporting Agencies This work was carried out within the framework of the state programme of scientific research «Convergence-2025» (subprogramme «Mathematical models and methods», assignment 1.5.01).
How to Cite
Demidenko, V. M. (2024). Conditions for the effective solvability of the quadratic choice problem. Part 1. Journal of the Belarusian State University. Mathematics and Informatics, 1, 45-58. Retrieved from https://journals.bsu.by/index.php/mathematics/article/view/6078
Issue
No 1 (2024): Journal of the Belarusian State University. Mathematics and Informatics
Section
Discrete Mathematics and Mathematical Cybernetics

Copyright (c) 2024 Journal of the Belarusian State University. Mathematics and Informatics

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

The authors who are published in this journal agree to the following:

  1. The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
  3. The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)