Tamsayılı doğrusal programlama sorunları, bilinmeyen değişkenlerin tamamının tam sayı veya tam sayı olması gerektiğini belirtirken doğrusal sistemleri çözmeye çalışırken ortaya çıkar. Doğrusal sistemler, programcının bir çözüm bulmaya çalıştığı bir durumu tanımlayan denklem setleridir. Genellikle, maksimize edilmesi veya minimize edilmesi gereken bir denklemden ve bilinmeyen değişkenlere sınır koyan bir veya daha fazla kısıtlayıcı denklemden oluşur. Sistemin doğrusal olması için her kısıtlamanın doğrusal bir denklem olması gerekir; yani, üsteleri birden fazla olan bilinmeyen değişken örnekleri içermemelidir.
Düzenli doğrusal sistemler bilgisayar kullanılarak kolayca çözülebilir. Program, türevi bularak ve sıfıra ayarlayarak bir çözümü tanımlayabilir. Ardından, fonksiyondaki yakın çevresini kontrol ederek noktanın maksimum veya minimum olduğunu doğrulayabilir. Türev, fonksiyon boyunca her noktada tanımlandığı sürece, bilgisayarın kontrol etmek için yalnızca sınırlı sayıda olası çözümü vardır.
Doğrusal programlama, tamsayılı kısıtlamanın eklenmesiyle tamsayılı doğrusal programlama haline gelir. Bu, sorunun aynı kaldığı anlamına gelir, ancak cevap bilinmeyen değerler için tamsayı değerlerinden oluşmalıdır: tam sayılar olmalıdır. Bazen, bu, fraksiyonların izin verildiği duruma kıyasla çözümün en düşük seviyede olacağı anlamına gelir; Bununla birlikte, nesnelerin çoğu zaman ayrık ve bölünmez birimler halinde geldiği gerçek dünyanın yansıtıcısıdır. Bu, tamsayılı doğrusal programlamayı iş uygulamaları için önemli kılar, çünkü firmalar kârlarını mümkün olduğunca azami seviyeye çıkarmak ister ancak bir ürünün bir kısmını satmayı seçemez.
Tamsayı kısıtlamaları yerine getirildiğinde, doğrusal sistemin çözümü sorunu NP tamamlandı. Bu, bir bilgisayarın sistemi çözmesi için gereken zamanın belirsiz olduğu anlamına gelir. Tamsayı kısıtlamalarıyla, bilgisayarlar türev aracını kullanamazlar; çünkü türevin sıfır noktasının bir tamsayıya düşeceği garantisi yoktur. Çözüm, tüm tam sayıların dışında en yüksek veya en düşük değere sahip tam sayı olacaktır, bu nedenle bilgisayarın hepsini denetlemesi gerekir - sınırsız zaman alabilir.
Programcılar, bu problemlerin karmaşıklığı ile başa çıkmak için buluşsal yöntemler veya problem çözme yöntemleri geliştirmiştir. Tamsayılı doğrusal programlama problemlerini çözmenin bir yöntemi, mevcut değer aralığını bir çözüme daraltmak için bilgisayarın orjinali ile ilgili bir dizi problemi çözdüğü dal ve sınır algoritmasıdır. Ancak karmaşık sorunlar için bu işlem uzun zaman alabilir.
