Wat is integer lineair programmeren?
Lineaire programmeringsproblemen met gehele getallen ontstaan bij het oplossen van lineaire systemen terwijl wordt gespecificeerd dat alle onbekende variabelen gehele getallen of gehele getallen moeten zijn. Lineaire systemen zijn sets vergelijkingen die een situatie beschrijven waarvoor de programmeur een oplossing probeert te vinden. Ze bestaan meestal uit een vergelijking die moet worden gemaximaliseerd of geminimaliseerd en een of meer beperkende vergelijkingen die grenzen stellen aan onbekende variabelen. Om het systeem lineair te maken, moet elke beperking een lineaire vergelijking zijn; dat wil zeggen, het mag geen instanties van de onbekende variabele bevatten met exponenten groter dan één.
Reguliere lineaire systemen kunnen eenvoudig worden opgelost met behulp van een computer. Het programma kan een oplossing identificeren door de afgeleide te vinden en deze op nul in te stellen. Het kan dan verifiëren dat het punt een maximum of minimum is door de onmiddellijke omgeving van de functie te controleren. Zolang de afgeleide op elk punt van de functie wordt gedefinieerd, kan de computer slechts een beperkt aantal mogelijke oplossingen controleren.
Lineaire programmering wordt integer lineaire programmering met de toevoeging van de integer-beperking. Dit betekent dat het probleem hetzelfde blijft, maar het antwoord moet bestaan uit gehele getallen voor de onbekende waarden: het moeten hele getallen zijn. Soms betekent dit dat de oplossing suboptimaal is in vergelijking met het geval waarin fracties zijn toegestaan; het is echter een afspiegeling van de echte wereld, waarin items vaak in discrete, ondeelbare eenheden worden aangeboden. Dit maakt integer lineair programmeren belangrijk voor bedrijfstoepassingen, omdat bedrijven de winst zoveel mogelijk willen maximaliseren, maar niet kunnen kiezen om een fractie van een product te verkopen.
Zodra de gehele beperkingen zijn ingevoerd, is het probleem van het oplossen van het lineaire systeem NP-compleet. Dit betekent dat de tijd die een computer nodig heeft om het systeem op te lossen, onbepaald is. Met beperkingen voor gehele getallen kunnen computers de tool van de afgeleide niet gebruiken omdat er geen garantie is dat het nulpunt van de afgeleide op een geheel getal valt. De oplossing is het gehele getal met de hoogste of laagste waarde van alle gehele getallen, dus de computer zou ze allemaal moeten controleren - een proces dat oneindig veel tijd kan kosten.
Programmeurs hebben heuristieken of methoden voor probleemoplossing ontwikkeld om met de complexiteit van deze problemen om te gaan. Een methode voor het oplossen van integer lineaire programmeringsproblemen is het vertakte en gebonden algoritme, waarbij de computer een reeks problemen oplost die verband houden met de oorspronkelijke om het beschikbare bereik van waarden te beperken tot één oplossing. Voor complexe problemen kan dit echter lang duren.