An exact method for solving the bi-objective Minimum Diameter-Cost Spanning Tree Problem

de Sousa, Ernando Gomes; Santos, Andréa Cynthia; Aloise, Dario José

doi:10.1051/ro/2014029

de Sousa, Ernando Gomes ¹ ; Santos, Andréa Cynthia ² ; Aloise, Dario José ¹

¹ Universidade do Estado do Rio Grande do Norte, UERN Rua Almino Afonso, 478, CEP 59.610-210, Mossoró, RN, Brasil.
² ICD-LOSI, Université de Technologie de Troyes 12, rue Marie Curie, CS 42060, 10004 Troyes Cedex, France.

RAIRO - Operations Research - Recherche Opérationnelle, Tome 49 (2015) no. 1, pp. 143-160.

Résumé

In this work, we propose a procedure to compute Pareto-optimal fronts for the bi-objective Minimum Diameter-Cost Spanning Tree problem (bi-MDCST). The bi-MDCST aims at finding spanning trees with minimum total cost and minimum diameter. Strategic decision problems for high-speed trains infrastructure, as well as tactical and operational optimization problems for network design and transportation can be modeled as bi-MDCST. The proposed exact procedure makes use of components from the multi-objective exact method Parallel Partitioning Method, and Pareto-optimal fronts have been computed for two benchmark instances from the literature. To the best of our knowledge, there are no works dedicated to providing Pareto-optimal fronts for the bi-MDCST.

Reçu le : 2014-04-26
Accepté le : 2014-05-05

MR Zbl

DOI : 10.1051/ro/2014029

Classification : 90-08, 90C27, 90C29, 68W99
Mots clés : Spanning trees, multi-objective optimization, Parallel Partitioning Method

Affiliations des auteurs :

de Sousa, Ernando Gomes ¹ ; Santos, Andréa Cynthia ² ; Aloise, Dario José ¹

@article{RO_2015__49_1_143_0,
     author = {de Sousa, Ernando Gomes and Santos, Andr\'ea Cynthia and Aloise, Dario Jos\'e},
     title = {An exact method for solving the bi-objective {Minimum} {Diameter-Cost} {Spanning} {Tree} {Problem}},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {143--160},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {1},
     year = {2015},
     doi = {10.1051/ro/2014029},
     mrnumber = {3349121},
     zbl = {1310.90098},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2014029/}
}

TY  - JOUR
AU  - de Sousa, Ernando Gomes
AU  - Santos, Andréa Cynthia
AU  - Aloise, Dario José
TI  - An exact method for solving the bi-objective Minimum Diameter-Cost Spanning Tree Problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2015
SP  - 143
EP  - 160
VL  - 49
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2014029/
DO  - 10.1051/ro/2014029
LA  - en
ID  - RO_2015__49_1_143_0
ER  -

%0 Journal Article
%A de Sousa, Ernando Gomes
%A Santos, Andréa Cynthia
%A Aloise, Dario José
%T An exact method for solving the bi-objective Minimum Diameter-Cost Spanning Tree Problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2015
%P 143-160
%V 49
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2014029/
%R 10.1051/ro/2014029
%G en
%F RO_2015__49_1_143_0

de Sousa, Ernando Gomes; Santos, Andréa Cynthia; Aloise, Dario José. An exact method for solving the bi-objective Minimum Diameter-Cost Spanning Tree Problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 49 (2015) no. 1, pp. 143-160. doi : 10.1051/ro/2014029. http://www.numdam.org/articles/10.1051/ro/2014029/

Bibliographie
Cité par

N.R. Achuthan, L. Caccetta, P.A. Caccetta and J.F. Geelen, Computational methods for the diameter restricted minimum weight spanning tree problem. Austral. J. Combin. 10 (1994) 51–71. | MR | Zbl

J.E.C. Arroyo, P.S. Vieira and D.S. Vianna, A GRASP algorithm for the multi-criteria minimum spanning tree problem. Ann. Oper. Res. 159 (2008) 125–133. | DOI | MR | Zbl

J.-F. Bérubé, M. Gendreau and J.-Y. Potvin, An exact $ϵ$ -constraint method for bi-objective combinatorial optimization problems: Application to the Traveling Salesman Problem with profits. Eur. J. Oper. Res. 194 (2009) 39–50. | DOI | MR | Zbl

A. Chinchuluun and P.M. Pardalos, A survey of recent developments in multiobjective optimization. Ann. Oper. Res. 154 (2007) 29–50. | DOI | MR | Zbl

T.H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to algorithms. McGraw-Hill, New York (1990). | MR | Zbl

N. Deo and A. Abdalla, Computing a diameter-constrained minimum spanning tree in parallel. Lect. Notes Comput. Sci. 1767 (2000) 17–31. | DOI | Zbl

M. Desrochers and G. Laporte, Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints. Oper. Res. Lett. 10 (1991) 27–36. | DOI | MR | Zbl

C.D. Dhaenems, J. Lemestre and E.G. Talbi, K-PPM: A new exact method to solve multi-objective combinatorial optimization problems. Eur. J. Oper. Res. 200 (2010) 45–53. | DOI | MR | Zbl

M. Ehrgott and X. Gandibleux, A survey and annotated bibliography of multiobjective combinatorial optimization. OR-Spektrum 22 (2000) 425–460. | DOI | MR | Zbl

M.R. Garey and D.S. Johnson, Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman, New York (1979). | MR | Zbl

L. Gouveia and T.L. Magnanti, Network flow models for designing diameter-constrained minimum-spanning and Steiner trees. Networks 41 (2003) 159–173. | DOI | MR | Zbl

L. Gouveia, L. Simonetti and E. Uchoa, Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs. Math. Program. 128 (2011) 123–148. | DOI | MR | Zbl

M. Gruber and G.R. Raidl, Variable neighborhood search for the bounded diameter minimum spanning tree problem. In P. Hansen, N. Mladenovic, J.A.M. Pérez, B.M. Batista, and J.M. MorenoVega, editors, Proc. of the 18th Mini Euro Conference on Variable Neighborhood Search, pages 1–11, Tenerife, 2005.

Y. Haimes, L. Ladson and D. Wismer, On a bicriterion formulation of the problems of integrated system identification and system optimization. IEEE Trans. Syst. Man Cybern. SMC 1 (1971) 296–297. | MR | Zbl

G.Y. Handler, Minimax location of a facility in an undirected graph. Transp. Sci. 7 (1978) 287–293. | DOI | MR

J.-M. Ho, D.T. Lee, C.-H. Chang and K. Wong, Minimum diameter spanning trees and related problems. SIAM J. Comput. 20 (1991) 987–997. | DOI | MR | Zbl

J. Lemesre, C. Dhaenens and E.G. Talbi, Parallel Partitioning Method (PPM): A new exact method to solve bi-objective problems. Comput. Oper. Res. 34 (2007) 2450–2462. | DOI | Zbl

D.R. Lima, A.C. Santos and D.J. Aloise, Um algoritmo evolucionário NSGA-II para resolver o problema bi-objetivo da árvore geradora de custo e diâmetro mínimos. In XVI Congreso Latino-Iberoamericano de Investigación Operativa, XLIV Simpósio Brasileiro de Pesquisa Operacional (CLAIO-SBPO), pages 689–699, 2012.

A. Lucena, C. Ribeiro and A.C. Santos, A hybrid heuristic for the diameter constrained minimum spanning tree problem. J. Glob. Optim. 46 (2010) 363–381. | DOI | MR | Zbl

M.V. Marathe, R. Ravi, R. Sundaram, S.S. Ravi, D.J. Rosenkrantz and H.B. Huntiii, Bicriteria network design problems. J. Algor. 28 (1998) 142–171. | DOI | MR | Zbl

C.E. Miller, A.W. Tucker and R.A. Zemlin, Integer programming formulations and Traveling Salesman Problems. J. ACM 7 (1960) 326–329. | DOI | MR | Zbl

T.F. Noronha, C.C. Ribeiro and A.C. Santos, Solving diameter-constrained minimum spanning tree problems by constraint programming. Int. Trans. Oper. Res. 17 (2010) 653–665. | DOI | MR | Zbl

G.R. Raidl and B.A. Julstrom, Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem. In Proc. of the 18th ACM Symposium on Applied Computing, pages 747–752, Melbourne (USA), 2003.

C. Requejo and E. Santos, Greedy heuristics for the diameter-constrained minimum spanning tree problem. J. Math. Sci. 161 (2009) 930–943. | DOI | MR | Zbl

S. Saha and R. Kumar, Bounded-diameter MST instances with hybridization of multi-objective EA. Int. J. Comput. Appl. 18 (2011) 17–25.

A.C. Santos, D.R. Lima and D.J. Aloise, Modeling and solving the bi-objective minimum diameter-cost spanning tree problem. J. Glob. Optim. (2013) 1–22. | MR

A.C. Santos, A. Lucena and C.C. Ribeiro, Solving diameter constrained minimum spanning tree problem in dense graphs. Lect. Notes Comput. Sci. 3059 (2004) 458–467. | DOI

F. Sourd and O. Spanjaard, A multiobjective Branch-and-Bound framework: Application to the biobjective spanning tree problem. INFORMS J. Comput. 20 (2008) 472–484. | DOI | MR | Zbl

S. Steiner and T. Radzik, Computing all efficient solutions of the biobjective minimum spanning tree problem. Comput. Oper. Res. 35 (2008) 198–211. | DOI | MR | Zbl

E.L. Ulungu and J. Teghem, The two Phases Method: An efficient procedure to solve bi-objective combinatorial optimization problems. Foundations of Computing and Decision Sciences 20 (1995) 149–165. | MR | Zbl

M. Visée, J. Teghem, M. Pirlot and E.L. Ulungu, Two-Phases Method and Branch and Bound procedures to solve the bi-objective knapsack problem. J. Glob. Optim. 12 (1998) 139–155. | DOI | MR | Zbl

A. Zhou, B.-Y. Qu, H. Li, S.-Z. Zhao, P.N. Suganthan and Q. Zhang, Multiobjective evolutionary algorithms: A survey of the state of the art. Swarm and Evolutionary Computation 1 (2011) 32–49. | DOI

G. Zhou and M. Gen, Genetic algorithm approach on multi-criteria minimum spanning tree problem. Eur. J. Oper. Res. 114 (1999) 141–152. | DOI | Zbl

C. Zopounidis and P.M. Pardalos, Handbook of multicriteria analysis, vol. 103. Springer (2010). | Zbl

Cité par Sources :