Karma Tamsayılı Doğrusal Programlama (MILP)

Karma tamsayılı doğrusal programlama (MILP), min c^T x + d^T y s.t. Ax + By ≤ b, x ≥ 0, y ∈ Z^p_+ kanonik formundaki problem sınıfıdır; burada x ∈ R^n sürekli ve y ∈ Z^p tamsayı karar değişkenleridir. Tamsayı kısıtı çoğunlukla ikili y ∈ {0,1}^p (binary) biçiminde belirir ve mantıksal kararları (yatırım yap/yapma, makine aç/kapat, rota kullan/kullanma, ürün-tedarikçi-zaman ataması) modeller. Sabit-maliyet, ayrık miktar/lot büyüklüğü, disjonksiyon ve big-M formülasyonları tamsayı değişkenleri zorunlu kılar. Karmaşıklık: MILP NP-hard sınıfındadır (Cook 1971 SAT indirgemesi, Karp 1972'nin 21 NP-tam probleminin çoğu MILP olarak ifade edilebilir); sürekli LP gevşetmesi (y'nin tamsayı kısıdını kaldırıp y ≥ 0 yapma) polinom zamanda çözülür ve alt sınır (minimizasyon için) verir. Klasik çözüm algoritması Land ve Doig (1960) tarafından önerilen branch-and-bound — LP gevşetmesini çöz, kesirli y_i değişkeninde dallandır, sınır kötüleşen alt-ağaçları buda. Gomory (1958) fraksiyonel kesimler, Padberg ve Rinaldi (1991) genel kesim üreten branch-and-cut çerçevesini olgunlaştırdı; modern çözücüler cutting plane (Gomory, lift-and-project, MIR, cover), node presolve, primal heuristics (feasibility pump, RINS), conflict analysis ve parallel branch-and-bound katmanlarını birleştirir. Pratik MILP modelleri tesisat yeri seçimi (Fixed Charge Facility Location), vehicle routing, üretim-çizelgeleme, atama, paketleme, ağ tasarımı, portföy seçimi (kardinalite kısıtı) ve enerji unit-commitment problemlerini kapsar.