Voir la source de Problème de couverture par ensembles

[[File:SetCover.svg|vignette|Exemple d'une instance du problème de couverture par ensembles.]]
En [[informatique théorique]], le '''problème de couverture par ensembles''' ('''''Set Cover problem''''' en anglais<ref>cette traduction française est notamment présente dans la traduction de {{harv|Vazirani 2001}} (voir [http://perso.ens-lyon.fr/nicolas.schabanel/livre_approx.html la table des matières sur le site de Nicolas Schabanel (traducteur)]) </ref>) est un problème d'[[algorithmique]] particulièrement important car c'est l'un des [[21 problèmes NP-complets de Karp]] {{harv|Karp 1972}}.

Étant donné un [[ensemble]] ''A'', on dit qu'un élément ''e'' est couvert par ''A'' si ''e'' appartient à ''A''. Étant donné un ensemble ''U'' et une famille ''S'' de sous-ensembles de ''U'', le problème consiste à couvrir tous les éléments ''U'' avec une sous-famille de ''S'' la plus petite possible.

Une version plus générale consiste à assigner des poids aux éléments de ''S'', et à chercher la sous-famille de poids minimal.

== Exemple introductif ==

On considère un ensemble de cinq éléments à couvrir : <math>U=\{1,2,3,4,5 \}</math>. On considère les sous-ensembles : <math>\{2,4\}, \{3,4\}, \{4,5\}</math> et <math>\{1,2,3\}</math>. On essaye de couvrir tous les éléments avec des sous-ensembles. Par exemple <math>\{1,2,3\}, \{3,4\}, \{4,5\}</math> est une couverture, puisque chaque élément est dans au moins un des sous-ensembles. La couverture qui utilise le moins de sous-ensembles est <math>\{4,5\},\{1,2,3\}</math>, c'est donc cette couverture que l'on cherche à calculer.

== Définition formelle ==

Le [[problème de décision]] est le suivant :
: Entrée : un entier <math>k</math>, un ensemble <math>U</math> fini et <math>S</math> un sous-ensemble de l'ensemble des parties de <math>U</math>
: Question : existe-il un sous-ensemble <math>T</math> de <math>S</math>, de taille inférieure à <math>k</math>, tel que l'union des éléments présents dans les sous-ensembles de <math>T</math> est égale à <math>U</math> ?

Le problème d'optimisation associé consiste à minimiser le nombre de sous-ensembles utilisés.

Le problème se généralise à une version pondérée : à chaque ensemble <math>s \in S</math> on associe un poids <math>c(s)</math>, et le but est de minimiser la somme des poids de la couverture.

== Propriétés algorithmiques et complexité ==

=== NP-complétude ===
Le problème de couverture par ensembles est [[NP-difficile]] (et [[NP-complet]] dans sa forme décisionnelle). Une des preuves classiques est une réduction du [[problème de couverture par sommets]].

=== Formulation sous forme de programme linéaire ===

Il est fructueux d'exprimer ce problème comme un problème d'[[optimisation linéaire en nombres entiers]].

En prenant une variable <math>x_S</math> pour chaque sous-ensemble, le programme linéaire naturel est le suivant :

<center>
{|
| minimiser : 
| <math>\sum_{S \in \mathcal S}x_S</math>
|
| (Minimiser le nombre de sous-ensembles)
|-
| tel que : 
| <math>\sum_{S\colon e \in S} x_S \geqslant 1 </math>
| <math>\forall e\in \mathcal U</math>
| (Tous les éléments sont couverts)
|-
|
| <math>x_S \in \{0,1\}</math>
| <math>\forall S\in \mathcal S</math>.
| (Chaque sous-ensemble est, ou bien dans la couverture, ou bien pas)
|}
</center>

Si l'on associe un poids <math>c(S)</math> à chaque ensemble, le problème devient :

<center>
{|
| minimiser : 
| <math>\sum_{S \in \mathcal S}c(S) \cdot x_S</math>
|
| (Minimiser le poids total des sous-ensembles)
|-
| tel que : 
| <math>\sum_{S\colon e \in S} x_S \geqslant 1 </math>
| <math>\forall e\in \mathcal U</math>
| (Tous les éléments sont couverts)
|-
|
| <math>x_S \in \{0,1\}</math>
| <math>\forall S\in \mathcal S</math>.
| (Chaque sous-ensemble est, ou bien dans la couverture, ou bien pas)
|}
</center>

=== Relations avec d'autres problèmes algorithmiques ===

* Le [[problème de couverture de sommets]] est un cas particulier de ce problème, sur un [[théorie des graphes|graphe]].
* Le problème dual du problème de couverture par ensembles est le [[set packing]].
* Le [[problème de la couverture exacte]] est le même problème mais avec une contrainte supplémentaire : les éléments de l'univers ne doivent être couverts qu'une seule fois.
* Le [[problème de couverture maximale]] est le même problème mais avec une contrainte supplémentaire : les éléments de l'univers ne doivent être couverts qu'un nombre maximal de fois.

== Algorithmes ==
=== Algorithmes d'approximation ===
Le problème de couverture par ensemble étant NP-complet, de nombreux [[algorithme d'approximation|algorithmes d'approximation]] ont été inventés. On peut citer en exemple l'[[algorithme glouton]], un algorithme de ''dual fitting'', un algorithme par arrondi à partir du [[optimisation linéaire|programme linéaire]], et un [[schéma primal-dual]]<ref>{{Approximation algorithms (Vazirani)}}, chap. 2, 13, 14 et 15.</ref>. On peut analyser l'algorithme glouton avec la [[méthode des poids multiplicatifs]]<ref name=AroraHK>
{{article
| titre=The Multiplicative Weights Update Method: a Meta-Algorithm and Applications
| auteur1= [[Sanjeev Arora]] | auteur2= Elad Hazan |auteur3= Satyen Kale
| périodique=[[Theory of Computing]]
| volume=8 | numéro=1| passage=121-164
|année =2012
|lire en ligne= https://theoryofcomputing.org/articles/v008a006/v008a006.pdf
}}</ref>. Le gap d'intégralité du LP est logarithmique.

Il existe des résultats sur la difficulté d'approximation du problème, dus d'abord à [[Carsten Lund|Lund]] et [[Mihalis Yannakakis|Yannakakis]]<ref>{{harvnb |Lund|Yannakakis|1994}}</ref>
puis [[Uriel Feige|Feige]]<ref>{{harvnb|Feige|1998}}</ref>, puis [[Ran Raz|Raz]], [[Shmuel Safra|Safra]], [[Noga Alon|Alon]] et Moshkovitz. Ce dernier résultat donne une borne inférieure de <math>c\cdot\ln{n}</math>, où <math>c</math> est une constante, sous l'hypothèse [[problème P=NP|P différent de NP]]<ref>{{harvnb|Raz|Safra|1997}}</ref>{{,}}<ref>{{harvnb|Alon|Moshkovitz|Safra|2006}}</ref>. Ces résultats sont basés sur les [[Système de preuve interactive|preuves interactives]] et le [[théorème PCP]]<ref>Voir par exemple l'introduction de l'article de Lund et Yannakakis.</ref>.

=== Algorithmes heuristiques ===

Des techniques pour résoudre les problèmes de couverture comprennent les méthodes exactes, la programmation mathématique, et des  méthodes heuristiques et métaheuristiques, les [[algorithmes génétiques]] ou [[Algorithme mémétique|mémétiques]]. Parmi ces méthodes, certains algorithmes métaheuristiques peuvent résoudre des cas volumineux du problème de couverture en un temps raisonnable. Leurs hybridations avec d'autres techniques donnent des résultats encore meilleurs, tant dans les applications de référence que dans le monde réel<ref name="BrévilliersLepagnot2018">{{article|nom1=Brévilliers|prénom1=Mathieu|nom2=Lepagnot|prénom2=Julien|nom3=Idoumghar|prénom3=Lhassane|nom4=Rebai|prénom4=Maher|nom5=Kritter|prénom5=Julien|titre=Hybrid differential evolution algorithms for the optimal camera placement problem|journal=Journal of Systems and Information Technology|volume=20|numéro=4|année=2018|pages=446–467|issn=1328-7265|doi=10.1108/JSIT-09-2017-0081}}</ref>{{,}}<ref name="PinardMoalic2020">
{{article
|nom1=Pinard|prénom1=Maxime
|nom2=Moalic|prénom2=Laurent
|nom3=Brévilliers|prénom3=Mathieu
|nom4=Lepagnot|prénom4=Julien
|nom5=Idoumghar|prénom5=Lhassane|titre=A Memetic Approach for the Unicost Set Covering Problem
|journal = Lecture Notes in Computer Science
|titre volume =  Learning and Intelligent Optimization (LION 2020)
|volume=12096|année=2020|pages=233–248|issn=0302-9743|doi=10.1007/978-3-030-53552-0_23}}</ref>.

== Importance du problème et historique ==

Ce problème d'optimisation combinatoire peut être lié à un large éventail d'applications du monde réel, par exemple la programmation des équipes<ref name="Balas1983">{{chapitre|auteur1= E. Balas|titre = A class of location, distribution and scheduling problems: modeling and solution methods
|titre ouvrage = Proceedings of the Chinese-U.S. Symposium on Systems Analysis
|collection = Wiley Series on Systems Engineering and Analysis
|éditeur = Wiley |année = 1983 | isbn = 978-0-471-87093-7}}.</ref>, la localisation d'installations<ref name="FarahaniAsgari2012">{{article|nom1=Farahani|prénom1=Reza Zanjirani|nom2=Asgari|prénom2=Nasrin|nom3=Heidari|prénom3=Nooshin|nom4=Hosseininia|prénom4=Mahtab|nom5=Goh|prénom5=Mark|titre=Covering problems in facility location: A review|journal=Computers & Industrial Engineering|volume=62|numéro=1|année=2012|pages=368–407|issn=0360-8352|doi=10.1016/j.cie.2011.08.020}}</ref>
, les problèmes de logistique urbaine<ref name="BoschettiManiezzo2015">{{article|nom1=Boschetti|prénom1=Marco|nom2=Maniezzo|prénom2=Vittorio|titre=A set covering based matheuristic for a real-world city logistics problem|journal=International Transactions in Operational Research|volume=22|numéro=1|année=2015|pages=169–195|issn=0969-6016|doi=10.1111/itor.12110}}</ref> et le placement optimal des caméras<ref name="KritterBrévilliers2019">{{article|nom1=Kritter|prénom1=Julien|nom2=Brévilliers|prénom2=Mathieu|nom3=Lepagnot|prénom3=Julien|nom4=Idoumghar|prénom4=Lhassane|titre=On the optimal placement of cameras for surveillance and the underlying set cover problem|journal=Applied Soft Computing|volume=74|année=2019|pages=133–153|issn=1568-4946|doi=10.1016/j.asoc.2018.10.025}}</ref>{{,}}
<ref name="BrévilliersLepagnot2018" />

[[Vijay Vazirani]] dit dans son livre {{harv|Vazirani 2001}}, que «l'étude de ce problème a permis le développement de techniques qui ont ensuite été utilisées dans tout le domaine [des algorithmes d'approximation]»<ref>En anglais : ''a problem whose study led to the development of fundamental techniques for the entire field''.</ref>.

== Bibliographie ==

* {{Approximation algorithms (Vazirani)}}
* {{Reducibility Karp 1972}}
* {{article
 | langue = en
 | nom = Chvátal | prénom = Václav | lien auteur = Václav Chvátal
 | titre = A Greedy Heuristic for the Set-Covering Problem.
 | journal =  Mathematics of Operations Research
 | volume = 4 | numéro = 3  | passage = 233-235
 | année = 1979 
 }}
* {{article 
 | nom1=Alon | prénom1=Noga | lien auteur1 = Noga Alon 
 | nom2=Moshkovitz | prénom2=Dana 
 | nom3=Safra | prénom3=Shmuel | lien auteur3=Shmuel Safra 
 | titre=Algorithmic construction of sets for k-restrictions 
 | éditeur=ACM 
 | année=2006 
 | périodique=ACM Trans. Algorithms 
 | volume=2 | numéro=2 | passage=153-177 
 | issn=1549-6325 | doi=10.1145/1150334.1150336}}.
* {{article 
 | nom1=Feige | prénom1=Uriel 
 | titre = A threshold of ln n for approximating set cover 
 | année=1998 
 | périodique=Journal of the ACM | lien périodique = Journal of the ACM 
 | volume=45 | numéro=4 | passage=634-652
 | issn=0004-5411| doi=10.1145/285055.285059}}.
* {{article
 | nom1=Lund | prénom1=Carsten 
 | nom2=Yannakakis | prénom2=Mihalis | lien auteur2=Mihalis Yannakakis
 | titre=On the hardness of approximating minimization problems
 | éditeur=ACM 
 | périodique=Journal of the ACM
 | année=1994
 | volume=41 | numéro=5 | passage=960-981
 | issn=0004-5411 | doi=10.1145/185675.306789}}.
* {{chapitre
 | nom1=Raz | prénom1=Ran
 | nom2=Safra | prénom2=Shmuel | lien auteur2=Shmuel Safra
 | titre chapitre =A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP
 | titre ouvrage =STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing | éditeur=ACM 
 | isbn=978-0-89791-888-6 
 | année=1997 
 | passage=475-484}}.
* {{Article |prénom1=Daniel |nom1=Berend |prénom2=S. |nom2=Mamana |titre=A probabilistic algorithm for vertex cover |périodique=Theoretical Computer Science |volume=983 |numéro article=114306 |date=2024-02-01  |doi=10.1016/j.tcs.2023.114306 }}

== Notes et références ==
<references />
{{Palette 21 problèmes NP-complets de Karp}}{{Portail|informatique théorique}}

[[Catégorie:Problème NP-complet|Couverture par ensemble]]