kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Imitation Learning on Branching Strategies for Branch and Bound Problems
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematical Statistics.
2023 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Imitationsinlärning av Grenstrategier för Branch and Bound-Problem (Swedish)
Abstract [en]

A new branch of machine and deep learning models has evolved in constrained optimization, specifically in mixed integer programming problems (MIP). These models draw inspiration from earlier solver methods, primarily the heuristic, branch and bound. While utilizing the branch and bound framework, machine and deep learning models enhance either the computational efficiency or performance of the model. This thesis examines how imitating different variable selection strategies of classical MIP solvers behave on a state-of-the-art deep learning model.

A recently developed deep learning algorithm is used in this thesis, which represents the branch and bound state as a bipartite graph. This graph serves as the input to a graph network model, which determines the variable in the MIP on which branching occurs. This thesis compares how imitating different classical branching strategies behaves on different algorithm outputs and, most importantly, time span. More specifically, this thesis conducts an empirical study on a MIP known as the facility location problem (FLP) and compares the different methods for imitation.

This thesis shows that the deep learning algorithm can outperform the classical methods in terms of time span. More specifically, imitating the branching strategies resulting in small branch and bound trees give rise to a more rapid performance in finding the global optimum. Lastly, it is shown that a smaller embedding size in the network model is preferred for these instances when looking at the trade-off between variable selection and time cost.

Abstract [sv]

En ny typ av maskin och djupinlärningsmodeller har utvecklats inom villkors optimering, specifikt för så kallade blandade heltalsproblem (MIP). Dessa modeller hämtar inspiration från tidigare lösningsmetoder, främst en heuristisk som kallas “branch and bound”. Genom att använda “branch and bound” ramverket förbättrar maskin och djupinlärningsmodeller antingen beräkningshastigheten eller prestandan hos modellen. Denna uppsats undersöker hur imitation av olika strategier för val av variabler från klassiska MIP-algoritmer beter sig på en modern djupinlärningsmodell.

I denna uppsats används en nyligen utvecklad djupinlärningsalgoritm som representerar “branch and bound” tillståndet som en bipartit graf. Denna graf används som indata till en “graph network” modell som avgör vilken variabel i MIP-problemet som tas hänsyn till. Uppsatsen jämför hur imitation av olika klassiska “branching” strategier påverkar olika algoritmutgångar, framför allt, tidslängd. Mer specifikt utför denna uppsats en empirisk studie på ett MIP-problem som kallas för “facility location problem” (FLP) och jämför imitationen av de olika metoderna.

I denna uppsats visas det att denna djupinlärningsalgoritm kan överträffa de klassiska metoderna när det gäller tidslängd. Mer specifikt ger imitation av “branching” strategier som resulterar i små “branch and bound” träd upphov till en snabbare prestation vid sökning av den globala optimala lösningen. Slutligen visas det att en mindre inbäddningsstorlek i nätverksmodellen föredras i dessa fall när man ser på avvägningen mellan val av variabler och tidskostnad.

Place, publisher, year, edition, pages
2023. , p. 74
Series
TRITA-SCI-GRU ; 2023:067
Keywords [en]
Graph Networks, Convolutions, MIP, Branch and Bound, Facility Location Problem, MDP, Imitation Learning
Keywords [sv]
Graf nätverk, Faltning, Blandade heltaltsproblem, Branch and Bound, Facility Location Problem, Markov, Imitationsinlärning
National Category
Other Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-339539OAI: oai:DiVA.org:kth-339539DiVA, id: diva2:1811693
External cooperation
Echo State AB
Subject / course
Mathematical Statistics
Educational program
Master of Science - Applied and Computational Mathematics
Supervisors
Examiners
Available from: 2023-11-27 Created: 2023-11-14 Last updated: 2023-11-27Bibliographically approved

Open Access in DiVA

fulltext(1804 kB)219 downloads
File information
File name FULLTEXT01.pdfFile size 1804 kBChecksum SHA-512
1a0a19d6f42f64045b548ed59e3552a1a5a5a6f659c63203006eead3b588e26d267f2f4a6d15dd2aa5d971ced8e7eb00328e9dd91859264da66f3ea699f61523
Type fulltextMimetype application/pdf

By organisation
Mathematical Statistics
Other Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 219 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 262 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf