An application area of vertex enumeration problem (VEP) is the usage within objective space based linear/convex vector optimization algorithms whose aim is to generate (an approximation of) the Pareto frontier. In such algorithms, VEP, which is defined in the objective space, is solved in each iteration and it has a special structure. Namely, the recession cone of the polyhedron to be generated is the ordering cone. We consider and give a detailed description of a vertex enumeration procedure, which iterates by calling a modified “double description (DD) method” that works for such unbounded polyhedrons. We employ this procedure as a function of an existing objective space based vector optimization algorithm (Algorithm 1); and test the performance of it for randomly generated linear multiobjective optimization problems. We compare the efficiency of this procedure with another existing DD method as well as with the current vertex enumeration subroutine of Algorithm 1. We observe that the modified procedure excels the others especially as the dimension of the vertex enumeration problem (the number of objectives of the corresponding multiobjective problem) increases.
Keywords: Vertex enumeration, multiobjective optimization, vector optimization, polyhedral approximation
@article{RO_2021__55_S1_S2471_0,
author = {Kaya, \.Irfan Caner and Ulus, Firdevs},
title = {An iterative vertex enumeration method for objective space based vector optimization algorithms},
journal = {RAIRO. Operations Research},
pages = {S2471--S2485},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
doi = {10.1051/ro/2020139},
mrnumber = {4223204},
zbl = {1472.90121},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2020139/}
}
TY - JOUR AU - Kaya, İrfan Caner AU - Ulus, Firdevs TI - An iterative vertex enumeration method for objective space based vector optimization algorithms JO - RAIRO. Operations Research PY - 2021 SP - S2471 EP - S2485 VL - 55 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2020139/ DO - 10.1051/ro/2020139 LA - en ID - RO_2021__55_S1_S2471_0 ER -
%0 Journal Article %A Kaya, İrfan Caner %A Ulus, Firdevs %T An iterative vertex enumeration method for objective space based vector optimization algorithms %J RAIRO. Operations Research %D 2021 %P S2471-S2485 %V 55 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2020139/ %R 10.1051/ro/2020139 %G en %F RO_2021__55_S1_S2471_0
Kaya, İrfan Caner; Ulus, Firdevs. An iterative vertex enumeration method for objective space based vector optimization algorithms. RAIRO. Operations Research, Tome 55 (2021), pp. S2471-S2485. doi: 10.1051/ro/2020139
[1] , An algorithm for enumerating all vertices of a convex polyhedron. Computing 15 (1975) 181–193. | MR | Zbl | DOI
[2] , Computational experience with the reverse search vertex enumeration algorithm. Optim. Methods Softw. 10 (1998) 107–124. | MR | Zbl | DOI
[3] and , A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete Comput. Geom. 8 (1992) 295–313. | MR | Zbl | DOI
[4] , and , How good are convex hull algorithms? Comput. Geom. Theory App. 7 (1997) 265–302. | MR | Zbl | DOI
[5] , An algorithm for finding all vertices of a convex polyhedral set. J. Soc. Ind. Appl. Math. 9 (1961) 72–88. | MR | Zbl | DOI
[6] , and , The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. ACM TOMS 22 (1996) 469–483. | MR | Zbl | DOI
[7] , An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem. J. Global Optim. 13 (1998) 1–24. | MR | Zbl | DOI
[8] and , Projective geometry and the outer approximation algorithm for multiobjective linear programming. Preprint arXiv:1006.3085 (2010).
[9] , and , On-line and off-line vertex enumeration by adjacency lists. Oper. Res. Lett. 10 (1991) 403–409. | MR | Zbl | DOI
[10] and , Data envelopment analysis (dea)–thirty years on. Eur. J. Oper. Res. 192 (2009) 1–17. | MR | Zbl | DOI
[11] , and , Handbook on Data Envelopment Analysis. Vol. 164 of : International Series in Operations Research & Management Science. Springer, New York, NY (2011). | Zbl
[12] , Using multiobjective optimization to map the entropy region. Comput. Optim. App. 63 (2016) 45–67. | MR | Zbl | DOI
[13] and , An improved vertex enumeration algorithm. Eur. J. Oper. Res. 9 (1982) 359–368. | MR | Zbl | DOI
[14] , Multicriteria Optimization. Springer, New York, NY (2005). | MR | Zbl
[15] , and , An approximation algorithm for convex multi-objective programming problems. J. Global Optim. 50 (2011) 397–416. | MR | Zbl | DOI
[16] , and , A multiobjective optimization approach to compute the efficient frontier in data envelopment analysis. J. Multi-Criteria Decis. Anal. 26 (2019) 187–198. | DOI
[17] and , Double description method revisited. Comb. Comput. Sci. 1120 (1996) 91–111. | MR | Zbl
[18] , and , Benson type algorithms for linear vector optimization and applications. J. Global Optim. 59 (2014) 811–836. | MR | Zbl | DOI
[19] , , , and , Generating all vertices of a polyhedron is hard. Discrete Comput. Geom. 39 (2008) 174–190. | MR | Zbl | DOI
[20] , , and , A survey of DEA applications. Omega 41 (2013) 893–902. | DOI
[21] , Vector Optimization with Infimum and Supremum. Springer, Berlin-Heidelberg (2011). | MR | Zbl | DOI
[22] , BENSOLVE: A free VLP solver, version 1.2 (2012).
[23] and , BENSOLVE: A free VLP solver, version 2.0.1 (2015).
[24] , and , Primal and dual approximation algorithms for convex vector optimization problems. J. Global Optim. 60 (2014) 713–736. | MR | Zbl | DOI
[25] , , and , The double description method. Contrib. Theory Games 2 (1953) 51–74. | MR | Zbl
[26] and , Scalarizing vector optimization problems. J. Optim. Theory App. 42 (1984) 499–524. | MR | Zbl | DOI
[27] , Convex Analysis. Princeton University Press (1970). | MR | Zbl | DOI
[28] and , Computational results on an algorithm for finding all vertices of a polytope. Math. Program. 18 (1980) 308–329. | MR | Zbl | DOI
[29] , Canonical DC programming problem: outer approximation methods revisited. Oper. Res. Lett. 18 (1995) 99–106. | MR | Zbl | DOI
[30] , and , A survey of data envelopment analysis in energy and environmental studies. Eur. J. Oper. Res. 189 (2008) 1–18. | MR | Zbl | DOI
Cité par Sources :
