Geri Dön

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ı

  1. Tez No: 531965
  2. Yazar: EMİNE GÜNDOĞDU
  3. Danışmanlar: PROF. SİNAN GÜREL
  4. Tez Türü: Doktora
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2018
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

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

    İngilizce

    2019

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. YUSUF İLKER TOPCU

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

    İngilizce

    2023

    Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. ZEYNEP PELİN BAYINDIR

    PROF. DR. CEM İYİGÜN

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

    İngilizce

    2015

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. HANDE YAMAN PATERNOTTE

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

    İngilizce

    2009

    Endüstri ve Endüstri MühendisliğiBoğaziçi Üniversitesi

    Endüstri Mühendisliği Bölümü

    DOÇ. NECATİ ARAS

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

    İngilizce

    2022

    Endüstri ve Endüstri MühendisliğiSabancı Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ BURAK KOCUK

    DR. ÖĞR. ÜYESİ BESTE BAŞÇİFTCİ