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: Belirtilmemiş.
- 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ı: 120
Ö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
- Two-stage cutting stock problems and scheduling extensions
İki-aşamalı stok kesme problemleri ve çizelgeleme uzantıları
ZEYNEP SEZER
Doktora
İngilizce
2018
Endüstri ve Endüstri MühendisliğiBahçeşehir ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. İBRAHİM MUTER
- Sempatik kıyı koruma yapısı olarak kazıklı dalgakıranların düzenli ve düzensiz dalgalar altındaki performanslarının ve üzerine gelen yüklerin incelenmesi
Başlık çevirisi yok
TARKAN MUTLU
Doktora
Türkçe
1998
İnşaat Mühendisliğiİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. M. SEDAT KAPDAŞLI
- Makine öğrenmesi yöntemleri kullanılarak üç boyutlu nokta bulutlarının sınıflandırılması
Classification of three-dimensional point cloud via machine learning methods
KORAY AKSU
Yüksek Lisans
Türkçe
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiGeomatik Mühendisliği Ana Bilim Dalı
PROF. DR. HANDE DEMİREL
- FPGA üzerinde 5G uyumlu düşük yoğunluklu eşlik denetim kod çözücü gerçeklenmesi
Implementation of 5G compatible low density parity check decoder on FPGA
BARIŞ BİLGİLİ
Yüksek Lisans
Türkçe
2022
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. SIDDIKA BERNA ÖRS YALÇIN
PROF. DR. ALİ EMRE PUSANE
- Railway crew capacity planning problem with connectivity considerations in pairings
Eşleşmelerde bağlanılabilirliğin dikkate alındıgı demiryolları ekip kapasite planlama problemi
ALİ ÇETİN SUYABATMAZ
Yüksek Lisans
İngilizce
2012
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. GÜVENÇ ŞAHİN