Heltals linjär programmeringsproblem uppstår när man försöker lösa linjära system samtidigt som man specificerar att alla okända variabler måste vara heltal eller heltal. Linjära system är uppsättningar av 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 restriktion vara en linjär ekvation; det vill säga den får inte innehålla några instanser av den okända variabeln med exponenter 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 derivatan och sätta den lika med noll. Den kan sedan verifiera att punkten är ett maximum eller minimum genom att kontrollera dess omedelbara grannskap på funktionen. Så länge som derivatan är definierad vid varje punkt längs funktionen, har datorn endast ett begränsat antal möjliga lösningar att kontrollera.
Linjär programmering blir heltalslinjär programmering med tillägg av heltalsbegränsningen. Det betyder att problemet förblir detsamma, men svaret måste bestå av heltalsvärden för de okända värdena: de måste vara heltal. Ibland betyder detta att lösningen kommer att vara suboptimal jämfört med det fall då fraktioner är tillåtna; det reflekterar dock den verkliga världen, där föremål ofta kommer i diskreta, odelbara enheter. Detta gör heltals linjär programmering viktig 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 väl är på plats är problemet med att lösa det linjära systemet NP-komplett. Det betyder att den tid som krävs för en dator att lösa systemet är obestämd. Med heltalsbegränsningar kan datorer inte använda verktyget för derivatan eftersom det inte finns någon garanti för att nollpunkten för derivatan kommer att falla på ett heltal. Lösningen blir det heltal med det högsta eller lägsta värdet av alla heltal, så datorn måste kontrollera dem alla – en process som kan ta oändligt lång 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 linjära heltalsproblem är gren- och bunden algoritm, där datorn löser en serie problem relaterade till den ursprungliga för att begränsa det tillgängliga värdeintervallet till en lösning. För komplexa problem kan detta dock ta lång tid.