SOFTWARE PACKAGE FOR SOLVING EUCLIDEAN COMBINATORIAL OPTIMIZATION PROBLEMS WITH ACCURATE AND APPROXIMATE METHODS

Abstract

Combinatorial optimization problems are becoming more common in practice. This is due to the fact that a large number of applied problems are described by the models in which the solution is defined on combinatorial sets. Solving such problems requires the development of new methods or modification of existing methods, writing algorithms and their software implementation. The aim of the work is to create a software product for solving Euclidean combinatorial optimization problems with accurate and approximate methods. It is important to take into account the structure of combinatorial configurations, in particular, using graph theory. In addition to developing new mathematical approaches, it is essential to consider the current state of computer technology – the presence of powerful multiprocessor systems. Methodology. The high-level programming language Object Pascal of the Delphi programming environment was chosen for the development of the program. Scientific novelty. The paper describes the developed software package that implements methods for solving combinatorial optimization problems by different methods. The presented software product allows to solve linear programming problems by the method of combinatorial clipping on the basis of Carmarcar’s algorithm for conditional linear problems of combinatorial optimization on permutations. Unlike the known methods of combinatorial clipping for problems on vertically located sets, here the auxiliary problem of linear programming is solved not by a certain kind of simplex method, but by the polynomial Carmarcar algorithm. The developed software product also implements the second method of combinatorial clipping in conditional linear problems on vertically located sets with the exception of degeneracy in auxiliary linear programming problems. We also found a solution to the problem of combinatorial optimization by a modified method with the ability to add the necessary constraints and discard unnecessary ones. This approach has significantly increased the dimensionality of the tasks that can be solved. Conclusions. Due to the software package, it has become possible to solve combinatorial optimization problems using the representation of combinatorial polygon in the form of a graph of significant dimensions. The created software product allowed to conduct numerous experiments with all the above methods to confirm their practical effectiveness and correctness.