probleeminstantie

Probleeminstantie is een term uit wiskunde, computerwetenschap en operations research die verwijst naar een concrete invoer van een bepaald probleem. Het omvat alle data die nodig zijn om te bepalen of en hoe een oplossing kan worden gevonden, volgens de formele specificaties van het probleem. Een instantie kan bijvoorbeeld een graf met knopen en gewichten zijn, een set items met gewichten en waarden voor het knapsack-probleem, of een reeks clausules in CNF voor een SAT-probleem.

In tegenstelling tot de algemene probleemstelling, die het doel en de regels van de taak beschrijft, vertegenwoordigt een instantie een specifieke realisatie van die regels met vaste cijfers en structuur. Zo is het kortste-padprobleem een klasse van problemen, maar een graf met vijf knopen en specifieke randen een concrete instantie daarvan.

Instantiemethoden en -toepassingen spelen een centrale rol in onderzoek en praktijk. Instantie-inzicht helpt bij het begrijpen van algoritmeengedrag, het vergelijken van methoden en het inschatten van moeilijkheidsgraad. Kenmerken van een instantie, zoals omvang, densiteit, gewichtverdeling of de structuur van de input, kunnen de prestaties van algoritmes aanzienlijk beïnvloeden.

Instantiaties kunnen op verschillende manieren worden gegenereerd: willekeurig, semiwillekeurig of op basis van echte real-world data. Er bestaan benchmarksets en bibliotheken (voorbeelden variëren per domein) die representatieve of uitdagende instantiessets leveren. Voor beslissingsproblemen gaat een instantie na of er een oplossing voldoet aan een drempel; voor optimalisatieproblemen zoekt men de best mogelijke oplossing en de bijbehorende waarde. Het begrip instantiation is daarmee fundamenteel voor evaluatie en vergelijking van oplossingsmethoden.