Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems

Florios, Kostas and Mavrotas, George (2014): Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems. Published in: Applied Mathematics and Computation , Vol. 237, (15 June 2014): pp. 1-19.

Abstract

The calculation of the exact set in Multi-Objective Combinatorial Optimization (MOCO) problems is one of the most computationally demanding tasks as most of the problems are NP-hard. In the present work we use AUGMECON2 a Multi-Objective Mathematical Programming (MOMP) method which is capable of generating the exact Pareto set in Multi-Objective Integer Programming (MOIP) problems for producing all the Pareto optimal solutions in two popular MOCO problems: The Multi-Objective Traveling Salesman Problem (MOTSP) and the Multi-Objective Set Covering problem (MOSCP). The computational experiment is confined to two-objective problems that are found in the literature. The performance of the algorithm is slightly better to what is already found from previous works and it goes one step further generating the exact Pareto set to till now unsolved problems. The results are provided in a dedicated site and can be useful for benchmarking with other MOMP methods or even Multi-Objective Meta-Heuristics (MOMH) that can check the performance of their approximate solution against the exact solution in MOTSP and MOSCP problems.

• Item Type: MPRA Paper
• Language: English
• Keywords: multi-objective, traveling salesman problem, set covering problem, ε-constraint, 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, 164, Springer-Verlag, Berlin, 1979.

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

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

G. Mavrotas, K. Florios, An improved version of the augmented ε-constraint method (AUGMECON2) for finding the exact pareto set in multi-objective integer programming problems, Applied Mathematics and Computation 219 (2013) 9652-9669.

T. Lust, J. Teghem, The multiobjective traveling salesman problem: A survey and a new approach, Studies in Computational Intelligence 272 (2010) 119-141.

R. Fischer, K. Richter, Solving a multiobjective traveling salesman problem by dynamic programming, Mathematische Operationsforschung und Statistik - Series Optimization 13 (1982) 247-252.

P.C. Borges, M.P. Hansen, A basis for future successes in multiobjective combinatorial optimization, Technical Report, Institute of Mathematical Modelling, Technical University of Denmark, 1998.

M.P. Hansen, Use of substitute scalarizing functions to guide a local search based method: The case of moTSP, Journal of Heuristics 6 (2000) 419-431.

A. Jaszkiewicz, Genetic local search for multi-objective combinatorial optimization, European Journal of Operational Research 137 (2002) 50-71.

L. Paquete, T. Stützle, A two-phase local search for the biobjective traveling salesman problem, Lecture Notes in Computer Science 2632 (2003) 479-493.

L. Paquete, T. Stützle, Design and analysis of stochastic local search for the multiobjective traveling salesman problem, Computers & Operations Research 36 (2009) 2619-2631.

T. Lust, J. Teghem, Two-phase Pareto local search for the biobjective traveling salesman problem, Journal of Heuristics 16 (2010) 475-510.

T. Lust, A. Jaszkiewicz, Speed-up techniques for solving large-scale biobjective TSP, Computers & Operations Research 37 (2010) 521-533.

A. Jaszkiewicz, P. Zielniewicz, Pareto memetic algorithm with path relinking for bi-objective traveling salesperson problem, European Journal of Operational Research 193 (2009) 885-890.

W. Peng, Q. Zhang, H. Li, Comparison between MOEA/D and NSGA-II on the multi-objective travelling salesman problem, Studies in Computational Intelligence 171 (2009) 309-324.

F. Samanlioglu, W.G. Ferrell Jr, M.E. Kurz, A memetic random-key genetic algorithm for a symmetric multi-objective traveling salesman problem, Computers & Industrial Engineering 55 (2008) 439-449.

C. García-Martínez, O. Cordón, F. Herrera, A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP, European Journal of Operational Research 180 (2007) 116-148.

J. Cheng, G. Zhang, Z. Li, Y. Li, Multi-objective ant colony optimization based on decomposition for bi-objective traveling salesman problems, Soft Computing 16 (2012) 597-614.

M. López-Ibáñez, T. Stüzle, An analysis of algorithmic components for multiobjective ant colony optimization: A case study on the biobjective TSP, in: P. Collet et al. (Eds.), EA 2009, LNCS 5975, Springer-Verlag, Berlin Heidelberg, 2009, pp. 134-145.

A. Liefooghe, J. Humeau, S. Mesmoudi, L. Jourdan, E-G. Talbi, On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems, Journal of Heuristics 18 (2012) 317-352.

L. Paquete, Stochastic local search algorithms for multiobjective combinatorial optimization: Methods and analysis. Dissertations in Artificial Intelligence, Vol. 295, AKA Verlag/ IOS Press, 2006.

T. Lust, New metaheuristics for solving MOCO problems: application to the knapsack problem, the traveling salesman problem and IMRT optimization, PhD Thesis, Université de Mons, Mons, Belgium, 2009.

O. Özpeynirci, M. Köksalan, Pyramidal tours and multiple objectives, Journal of Global Optimization 48 (2007) 569-583.

O. Özpeynirci, M. Köksalan, Multiobjective traveling salesperson problem on Halin graphs, European Journal of Operational Research 196 (2009) 155-161.

M. Stanojević, M. Vujošević, B. Stanojević, Computation results of finding all efficient points in multiobjective combinatorial optimization, International Journal of Computers, Communications & Control 3 (2008) 374-383.

J.F. Bérubé, M. Gendreau, J-Y. Potvin, An exact ε-constraint method for bi-objective combinatorial optimization problems: Application to the traveling salesman problem with profits, European Journal of Operational Research 194 (2009) 39-50.

N. Jozefowiez, F. Glover, M. Laguna, Multi-objective meta-heuristics for the traveling salesman problem with profits, Journal of Mathematical Modelling and Algorithms 7 (2008) 177-195.

B. Manthey, L. Shankar Ram, Approximation algorithms for multi-criteria traveling salesman problems, Algorithmica 53 (2009) 69-88.

G. Laporte, The traveling salesman problem: An overview of exact and approximate algorithms, European Journal of Operational Research 59 (1992) 231-247.

C.H. Papadimitriou, The euclidean traveling salesman problem is NP-complete, Theoretical Computer Science 4 (1977) 237-244.

D. Applegate, R. Bixby, V. Chvátal, W. Cook, On the solution of travelling salesman problems, Documenta Mathematica 3 (1998) 645-656.

A. Volgenant, Symmetric traveling salesman problems, European Journal of Operational Research 49 (1990) 153-154. Source Code available at ftp://www.mathematik.uni-kl.de/pub/Math/ORSEP/VOLGENAN.ZIP.

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.

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.

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

K. Khalili-Damghani, M. Tavana, S. Sadi-Nezhad, An integrated multi-objective framework for solving multi-period project selection problems, Applied Mathematics and Computation 219 (2012) 3122-3138.

T. Lust, J. Teghem, D. Tuyttens, Very large-scale neighborhood search for solving multiobjective combinatorial optimization problems, in: R.H.C. Takahashi et al. (Eds.), EMO 2011, LNCS 6576, Springer-Verlag, Berlin Heidelberg, 2011, pp. 254-268.

A. Jaszkiewicz, A comparative study of multiple-objective metaheuristics on the bi-objective set covering problem and the Pareto memetic algorithm, Annals of Operations Research 131 (2004) 135-158.

C. Prins, C. Prodhon, R.W. Calvo, Two-phase method and Lagrangian relaxation to solve the bi-objective set covering problem, Annals of Operations Research 147 (2006) 23-41.

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

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

K.M. Miettinen, Nonlinear Multiobjective Optimization, Kluwer Academic Publishers, Boston, 1998.

M.R. Bussieck, Introduction to GAMS Branch-and-Cut Facility, Technical report, GAMS Development Corp., 2003. http://www.gams.com/docs/bch.htm

GAMS Corp., Traveling Salesman problem with BCH, http://www.gams.com/modlib/libhtml/bchtsp.htm.

M.R. Bussieck, Column generation in GAMS – Extending the GAMS Branch-and-Cut-and-Heuristic (BCH) facility, 83rd Working Group Meeting Real World Optimization, Workshop “Mathematical Optimization in Transportation – Airline, Public, Transport, Railway” GOR, Bad Honnef, Germany, 2009. Available online at: http://www.gams.com/presentations/bussieck_cg.pdf

G. Reinelt, TSPLIB – A traveling salesman problem library, ORSA Journal on Computing 3 (1991) 376-384.

G. Reinelt, TSPLIB95, URL: http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.

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

https://sites.google.com/site/thibautlust/research/multiobjective-tsp (last accessed on July 24th 2013).

http://eden.dei.uc.pt/~paquete/tsp (last accessed on July 22nd 2013).

http://xgandibleux.free.fr/MOCOlib/MOSCP.html (last accessed on July 29th 2013).

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.

K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Chichester, 2001.

V. Khare, X. Yao, K. Deb, Performance scaling of multi-objective evolutionary algorithms, in: C.M. Fonseca et al. (Eds.), EMO 2003, LNCS 2632, Springer-Verlag, Berlin Heidelberg, 2003, pp.376-390.

M. Visée, J. Teghem, M. Pirlot, E.L. Ulungu, Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem, Journal of Global Optimization 12 (1998) 139-155.

A. Przybylski, X. Gandibleux, M. Ehrgott, Two phase algorithms for the bi-objective assignment problem, European Journal of Operational Research 185 (2008) 509-533.

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.

W.H. Press, S.A. Teukolsky, W.T. Vetterling, B.P. Flannery, Numerical Recipes in Pascal. The art of Scientific Computing, Cambridge University Press, 1989.

K. Helsgaun, An effective implementation of the Lin-Kernighan traveling salesman heuristic, European Journal of Operational Research 126 (2000) 106-130.

C.E. Miller, A.W. Tucker, R.A. Zemlin, Integer programming formulations of traveling salesman problems, Journal of the Association for Computing Machinery 7 (1960) 326-329.

M. Ozlen, B.A. Burton, C.A.G. MacRae, Multi-objective integer programming: An improved recursive algorithm, Journal of Optimization Theory and Applications 2013, inPress (DOI 10.1007/s10957-013-0364-y).

O. Özpeynirci, M. Köksalan, An exact algorithm for finding extreme supported nondominated points of multiobjective mixed integer programs, Management Science 56 (2010) 2302-2315.

D. Applegate, R. Bixby, V. Chvátal, W. Cook, Concorde TSP solver http://www.tsp.gatech.edu/concorde.html

J. Lemesre, C. Dhaenens, E.G. Talbi, Parallel partitioning method (PPM): A new exact method to solve bi-objective problems, Computers & Operations Research 34 (2007) 2450-2462.

K. Dächert, J. Gorski, K. Klamroth, An augmented weighted Tchebycheff method with adaptively chosen parameters for discrete bicriteria optimization problems, Computers & Operations Research 39 (2012) 2929-2943.