In this study, row generation techniques are applied on general linear programming problems with a very large number of constraints with respect to the problem dimension. A lower bound is obtained for the change in the objective value caused by the generation of a specific row. To achieve row selection that results in a large shift in the feasible region and the objective value at each row generation iteration, the lower bound is used in the comparison of row generation candidates. For a warm-start to the solution procedure, an effective selection of the subset of constraints that constitutes the initial LP is considered. Several strategies are discussed to form such a small subset of constraints so as to obtain an initial solution close to the feasible region of the original LP. Approximation schemes are designed and compared to make possible the termination of row generation at a solution in the proximity of an optimal solution of the input LP. The row generation algorithm presented in this study, which is enhanced with a warm-start strategy and an approximation scheme is implemented and tested for computation time and the number of rows generated. Two efficient primal simplex method variants are used for benchmarking computation times, and the row generation algorithm appears to perform better than at least one of them especially when number of constraints is large.

Bu tez çalışmasında, kısıt sayısı problem boyutuna göre çok fazla olan doğrusal programlama problemleri üzerinde kısıt türetme teknikleri uygulandı. Eklenen bir kısıtın amaç fonksiyon değerinde ortaya çıkardığı değişim için bir alt sınır değeri hesaplanabileceği ortaya kondu. Her kısıt türetme adımında, problemin olurlu bölgesinde büyük bir daralma ve amaç fonksiyon değerinde büyük bir değişim sağlayabilmek için bu alt sınır hesabı kısıt türetme adaylarının karşılaştırılması için kullanıldı. Problem çözümüne hızlı bir başlangıç yapabilmek için, ilk doğrusal programlama alt probleminin kısıtlarının etkin bir biçimde seçimini sağlayacak yöntemler araştırıldı. İlk alt problem çözümünün asıl doğrusal programlama probleminin olurlu bölgesine yakın olmasını sağlayacak, mümkün olduğunca küçük bir başlangıç kısıt alt kümesinin elde edilmesinde kullanılabilecek yöntemler değerlendirildi. Asıl problemin en iyi çözümüne yeterince yakın bir çözüm noktasında kısıt türetimine son verebilmek için yaklaşım tasarımları ele alındı ve karşılaştırıldı. Bu çalışmada sunulan kısıt türetme algoritması bir hızlı başlangıç tekniği ve yaklaşım tasarısıyla geliştirilerek bilgisayar üzerinde uygulandı. Bu uygulama algoritmanın hesaplama süresinin ve türettiği kısıt sayısının sınanmasında kullanıldı. Hesaplama zamanları iki verimli temel simpleks yöntemi ile karşılaştırıldı. Karşılaştırmalara göre, kısıt türetme algoritmasının bu iki yöntemden en az birinden, özellikle kısıt sayısı büyük olduğunda, daha hızlı çalıştığı ortaya çıktı.