TY - JOUR
T1 - Evaluation of nondominated solution sets for k-objective optimization problems
T2 - An exact method and approximations
AU - Kim, B.
AU - Gel, Esma
AU - Fowler, John
AU - Carlyle, W. M.
AU - Wallenius, J.
N1 - Funding Information:
The authors would like to acknowledge the support of the National Science Foundation under contract DMII-0121815.
PY - 2006/9/1
Y1 - 2006/9/1
N2 - Integrated Preference Functional (IPF) is a set functional that, given a discrete set of points for a multiple objective optimization problem, assigns a numerical value to that point set. This value provides a quantitative measure for comparing different sets of points generated by solution procedures for difficult multiple objective optimization problems. We introduced the IPF for bi-criteria optimization problems in [Carlyle, W.M., Fowler, J.W., Gel, E., Kim, B., 2003. Quantitative comparison of approximate solution sets for bi-criteria optimization problems. Decision Sciences 34 (1), 63-82]. As indicated in that paper, the computational effort to obtain IPF is negligible for bi-criteria problems. For three or more objective function cases, however, the exact calculation of IPF is computationally demanding, since this requires k ({greater than or slanted equal to}3) dimensional integration. In this paper, we suggest a theoretical framework for obtaining IPF for k ({greater than or slanted equal to}3) objectives. The exact method includes solving two main sub-problems: (1) finding the optimality region of weights for all potentially optimal points, and (2) computing volumes of k dimensional convex polytopes. Several different algorithms for both sub-problems can be found in the literature. We use existing methods from computational geometry (i.e., triangulation and convex hull algorithms) to develop a reasonable exact method for obtaining IPF. We have also experimented with a Monte Carlo approximation method and compared the results to those with the exact IPF method.
AB - Integrated Preference Functional (IPF) is a set functional that, given a discrete set of points for a multiple objective optimization problem, assigns a numerical value to that point set. This value provides a quantitative measure for comparing different sets of points generated by solution procedures for difficult multiple objective optimization problems. We introduced the IPF for bi-criteria optimization problems in [Carlyle, W.M., Fowler, J.W., Gel, E., Kim, B., 2003. Quantitative comparison of approximate solution sets for bi-criteria optimization problems. Decision Sciences 34 (1), 63-82]. As indicated in that paper, the computational effort to obtain IPF is negligible for bi-criteria problems. For three or more objective function cases, however, the exact calculation of IPF is computationally demanding, since this requires k ({greater than or slanted equal to}3) dimensional integration. In this paper, we suggest a theoretical framework for obtaining IPF for k ({greater than or slanted equal to}3) objectives. The exact method includes solving two main sub-problems: (1) finding the optimality region of weights for all potentially optimal points, and (2) computing volumes of k dimensional convex polytopes. Several different algorithms for both sub-problems can be found in the literature. We use existing methods from computational geometry (i.e., triangulation and convex hull algorithms) to develop a reasonable exact method for obtaining IPF. We have also experimented with a Monte Carlo approximation method and compared the results to those with the exact IPF method.
KW - Combinatorial optimization
KW - Metaheuristics
KW - Multiple objective programming
UR - http://www.scopus.com/inward/record.url?scp=33646503266&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33646503266&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2005.01.029
DO - 10.1016/j.ejor.2005.01.029
M3 - Article
AN - SCOPUS:33646503266
SN - 0377-2217
VL - 173
SP - 565
EP - 582
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 2
ER -