An improved version of the augmented epsilon-constraint method (AUGMECON2) for finding the exact Pareto set in Multi-Objective Integer Programming problems

Mavrotas, George and Florios, Kostas (2013): An improved version of the augmented epsilon-constraint method (AUGMECON2) for finding the exact Pareto set in Multi-Objective Integer Programming problems. Published in: Applied Mathematics and Computation , Vol. 219, No. 18 (15 May 2013): pp. 9652-9669.

Abstract

Generation (or a posteriori) methods in Multi-Objective Mathematical Programming (MOMP) is the most computationally demanding category among the MOMP approaches. Due to the dramatic increase in computational speed and the improvement of Mathematical Programming algorithms the generation methods become all the more attractive among today’s decision makers. In the current paper we present the generation method AUGMECON2 which is an improvement of our development, AUGMECON. Although AUGMECON2 is a general purpose method, we will demonstrate that AUGMECON2 is especially suitable for Multi-Objective Integer Programming (MOIP) problems. Specifically, AUGMECON2 is capable of producing the exact Pareto set in MOIP problems by appropriately tuning its running parameters. In this context, we compare the previous and the new version in a series of new and old benchmarks found in the literature. We also compare AUGMECON2’s performance in the generation of the exact Pareto sets with established methods and algorithms based on specific MOIP problems (knapsack, set packing) and on published results. Except from other Mathematical Programming methods, AUGMECON2 is found to be competitive also with Multi-Objective Meta-Heuristics (MOMH) in producing adequate approximations of the Pareto set in Multi-Objective Combinatorial Optimization (MOCO) problems.

• Item Type: MPRA Paper
• Language: English
• Keywords: Multi-Objective Programming, ε-constraint method, exact Pareto set
• Subjects: C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C61 - Optimization Techniques ; Programming Models ; Dynamic Analysis; C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C63 - Computational Techniques ; Simulation Modeling

References

R.E. Steuer, Multiple Criteria Optimization.Theory, Computation and Application, Krieger, Malabar FL, 1986.

C.L. Hwang, A. Masud, Multiple Objective Decision Making. Methods and Applications: A state of the art survey, Lecture Notes in Economics and Mathematical Systems Vol. 164, Springer-Verlag, Berlin, 1979.

G. Mavrotas, Effective implementation of the ε-constraint method in multi-objective mathematical programming problems, Applied Mathematics and Computation 213 (2009) 455-465.

M. Ehrgott, D.M. Ryan, Constructing Robust Crew Schedules with Bicriteria Optimization, Journal of Multi-Criteria Decision Analysis 11 (2002) 139-150.

M. Laumanns, L. Thiele, E. Zitzler, An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method, European Journal of Operational Research 169 (2006) 932-942.

H.W. Hamacher, C.R. Pedersen, S. Ruzika, Finding representative systems for discrete bicriterion optimization problems, Operations Research Letters 35 (2007) 336-344.

C.A. Coello Coello, D.A. Van Veldhuizen, G.A. Lamont, Evolutionary Algorithms for Solving Multi-Objective Problems, Kluwer Academic Publishers, Boston, MA, 2002.

Κ. Deb, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley and Sons, Chichester, 2001.

K. Florios, G. Mavrotas, D. Diakoulaki, Solving multi-objective, multi-constraint knapsack problems using mathematical programming and evolutionary algorithms, European Journal of Operational Research 203 (2010) 14-21.

A. Chinchuluun, P.M. Pardalos, A survey of recent developments in multiobjective optimization, Annals of Operations Research 154 (2007) 29-50.

G.R. Bitran, Linear multiple objective programs with zero-one variables, Mathematical Programming 13 (1977) 121-139.

G.R. Bitran, Theory and algorithms for linear multiple objective programs with zero-one variables, Mathematical Programming 17 (1979) 362-390.

D. Klein, E. Hannan, An algorithm for the multiple objective integer linear programming problem, European Journal of Operational Research 9 (1982) 378-385.

L.G. Chalmet, L. Lemonidis, D.J. Elzinga, An algorithm for the bi-criterion integer programming problem, European Journal of Operational Research 25 (1986) 292-300.

G.R. Jahanshahloo, F. Hosseinzadeh, N. Shoja, G. Tohidi, A method for generating all efficient solutions of 0-1 multi-objective linear programming problem, Applied Mathematics and Computation 169 (2005) 874-886.

F. Sourd, O. Spanjaard, A multiobjective branch-and-bound framework: Application to the biobjective spanning tree problem, INFORMS Journal on Computing 20(3) (2008) 472-484.

T.K. Ralphs, M.J. Saltzman, M.M. Wiecek, An improved algorithm for solving biobjective integer programs, Annals of Operations Research 147 (2006) 43-70.

M. Ozlen, M. Azizoglu, Multi-objective integer programming: A general approach for generating all non-dominated solutions, European Journal of Operational Research 199 (2009) 25-35.

A. Przybylski, X. Gandibleux, M. Ehrgott, A two-phase method for multi-objective integer programming and its application to the assignment problem with three objectives, Discrete Optimization 7 (2010) 149-165.

Y.Y. Haimes, L.S. Lasdon, D.A. Wismer, On a bicriterion formulation of the problems of integrated system identification and system optimization, IEEE Transactions on Systems, Man, and Cybernetics 1 (1971) 296-297.

D. Rayside, H.C. Estler, D. Jackson, The guided improvement algorithm for exact, general-purpose, many-objective combinatorial optimization, Massachusetts Institute of Technology Technical Report, Computer Science and Artificial Intelligence Laboratory, 2009.

M. Ehrgott, S. Ruzika, Improved ε-constraint method for multiobjective programming, Journal of Optimization Theory and Applications 138 (2008) 375-396.

J. Sylva, A. Crema, A method for finding the set of non-dominated vectors for multiple objective integer linear programs, European Journal of Operational Research 158 (2004) 46-55.

J. Sylva, A. Crema, A method for finding well-dispersed subsets of non-dominated vectors for multiple objective mixed integer linear programs, European Journal of Operational Research 180 (2007) 1011-1027.

B. Lokman, Approaches for multi-objective combinatorial optimization problems, MSc Thesis, Middle East Technical University, Ankara, 2007.

M. Koksalan, B. Lokman, Approximating the nondominated frontiers of multi-objective combinatorial optimization problems, Naval Research Logistics 56 (2009) 191-198.

J. Teghem, P.L. Kunsch, A survey of techniques for finding efficient solutions to multi-objective integer linear programming, Asia-Pacific Journal of Operational Research 3 (1986) 95-108.

E.L. Ulungu, J. Teghem, Multi-objective combinatorial optimization problems: A survey, Journal of Multi-Criteria Decision Analysis 3 (1994) 83-104.

L.M. Rasmussen, Zero-one programming with multiple criteria, European Journal of Operational Research 26 (1986) 83-95.

M. Ehrgott, X. Gandibleux, A survey and annotated bibliography of multiobjective combinatorial optimization, OR Spectrum 22 (2000) 425-460.

M.J. Alves, J. Climaco, A review of interactive methods for multiobjective integer and mixed-integer programming, European Journal of Operational Research 180 (2007) 99-115.

A. Jaszkiewicz, On the computational efficiency of multiple objective metaheuristics. The knapsack problem case study, European Journal of Operational Research 158 (2004) 418-433.

E. Zitzler, L. Thiele, Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach, IEEE Transactions on Evolutionary Computation 3 (1999) 257-271.

K. Klamroth, M.M. Wiecek, Dynamic programming approaches to the multiple criteria knapsack problem, Naval Research Logistics 47 (2000) 57-76.

T. Erlebach, H. Kellerer, U. Pferschy, Approximating multiobjective knapsack problems, Management Science 48 (2002) 1603-1612.

R. Shah, P. Reed, Comparative analysis of multiobjective evolutionary algorithms for random and correlated instances of multiobjective d-dimensional knapsack problems, European Journal of Operational Research 211 (2011) 466-479.

T. Lust, J. Teghem, The multiobjective multidimensional knapsack problem: a survey and a new approach, International Transactions in Operational Research 19 (2012) 495-520.

A. Jaszkiewicz, On the performance of multiple-objective genetic local search on the 0/1 knapsack problem – A comparative experiment, IEEE Transactions on Evolutionary Computation 6 (2002) 402-412.

M. Laumanns, L. Thiele, E. Zitzler, 2005. An adaptive scheme to generate the Pareto front based on the epsilon-constraint method, in: J. Branke, K. Deb, K. Miettinen, R. Steuer (Eds.), Practical Approaches to Multi-Objective Optimization, Dagstuhl Seminar Proceedings, Vol. 04461, URN: urn:nbn:de:0030-drops-2465, URL: http://drops.dagstuhl.de/opus/volltexte/2005/246.

G.L. Nemhauser, L.A. Wolsey, Integer and Combinatorial Optimization, Wiley, 1999.

X. Delorme, X. Gandibleux, F. Degoutin, Evolutionary, constructive and hybrid procedures for the bi-objective set packing problem, European Journal of Operational Research 204 (2010) 206-217.

F. Tricoire, Multi-directional local search, Computers & Operations Research 39 (2012) 3089-3101.

H. Isermann, R.E. Steuer, Computational experience concerning payoff tables and minimum criterion values over the efficient set, European Journal of Operational Research 33 (1987) 91-97.

M.I. Dessouky, M. Ghiassi, W.J. Davis, Estimates of the mínimum nondominated criterion values in multiple criteria decisión making, Engineering Costs and Production Economics 10 (1986) 95-104.

B. Metev, V. Vassilev, A method for nadir point estimation in MOLP problems, Cybernetics and Information Technologies 3 (2003) 15-24.

M.J. Alves, J.P. Costa, An exact method for computing the nadir values in multiple objective linear programming, European Journal of Operational Research 198 (2009) 637-646.

J.M. Jorge, An algorithm for optimizing a linear function over an integer efficient set, European Journal of Operational Research 195 (2009) 98-103.

A. Brooke, D. Kendrick, A. Meeraus, R. Raman, GAMS. A user’s guide, GAMS development corporation, Washington, 1998.

E. Zitzler, M. Laumanns, L. Thiele, SPEA2: Improving the strength pareto evolutionary algorithm for multiobjective optimization, in: K. Giannakoglou, D. Tsahalis, J. Periaux, K. Papailiou, T. Fogarty (Eds.), Evolutionary Methods for Design, Optimization, and Control, Barcelona, CIMNE , Spain, 2002, pp. 19-26.

C.H. Papadimitriou, K. Steiglitz, Combinatorial optimization: algorithms and complexity, Dover, New York, 1998.

F. Degoutin, Problemes bi-objectifs en optimization combinatoire et capacite d’infrastructures ferroviaires. Master Thesis. Universite de Valenciennes et du Hainaut Cambresis, Valenciennes, France, 2002 (in French).

X. Delorme, X. Gandibleux, F. Degoutin, Résolution approchée du problème de set packing bi-objectifs. In Proceedings de l'École d'Automne de Recherche Opérationnelle de Tours (EARO), October 2003, pp. 74-80 (in French).

G. Mavrotas, D. Diakoulaki, Multi-criteria branch & bound: A vector maximization algorithm for Mixed 0-1 Multiple Objective Linear Programming, Applied Mathematics and Computation 171 (2005) 53-71.

J.J. Dongarra, Performance of Various Computers Using Standard Linear Equations Software, Linpack Benchmark Report, University of Tennessee Computer Science Technical Report, CS-89-85, 2008.

S. Bleuler, M. Laumanns, L. Thiele, E. Zitzler, PISA – A Platform and Programming Language Independent Interface for Search Algorithms, in: C. Fonseca, P. Fleming, E. Zitzler, K. Deb, L. Thiele (Eds.), Evolutionary Multi-Criterion Optimization, Springer, Heidelberg, 2003, pp. 494-508.

S. Bleuler, M. Laumanns, L. Thiele, E. Zitzler 2003. The PISA Homepage. Available online at http://www.tik.ee.ethz.ch/pisa.

G. Mavrotas, D. Diakoulaki, A. Kourentzis, Selection among ranked projects under segmentation, policy and logical constraints, European Journal of Operational Research 187 (2008) 177-192.