Kesme Düzlemi Yöntemi

Kesme düzlemi yöntemi (cutting plane method), tamsayılı programlama (IP) ve karma tamsayılı programlama (MIP) problemlerinde LP gevşemesini iteratif olarak **geçerli eşitsizlikler** (valid inequalities) ile sıkıştıran, böylece fizibıl tamsayı çözümlerini hariç tutmadan LP gevşemesinin fraksiyonel optimumunu kesen klasik bir tekniktir. Yöntemi Gomory (1958) tamsayılı programlama için (Gomory fractional cut) ve Gomory (1960) karma tamsayı varyantı için (Gomory mixed-integer cut) ortaya atmıştır. Algoritma şudur: LP gevşemesi çözülür; eğer çözüm tamsayıysa optimum bulundu; aksi takdirde fraksiyonel çözümü hariç tutan ancak tüm tamsayı fizibıl noktaları koruyan bir kesim üretilir, modele eklenir, LP yeniden çözülür; bu döngü çözüm tamsayı olana kadar sürer. Kesim aileleri probleme özgüdür: knapsack cover cuts, flow cover cuts, clique cuts (graph coloring/IP), mixed-integer rounding (MIR), Chvátal-Gomory cuts, lift-and-project cuts (Balas, Ceria ve Cornuéjols 1993), TSP için Padberg-Rinaldi (1991) subtour ve comb eşitsizlikleri. Saf Gomory kesimi pratikte yavaş yakınsadığı için modern uygulamalar kesimleri branch-and-bound ile birleştirir (branch-and-cut, Padberg ve Rinaldi 1991) — bu modern MIP çözücülerin temel mimarisidir. Kesim üretimi otomatiktir; kullanıcı çoğunlukla görmez. Nemhauser ve Wolsey (1988), Wolsey (1998) ve Cornuéjols (2008) referans okumalardır.