Tamsayı Programlama (IP)

Tamsayı programlama (pure IP), min c^T x s.t. Ax ≤ b, x ∈ Z^n_+ kanonik formundaki problem sınıfıdır; tüm karar değişkenleri tamsayıdır. Özel hâli 0-1 (binary) IP — x ∈ {0,1}^n — sırt çantası, atama, küme kapsama, küme bölümleme, gezgin satıcı (TSP), eşleme ve grafik renklendirme gibi kombinatoryal optimizasyon problemlerinin doğal formülasyonudur. Karmaşıklık: pure IP, Karp'ın (1972) 21 NP-tam problem listesinde 0-1 IP olarak yer alır; Lenstra (1983) sabit boyutta IP'nin polinom zamanda çözülebileceğini gösterdi (boyut girdi olarak alındığında pratik değil). Sürekli LP gevşetmesinin tamsayı kısıtı eklendiğinde optimum değer şiddetle değişebilir; integrality gap problemin formülasyon kalitesinin temel göstergesidir. Klasik çözüm algoritması Gomory'nin (1958) kesim düzlemi (cutting plane) yöntemidir: LP gevşetmesini çöz, optimum kesirli ise simpleks tablo bilgisinden tüm tamsayı çözümleri içeren ama mevcut LP optimumunu dışlayan bir kesim üret, ekle, tekrar çöz; sonlu sayıda iterasyonda tamsayı optimum bulunur (teorik). Pratikte Land ve Doig (1960) branch-and-bound, daha sonra branch-and-cut (Padberg ve Rinaldi 1991) çerçevesi daha hızlıdır. Polyhedral teori — Chvátal (1973), Schrijver (1986) — fizibil tamsayı noktalarının dışbükey hull'unu (TSP'nin subtour eliminasyon, blossom eşitsizlikleri gibi) tanımlayan eşitsizliklerle güçlü gevşetme üretir. Pratik uygulama: TSP / araç rotalama (Dantzig, Fulkerson, Johnson 1954), atama, çizelgeleme, ağ akışı, cutting stock (Gilmore ve Gomory 1961), bin packing.