(599i) Application of Global Solution Algorithm, Interval Analysis, in Pareto Optimal and Pareto Frontier Solving Strategy
Pareto optimal (or Pareto set, Pareto frontier) is a concept in economics with applications especially in engineering and social sciences. The term is named after Vilfredo Pareto (1848–1923), an Italian economist who practiced the concept in his studies of economics.
Solving Pareto optimal and Pareto frontier involve solution strategy of multi-objective optimization where solutions come as "set". One approach extensively applied is the weighted sum approach, which had been studied with generic algorithm. Due to the fact that Pareto optimal set is a NP-hard problem, effort of obtaining the "whole set" is time consuming. Part of the "set" could even be missing if one (or more) of the functions within the multi-object optimization group is concave. Thus, more complicated approaches other than weighted sum have to be applied, which, if solved by generic algorithm, guarantee of discovering the "whole set" is still a mystery.
In our study, interval analysis, one of the global solution algorithms, had been applied to solve Pareto optimal and frontier. To avoid NP-hard, scheduling of the weighted sum factors had been applied with sufficient coverage. The ability of solving convex and concave optimal functions by global solution algorithm, such as interval analysis, enabled the weighted sum approach to discover the "whole set" of Pareto optimal solution with concave functions involved. The only problem by applying global solution algorithm seems to be the definition of the scheduling for the weighted sum factors. However, proper restricts under engineering consideration may provide reasonable suggestion on the coverage of the weighted sum factors, so that "whole set" is discovered with finite solutions.
This is the first attempt of applying deterministic solution algorithm to solve Pareto optimal and frontier. However, one has to apply proper restricts under engineering and economic considerations to avoid the NP-hard issue, as well as the ability of solving concave functions such as global solution algorithms.
See more of this Group/Topical: Computing and Systems Technology Division