Methods of reduction of insolvable problems of combinatorial optimization to solvable problems

Abstract

For the selection of subclasses of solvable problems from the classes of unsolvable ones the necessity to determine their complexity is shown in the article. On this basis the classification of solvable problems, which are allocated by the selected similarity degree and the way of modeling the objective function, according to the structure of the input data and the structure of its argument is carried out. On the example of some classes of unsolvable problems of combinatorial optimization methods their attempts to make them solvable are described.