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: Derin öğrenme, Doğrusal programlama, Eşitsizlik, Optimizasyon, Deep learning, Linear programming, Inequality, Optimization
- 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ı: Belirtilmemiş.
Ö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 KontrolGeorgıa Instıtute Of TechnologyDOÇ. DR. SANTANU S. DEY
YRD. DOÇ. DR. X. ANDY SUN
- Ayrık zamanlı sistemlerde belli zaman özelliklerini sağlayan optimum PID kontrolör tasarımı
PID design for discrete time control system to satisfy certain time domain specification
UFUKTAN YAVUZ
Yüksek Lisans
Türkçe
1992
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiPROF.DR. M. KEMAL SARIOĞLU
- 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ğiTechnısche Unıversıteıt EındhovenYrd. DOÇ. Dr. LEYLA ÖZKAN
- Optimization-driven data-based constraints identification via explicit mathematical and implicit machine-learning-based constitutives
Açık matematiksel ve örtülü makine öğrenmesi temelli kurucu özgenlerle eniyileme öncüllü veri tabanlı kısıtlar özdeşimi
ABDULLAH ALADAĞ
Yüksek Lisans
İngilizce
2023
Kimya MühendisliğiBoğaziçi ÜniversitesiKimya Mühendisliği Ana Bilim Dalı
PROF. DR. ŞÜKRÜ UĞUR AKMAN
- Graph attention network (GAT) based branching in combinatorial optimization problems
Kombinatoryal optimizasyon problemlerinde graf dikkat ağı (GAT) bazlı dallanma
GÖKHAN MURALİ
Yüksek Lisans
İngilizce
2024
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. METİN TÜRKAY