TAMSAYILI DOĞRUSAL PROGRAMLAMA PROBLEMLERİNİN ÇÖZÜMÜNDE LAGRANGE YÖNTEMİ (LAGRANGE RELAXATION)

Optimizasyon problemleri genel olarak iki kategori içinde ele alınmaktadır. Problemlerin bir kısmı "kolay" olarak adlandırılan ve çözüm süreleri polinom zamanla sınırlanan problemler olup, geriye kalan büyük bir grup "zor" olarak adlandırılan ve üstel zaman gerektiren problemlerden oluşmaktadır.1 Tamsayılı programlama problemlerinin büyük bir kısmı zor olarak adlandırılan ikinci grup içinde yer almaktadır. Lagrange yöntemi ile problem çözme yaklaşımının 1970'te Held-Karp'm birlikte geliştirdikleri Minimum Maliyetli Ağaç-Gezen Satıcı Problemi uygulaması ile doğduğu kabul edilmektedir2 v e 3. 1970'ten itibaren birçok çalışma gerçekleştirilmiş olup, bu çalışmalarda optimizasyon problemlerinin büyük bir kısmı için, problemi güçleştiren kısıtların çok az sayıda kısıttan ibaret olduğu, bu kısıtların bulunmaması halinde problemin kolayca çözülebilen problemler sınıfına girebileceği ifade edilmiştir. 1974'teki çalışmasında Geoffrion, kısıtların dualize edilmesi olarak ifade edilen yönteme Lagrange Yöntemi (Lagrange Relaxation) adını vermiştir.4 Lagrange Yöntemi ile karmaşık olan orjinal problemi çözümü daha kolay olan bir probleme indirgenmektedir.