Розв’язування квадратичної задачі про призначення
Journal Title: Математичне моделювання - Year 2018, Vol 1, Issue 2
Abstract
THE SOLUTION OF THE QUADRATIC ASSIGNMENT PROBLEM Kosolap A.I., Dubovik D.A. Abstract The quadratic assignment problem is fairly well known and one of the most important and complex in combinatorial optimization. It occurs when solving various applied problems. This task is used in solving the problems of placement, loading multiprocessor systems, tracing printed circuit boards, in many problems of design and topological engineering. The classical linear assignment problem has an effective solution method, and replacing the linear objective function by a quadratic one considerably complicates the problem. To solve the quadratic assignment problem are used branch and boundary methods, genetic, evolutionary and other methods that use random search. Significant progress in solving this problem by these methods hasn’t been achieved. In the methods of branches and boundaries, a decision tree is constructed. Each tree requires a solution to the problem with additional linear constraints. Therefore, at each iteration of this method, the dimension of the problem increases. With increasing dimension of the problem, the number of tree branches increases exponentially. This allows on modern PC to solve such a problem by this method of only small dimension. At the same time, random search methods don’t guarantee obtaining an exact solution and allow finding it with a certain probability. All this stimulates the search for new methods for solving the quadratic assignment problem. In practice, QAP can be used for example for the following purpose. It is necessary to place n components of the printed circuit board in m positions of the installation space so that the total length of the electrical connections between the components would be minimal. This minimization is determined by the quadratic target function. The complexity of the solution of the problem is expressed not only in Boolean variables, but also in the fact that the quadratic objective function is not convex. The constraints in this case are part of the vertices of the hypercube, and the solution can be achieved at one of the vertices. It is necessary to fill the square matrix xij with zeros and ones, and in each row and in each column there must be only one unit. This matrix should minimize the quadratic target function. To bring the quadratic target function to a convex species, we need to use a quadratic regularization, which transforms the initial problems to a new form the maximization of the Euclidean norm of a vector on a convex set. We use an effective is primer-dual interior point method for the solution of the received problem. Generally, it is necessary to use also a dichotomy method. Currently, comparative numerical experiments are carried out that implement a straight-duplex internal point method for solving a transformed problem. The first results show that the considered method can be used to solve quadratic assignment problem a large dimension. References [1] Commander, C.W. A Survey of the Quadratic Assignment Problem, with Applications. The University of Florida, 2003, 18 p. [2] Cook W. Fifty-Plus Years of Combinatorial Integer Programming. Georgia Institute of Technology, 2009, 39 p. [3] Kenneth V.P. Differential Evolution. A Practical Approach to Global Optimization. Berlin, Heidelberg: Springer-Verlag, 2005, 542 p. [4] Lawler E.L., The quadratic assignment problem, Management Science 9, 1963, pp. 586–599. [5] Kaufmann L., Broeckx F. An algorithm for the quadratic assignment problem using Benders’ decomposition. European Journal of Operational Research, 1978, no.2, pp. 204–211. [6] Frieze A.M., Yadegar J. On the quadratic assignment problem, Discrete Applied Mathematics, 1983, no.5, pp. 89–98. [7] Adams W.P., Johnson T.A. Improved linear programming-based lower bounds for the quadratic assignment problem, in Quadratic Assignment and Related Problems, P. M. Pardalos and H. Wolkowicz, eds., DIMACS Series on Discrete Mathematics and Theoretical Computer Science, 1994, no. 16, pp. 43–75. [8] Burkard R.E. Locations with spatial interactions: the quadratic assignment problem, in Discrete Location Theory, P. B. Mirchandani and R. L. Francis, eds., Wiley, 1991, pp. 387–437. [9] Burkard R.E., Bonniger T.A heuristic for quadratic boolean programs with applications to quadratic assignment problems. European Journal of Operational Research, 1983, no.13, pp. 374–386. [10] Burkard R.E., Derigs U. Assignment and matching problems: Solution methods with Fortran programs. Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, Berlin, 1980, no. 184, 148 p. [11] Glover F., Improved linear integer programming formulations of nonlinear integer problems, Management Science, 1975, no.22, pp. 455–460. [12] Geoffrion A.M. Lagrangean relaxation and its uses in integer programming, Mathematical Programming Study, 1974, no.2, pp. 82–114. [13] Gilmore P.C. Optimal and suboptimal algorithms for the quadratic assignment problem, SIAM Journal on Applied Mathematics, 1962, no.10, pp. 305–313. [14] Gavett J. W., Plyter N. V. The optimal assignment of facilities to locations by branch and bound, Operations Research, 1966, no.14, pp. 210–232. [15] Land A.M. A problem of assignment with interrelated costs, Operations Research Quarterly, 1963, no.14, pp. 185–198. [16] Nugent C.E., Vollmann T.E., Ruml J. An experimental comparison of techniques for the assignment of facilities to locations, Journal of Operations Research, 1969, no.16, pp. 150–173. [17] Burkard R.E. Assignment problems. University of Bolona, 2009, 392 p. [18] Dorigo M., Maniezzo V. and Colorni A. Positive feedback as a search strategy. Technical Report 91-016, Dipartimento di Elettronica e Informazione, Milano: Politecnico di Milano, 1991, 20 p. [19] Dorigo M., Maniezzo V. and Colorni A. The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics–Part B 26, 1996, pp. 29–41. [20] Rutkovskaya, D. Neural networks, genetic algorithms and fuzzy systems: Per. from polish I.D. Rudinsky / D. Rutkovskaya, M. Pilinsky, L. Rutkovsky. – M.: Hotline - Telecom, 2006, 452 p. [21] Morov V.A. Primenenie geneticheskogo algoritma do zadach optimizatcii. Realizatciya geneticheskogo algoritma dlya problemu komivoyagera. [Application of the genetic algorithm to optimization problems. Realization of the genetic algorithm for the traveling salesman problem.] Vestnik Amurskogo Gosudarstvennogo Universiteta, 2012. – Vol. 57: Estestvennie i econ. nayki. pp. 18–22. (in Russian). [22] Taillard, E. Robust taboo search for the quadratic assignment problem. Parallel Computing, 1991, no.17, pp. 443–455. [23] Battiti, R. and Tecchiolli, G. The reactive tabu search. ORSA Journal on Computing, 1994, no.6(2), pp. 126–140. [24] Drezner, Z. The extended concentric tabu for the quadratic assignment problem. To appear in European Journal of Operational Research, 2005, no.160, pp. 416–422. [25] Minu M. Matematicheskoe programmirovanie [Mathematical programming]. М.: Nauka, 1990, 487 p. (in Russian). [26] Kosolap A.I. Globalnaya optimizatciya. Metod tochnoy kvadratichnoy regulyarizatcii. [Global optimization. Method of exact quadratic regularization]. Dnepropetrovsk: PGАСА, 2015, 164 p. (in Russian). [27] Nocedal J., Wright S.J. Numerical optimization. Springer, 2006, 685 p.
Authors and Affiliations
А. І. Косолап, Д. О. Дубовик
Keywords
Related Articles
- EP ID EP444596
- DOI 10.31319/2519-8106.2(39)2018.154222
- Views 83
- Downloads 0
Математичне моделювання теплового стану будівельних конструкцій з використанням матеріалів з фазовими переходами
MATHEMATICAL DESIGN OF THE THERMAL STATE OF BUILDING CONSTRUCTIONS WITH THE USE OF MATERIALS WITH PHASE TRANSITIONS Karimov I.K., Dolgopolov I.S., Jacenko A.L.,Tuchin V.T. Abstract The authors focus on the problem the f...
Оптимизация технологии получения многокомпонентных покрытий на основе титана в условиях СВС
OPTIMIZATION OF TECHNOLOGY OF RECEIPT OF MULTICOMPONENT COVERINGS ON BASIS OF TITAN IN THE CONDITIONS OF SHS. Sereda B.P., Palekhova I.V., Kruglyak I.V. Abstract One of effective methods of chemical - thermal treatment...
Система термодинамических соотношений для описания процессов взаимодействия расплавов в горне доменной печи на основе параметров межатомного взаимодействия
The system of thermodynamic parities in the form of criteria and models for an estimation of results of interaction melts in a forge of a blast furnace on the basis of parametres of internuclear interaction for the purpo...
МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТРАСИ ГІДРОТРАНСПОРТУ ЗА ДОПОМОГОЮ ПАРАБОЛІЧНИХ СПЛАЙНІВ
MATHEMATICAL MODELLING A ROUTE OF HYDROTRANSPORT BY MEANS OF PARABOLIC SPLINES Hasylo Yu.A., Levchuk K.O., Romaniuk R.Ja. Abstract One of dustiness sources on work stations is open transportation of loose materials (san...
Решение задачи конвективно-радиационного нагрева (охлаждения) тел простой геометрической формы методом конечных разностей
SOLUTION OF THE PROBLEM FOR CONVECTIVE RADIATION HEATING (COOLING) OF BODIES WITH SIMPLE GEOMETRIC FORM BY THE METHOD OF FINITE DIFFERENCES Gorbunov A.D., Ukleina S.V. Abstract The heating or cooling of bodies under t...