Row generation techniques for approximate solution of linear programming problems
Doğrusal programlama problemlerinin yaklaşık çözümü için kısıt türetme teknikleri
- Tez No: 275081
- Danışmanlar: DOÇ. DR. EMRE ALPER YILDIRIM
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2010
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Ü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ı: 86
Özet
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ı.
Özet (Çeviri)
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.
Benzer Tezler
- Türbin kanatlarında jet çarptırmalı soğutmanın deneyselve sayısal olarak incelenmesi
Başlık çevirisi yok
MEHMET BORA KÜÇÜKALPELLİ
Yüksek Lisans
Türkçe
2021
Makine Mühendisliğiİstanbul Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DOÇ. DR. LEVENT ALİ KAVURMACIOĞLU
- 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
- Draman Kefeli (Kefevi) Camisi koruma projesi
Draman Kefeli (Kefevi) Mosque conservation project
DUYGU MELİKE ARSLAN
Yüksek Lisans
Türkçe
2017
Mimarlıkİstanbul Teknik ÜniversitesiMimarlık Ana Bilim Dalı
DOÇ. DR. ZEYNEP ERES ÖZDOĞAN
- Katlıdizeylerin çokdeğişkenliliği yükseltilmiş çarpımlar üçköşegencil gösterilim yoluyla ayrıştırımı: Kavramcıl taban ve uygulayışlar
Tridiagonal folmat enhanced multivariance products representation: Conceptual background and applications
ZEYNEP GÜNDOĞAR
Doktora
Türkçe
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiHesaplamalı Bilimler ve Mühendislik Ana Bilim Dalı
PROF. DR. METİN DEMİRALP
- Alümina ilavesinin Li2O-ZnOSi2 cam ve cam seramiklerinin kristalizasyon davranışı, mekaniksel ve kimyasal özellikleri üzerine etkisi
Başlık çevirisi yok
ELVAN BİLGE ÇUKUR