Optimallik Boşluğu

Optimallik boşluğu, bir optimizasyon probleminde mevcut en iyi fizibil çözümün değeri (upper bound UB, minimizasyonda) ile o noktaya kadar elde edilmiş en iyi dual sınırın (lower bound LB) arasındaki uzaklığı ölçer; iki standart tanım vardır. Mutlak boşluk (absolute gap) = |UB - LB|. Bağıl boşluk (relative gap, MILP literatüründe yaygın varyant) = |UB - LB| / max(ε, |UB|) ya da bazı çözücülerde |UB - LB| / max(ε, |LB|) — paydadaki referansa göre farklılaşır (ε bölme-sıfır koruması). Boşluk sıfır ise mevcut çözüm optimumdur ve algoritma sonlandırılır; pratikte çözücüler kullanıcı tanımlı bir tolerans (genellikle %0.01-%1) altına düşünce 'optimum-yakını' bayrağıyla durur. Boşluğun mantıksal kökeni dualite teorisidir: LP dualitesinde primal-dual fizibil her çift için zayıf dualite UB ≥ LB sağlar, güçlü dualite tüm fizibil LP'ler için bu eşitsizliği eşitliğe çevirir. MILP'de LP gevşetmesi LB üretir, branch-and-bound LB'yi düğüm-bazında günceller, primal sezgiseller ve dallandırma keşifleri UB'yi günceller. Boşluğun yorumu: %5 boşluk 'çözüm değeri optimumdan en fazla %5 daha kötü olabilir' demektir — yani bilinen bir LB altında ek iyileştirme matematiksel olarak imkânsızdır. Pratik kullanım: yöneticiye risk-iletişimi (en kötü-durum gerçekleşmesi), erken-durdurma kararı (uzun branch-and-cut'ta zaman/kalite dengesi), benchmark karşılaştırması (sezgisellerin ne kadar 'iyi' olduğu boşluk üzerinden ölçülür). Doğrusal olmayan dışbükey programlamada Lagrangian dualite gap'i, dışbükey-olmayan programlamada gevşeme gap'i benzer kavramlardır. Standard referanslar Nemhauser ve Wolsey (1988) ve Wolsey (1998).