Verzamelingenoverdekking

Gegeven een verzameling U (de universele verzameling), en anderzijds een verzameling S van deelverzamelingen van U, waarvan de vereniging gelijk is aan U. Een verzamelingenoverdekking (set cover) van U bestaat uit een of meer verzamelingen uit S zodanig dat hun vereniging ook gelijk is aan U.

In het vervolg van dit artikel wordt overal overdekking gebruikt in plaats van verzamelingenoverdekking.

Overdekkingsprobleem

Het overdekkingsprobleem (set cover probleem) is een fundamenteel probleem uit de computerwetenschap, waarmee vele plannings- en selectieproblemen gemodelleerd kunnen worden.

Als beslissingsprobleem luidt dit probleem: voor een gegeven getal k, is het mogelijk om met k of minder verzamelingen uit S een overdekking van U te maken? Dit is een NP-volledig probleem.

Het (ongewogen) optimalisatieprobleem vraagt: wat is het kleinste aantal verzamelingen uit S die een overdekking van U vormen? Dit probleem is NP-moeilijk.

In vele gevallen is aan elke verzameling uit S een gewicht of een kost verbonden. Het gewogen overdekkingsprobleem wordt dan: vind een overdekking van U waarvan het totale gewicht zo klein mogelijk is.

Voorbeeld

Stel $U=\{1,2,3,4,5\}$ en de verzameling van deelverzamelingen $S=\{\{1,2,3\},\{2,4\},\{3,4\},\{4,5\}\}$. De vereniging van $S$ is $U$ en is dus een (triviale) overdekking. Maar er bestaat een overdekking met minder verzamelingen uit $S$, namelijk $\{\{1,2,3\},\{4,5\}\}$.

Wiskundige formulering

Veronderstel dat de universele verzameling bestaat uit m elementen: $U=\{u_{1}\dots u_{m}\}$ en dat er n verzamelingen zijn in S: $S=\{S_{1}\dots S_{n}\}$.

De verzameling S kan voorgesteld worden door een matrix A van m rijen en n kolommen, waarbij het element op rij i en kolom j 1 is als u_i een element is van S_j en anders 0. Men zegt dat S_j het element u_i "overdekt". De j-de kolom in A komt dus overeen met de verzameling S_j.

De eventuele kosten zijn reële getallen c₁ ... c_n, behorend bij de verzamelingen S₁ ... S_n.

De overdekking wordt voorgesteld door beslissingsvariabelen x₁... x_n, een per verzameling uit S. Die zijn ofwel 0 ofwel 1; x_j = 1 betekent dat de j-de verzameling deel uitmaakt van de overdekking.

Het ongewogen probleem is een 0-1-lineair programmeringsprobleem:

[1] minimiseer $\sum _{i=1}^{n}x_{i}$

met als beperkingen:

[2] $x_{i}\in \{0,1\}$ en

[3] $\sum _{j=1}^{n}a_{i,j}x_{j}\geqslant 1$ voor $i=1\dots m$.

Deze laatste uitdrukking betekent: de kolommen in A van de verzamelingen die niet geselecteerd zijn voor de overdekking, worden op nul gezet. Er moet echter in elke rij van A minstens een element 1 staan, met andere woorden elk element uit U moet overdekt zijn door minstens een verzameling uit S.

Voor het gewogen probleem wordt de doelfunctie [1]:

[4] minimiseer $\sum _{i=1}^{n}c_{i}x_{i}$

Het ongewogen probleem is dus slechts een bijzonder geval hiervan, namelijk wanneer alle gewichten even groot zijn; dan kunnen ze geschrapt worden uit de doelfunctie.

Toepassingsvoorbeelden

Wat is het minimumaantal voorzieningen dat alle behoeften dekt?

• een klassieke toepassing is het facility location problem, waarin gezocht wordt hoe aan een aantal gespreide "behoeften" of "klanten" (demands) te voldoen met een zo klein mogelijk aantal "voorzieningen" (facilities). De "behoeften" en "voorzieningen" zijn locaties, knooppunten in een netwerk of iets anders. Een voorziening dekt slechts een behoefte als ze voldoende dicht in de buurt van de behoefte ligt (gemeten in afstand of in tijd). Voorzieningen zijn bijvoorbeeld brandweerdepots waarvan verwacht wordt dat de brandweer binnen een bepaalde tijd op de plaats van de behoefte (brandbestrijding) kan zijn. In dit geval is U de verzameling van alle behoeften. Er zijn n mogelijke locaties beschikbaar voor de voorzieningen, die tezamen alle behoeften kunnen dekken. S_j is de verzameling behoeften die voorziening j kan dekken. Het (ongewogen) probleem is: wat is het kleinst aantal voorzieningen dat alle behoeften dekt? Bij een gewogen variant zou c_j de kost kunnen zijn om de voorziening j op te richten. (Een meer complexe vorm van het probleem houdt ook rekening met de kost om vanuit voorziening V te voldoen aan behoefte B, wat meestal een functie is die stijgt met de afstand ertussen)

• in de spoeddienst van een ziekenhuis moet een aantal dokters beschikbaar zijn om elke ingreep te kunnen uitvoeren die nodig kan zijn. Stel U is de verzameling van alle mogelijke ingrepen. Er zijn n dokters. S_j is de verzameling van ingrepen die dokter j mag uitvoeren. Wat is het kleinst aantal dokters dat moet aanwezig zijn, opdat elke ingreep kan uitgevoerd worden door minstens een dokter? In een "gewogen" versie is de "kost" van een dokter zijn/haar salaris en het probleem is die dokters te selecteren die alle ingrepen kunnen uitvoeren en waarvoor de totale salariskost zo laag mogelijk is. Dit soort selectieproblemen stelt zich onder meer ook bij luchtvaartmaatschappijen: welke bemanningen toewijzen aan welke vluchten?

• Een voorbeeld op gebied van natuurbehoud: men wenst een aantal gevoelige of bedreigde soorten (of biotopen...) te beschermen door het inrichten van natuurreservaten. Die soorten vormen de verzameling U. Er zijn n terreinen beschikbaar, die elk een of meer van die soorten herbergen. Wat is het minimaal aantal terreinen dat alle beoogde soorten omvat? (In de gewogen versie kleven aan elk terrein kosten, bijvoorbeeld voor aankoop en onderhoud)

Algoritmen

Een algemeen algoritme om een overdekking C te maken, voor het niet-gewogen overdekkingsprobleem, is:

(1) begin met C als lege verzameling

(2) vind een element uit U dat nog niet overdekt is door een verzameling uit C

(3) vind een verzameling uit S die nog niet behoort tot C, en die dat element overdekt. Voeg die verzameling toe aan C

(4) herhaal (2) en (3) zolang er niet-overdekte elementen zijn in U.

De selectiestap (3) kan op allerlei manieren gebeuren. Een gretig algoritme zal die verzameling kiezen die zoveel mogelijk elementen uit U bevat die nog niet overdekt zijn. Maar dit garandeert niet dat de bekomen overdekking minimaal is. Het vinden van het optimum (minimum) is een complex optimalisatieprobleem waarvoor vele algoritmen ontwikkeld zijn, zowel exacte (die echter niet efficiënt zijn voor grote problemen) als benaderende algoritmen die gebruikmaken van heuristieken en metaheuristieken om in een eindig aantal stappen en in een acceptabele tijd een goede, maar niet noodzakelijk de optimale, oplossing te vinden. Voor realistische problemen met vaak meerdere duizenden variabelen en verzamelingen volstaat dit dikwijls.

Het is mogelijk dit probleem te benaderen met LP-relaxatie. Men laat dan de eis dat de onbekenden x₁ ... x_n 0 of 1 zijn los en vervangt die door de beperking 0 ≤ x_j ≤ 1. Het resulterende lineaire programmeringsprobleem kan efficiënt opgelost worden, maar men bekomt dan niet-gehele waarden voor de onbekenden. Uitgaande van die oplossing kan men met een branch and bound-algoritme de optimale waarde van het originele probleem zoeken.

Varianten

• wanneer men in de voorwaarden van het probleem (formule [3]) de ongelijkheid ≥ vervangt door gelijkheid:

$\sum _{j=1}^{n}a_{i,j}x_{j}=1$

dan bekomt men het set partition problem: nu mag elk element uit U slechts door een enkele verzameling uit S overdekt worden. Dat wil zeggen dat de overdekking een partitie van U moet zijn; dit is een exacte overdekking.

• soms wordt geëist dat de bovenstaande som ≥ 2 is in plaats van ≥ 1. In het "facility location"-probleem betekent dit dat elke behoefte door minstens twee voorzieningen moet gedekt worden, met andere woorden er wordt reservecapaciteit of redundantie ingebouwd.

• het maximum k-coverage-probleem stelt een bovengrens aan het aantal verzamelingen dat kan behoren tot de overdekking. Daardoor kan het zijn dat niet elk element uit U kan overdekt worden. Het probleem is dan: selecteer k deelverzamelingen uit S, zodanig dat hun vereniging zoveel mogelijk elementen uit de universele verzameling overdekt, of in het gewogen geval, waarbij aan elk element uit de universele set U een gewicht is toegekend: zodanig dat het totale gewicht van de elementen die ze overdekken zo groot mogelijk is.

Bronnen, noten en/of referenties