Speeding up branch and bound algorithm for airline Crew scheduling problem by using machine learning techniques
Makine öğrenme teknikleri kullanarak Crew programlama sorunu için şube ve sınava algoritmasının hızlanması
- Tez No: 565664
- Danışmanlar: DR. ÖĞR. ÜYESİ NAZIM KEMAL ÜRE
- Tez Türü: Yüksek Lisans
- Konular: Havacılık Mühendisliği, İletişim Bilimleri, Aeronautical Engineering, Communication Sciences
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2019
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Uçak ve Uzay Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Uçak ve Uzay Mühendisliği Bilim Dalı
- Sayfa Sayısı: 71
Özet
Büyük ölçekli tamsayılı doğrusal programlama optimizasyon problemlerinin çözülmesi süreci, gurobi ve Cplex gibi en hızlı çözücülerle bile uzun sürer, nispeten büyük ölçekli bir optimizasyon problemini çözmek için 24 saat, hatta birkaç gün gerekebilir. Bu problemlerin sadece parametrelerdeki küçük farklılıklara rağmen günde birkaç kez çözülmesi verimli değildir. Şirketler bu süreci hızlandırarak hem zaman hem de finansal açıdan tasarrufta bulunabilirler. En kötü durumda bile optimizasyon kalitesinin çok küçük bir kısmını feda ederek problemi çok daha hızlı çözmek iyi bir fikirdir. Bazı problemler için en iyiye yakın bir çözüm (tanımlı bir büyüklüğe kadar) vardır ve zamandan tasarruf açısından tercih edilir. Optimizasyon veya matematiksel programlama, birçok disiplinde nicel problemleri çözmek için kullanılan matematiksel ilkeler ve yöntemler topluluğudur. Tamsayılı Doğrusal Programlama (ILP) olan bir tür optimizasyon problemidir. karar değişkenlerinin hepsinin veya bir kısmının ilave bir kısıtlaması tamsayı olmalıdır. Dal ve cilt (B \& B) tamsayılı doğrusal çözmek için en ünlü tekniktir Programlama (ILP) optimizasyon problemleri.B \& B, kökün bütün aday çözümlerden oluştuğu köklü bir ağaç oluşturur. ve yapraklar çözelti alt-kümesini göstermektedir. Genel olarak, dal ve sınır algoritması tüm ağacı geçmeli ve tümünü ziyaret etmelidir. üç arama stratejisinden biri ile en uygun çözümü bulmak için düğümler. Gurobi veya Cplex gibi her çözücü bir veya kombinasyonu izler (yöntemleri) ağaç geçiş yöntemleri düğümleri okumak için. Tam bir ağaç traversi en iyi çözümü verir fakat algoritma algoritması çok zaman alır. Herhangi bir maliyet fonksiyonunu düşünmeden kör davranır. Özel algoritmanın bir katkısı olabileceği yer burasıdır. Özel algoritma, ağacın boyutunu küçük tutacak şekilde çalışır. Arama ağacındaki keşfedilen düğümlerin sayısını mümkün olduğunca düşük tutun. Ayrıca ağaçtaki her düğümle ilgili tüm ayrıntıları sağlar. Özel Şube ve sınır algoritmasının özellikleri, Etkileşimli Yaklaşımı uygulamak için ilk adımları sağlar. İnteraktif yaklaşım bu çalışmada kullanılan ve eniyileştirmenin taklit öğreniminden yararlandığı en önemli yöntemdir. Makine Öğrenmesi, verileri analiz etmek için bir dizi yöntem ve bilgisayarlar için bir yöntemdir geleceği tahmin etmek. Derin Öğrenme, bilgisayarlara ne olduğunu yapmalarını öğreten bir makine öğrenme tekniğidir. doğal olarak insanlara. Bu araştırmanın ilk yaklaşımında (“Doğrudan Yaklaşım”) birkaç tür kullandık Konvolüsyonel Sinir Ağları gibi bu alt alandaki ağların listesi. Üçüncü yaklaşımda kullanılan taklit öğrenme, denetimli öğrenmenin bir çeşididir, ancak bir seferde tek bir vakayı öngörmek yerine, bir sekansı tahmin eder. Takviye Öğrenme, bir Makine Öğrenmesi türüdür ve dolayısıyla Yapay Zeka da bir dalıdır. Makinelerin ve yazılım temsilcilerinin ideal davranışı otomatik olarak belirlemesini sağlar belirli bir bağlamda, performansını en üst düzeye çıkarmak için. Bir RL probleminin unsurlarını tanımlayan anahtar terimler çevre, devlet, ödül, politika ve değerdir. Bu üç yaklaşımı uyguladığımız eldeki sorun, atfedilebilecek büyük çaplı bir mürettebat çizelgeleme problemidir. İkili karar değişkenleriyle bir tamsayılı doğrusal programlama (ILP) problemi, İkili bir tamsayı programlama yapar. Bu çalışma için veriler ilk aşamada hazır olmadığından, kullanılmaya çalışıldı. bazı kriterler ve yöntemlerin nasıl çalıştığını görün. araştırma aldıktan sonra devam etti Ana veriler. Optimizasyon, Makine Öğrenimi yöntemlerinde kullanılan bir teknikti, burada optimizasyon problemlerinde ML tekniklerini kullanmanın yolunu bulmaya ve avantaj elde etmeye çalışıyoruz. Bu teknik, çözümleri tahmin ederek veya problemlerin nasıl çözüleceğini öğrenerek çözme sürecini hızlandırır. Bu çalışmada üç farklı yaklaşım önerildi; Doğrudan Yaklaşım, Yardımcı Yaklaşım ve Etkileşimli Yaklaşım. Doğrudan Yaklaşım, problemi doğrudan sinir ağ modeline girmekten doğrudan çözümleri öngören, böylece eğitim verilerinin çözümlerini öğrenen / ezberleyen ve test setindeki benzer problemlerin (aynı ailedeki problemler) çözümlerini öngören denetimli bir öğrenme yaklaşımıdır. Bu yaklaşımda, veri ön işleme adımında farklı stratejilerle birkaç farklı ağ kullanılmıştır. Genel fikir, çözüm vektörünü elde etmek ve sınırlayıcı matris“A”, maliyet vektörü“c”ve“x”kısıtlama matrisini,“c”maliyet vektörünü ve“x”çözüm vektörünü eğitim ve tahmin için ağa beslemek için kriterleri çözmektir. görünmeyen verilerin çözümleri. Bu yaklaşım çok hızlı ancak çözüm güvenilir değil ve daha iyi bir model geliştirmek için tonlarca veri gerekiyor. İkinci yaklaşım (Yardımcı Yaklaşım), problemin çözümünü kabaca tahmin etmek için derin bir öğrenme modeli kullanır ve daha sonra bu çözümü ticari çözücülere bir başlangıç noktası olarak besler (örn. Gurobi). Bu yöntemde, ilk adımlar (veri oluşturma, eğitim ve test) öncekiyle aynıdır, ancak bu kez test setinin öngörülen çözümü, test set problemlerini çözücünün ilk tohumları olarak ve Bu şekilde, en uygun çözüm için gereken süre kısalır. Umut veren bir yaklaşım olan İnteraktif Yaklaşım, çözücüler tarafından atılan adımları taklit etmek için bir sinir ağı modelini eğitmek için kullanılır. Bu yaklaşım, ticari çözücülerin en uygun çözüme ulaşmak için nasıl davrandıklarını öğrenmek için en gelişmiş algoritmaları kullanır. Önceki iki yaklaşımın aksine, çözücü çözme süreci hakkında daha fazla ayrıntıya ihtiyaç vardır. Sadece gurobi / Cplex'in sağladığı çözüme sahip olmak artık yeterli değil, Dal-Sınır algoritmasında neler olup bittiğine dair detaylar da gereklidir. SCIP Optimization Suite ve GAMS gibi bu bilgileri sağlayan bazı çözücüler / kütüphaneler var ancak bunlardan istenen özellikleri alabilmek için kaynak kodlarını değiştirmek gerekmekte. Ayrıca, bağımsız dal-sınır algoritmaları (çözücüler çerçevesinde) yalnızca çözümler ve bazı işe yaramayan bilgiler verir. Her bir düğümün detayını sağlayan özel bir dal-sınır algoritması yazmak iyi bir fikirdir ve bu yaklaşımın ilk adımıdır.“Davranış Klonlama”, gerekli özelliklerle eğitilir ve Dal ve Sınır algoritmasının her aşamasında çözücünün davranışını taklit eder; bu, üç adımı (Düğüm Dallanması, Düğüm Seçimi ve reddedilen LP'nin çözülmesi) atlayarak dal-sınır algoritmasının çözme zamanının azalmasına neden olur Büyük ölçekli optimizasyon çözme sürecini hızlandırmak, endüstri oyuncuları ve paydaşları için her zaman büyük öneme sahip olmuştur. Bu sorunlar için kapsamlı bir çalışma yapılmış ve elde edilen sonuçlar umut vericidir. Bu çalışmada ele alınan yaklaşımlar arasında, yardımcı ve etkileşimli olanlar daha büyük umut verici sonuçlar vermiş ve büyük ölçekli optimizasyon problemlerinin çözümünde kayda değer bir gelişme göstermiştir. Gelecekteki araştırmalar için, bu soruna yaklaşmak için Ters Takviye Öğrenme (IRL) ve Geometrik Derin Öğrenme (GDL) yöntemlerini kullanma planım var.
Özet (Çeviri)
Solving process of large scale integer linear programming optimization problems is time consuming even by fastest solvers such as gurobi and Cplex, taking 24 hours or even several days to solve a relatively large-scale optimization problem. This process is not efficient for companies which need to solve such these problems several times a day with just slightly difference in parameters. Companies can benefit from speeding up this process both from the time and financial issues. In the worst case, it is still a good idea to solve these optimization problems faster by sacrificing a portion/bit of solution quality. For some problems, a sub-optimal solution (up to a defined magnitude) still works and preferable in terms of time-saving for the solution time. Optimization has been a technique used in Machine Learning methods, here we try to do the way around and get advantages of using ML techniques in optimization problems. This technique will result in speeding up the solving process by predicting the solutions or learning how to solve the problems. Three different approaches were proposed in this study; Direct Approach, Assistive Approach, and Interactive Approach. Starting with (Direct Approach), a supervised learning approach to predict the solutions directly from inputting the problem into neural network model; learn/memorize the solutions of training data and predicting solutions of similar problems (problems in the same family) of the test set. In this approach, several different networks were used with different strategies in data pre-processing. The general idea is to solve benchmarks with the solver to achieve the vector of solutions and feed the constraint matrix“A”, the cost vector“c”as well as the solution vector“x”of Integer Linear Programming problem as the input data to train the network and predict the solutions of unseen data. This approach is so fast, the solution is not reliable and needs tons of data to train a better model. The second approach (Assistive Approach) uses a deep learning model to roughly estimate the solution for the problem and then feed that solution as an initial point to the commercial solvers (e.g. Gurobi). In this method, initial steps (data generation, train and test) are the same as previous one but this time the predicted solution of test set will be the initial seeds of the solver to solve the test set problems which results in boosting the required time to find the optimal solution. A promising approach (Interactive Approach) was taken to train a neural network model to imitate the steps taken by the solvers. This approach uses state-of-the-art algorithms to learn how commercial solvers behave in order to reach an optimal solution. Unlike previous two approaches, it is needed to have more details about the solving process of solvers. Having just the solution which gurobi/Cplex provides would not be enough anymore. These details are about what is going on during applying the Branch and Bound algorithm. There are some solver/libraries which provide this information such as SCIP Optimization Suite and GAMS but to get desired features from them it was necessary to change their source code. Also, stand-alone B\&B algorithms (out of the frame of solvers) give just the solutions and some undesired information. Writing a custom B\&B algorithm which provides detail of each node was a good idea and initial step of this approach.“Behavior Cloning”is trained with necessary features and it imitates the behavior of the solver in each step of Branch and Bound which causes a reduction in solving time by skipping three steps (Node Branching, Node Selection and solving LP of the rejected node) of B\&B algorithm. Speed up the solving process of large-scale optimization has always been of great importance to industry players and stakeholders. An extensive study is done for such these problem and the acquired results are promising. Amongst the approaches taken in this work, the assistive and interactive ones have shown more promising results and considerable enhancement in solving the large-scale optimization problems. For the future researches, I have plan to use Inverse Reinforcement Learning (IRL) and Geometric Deep Learning (GDL) methods to approach this problem.
Benzer Tezler
- Exact solution approaches for non-Hamiltonian vehicle routing problems
Hamilton olmayan araç rotalama problemleri için kesin çözüm yaklaşımları
AMİNE GİZEM ÖZBAYGIN
Doktora
İngilizce
2017
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
PROF. DR. OYA KARAŞAN
- Kredi kartları ve Türkiye'deki uygulaması: karşılaşılan sorunlar ve çözüm önerileri
Başlık çevirisi yok
BEDİ TÜRETKEN
- İstanbul'da Helenizm: Sosyo-kültürel örgütlenmeler (1908-1922)
Hellenizm in İstanbul: Socio-cultural organizations (1908-1922)
ÇAĞLA DERYA TAĞMAT
Doktora
Türkçe
2015
SosyolojiAnkara ÜniversitesiAtatürk İlkeleri ve İnkılap Tarihi Ana Bilim Dalı
PROF. DR. TEMUÇİN FAİK ERTAN
- Kütüphane ortamında yüz ve parmak izi tanıma sisteminin geliştirilmesi
Development of face and fingerprint recognition system in library environment
MOHAMMED RIDHA MOHAMMED AHMED ALSARRAR
Doktora
Türkçe
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKastamonu ÜniversitesiMalzeme Bilimi ve Mühendisliği Ana Bilim Dalı
DOÇ. DR. YASEMİN GÜLTEPE
- Biyolojik işaretlerin gelişmiş bir sayısal işaret işlemcisiyle işlenmesi
Biomedical signal processing using a high performance DSP
DERYA DEMİR
Yüksek Lisans
Türkçe
1991
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. ERTUĞRUL YAZGAN