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

在这项研究中。我们将几类多目标优化问题转化为单目标非凸优化问题，并给出了生成全局最优解的有效算法。主要结果如下：1我们研究了一个约束两个目标的乘积小于或等于给定常数的问题。我们开发了一个在有限时间内生成全局最优解的算法。在工作站上的计算结果表明，只要包含乘积的约束个数小于5个，该算法就具有较好的实用性。2.提出了一种分枝定界算法来求解一个带有0-1背包约束的多目标优化问题。我们将拉格朗日松弛引入到定界过程中，但是定界所需的时间仅是问题规模中的低阶多项式。该算法成功地解决了20个目标和…问题研究了具有0-1背包约束的多目标优化问题和具有凹生产成本的生产运输问题之间的关系。然后，我们将前者的算法推广到后者的网络问题。该算法所需的计算时间是现有算法的几百倍。4我们研究了一个双目标最短路径问题，并提出了两个强多项式算法。一种是决策者的效用函数是拟凹的情况，另一种是效用函数是拟凸的情况。我们证明了这两种算法都直接适用于车载导航系统等，所有上述问题都具有高度非凸的低阶结构。我们证明了，即使问题属于众所周知的困难类，通过利用它们的特殊结构，在理论和实际意义上都可以设计出有效的算法。较少

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