Exact decomposition algorithms for nonlinear location and hub location problems
Doğrusal olmayan yer seçimi ve ana dağıtım üssü seçimi problemleri için kesin ayrıştırma algoritmaları
- Tez No: 531965
- Danışmanlar: PROF. SİNAN GÜREL
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2018
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 190
Özet
Zor optimizasyon problemlerini çözmek için kesin çözüm algoritmaları geliştirmek, yöneylem araştırması literatüründe önemli konulardan biridir. Bu tez kapsamında, seçilen doğrusal olmayan yer seçimi ve ana dağıtım üssü seçimi problemleri için Benders ayrıştırma algoritmasına dayanan kesin çözüm yöntemleri geliştirdik. Son ele alınan problemde, hem amaç fonksiyonu hem de kısıtlar doğrusal değil iken, ilk ve ikinci problem sadece doğrusal olmayan kısıtlar içermektedir. Önerdiğimiz ayrıştırma algoritmalarında, problemlere özgü olurluluk ve optimallik kesileri türettik. Benders ayrıştırma algoritmasına ek olarak, kablosuz yerel ağ tasarım problemi için karma tamsayılı ikinci dereceden konik bir formulasyon önerdik. Deneysel çalışmalarımızda, konik formulasyonun performansının Benders ayrıştırma algoritması temelli algoritmaların performansından daha iyi olduğunu gösterdik. Bu önerilen formulasyon, ele alınan kısıtların yapısı aynı kaldığı sürece tüm konveks amaç fonksiyonlarının bulunduğu modeller için geçerlidir. İkinci problem, (0-1) karar değişkenlerinin birbirleriyle çarpılmasından oluşan doğrusal olmayan kapasite kısıtları içermektedir. Bu problem için, içinde çeşitli iyileştirme algoritmalarının kullanıldığı dal-kontrol algoritması önerdik. Son problemde hem doğrusal olmayan amaç fonksiyonunu hem de doğrusal olmayan kısıtları Benders ayrıştırma algoritması içerisinde çözdük. İkinci ve son problem için önerdiğimiz Benders ayrıştırma algoritması temelli çözüm yaklaşımlarının performansının ticari çözücülerden daha iyi olduğunu gösterdik.
Özet (Çeviri)
Developing exact solution algorithms to solve difficult optimization problems is one of the most important subjects in the operations research literature. In this dissertation, we develop Benders decomposition based exact solution algorithms (BDTAs) for handling non-linearity in three selected nonlinear integer location/hub location problems. The first and second problem include nonlinear capacity constraints, while in the last problem, both objective function and the capacity constraints are nonlinear. In our decomposition algorithms, we used problem specific, logic based feasibility and optimality cuts. In addition to BDTAs, we propose a MISOCP reformulation for solving the nonlinear integer model, which arises in wireless local area networks, to optimality by using commercial solvers. Our computational study demonstrates that the performance of MISOCP is better than that of Benders decomposition based algorithms. This reformulation is general for any convex objective function as long as the constraints have the same structure as those in the first problem that we studied in this dissertation. The second problem includes nonlinear constraints in which product of binary variables exist and we develop a branch-and-check algorithm with several enhancement steps. In the last problem, nonlinear terms in the objective function and constraints are handled in Benders decomposition scheme. Our computational study demonstrates that the performance of Benders decomposition type algorithm is better than that of commercial solvers for especially difficult instances.
Benzer Tezler
- Uncapacitated multiple allocation hub location problem under congestion
Trafik sıkışıklığı altında çok atamalı kapasite kısıtsız ana dağıtım üssü yerleşim problemi
ÇAĞRI ÖZGÜN KİBİROĞLU
Doktora
İngilizce
2019
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. YUSUF İLKER TOPCU
- Stochastic emergency medical service vehicle location problem: Equity, performance evaluation and mathematical models
Stokastik acil tıbbi hizmet aracı konum problemi: Eşitlik, performans değerlendirme ve matematiksel modeller
MUHARREM ALTAN AKDOĞAN
Doktora
İngilizce
2023
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ZEYNEP PELİN BAYINDIR
PROF. DR. CEM İYİGÜN
- Nonlinear mixed integer programming models and algorithms for fair and efficient large scale evacuation planning
Adil ve etkin büyük ölçekli tahliye planlaması için doğrusal olmayan karışık tamsayılı modeller ve algoritmalar
VEDAT BAYRAM
Doktora
İngilizce
2015
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. HANDE YAMAN PATERNOTTE
- Quantitative models for decision making in reverse logistics network design
Tersine lojistik ağ tasarımı kararlarında sayısal modeller
AYŞE CİLACI TOMBUŞ
Doktora
İngilizce
2009
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Bölümü
DOÇ. NECATİ ARAS
- Mathematical programming approaches for two problems in energy systems
Enerji sistemlerinden iki problem için matematiksel programlama yaklaşimlari
BAHAR CENNET OKUMUŞOĞLU
Yüksek Lisans
İngilizce
2022
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ BURAK KOCUK
DR. ÖĞR. ÜYESİ BESTE BAŞÇİFTCİ