Simultaneous column-and-row generation for solving large-scale linear programs with column-dependent-rows

Abstract

Bu tezde genel bir problem sınıfa ait büyük-ölçekli doğrusal programlama problemleriele alınmıştır. Bu problemler genellikle çok sayıda kolon içeren doğrusal programlardaortaya çıkmaktadır. Bu formülasyonların ayırıcı özelliği bağlayıcı kısıtlardır. Bukısıtlar ya formülasyona direk eklenemeyecek kadar çoktur ya da tüm kısıt seti ancaktüm kolonlar yaratıldığında tanımlanabilir. Kolon ve satırlar arasındaki bu bağımlılıknedeniyle bu doğrusal programlama sınıfına kolon-bağlı-satırlar problemleri denilmiştir.Bu problemleri çözebilmek için yeni bir çözüm yöntemi içinde hem kolon hem desatır türetilebilmelidir. Bu tezde önerilen çözüm yaklaşımına eşzamanlı kolon-ve-satırtüretme adı verilmektedir. Öncelikle kolon-bağlı-satırlar problemleri için varsayımlartanımlanmıştır. Bu varsayımlar yeterince geneldir ve literatürde bilinen tüm kolon-bağlı-satırlar problemlerini kapsamaktadır. Ardından önerilen kolon-ve-satır türetmealgoritmasında kullanılan ücretlendirme altproblemleri detaylı olarak tanımlanmıştır.Bunu algoritmanın optimalliği üzerine formal bir tartışma izlemektedir. Ayrıca bu genelalgoritma Lagrange gevşetmesi yaklaşımı ile birleştirilmiştir. Bu birleştirme kolon-ve-satır türetme için farklı bir bakış açısı sağladığı gibi kolon-bağlı-satırlar problemleriniçözmek için yeni bir yöntem ortaya koymaktadır. Önerilen çözüm yöntemleriçok-aşamalı stok kesme problemi, zaman-kısıtlı rotalama problemi ve karesel kümekaplama problemi gibi değişik problemlere uygulanmıştır. Önerilen yaklaşımların performanslarınıdeğerlendirmek için bilgisayısal deneyler yapılmıştır.

In this thesis, we handle a general class of large-scale linear programming problems.These problems typically arise in the context of linear programming formulations withexponentially many variables. The defining property for these formulations is a set oflinking constraints, which are either too many to be included in the formulation directly,or the full set of linking constraints can only be identified, if all variables are generatedexplicitly. Due to this dependence between columns and rows, we refer to this class oflinear programs as problems with column-dependent-rows. To solve these problems, weneed to be able to generate both columns and rows on-the-fly within a new solutionmethod. The proposed approach in this thesis is called simultaneous column-and-rowgeneration. We first characterize the underlying assumptions for the proposed columnand-row generation algorithm. These assumptions are general enough and cover allproblems with column-dependent-rows studied in the literature up until now. We thenintroduce, in detail, a set of pricing subproblems, which are used within the proposedcolumn-and-row generation algorithm. This is followed by a formal discussion on theoptimality of the algorithm. Additionally, this generic algorithm is combined with Lagrangian relaxation approach, which provides a different angle to deal with simultaneouscolumn-and-row generation. This observation then leads to another method tosolve problems with column-dependent-rows. Throughout the thesis, the proposed solutionmethods are applied to solve different problems, namely, the multi-stage cuttingstock problem, the time-constrained routing problem and the quadratic set coveringproblem. We also conduct computational experiments to evaluate the performance ofthe proposed approaches.