Finding the non-dominated set of the bi-objective quadratic knapsack problem
İki amaç fonksiyonlu karesel sırt çantası probleminin etkin çözüm kümesini bulma
- Tez No: 346193
- Danışmanlar: PROF. DR. SERPİL SAYIN KARABATI
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2013
- 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ı: 86
Özet
Çok amaçlı optimizasyon gerçek hayat problemlerini modellemeyi ve çözmeyi amaçlar. İki amaç fonksiyonlu problemlerde de çok amaçlı optimizasyonda olduğu gibi etkin çözümler bulunmaya çalışılır. İki amaç fonksiyonlu doğrusal sırt çantası problemi çok sayıda etkin çözümü bulunan zor kabul edilen bir problemdir. Bu problemin karesel versiyonu olan iki amaç fonksiyonlu karesel sırt çantası problemini (İKSP) çalıştık. Literatürdeki uygulamalar yetersiz olduğundan etkin çözüm kümesinin yapısının araştırılmasını hedefledik. Etkin çözümler kümesini bulmak için epsilon kısıt yöntemini, destekli etkin çözümleri bulmak için ise bir doğrusal skalarizasyon yöntemi kullandık. Farklı doluluk değerleri ile rassal yaratılan İKSP'leri CPLEX ile çözüp sonuçları illüstrasyonlar ve kapsama hataları ile raporladık. Doluluk değerleri düşükken doğrusal versiyona yaklaşan İKSP'ler daha çok sayıda etkin çözüme sahiptir. Çözdüğümüz problemler için etkin çözüm sayılarının çok fazla olmadığını gene de yüksek cpu zamanları gerektirdikleri için zor problemler olduklarını belirledik. Destekli etkin çözümlerin ağırlıklı doğrusal skalarizasyon ile bulunmasının daha kolay olduğunu söyleyebiliriz. Bu çözümler tüm çözüm kümesinin bir temsili olarak alındığında ortalama kapsama hatalarının kabul edilebilir seviyede olduğu görülebilir. Bunların yanında, üç köşegenli matrislerle oluşturulmuş İKSP'leri de çözüp raporladık. Bu problemlerin çözümü ise daha kolaydı ve daha az çözüm zamanı gerektirdi.
Özet (Çeviri)
Multi-objective optimization aims to model and solve real life problems. In bi-objective problems, as in the case of multi-objective problems, non-dominated solutions are of interest. The bi-objective linear knapsack problem is well-studied and is known to be a difficult problem with a lot of non-dominated solutions. We have studied the quadratic version of this problem, the bi-objective quadratic knapsack problem (BQKP). Our goal is to investigate the structure of the non-dominated set in BQKP since reports on implementations in the literature are inadequate so far. We use the epsilon constraint method to find non-dominated solutions and use a linear scalarization to obtain supported non-dominated solutions. Randomly generated BQKP's with different percentage of fullness values are solved on the commercial solver CPLEX and results of these problems are reported with illustrations and coverage errors. BQKP's with small percentage of fullness levels resembles more to the linear version of the problem with higher number of non-dominated solutions. We observe that the number of non-dominated solutions is not many for the size of BQKP's we had solved yet the problem is still hard to solve since some of the test problems required long cpu times. Supported non-dominated solutions are relatively easier to obtain by using a weighted sum scalarization. When supported non-dominated solutions are regarded as a representation of the entire non-dominated set, averages coverage errors are at acceptable levels for all problem types studied in this work. BQKP's with tri-diagonal quadratic matrices are also solved and reported. Tri-diagonally structured problems are easier to solve and require less computation time.
Benzer Tezler
- Multi-objective shipment consolidation and dispatching problem
Çok amaçlı yük birlestirme ve sevkiyat problemi
ÖZGE BÜYÜKDEVECİ
Yüksek Lisans
İngilizce
2022
Endüstri ve Endüstri Mühendisliğiİzmir Ekonomi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. SELİN ÖZPEYNİRCİ
DOÇ. DR. NAİL ÖZGÜR ÖZPEYNİRCİ
- 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 algorithms for generating the non-dominated points of multi-objective mixed-integer linear programming problems
Çok-amaçlı karma tamsayı doğrusal programlarının etkin noktalarının üretilmesi için kesin algoritmalar
SEYYED AMİR BABAK RASMİ
Doktora
İngilizce
2018
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. METİN TÜRKAY
- Kan tedarik zinciri ağ tasarımı ve süreç yönetiminde çok aşamalı stokastik programlama modelleri ve çözüm yaklaşımı
Multi-stage stochastic programming models and solution approach for blood supply chain network design and management
GÜL İMAMOĞLU
Doktora
Türkçe
2024
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. Y. İLKER TOPÇU
PROF. DR. NEZİR AYDIN
- Sürdürülebilir toplu konut yerleşmesi tasarımı için Pareto genetik algoritmaya dayalı bir model önerisi: SSPM
A model for sustainable site layout design with pareto genetic algorithm: SSPM
YAZGI AKSOY