A study on efficient algorithms for nonlinear nonconvex network programming problems

在本研究中，我们研究了某些类别的非凸费用网络流问题，并提出了有效的算法产生全局最优解。主要结果如下：1在通常的两端点网络中，我们提出了一种使总运输费用最小化，同时使总流量最大化的方法。为了实现这一目标，我们优化了这两个值的乘积，并证明了连续最短路径算法在伪多项式时间内产生全局最优解，在多项式时间内产生ε最优解。2我们开发了伪多项式算法来解决一个生产运输问题，该问题等价于至多三个非线性变量的能力约束最小凹成本流问题。该算法包括两个阶段：第一阶段产生一个可行的解决方案，从它开始，第二阶段寻找一个全局最优的解决方案，以同样的方式解决一个最小的线性费用流问题3我们扩展的思想用于解决问题2，并解决了一个最大流问题与一个额外的反向凸约束在伪多项式时间。我们首先采用二分搜索的方法产生一个候选最优解，然后用类似于[2]的算法检验其全局最优性。上述算法都是利用问题的低秩（拟）秩设计的，在理论和实践上都是有效的。我们推广了这一特殊的问题结构，得到了如下结果：4证明了多凸目标规划可以化为单非凸目标规划，并给出了一个产生全局最优解的外逼近算法。计算实验表明，当目标数小于5时，该算法是有效的。

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.