<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>In this paper, we have done a rapid and very simple algorithm that resolves the multiple objective combinatorial optimization problem. This, by determining a basic optimal solution, which is a strong spanning tree constructed, according to a well-chosen criterion. Consequently, our algorithm uses notions of Bellman’s algorithm to determine the best path of the network, and Ford Fulkerson’s algorithm to maximise the flow value. The Simplex Network Method that permits to reach the optimality conditions manipulates the two algorithms. In short, the interest of our work is the optimization of many criteria taking into account the strong spanning tree, which represents the central angular stone of the network. To illustrate that, we propose to optimize a bi-objective distribution problem.</p>
</abstract>

In this paper, we have done a rapid and very simple algorithm that resolves the multiple objective combinatorial optimization problem. This, by determining a basic optimal solution, which is a strong spanning tree constructed, according to a well-chosen criterion. Consequently, our algorithm uses notions of Bellman’s algorithm to determine the best path of the network, and Ford Fulkerson’s algorithm to maximise the flow value. The Simplex Network Method that permits to reach the optimality conditions manipulates the two algorithms. In short, the interest of our work is the optimization of many criteria taking into account the strong spanning tree, which represents the central angular stone of the network. To illustrate that, we propose to optimize a bi-objective distribution problem.

New Algorithm Permitting the Construction of an Effective Spanning Tree

Département de Recherche Opérationnelle, Faculté de Mathématiques

Université des sciences et de la Technologie Houari Boumedienne, Bab-Ezzouar (Algérie). Works at Faculté des Hydrocarbures et de la Chimie, Université M’Hamed Bougara

Faculté des Mathématiques, / Laboratoire « AMCD&RO »

Foundations of Computing and Decision Sciences

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"New Algorithm Permitting the Construction of an Effective Spanning Tree"}

In this paper, we have done a rapid and very simple algorithm that resolves the multiple objective combinatorial optimization problem. This, by determining a...

New Algorithm Permitting the Construction of an Effective Spanning Tree

Publié en ligne: 05 oct. 2023

Pages: 313 - 329

Reçu: 12 juin 2022

Accepté: 10 mars 2023

DOI: https://doi.org/10.2478/fcds-2023-0012

Mots clés
Bi-objective minimum cost flow problem, Network flows, Linear programming, Minimum spanning tree, Efficient extreme point

© 2023 Salima Nait Belkacem et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

New Algorithm Permitting the Construction of an Effective Spanning Tree

Publié en ligne: 05 oct. 2023

Pages: 313 - 329

Reçu: 12 juin 2022

Accepté: 10 mars 2023

DOI: https://doi.org/10.2478/fcds-2023-0012

Mots clésBi-objective minimum cost flow problem, Network flows, Linear programming, Minimum spanning tree, Efficient extreme point

© 2023 Salima Nait Belkacem et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Mots clés
Bi-objective minimum cost flow problem, Network flows, Linear programming, Minimum spanning tree, Efficient extreme point