Graphical method to solve combinatorial optimization problems

Abstract

Proposed was a graphical method to solve decomposable problems of combinatorial optimization with the of use the Bellman optimality principle. In distinction to the dynamic programming algorithms based on the same principle, the graphical algorithm considers all possible system states by groups and not separately. This becomes possible if one takes into account the analytical form of the objective function, that is, handles the function “graph” and transforms it analytically at each stage. The graphical method enables one to reduce running time of solution of some problems and construct efficient approximation schemes. The results of numerical experiments corroborate efficiency of the of the graphical method.