Simultaneous column-and-row generation for solving large-scale linear programs with column-dependent-rows
Kolon-bağlı-satır problemlerinin çözümü için eşzamanlı kolon-ve-satır türetme
- Tez No: 309419
- Danışmanlar: DOÇ. DR. Ş. İLKER BİRBİL
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Tam sayılı programlama, Integer programming
- Yıl: 2011
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
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.
Özet (Çeviri)
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.
Benzer Tezler
- The Effect of government price support on wheat farming and wheat marketing in Turkey
Başlık çevirisi yok
GÜNEŞ GÜLSEN ÖZEL
Yüksek Lisans
İngilizce
1987
EkonomiOrta Doğu Teknik ÜniversitesiYöneylem Araştırması Ana Bilim Dalı
PROF. DR. HALİM DOĞRUSÖZ
- İki aşamalı en küçük kareler yöntemi üzerine bir araştırma
Başlık çevirisi yok
SEMRA AKSAKAL
Yüksek Lisans
Türkçe
1986
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
DOÇ. DR. ŞABAN EREN
- Eşanlı (simultane) denklem sistemleri ve Türkiye ayçiçeği piyasasına uygulanması
Başlık çevirisi yok
ÖKKEŞ KULAKOĞLU