Discretization based solution approaches for the circle packing problem
Çember paketleme problemi için ayrıklaştırma temelli çözüm yaklaşımları
- Tez No: 680411
- Danışmanlar: DR. ÖĞR. ÜYESİ 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: 2021
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 69
Özet
Bu tezde, verilen bir grup çemberi içeren en küçük konteynerin bulunmasını amaçlayan çember paketleme problemi ele alınmıstır. Çember paketleme problemi konveks olmayan ikinci dereceden kısıtlı karesel programlama problemi olarak ele alınabilir ve zor bir problem olarak bilinir. Bu problem gıda, otomotiv, tekstil ve kimya sektörleri gibi çok farklı alanlarda uygulamalara sahiptir. Ilgili problem için konteynerin yarıçapı üzerinden yarılama metoduna dayalı yinelemeli bir çözüm yöntemi gelistirilmistir. Algoritmanın her adımında problemin kısıtlanmıs ve gevsetilmis versiyonu için ayrıklastırılmıs konteyner üzerinde tanımlanmıs iki farklı karma tamsayılı dogrusal programlama gösterimi olusturulmustur. Kısıtlanmıs versiyonda, orijinal problemde verilen çemberlerin merkezlerinin yerlestirilebilecegi sürekli alan ayrıklastırma sonucu elde edilen karelerin köse noktalarına kısıtlanmıstır. Benzer sekilde, çember merkezlerinin aday kareler tarafından içerildigi varsayılarak gevsetilmis versiyon insa edilmistir. Ayrıca, çember paketleme probleminin kendine özgü özellikleri kullanılarak bazı analitik çıkarımlar yapılmıs ve gelistirilen yönteminin elde edilen bilgilerle beslenmesi saglanmıstır. Gelistirdigimiz algoritmanın basarımının belirlenmesi için, literatürdeki örnekler kullanılarak bir deneysel çalısma gerçeklestirilmis ve elde edilen sonuçlar raporlanmıstır. Deneysel çalısmada, gelistirilen çözüm yönteminin basarım analizi için orijinal problem için gelistirilen dogrusal olmayan programlama gösterimi BARON ve Gurobi çözücüleri kullanılarak çözdürülmüs ve algoritmayla karsılastırılmıstır. Ayrıca, otomotiv endüstrisinden bir gerçek hayat problemi için gerçeklestirilen çalısma detaylandırılmıstır.
Özet (Çeviri)
In this thesis, we study the Circle Packing Problem (CPP), which involves packing a set of circles into the smallest surrounding container. This problem can be cast as a nonconvex quadratically constrained quadratic program with reverse convex constraints, which is difficult to solve in general. The CPP arises in different application areas such as automobile, textile, food, and chemical industries. For this problem, we propose an iterative solution approach based on a bisection-type algorithm on the radius of the surrounding container. At each iteration, the algorithm solves two different mixed-integer linear programming formulations proposed for a restricted and a relaxed version of the original problem over the discretized surrounding container. In the restricted version, the centers of the circles can only be located at the candidate points in each cell. By changing some properties of the restricted version, we also construct a relaxed version of the original problem. We also added an enhancement to the algorithm that exploits the special structure of CPP. We perform a computational study in order to evaluate the performance of our algorithm. We compare the results from our algorithm with those from both BARON and Gurobi that solve the original nonlinear formulation, and also with the results of other methods from the literature. In addition, we examine a case study from a real life problem from the automobile industry, which is solved to a small optimality gap.
Benzer Tezler
- Ayrık optimizasyon problemlerinin çözümü için Jaya algoritması tabanlı yeni yaklaşımlar
Jaya algorithm based new approaches for solving discrete optimization problems
MURAT ASLAN
Doktora
Türkçe
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKonya Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. MESUT GÜNDÜZ
- Yeraltı sularında radyonüklid transportunun çizgiler yöntemi ile modellenmesinde açık ve kapalı zaman ayrıklaştırma yöntemlerinin karşılaştırılması
Comparıson of explicit and implicit temporal discretization methods in modelling groundwater radionuclide transport with the method of lines
FURKAN ÖZYİĞİT
Yüksek Lisans
Türkçe
2024
EnerjiBursa Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ TAYFUN TANBAY
- Yüksek basınç gradyanlı akışın sayısal modellenmesi
A numerical study on high pressure gradient flows
ALAZ TALAY
Yüksek Lisans
Türkçe
2015
Gemi Mühendisliğiİstanbul Teknik ÜniversitesiGemi İnşaatı ve Gemi Makineleri Mühendisliği Ana Bilim Dalı
PROF. DR. ÖMER GÖREN
- Bazı kuantum mekaniksel sistemlerinin bilgisayar benzetişimi
Computer simulation of some quantum mechanical systems
ENDER ÖZTAŞ
Yüksek Lisans
Türkçe
1997
Mühendislik Bilimleriİstanbul Teknik ÜniversitesiMatematik Mühendisliği Ana Bilim Dalı
PROF. DR. METİN DEMİRALP
- Rosenau-RLW denkleminin çözümü için sonlu fark yöntemi üzerine temellenmiş bir nümerik şema
Based on the finite difference method for the solution of the Rosenau-RLW equation a numerical diagram
TUBA KARADAŞ
Yüksek Lisans
Türkçe
2023
Matematikİnönü ÜniversitesiMatematik Ana Bilim Dalı
PROF. DR. SELÇUK KUTLUAY
PROF. DR. YUSUF UÇAR