Infeasibiliteit

Infeasibiliteit is de toestand waarin een wiskundig model geen oplossing heeft die aan alle beperkingen voldoet. In optimalisatie en besliskunde verwijst het naar het onvermogen om een punt te vinden dat aan alle randvoorwaarden voldoet. Bij lineaire of niet-lineaire programmeringsproblemen betekent infeasibiliteit dat de feasible set leeg is.

Oorzaken van infeasibiliteit zijn onder meer tegenstrijdige of te strakke beperkingen, fouten in de modellering of in de ingevoerde data, en inconsistenties tussen verschillende vereisten (bijvoorbeeld integrale en continue beslisvariabelen in combinatie met strikte constraints). Ook kunnen knelpunten ontstaan door discrete keuzes, waardoor geen enkele combinatie aan alle voorwaarden voldoet.

Detectie en diagnose gebeuren vaak met algebraïsche en numerieke methoden. Een veelgebruikte aanpak is de fase-I-procedure van het simplex-algoritme of interior-point methoden, die probeert een fea­sibiliteitsbasis te vinden. Lukt dat niet, dan is het probleem infeasible onder de huidige modelleringskeuzes. Sensitiviteitsanalyses en constraint propagation helpen bij het identificeren welke beperkingen bijdragen aan de infeasibiliteit.

Aanpak omvat het herformuleren van het model, het relaxeren van bepaalde beperkingen, of het introduceren van slack- of surplusvariabelen en penalty-termen. In sommige gevallen kan robuuste of stochastic optimization uitkomst bieden door onzekerheden te modelleren of tolerantiebands toe te staan.

Voorbeeld: als een variabele x zowel voldoet aan x ≥ 3 als aan x ≤ 2, dan is het lineaire programma infeasible. Infeasibiliteit hoeft niet te betekenen dat het hele systeem onbruikbaar is; vaak wijst het op suggesties voor data, aannames of vereisten die herzien moeten worden.