A study on efficient algorithms for multiple objective optimization prob-lems

在这项研究中。我们将多目标优化问题转化为单目标非凸优化问题，并提出了生成全局最优解的有效算法。我们研究了一个限制两个目标的乘积小于或等于给定常数的问题。我们开发了一种在有限时间内生成全局最优解的算法。在工作站上的计算结果表明，只要包含乘积的约束数小于5个，该算法就具有一定的实用性针对0-1背包约束下的多目标优化问题，提出了一种分支定界算法。我们将拉格朗日弛豫引入到边界过程中；但是，边界所花费的时间在问题规模中只是一个低阶多项式。该算法成功地在20秒内解决了20个目标和超过120个变量的问题研究了具有0-1背包约束的多目标优化问题与具有凹生产成本的生产运输问题之间的关系。然后，我们将前者的算法推广到后者的网络问题。与现有算法相比，该算法的计算时间缩短了几百倍研究了一个双目标最短路径问题，给出了两个强多项式算法。一种情况是决策者的效用函数是准凹的；另一种是针对效用函数是拟凸的情况。我们证明了这两种算法都可以直接应用于车载导航系统等等。上述问题都具有高度非凸低秩结构。我们表明，尽管问题属于一个众所周知的硬类，但通过利用它们的特殊结构，在理论和实践意义上都有可能设计出有效的算法。少

In this research. we formulated some classes of multiple objective optimization problems into single objective nonconvex optimization problems and proposed efficient algorithms for generating globally optimal solutions to the resulting problems. A few of the results are listed below :1 We studied a problem constraining the product of two objectives to be less than or equal to a given constant. We developed an algorithm for generating a globally optimal solution within a finite time. The computational results on a workstation indicated that the algorithm is reasonably practical as long as the number of constraints containing the product is less than five.2 We developed a branch-and-bound algorithm to resolve a multi-objective optimization with a 0-1 knapsack constraint. We incorporated a Lagrangian relaxation into the bounding procedure ; but the time taken for bounding is only a lower-order polynomial in the problem size. The algorithm succeeded in solving problems of 20 objectives and … More 120 variables within 20 seconds.3 We investigated the relationship between the multi-objective optimization with a 0-1 knapsack constraint and a production-transportation problem with concave production costs. We then extended the algorithm for the former to the latter network problem. The computational time needed by the algorithm was a few hundreds times less than those by the existing algorithms.4 We studied a bi-objective shortest path problem and developed two strongly polynomial algo- rithms. One is for the case that the utility function of the decision maker is quasi-concave ; and the other is for the case that the utility function is quasi-convex. We showed that both algorithms are directly applicable to in-car navigation systems and so forth.All the above mentioned problems have highly nonconvex but low-rank structures. We showed that, even though the problems belong to a well-known hard class, it is possible to design efficient algorithms both in theoretical and practical senses, by exploiting their special structures. Less