Geodesic
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

Voir la notice de l'article provenant de la source Numdam

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
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :