|
 
|
[BD06a] Résolution d'un problème combinatoire fractionnaire par la programmation linéaire mixte
Revue Nationale avec comité de lecture : Journal RAIRO, vol. 40, pp. 97-111, 2006Mots clés: Fractional combinatorial Optimisation, Sum of hyperbolic ratios, Mixed-integer linear programming, Branch-and-bound, Experiments.
Résumé:
Les programmes mathématiques fractionnaires apparaissent dans de nombreux domaines de
la recherche opérationnelle, de l’informatique et de l’économie. Nous considérons dans ce papier
le problème de la maximisation de la somme de plusieurs ratios hyperboliques en variables 0-1
(SRH). Contrairement à la maximisation dÂ’un seul ratio, très peu dÂ’auteurs se sont intéressés Ã
ce problème. Nous proposons deux formulations de SRH par des programmes linéaires en variables
mixtes et deux stratégies différentes pour résoudre ces programmes. La première consiste Ã
appliquer directement un outil général de programmation linéaire en variables mixtes et la deuxième
est fondée sur un algorithme de branch and bound spécifique qui utilise une réécriture plus
précise des programmes en chaque noeud de l’arbre de recherche. Nous présentons également
une résolution de SRH par une méthode heuristique et nous exploitons la solution ainsi obtenue
pour améliorer la première stratégie. Nous présentons des résultats expérimentaux permettant de
comparer les différentes approches.
Mots-clés : Optimisation combinatoire fractionnaire, Somme de ratios hyperboliques, Programmation
linéaire en variables mixtes, Branch-and-bound, Expérimentation.
Equipe:
oc
BibTeX
| @article { | |||
| BD06a, | |||
| title | = | "{Résolution d'un problème combinatoire fractionnaire par la programmation linéaire mixte}", | |
| author | = | "A. Billionnet and K. Djebali", | |
| journal | = | "RAIRO", | |
| year | = | 2006, | |
| volume | = | 40, | |
| pages | = | "97-111", | |
| } | |||
