A study on efficient algorithms for nonlinear nonconvex network programming problems

点击翻译按钮获取中文摘要

In this research, we studied certain classes of nonconvex cost network flow problems and proposed efficient algorithms for generating globally optimal solutions. A few of the results are listed below :1 In the usual two-terminal network, we proposed a method for minimizing the total transportation cost and for simultaneously maximizing the total flow. To accomplish it, we optimized the product of these two values and showed that a successive shortest path algorithm yields a globally optimal solution in pseudo-polynomial time and an epsilon-optimal solution in polynomial time.2 We developed pseudo-polynomial algorithm to solve a production-transportation problem equivalent to the capacitated minimum concave cost flow problems with at most three nonlinear variables. The algorithm consists of two phases : the first phase generates a feasible solution ; starting from it, the second phase searches for a globally optimal solution in the same way as solving a minimum linear-cost flow problem3 We extended the idea used to solve the problem in 2 and solved a maximum flow problem with an additional reverse convex constraint in pseudo-polynomial time. We first applied a binary search procedure to generate a candidate for an optimal solution, and then checked its globally optimality using the algorithm similar to the one in 2.All the above mentioned algorithms were designed by exploiting low-rank (quasi) concavity possessed by the problems, and were shown to be efficient in both practical and theoretical senses. We generalized this special problem structure and obtained the following result :4 We showed that a multiple convex objective program can be reduced to a single nonconvex objective program, and developed an outer approximation algorithm for generating a globally optimal solution. Computational experiments indicated that the algorithm is practically efficient when the number of objectives is less than five.