This article is cited in 14 papers

Optimization methods in management

Network programming techniques

V. N. Burkov, I. V. Burkova, M. V. Popok, T. I. Ovehinnikova

Institute of Control Sciences, Russian Academy of Sciences

Abstract: A new approach to discrete optimization tasks named network planning techniques is offered. The method is based on the opportunity to present multivariable functions as a superposition of several simpler functions. The superposition structure is presented as a network whose inputs correspond to arguments, while the outputs correspond to the function. The paper shows that if the network has a tree structure, then the solution is reduced to sequential solving of simpler problems. In the general case, it is proposed to transform the network into the tree by separating network vertexes. It is proved that the problem solution for the transformed structure delivers the lower bound of the original problem's objective function (in case of a minimization task). The technique is illustrated with the example of the known stones problem.

UDC: 65.012