Theory and practice of NP-hard structure synthesis problem solution by means of software tools

Аuthors

Anisimov A. V.^*, Romanova T. N.^**

Bauman Moscow State Technical University, MSTU, 5, bldg. 1, 2-nd Baumanskaya str., Moscow, 105005, Russia

*e-mail: alan_mephi@mail.ru
**e-mail: rtn@bmstu.ru

Abstract

An example of NP-hard structure synthesis problem solution is described. The problem is typical for enterprise automation processes. Optimization statement of the problem is formulated. Appropriate software implementation is presented in regard to such problem class for three approximate solution search methods as well as for one accurate development search method. Data structures used for the method implementation are described. Analytical and numerical estimations are compared for precision and complexity oj involved optimization techniques.

Keywords:

structural synthesis; NP-hardness; approximate method; local improvement method; exhaustive search; Rado-Edmonds greedy algorithm; combinatorially optimization problem; asymptotic computational complexity estimation