Hva er heltall lineær programmering?

Lineære programmeringsproblemer med heltall oppstår når du prøver å løse lineære systemer mens du spesifiserer at alle de ukjente variablene må være heltal, eller hele tall. Lineære systemer er sett med ligninger som beskriver en situasjon som programmereren prøver å finne en løsning for. De består vanligvis av en ligning som må maksimeres eller minimeres og en eller flere begrensende ligninger som setter grenser for ukjente variabler. For at systemet skal være lineært, må hver begrensning være en lineær ligning; det vil si at den ikke må inneholde forekomster av den ukjente variabelen med eksponenter som er større enn en.

Vanlige lineære systemer kan enkelt løses ved hjelp av en datamaskin. Programmet kan identifisere en løsning ved å finne derivatet og sette det lik null. Den kan da bekrefte at punktet er et maksimum eller minimum ved å sjekke det umiddelbare nabolaget på funksjonen. Så lenge derivatet er definert på hvert punkt langs funksjonen, har datamaskinen bare et begrenset antall mulige løsninger å sjekke.

Lineær programmering blir heltall lineær programmering med tillegg av heltallsbegrensningen. Dette betyr at problemet forblir det samme, men svaret må bestå av heltallverdier for de ukjente verdiene: De må være hele tall. Noen ganger betyr dette at løsningen vil være suboptimal sammenlignet med tilfellet der brøk er tillatt; den reflekterer imidlertid den virkelige verden, der gjenstander ofte kommer i diskrete, udelelige enheter. Dette gjør heltalær programmering viktig for forretningsapplikasjoner, siden firmaer ønsker å maksimere fortjenesten så mye som mulig, men ikke kan velge å selge en brøkdel av et produkt.

Når heltallsbegrensningene er på plass, er problemet med å løse det lineære systemet NP-komplett. Dette betyr at tiden som er nødvendig for en datamaskin for å løse systemet, er ubestemmelig. Med heltallsbegrensninger kan ikke datamaskiner bruke verktøyet til det deriverte, fordi det ikke er noen garanti for at derivatens nullpunkt vil falle på et helt tall. Løsningen vil være heltalet med den høyeste eller laveste verdien av alle heltalene, slik at datamaskinen må sjekke dem alle - en prosess som kan ta uendelig mye tid.

Programmerere har utviklet heuristikker, eller metoder for problemløsning, for å takle kompleksiteten i disse problemene. En metode for å løse helt linjære programmeringsproblemer er grenen og bundet algoritme, der datamaskinen løser en serie problemer relatert til den opprinnelige en for å begrense det tilgjengelige verdiområdet til en løsning. For komplekse problemer kan dette imidlertid ta lang tid.