Abstract
We develop a primal-dual simplex algorithm for multicriteria linear programming. It is based on the scalarization theorem of Pareto optimal solutions of multicriteria linear programs and the single objective primal-dual simplex algorithm. We illustrate the algorithm by an example, present some numerical results, give some further details on special cases and point out future research.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ehrgott, M., Wiecek, M.M.: Multiobjective programming. In: Figueira, J., Greco, S., Ehrgott, M. (eds.) Multiple Criteria Decision Analysis: State of the Art Surveys. International Series in Operations Research and Management Science, vol. 76, pp. 667–708. Springer, New York (2005)
Steuer, R.E.: ADBASE: A MOLP solver. Technical report, Terry College of Business, University of Georgia, Athens, GA (2000)
Benson, H.P.: An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem. J. Glob. Optim. 13, 1–24 (1998)
Abhyankar, S.S., Morin, T.L., Trafalis, T.: Efficient faces of polytopes: interior-point algorithms, parametrization of algebraic varieties, and multiple objective optimization. Contemp. Math. 114, 319–341 (1990)
Arbel, A.: Anchoring points and cones of opportunities in interior multiobjective linear programming. J. Oper. Res. Soc. 45, 83–96 (1994)
Arbel, A.: An interior multiobjective primal-dual linear programming algorithm based on approximated gradients and efficient anchoring points. Comput. Oper. Res. 24, 353–365 (1997)
Zeleny, M.: Linear Multiobjective Programming. Lecture Notes in Economics and Mathematical Systems, vol. 95. Springer, Berlin (1974)
Benson, H.P., Sun, E.: Outcome space partition of the weight set in multiobjective linear programming. J. Optim. Theory Appl. 105, 17–36 (2000)
Hamel, H., Heyde, F., Löhne, A., Tammer, C., Winkler, K.: Closing the duality gap in linear vector optimization. J. Convex Anal. 11, 163–178 (2004)
Ahuja, R., Magnanti, T., Orlin, J.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs (1994)
Ulungu, E.L., Teghem, J.: The two-phases method: an efficient procedure to solve biobjective combinatorial optimization problems. Found. Comput. Decis. Sci. 20, 149–165 (1994)
Geoffrion, A.: Proper efficiency and the theory of vector maximization. J. Math. Anal. Appl. 22, 618–630 (1968)
Luenberger, D.G.: Linear and Nonlinear Programming. Addison-Wesley, Reading (1989)
Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer, Berlin (1987)
Steuer, R.E.: Multiple Criteria Optimization: Theory, Computation, and Application. Krieger Publishing Company, Malabar (1989)
Przybylski, A.: Application of primal-dual simplex method for MOLP to the MO assignment problem. Technical Report, University of Nantes, Nantes, France (2005)
Barber, C.B., Dobkin, D.P., Huhdanpaa, H.: The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. 22, 469–483 (1996)
Isermann, H.: The enumeration of the set of all efficient solutions for a linear multiple objective program. Oper. Res. Q. 28, 711–725 (1977)
Hershberger, J., Shuri, S.: Offline maintenance of planar configurations. J. Algorithms 21, 453–475 (1996)
Ehrgott, M., Gandibleux, X.: Approximative solution methods for multiobjective combinatorial optimization. Top 12, 1–85 (2004)
Sedeño-Noda, A., González-Martín, C.: An algorithm for the biobjective integer minimum cost flow problem. Comput. Oper. Res. 28, 139–156 (2001)
Visée, M., Teghem, J., Pirlot, M., Ulungu, E.L.: Two-phases method and branch-and-bound procedures to solve the biobjective Knapsack problem. J. Glob. Optim. 12, 139–155 (1998)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by H.P. Benson.
The paper was written during a visit of the first author to the University of Sevilla financed by a grant of the Andalusian Consejería de Educación. The research of the first author was partially supported by University of Auckland Grant 3602178/9275. The research of the second and third authors was partially financed by Spanish Grants BFM2001-2378, BFM2001-4028, MTM2004-0909 and HA2003-0121.
We thank Anthony Przybylski for the implementation and making his results available. We thank the anonymous referees, whose comments have helped us to improve the presentation of the paper.
Rights and permissions
About this article
Cite this article
Ehrgott, M., Puerto, J. & Rodríguez-Chía, A.M. Primal-Dual Simplex Method for Multiobjective Linear Programming. J Optim Theory Appl 134, 483–497 (2007). https://doi.org/10.1007/s10957-007-9232-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-007-9232-y