Oleksiichuk Y. Combinatorial optimum flow problem in the network and methods of its solutions

The combinatorial optimum flow problem in transport network was first formulated. NP-hard of combinatorial maximum flow problems and combinatorial minimum cost flow problem is proved. Mathematical model of the considered problem is the problem of Euclidean combinatorial optimization. The direct combinatorial cut-off method is proposed and justified for solving of this problem. The greedy method is proposed for the approximate solution of combinatorial maximum flow problem. The assessment of complexity of this method is made. Branch and bound method and the simulated annealing method are applied to solve combinatorial maximum flow problem. Numerical experiments are executed for all offered methods.