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
A case study of disjunctive programming: Determining optimal motion trajectories for a vehicle by mixed-integer optimization
KTH, School of Engineering Sciences (SCI).
KTH, School of Engineering Sciences (SCI).
2023 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

This report considers an application of mixed-integer disjunctive programming (MIDP)where a theoretical robot can jump from one point to another and where the number ofjumps is to be minimized. The robot is only able to jump to the north, south, east andwest. Furthermore, the robot should also be able to navigate and jump around or across anypotential obstacles on the way. The algorithm for solving this problem is set to terminatewhen the robot has reached a set of end coordinates. The goal of this report is to find amethod for solving this problem and to investigate the time complexity of such a method.The problem is converted to big-M representation and solved numerically. Gurobi is theoptimization solver used in this thesis. The model created and implemented with Gurobiyielded optimal solutions to problems of the form above of varying complexity. For most ofcases tested, the time complexity appeared to be linear, but this is likely due to presolvingperformed by Gurobi before running the optimization. Further tests are needed to determinethe time complexity of Gurobi’s optimization algorithm for this specific type of problem.

Place, publisher, year, edition, pages
2023.
Series
TRITA-SCI-GRU ; 2023:114
Keywords [en]
Optimization, disjunctive programming, integer programming, Gurobi, big-M, nonlinear programming
National Category
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-330287OAI: oai:DiVA.org:kth-330287DiVA, id: diva2:1776821
Subject / course
Optimization and Systems Theory
Educational program
Master of Science in Engineering - Engineering Mathematics
Supervisors
Examiners
Available from: 2023-06-28 Created: 2023-06-28 Last updated: 2023-06-28Bibliographically approved

Open Access in DiVA

fulltext(804 kB)243 downloads
File information
File name FULLTEXT01.pdfFile size 804 kBChecksum SHA-512
5a3f07d9f3d30d9f37c22f17d0dab55cc8cb01e8b2b3e8670e15399a331213621442cf4e4bc4a815fd977d2b275716ac0bcec0632cbb145dccd07d7da18e1512
Type fulltextMimetype application/pdf

By organisation
School of Engineering Sciences (SCI)
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 244 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: 246 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