Un algorithme primal de génération de colonnes pour le problème du p-Centre-Somme

Abstract

Définitions -- Généralisation et propriétés -- Formulations mathématiques -- Dégénérescence des relaxations linéaires -- Comparaison théorique des bornes -- Propriétés spécifiques du (PL2) -- Résolution du problème -- Justification de la génération de colonnes -- Décomposition -- Propriétés et résolution du problème auxiliaire -- Résolution de la relaxation linéaire -- Suggestion d'une énumération implicite -- Règle de branchement -- Sélection des usagers -- Convergence de l'énumération -- Qualité du branchement -- Rapprochement avec les bornes supérieures générales -- Stratégies de branchement -- Modification de la matrice du (PM) -- Résolution du problème auxiliaire sous le branchement -- Problème auxiliaire sous un branchement général -- Méthode de résolution -- Résultats -- Bancs d'expérimentation -- Comparaison expérimentale des bornes -- Comparaison avec la littérature -- Performance de la règle de branchement -- Effet du degré d'intersection entre I et J -- Effet de la dimension des instances -- Complément et différentes extensions -- Extension aux coûts d'affectation non linéaires -- Fonctions du type logarithmique et exponentiel -- Fonctions du type par paliers -- Intégration de contraintes à même les Lj et le Ej -- Généralisation du modèle -- Nouvel algorithme pour le problème de Recouvrement -- Application au domaine de localisation continue -- Interprétation étendue du modèle.