Vad är heltal linjär programmering?

Linjära programmeringsproblem med heltal uppstår när man försöker lösa linjära system samtidigt som man anger att alla okända variabler måste vara heltal eller heltal. Linjära system är uppsättningar ekvationer som beskriver en situation för vilken programmeraren försöker hitta en lösning. De består vanligtvis av en ekvation som måste maximeras eller minimeras och en eller flera begränsande ekvationer som sätter gränser för okända variabler. För att systemet ska vara linjärt måste varje begränsning vara en linjär ekvation; det vill säga den får inte innehålla några fall av den okända variabeln med exponenter som är större än en.

Vanliga linjära system kan enkelt lösas med hjälp av en dator. Programmet kan identifiera en lösning genom att hitta derivatet och ställa det lika med noll. Den kan sedan verifiera att punkten är ett maximalt eller minimum genom att kontrollera dess omedelbara närområde på funktionen. Så länge derivatet definieras vid varje punkt längs funktionen, har datorn bara ett begränsat antal möjliga lösningar att kontrollera.

Linjär programmering blir heltal linjär programmering med tillägg av heltalsbegränsningen. Detta betyder att problemet förblir detsamma, men svaret måste bestå av heltal för de okända värdena: de måste vara hela siffror. Ibland betyder detta att lösningen blir suboptimal jämfört med fallet där fraktioner är tillåtna. det återspeglar emellertid den verkliga världen, där artiklar ofta kommer i diskreta, odelbara enheter. Detta gör heltal linjär programmering viktigt för affärsapplikationer, eftersom företag vill maximera vinsten så mycket som möjligt men inte kan välja att sälja en bråkdel av en produkt.

När heltalsbegränsningarna är på plats är problemet med att lösa det linjära systemet NP-komplett. Detta innebär att tiden som krävs för en dator för att lösa systemet är obestämd. Med heltalsbegränsningar kan datorer inte använda derivatets verktyg eftersom det inte finns någon garanti för att derivatets nollpunkt kommer att falla på ett heltal. Lösningen kommer att vara heltalet med det högsta eller lägsta värdet av alla heltal, så datorn måste kontrollera dem alla - en process som kan ta en oändlig tid.

Programmerare har utvecklat heuristik, eller metoder för problemlösning, för att hantera komplexiteten i dessa problem. En metod för att lösa heltaliga linjära programmeringsproblem är grenen och den bundna algoritmen, i vilken datorn löser en serie problem relaterade till det ursprungliga för att begränsa det tillgängliga värdet för en lösning. För komplexa problem kan det dock ta lång tid.