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ı: Belirtilmemiş.
Ö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 ç oz umlerin 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
- 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
- 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
- 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İŞ
- Çok amaçlı karar verme metodları ve tekstil sanayiinde bir uygulama
Multiple criteria decision making methods and an application to the textile industry
H.EDA ÖZTÜRK
Yüksek Lisans
Türkçe
1992
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiPROF. DR. RAMAZAN EVREN