Un algorithme de programmation par contraintes pour la recherche d'allocations leximin-optimales

Résumé : Dans le cadre de la programmation par contraintes, nous proposons un algorithme résolvant le problème suivant : allouer d'une manière équitable et efficace un ensemble fini d'objets à des agents ayant chacun leurs utilités propres, sous des contraintes d'admissibilité. L'algorithme calcule une allocation maximisant l'ordre leximin sur les profils d'utilités des agents. Nous décrivons de plus le domaine d'application qui a motivé ces travaux : le partage de ressources satellitaires. Nous en extrayons un problème simple et précis d'allocation équitable, qui nous sert de base, grâce à un générateur de jeux de tests, pour l'évaluation de l'algorithme proposé. Deux implantations de l'algorithme sont comparées, l'une en programmation par contrainte «pure», avec Choco [14], l'autre en programmation linéaire mixte avec Cplex [12].
Type de document :
Communication dans un congrès
Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00085776
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 09:39:00
Dernière modification le : mercredi 28 mars 2018 - 14:16:10
Document(s) archivé(s) le : lundi 5 avril 2010 - 22:19:50

Fichier

Identifiants

  • HAL Id : inria-00085776, version 1

Collections

Citation

Sylvain Bouveret, Michel Lemaître. Un algorithme de programmation par contraintes pour la recherche d'allocations leximin-optimales. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006. 〈inria-00085776〉

Partager

Métriques

Consultations de la notice

158

Téléchargements de fichiers

938