Metaheuristic Downhill Simplex Method in Combinatorial Optimization

Hulianytskyi L.F. and Sergienko I.V.

Cybernetics and Systems Analysis. – 2007. – 43, No. 6 (November–December). – P. 822–829.


The concept of combinatorial objects is formalized. It allows strict definition of a combinatorial optimization problem (COP). An efficient metaheuristic method to solve COPs (H-method) is considered. It includes stochastic local search algorithms as a built-in procedure. A parallel implementation of the H-method is set forth and analyzed. The results from a numerical experiment and solution of some well-known COPs on personal computers and on the SKIT cluster supercomputer are presented.

Ключові слова: combinatorial optimization problem, metaheuristic algorithms, stochastic local search, parallel computations, cluster, quadratic assignment problem.