Sütun oluşturma - Column generation

Sütun oluşturma veya gecikmeli sütun oluşturma , büyük doğrusal programları çözmek için etkili bir algoritmadır .

Kapsayıcı fikir, birçok doğrusal programın tüm değişkenleri açıkça dikkate alamayacak kadar büyük olmasıdır. Buradaki öncül, değişkenlerin çoğunun temel olmayacağı ve optimum çözümde sıfır değerini alacağıdır. Bu nedenle, problemi çözerken teoride yalnızca bir değişken alt kümesinin dikkate alınması gerekir. Sütun oluşturma, bu fikri yalnızca amaç işlevini geliştirme potansiyeline sahip değişkenleri üretmek için kullanır - yani, negatif düşük maliyetli değişkenleri bulmaktır (genelliği kaybetmeden sorunun bir minimizasyon sorunu olduğu varsayılır ).

Çözülen problem iki probleme ayrılır: ana problem ve alt problem. Ana problem, yalnızca değişkenlerin bir alt kümesinin dikkate alındığı orijinal problemdir. Alt problem, yeni bir değişkeni tanımlamak için oluşturulan yeni bir problemdir. Alt problemin amaç işlevi, mevcut ikili değişkenlere göre yeni değişkenin maliyetinin düşürülmesidir ve kısıtlamalar, değişkenin doğal olarak oluşan kısıtlamalara uymasını gerektirir.

Süreç aşağıdaki gibi işliyor. Ana problem çözüldü - bu çözümden, ana problemdeki kısıtlamaların her biri için çifte fiyat elde edebiliyoruz. Bu bilgi daha sonra alt problemin amaç fonksiyonunda kullanılır. Alt problem çözüldü. Alt problemin objektif değeri negatif ise, negatif indirgenmiş maliyetli bir değişken tanımlanmıştır. Bu değişken daha sonra ana probleme eklenir ve ana sorun yeniden çözülür. Ana problemi yeniden çözmek, yeni bir ikili değerler kümesi oluşturacaktır ve süreç, hiçbir negatif azaltılmış maliyet değişkeni tanımlanmayana kadar tekrarlanır. Alt problem, negatif olmayan düşük maliyetli bir çözüm döndürür, ana problemin çözümünün optimal olduğu sonucuna varabiliriz.

Çoğu durumda, bu, daha önce inatçı olduğu düşünülen büyük doğrusal programların çözülmesine izin verir. Bunun başarıyla kullanıldığı klasik bir problem örneği, stok kesme problemidir . Doğrusal programlamada bu tür bir yaklaşımı kullanan belirli bir teknik, Dantzig-Wolfe ayrıştırma algoritmasıdır. Ek olarak, sütun oluşturma, mürettebat çizelgeleme , araç rotası ve kapasitif p-medyan problemi gibi birçok soruna uygulanmıştır .