Nondominated points of biobjective mixed-integer programming problems
Iki amaçlı karışık tamsayılı programlama problemlerinin nondominated noktaları
- Tez No: 367661
- Danışmanlar: PROF. DR. METİN TÜRKAY
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2014
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 110
Özet
Ayrık noktalar, açık/kapalı ya da yarı-açık/yarı-kapalı doğru parçası ya da eğrilerden oluşan“Nondominated frontier”, iki amaçl karışık tamsayılı doğrusal ya da doğrusal olmayan programlama (BOMILP) problemlerinde amaç alanını belirlemede sıklıkla kullanılır. Bazı araştırmacılar nondominated frontier'de bulunan karmaşıklıklar azaltmak için bu problemlerin belli türlerini incelemiştir. Bazı algoritmalar da nondominated setin altkümesini bulmayı önermiştir. Doğrusal olmayan süreçlere ve sistemlere ait pek çok matematiksel model geliştirilmiş ve bu modeller epsilon kısıtı (epsilon constraint), ağırlıklı toplam (weighted sum) ve minimum uzaklık (minimum distance) gibi yöntemler kullanılarak çözülmüştür. Bu tez BOMILP problemlerin nondominated frontier'lerindeki bazı olası karmaşıklıkları ve var olan algoritmaların handikaplarını özetler ve genel olarak BOMILP problemlerinin nondominated frontier'i ile birlikte her bir nondominated noktaya ait tamsayılı değişkenlerin değerlerini bulmaya yarayan verimli bir algoritma (ENPOBOMIP) sunar. Bununla birlikte biz bu tezde, doğrusal olmayan network sentez problemleri için genelleştirilmiş disjonktif programlama kullanılarak formüle edilmiş iki amaçlı karışık tamsayılı doğrusal olmayan problemleri inceledik ve augmented epsilon kısıt metodunu ve“logic-based outer approximation”metodunu (OA) baz alarak epsilon-OA adıyla bir algoritma geliştirdik. Önerilen algoritmanın teorik karakterizasyonu ile birlikte elde edilen çozumlerin etkin (efficient) olduğunu gösterdik. ENPOBOMIP ve var olan algoritmalar arasında karşılaştırmalı bir analiz sunabilmek için tanınımş üç problem üzerine deneysel bir çalışma yürüttük ve algoritmamızın çözüm kalitesi ve hesaplama performansı bazında diğerlerinden daha iyi sonuçlar verdiğini gördük. Ek olarak, epsilon-OA algoritmasının verimliliğini OA içeren ve içermeyen augmented epsilon kısıt metodlarını ve de epsilon kısıt metodunu kullanarak kıyasladık. Elde ettiğimiz sonuçlarda, epsilon-OA yönteminin doğrusal olmayan proses networklerini içeren iki amaçlı genelleştirilmiş disjonktif problemleri çozmede çok verimli olduğunu gördük.
Özet (Çeviri)
The nondominated frontier in the objective space of biobjective mixed-integer linear/nonlinear programming problems consists of points that cannot be improved in value of one of the objectives without degrading the other objective value. This frontier is usually very involved consisting of many isolated points and open, closed, or half-open/half-closed line segments or curves. Some researchers considered specific classes of these problems to reduce the complexities in nondominated frontier. Some algorithms have been also proposed to find a subset of nondominated set. Several mathematical models for nonlinear process network problems have been developed and solved using epsilon-constraint, weighted sum, and minimum distance. This thesis outlines some possible complexities in nondominated frontier of BOMILPs and drawbacks of existing algorithms, and proposes an effective algorithm, EnpoBomip, to find the exact nondominated frontier of general BOMILPs, as well as all possible values of integer variables associated with each nondominated point. We also investigate biobjective mixed-integer nonlinear problems that are formulated using generalized disjunctive programming for nonlinear network synthesis problems and propose an effective algorithm, epsilon-OA, based on augmented epsilon-constraint and logic-based outer approximation (OA). We provide theoretical characterization of the proposed algorithm and show that the solutions generated are efficient. An experimental study is conducted to present a comparative analysis between EnpoBomip and the existing algorithms on three well-known problems, and show that our novel algorithm significantly outperforms others with respect to solution quality and computational performance. We also illustrate the effectiveness of epsilon-OA compared to the augmented epsilon-constraint with/without OA, and the traditional epsilon-constraint. Based on the results, epsilon-OA is very effective in solving the biobjective generalized disjunctive programming problems in the synthesis of nonlinear process networks.
Benzer Tezler
- An exact algorithm for biobjective integer programming problems
İki amaçlı tamsayılı programlama problemleri için kesin bir algoritma
SALİHA FERDA DOĞAN
Yüksek Lisans
İngilizce
2019
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. FİRDEVS ULUS
YRD. DOÇ. DR. ÖZLEM KARSU
- Exact solution algorithms for biobjective mixed integer programming problems
İki amaçlı karma doğrusal programlama problemleri için tam sonuç veren algoritmalar
DENİZ EMRE
Yüksek Lisans
İngilizce
2020
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ FİRDEVS ULUS
DR. ÖĞR. ÜYESİ ÖZLEM KARSU
- A mathematical modeling approach for managing regional blood bank operations
Bölgesel kan bankası operasyonlarının yönetimi için matematiksel modelleme yaklaşımı
HALİT METEHAN DİLAVER
Yüksek Lisans
İngilizce
2018
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ ÖZLEM KARSU
DR. ÖĞR. ÜYESİ BENHÜR SATIR
- Shelter site location under demand uncertainty: A chance-constrained multi-objective modeling framework
Rassal talep altında barınak alanı yer seçimi problemi: Olasılıksal kısıtlı çok amaçlı modelleme yaklaşımı
ÖMER BURAK KINAY
Yüksek Lisans
İngilizce
2017
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. BAHAR YETİŞ
- Finding all equitably non-dominated points of multiobjective integer programming problems
Çok amaçlı tam sayılı programlama problemlerinin tüm eşitlikçi baskın noktalarını bulma
SEYİT ULUTAŞ
Yüksek Lisans
İngilizce
2023
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ÖZLEM KARSU