An exact method to generate all nondominated spanning trees
Boumesbah, Asma1 ; Chergui, Mohamed El-Amine1
1 Faculty of Mathematics, USTHB, RECITS Laboratory, O2M team, Algiers, Algeria.
RAIRO - Operations Research - Recherche Opérationnelle, Special issue - Advanced Optimization Approaches and Modern OR-Applications, Tome 50 (2016) no. 4-5, pp. 857-867.

We describe an exact method to generate the nondominated set of the minimum spanning tree problem with at least two criteria. It is a separation and construction based method whose branching process is done with respect to edges belonging to at least two cycles of a given graph, inducing a step of constructing linear constraints that progressively break cycles while respecting the connectivity of the resulting graph. This has the effect of partitioning the initial graph into subgraphs, each of which corresponds to a discrete multi-objective linear program allowing to find the nondominated set of spanning trees. Randomly generated instances with more than two criteria are provided that show the efficiency of the method.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2016060
Classification : 90C10, 90C27, 90C29
Mots-clés : Minimum spanning tree, integer linear programming, multiple objective linear optimization, combinatorial optimization, branch and bound method
Boumesbah, Asma 1 ; Chergui, Mohamed El-Amine 1

1 Faculty of Mathematics, USTHB, RECITS Laboratory, O2M team, Algiers, Algeria. 
@article{RO_2016__50_4-5_857_0,
     author = {Boumesbah, Asma and Chergui, Mohamed El-Amine},
     title = {An exact method to generate all nondominated spanning trees},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {857--867},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {4-5},
     year = {2016},
     doi = {10.1051/ro/2016060},
     zbl = {1358.90110},
     mrnumber = {3570535},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2016060/}
}
TY  - JOUR
AU  - Boumesbah, Asma
AU  - Chergui, Mohamed El-Amine
TI  - An exact method to generate all nondominated spanning trees
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 857
EP  - 867
VL  - 50
IS  - 4-5
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2016060/
DO  - 10.1051/ro/2016060
LA  - en
ID  - RO_2016__50_4-5_857_0
ER  - 
%0 Journal Article
%A Boumesbah, Asma
%A Chergui, Mohamed El-Amine
%T An exact method to generate all nondominated spanning trees
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 857-867
%V 50
%N 4-5
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2016060/
%R 10.1051/ro/2016060
%G en
%F RO_2016__50_4-5_857_0
Boumesbah, Asma; Chergui, Mohamed El-Amine. An exact method to generate all nondominated spanning trees. RAIRO - Operations Research - Recherche Opérationnelle, Special issue - Advanced Optimization Approaches and Modern OR-Applications, Tome 50 (2016) no. 4-5, pp. 857-867. doi : 10.1051/ro/2016060. http://www.numdam.org/articles/10.1051/ro/2016060/

M. Abbas, M.E.-A. Chergui and M. Ait Mehdi, Efficient cuts for generating the nondominated vectors for multiobjective integer linear programming. Int. J. Math. Oper. Res. 4 (2012). | DOI | MR | Zbl

P.M. Camerini, G. Galbiati and F. Maffioli, The complexity of weighted multi-constrained spanning tree problems. Colloquium on the Theory of Algorithms. Edited by L. Lovàsz. North-Holland, Amsterdam (1984) 53–101. | MR | Zbl

C.G. Da Silva and J.C.N. Clìmaco, A note on the computation of ordered supported nondominated solutions in the bi-criteria minimum spanning tree problems. J. Telecomm. Inform. Techn. (2007) 11–15.

J.C.N. Clìmaco, E and A. Martins, bicriterion shortest path algorithm. Eur. J. Oper. Res. 11 (1982) 399–404. | DOI | MR | Zbl

H.W. Corley, Efficient spanning trees, Craveirinha and M. Pascoal, Multicriteria routing models in telecommunication networks-overview and a case study. J. Optim. Theory Appl. 45 (1985) 481–485. | Zbl

H.W. Hamacher and G. Ruhe, On spanning tree problems with multiple objectives. Annal. Oper. Res. 52 (1994) 209–230. | DOI | MR | Zbl

P. Hansen and N. Mladenović, Variable neighborhood search. Comput. Oper. Res. 24 (1997) 1097–1100. | DOI | MR | Zbl

P. Erdös and A. Rényi, On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5 (1960) 17–61. | MR | Zbl

J. B. Kruskal, On the Shortest Spanning Subtree of a Graph and the Travelling Salesman Problem. Proc. Amer. Math. Soc. 7 (1956) 48–50. | DOI | MR | Zbl

C.W. Marshall, Applied graph theory. Wiley-Interscience (1971). | MR | Zbl

M. Özlen and M. Azizoǧlu, Multi-objective integer programming, A general approach for generating all nondominated solutions. Eur. J. Oper. Res. 199 (2009) 25–35. | DOI | MR | Zbl

M. Özlen, B.A. Burton and C.A.G. Macrae, Multi-objective integer programming: An Improved Recursive Algorithm. J. Optim. Theory Appl. 160 (2014) 470–482. | DOI | MR | Zbl

R.C. Prim, Shortest Connection Networks and Some Generalizations. Bell Syst. Tech. J. 36 (1957) 1389–1401. | DOI

F. Sourd and O. Spanjaard, multi-objective branch-and-bound framework. Application to the bi-objective 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

R.E. Steuer, Multiple criteria optimization: theory, computation, and application. Wiley Series Prob. Math. Stat. Appl. Wiley (1986). | MR | Zbl

Cité par Sources :