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

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

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