Geri Dön

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

  1. Tez No: 275081
  2. Yazar: AHMED BURAK PAÇ
  3. Danışmanlar: DOÇ. DR. EMRE ALPER YILDIRIM
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2010
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    Türkçe

    2021

    Makine Mühendisliğiİstanbul Teknik Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    DOÇ. DR. LEVENT ALİ KAVURMACIOĞLU

  2. Draman Kefeli (Kefevi) Camisi koruma projesi

    Draman Kefeli (Kefevi) Mosque conservation project

    DUYGU MELİKE ARSLAN

    Yüksek Lisans

    Türkçe

    Türkçe

    2017

    Mimarlıkİstanbul Teknik Üniversitesi

    Mimarlık Ana Bilim Dalı

    DOÇ. DR. ZEYNEP ERES ÖZDOĞAN

  3. 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

    Türkçe

    2018

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Hesaplamalı Bilimler ve Mühendislik Ana Bilim Dalı

    PROF. DR. METİN DEMİRALP