Optimization-based bound tightening and new valid inequalities for the pooling problem
Havuzlama problemi için eniyileme tabanlı sınır sıkılaştırma yöntemi ve yeni geçerli eşitsizlikler
- Tez No: 784744
- Danışmanlar: DOÇ. DR. BURAK KOCUK
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 94
Özet
Havuzlama problemi, petrokimya endüstrisinde sıklıkla karşılaşılan NP-zor bir problemdir. Bu problem, üç katmanlı bir ağ üzerinde doğrusal olmayan ve dışbükey olmayan bir akış problemi olarak modellenebilir. Bu model, farklı özelliklere sahip hammaddelerin bazı ara tanklarda karıştırılmasını ve ardından istenen özelliklere sahip son ürünleri elde edilmesi için tekrar karıştırılmasını içerir. Havuzlama probleminin analizi oldukça aktif bir araştırma alanıdır ve önerilen farklı kesin gösterimler, gevşetmeler ve kısıtlamalar vardır. Buna karşın mevcut yöntemler havuzlar arasında akışlara izin verilen genelleştirilmiş havuzlama problemi örneklerinde çok iyi performans göstermemektedir. Bu çalışmada, iyi bilinen ve yakın zamanda önerilen {\it Girdi Tabanlı} ve {\it Çıktı Tabanlı} Akış Gösterimlerini temel alan bir çalışma yapıyoruz. Bu problemin doğrusal olmayan ve dışbükey olmayan yapısıyla başa çıkmak için literatürde önerilen farklı Doğrusal Programlama (LP) gevşetmeleri ile Karma Tamsayılı Programlama (MIP) gevşetmelerini ve kısıtlamalarını sunuyoruz. Yapısal olarak daha güçlü olan ve eşiz sınır kalitesi açısından öncekilerden daha iyi performans gösteren yeni LP gevşetmeleri geliştiriyoruz. Ayrıca, sınırların kalitesini artırmak için Yeniden Gösterim ve Doğrusallaştırma Tekniği'ne dayanan geçerli eşitsizlikler üretiyoruz. Buna ek olarak, Eniyileme Tabanlı Sınır Sıkılaştırma (OBBT) yöntemini kullanarak, literatürdeki havuzlama problemi örneklerinin düğüm ve kenar kapasiteleri için güçlü üst ve alt sınırlar üretiyoruz. Havuzlama problemi örneklerini farklı yöntemlerle çözmek için yeni sınırların etkisini araştırıyoruz. Test sonuçları, OBBT'nin çözüm kalitesini artırmaya ve ticari bir küresel eniyileme çözücüsünün hesaplama süresini önemli ölçüde azaltmaya yardımcı olduğunu göstermektedir. Ayrıca gevşetmelerin ve kısıtlamaların daha sıkı sınırlar elde etmesine yardımcı olur. Son olarak literatürdeki madencilik problemi örneklerini genelleştirilmiş havuzlama probleminin özel bir durumu olarak ele alıyor ve özel yapılarından yararlanarak farklı düğümlerin ve kenarların sınırlarını iyileştirmek için ucuz ve basit bir sınır sıkılaştırma yöntemi geliştiriyoruz. Hesaplama sonuçları bu yöntemin elde edilen eşiz sınırların kalitesini önemli ölçüde artırdığını göstermektedir.
Özet (Çeviri)
The pooling problem is a classical NP-hard problem in the chemical process and petroleum industries. This problem is modeled as a nonlinear, nonconvex network flow problem with a three-layer network; it involves blending the raw materials (source) with different specifications in some intermediate tanks (pool) and then mixing them again to obtain the final products (terminal) with desired specifications. The analysis of the pooling problem is quite an active research area, and there are different exact formulations, relaxations, and restrictions proposed. However, the state-of-the-art does not perform very well on generalized pooling problem instances in which flow streams between pools are allowed. In this work, we review the well-known and recently proposed {\it Source-Based} and {\it Terminal-Based} Multi-Commodity Flow Formulations. We present different Linear Programming (LP) relaxations as well as Mixed-Integer Programming (MIP) relaxations and restrictions proposed in the literature to deal with the nonlinearity and the nonconvexity of this problem. We develop new LP relaxations which are stronger by construction and outperform the previous ones in terms of the dual bound quality. Also, we generate valid inequalities based on the Reformulation Linearization Technique to improve the quality of the bounds. In addition, by making use of Optimization-Based Bound Tightening (OBBT), we produce strong upper and lower bounds on node and arc capacities of the pooling problem instances from the literature. We investigate the effect of new bounds to solve the pooling problem instances by different methods. Test results show that the OBBT helps to improve the solution quality and reduce the computational time of a commercial global optimization solver significantly. It also helps the relaxations and restrictions to obtain tighter bounds. Moreover, we consider the mining problem instances of the literature as a special case of the generalized pooling problem and develop a cheap and simple bound tightening method to improve the bounds of different nodes and arcs by exploiting their special structure. Computational results also show this method improves the quality of the obtained dual bounds significantly.
Benzer Tezler
- Global optimization methods for optimal power flow and transmission switching problems in electric power systems
Başlık çevirisi yok
BURAK KOCUK
Doktora
İngilizce
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGeorgia Institute of TechnologyDOÇ. DR. SANTANU S. DEY
YRD. DOÇ. DR. X. ANDY SUN
- Risk-aware model based control and applications on whey separation processes
Başlık çevirisi yok
MUHAMMED BAHADIR SALTIK
Doktora
İngilizce
2018
Elektrik ve Elektronik MühendisliğiTechnische Universiteit EindhovenYrd. DOÇ. Dr. LEYLA ÖZKAN
- Beamforming design for network multiple-input multiple-output (MIMO) systems with multiple cooperating base stations
Birden çok ortak çalışan baz istasyonu içeren çok girdili çok çıktılı veri ağları için hüzme biçimlendirme tasarımı
FEHMİ EMRE KADAN
Doktora
İngilizce
2021
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. ALİ ÖZGÜR YILMAZ
- Dağıtık bağlı veri sorgulama motorlarında performans yönetimi
Performance management in federated linked data query engines
BURAK YÖNYÜL
Yüksek Lisans
Türkçe
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. RIZA CENK ERDUR
- Lagrangean heuristics for the capacitated multi-facility location allocation problem
Sığa kısıtlı yer seçimi-taşıma problemlerinin çözümü için lagrange gevşetmesi tabanlı sezgisel yöntemler
BUKET AVCI
Yüksek Lisans
İngilizce
2007
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF.DR. KUBAN ALTINEL