Mixed Integer Programming and Graph Algorithms for Engineering Problems

Vortragende/r (Mitwirkende/r)
Nummer0000004343
Art
Umfang4 SWS
SemesterWintersemester 2020/21
UnterrichtsspracheEnglisch
Stellung in StudienplänenSiehe TUMonline

Termine

Teilnahmekriterien

Lernziele

After accomplishing this module, students are able to construct abstract models (e.g. graphs) for commonly-seen engineering problems, and apply algorithms or mathematical modeling methods to solve the problems systematically. In particular, students are able to analyze the problem space and solution space for a given engineering problem and understand that a small variance of the problem formulation can cause a significant change to the methodology. In addition, with a given method, students are able to evaluate its time complexity and measure its solution quality.

Beschreibung

In WS 2020/21 the course is planned to be presented online and asynchronous, i.e., download times of videos are at the discretion of participants. Content covered in this course: - Physical modeling, mixed integer linear programming (MILP), time complexity - Graph: vertex, edge, directed, degree, cyclic, planarity - Tree: binary search tree, MILP sort, quick sort, heaps - Distance-oriented graph: MILP shortest path, Dijkstra, A*, MILP spanning tree, Kruskal, MILP steiner tree, MILP planar routing - Conflict-oriented graph: vertex coloring, edge coloring, maximum independent set - Graph partition: max-flow min-cut, clustering - Set: set covering, exact covering - Scheduling and binding: time slot modeling, non-uniform time slot

Inhaltliche Voraussetzungen

Fundamental programming knowledge

Lehr- und Lernmethoden

Students learn the content of this course by attending the lectures and the tutorials. While the lectures focus on teaching the theories, the tutorials focus on consolidating students’ knowledge by applying learnt models and methods to solve varying problems. Both the lectures and tutorials are held in a teacher-centered style, but the students are always encouraged to interact with the lecturer and the tutor, especially when the students have different ideas regarding the models or algorithms.

Studien-, Prüfungsleistung

The examination will be in written form, the duration is 75 minutes. The students will demonstrate their capability to construct abstract models for commonly-seen engineering problems at given examples. They will show that they can select and apply appropriate solution algorithms and derive the corresponding mathematical constraints and objectives. They will also show that they can analyze the algorithm efficiency as well as the result quality.

Empfohlene Literatur

The following literatures are recommended: - Applied Mathematical Programming; Bradley, Hax, and Magnanti; Addison-Wesley 1977. - Introduction to Algorithms; Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein; The MIT Press 2009. - Introduction to Graph Theory; Douglas B. West; Pearson 2000.

Links


Vollständiges Lehrangebot

Bachelorbereich: BSc-EI, MSE, BSEEIT

 

WS

SS

Diskrete Mathematik für Ingenieure (BSEI, EI00460)

Discrete Mathematics for Engineers (BSEEIT) (Schlichtmann) (Januar)

 

O/P

WS

SS

Entwurf digitaler Systeme mit VHDL u. System C (BSEI, EI0690) (Ecker)

WS 20/21 block course after lecture period

O/O

 

SS

Entwurfsverfahren für integrierte Schaltungen (MSE, EI43811) (Schlichtmann)

--

WS

 

Methoden der Unternehmensführung (BSEI, EI0481) (Weigel)

--

WS

 

Praktikum System- und Schaltungstechnik (BSEI, EI0664) (Schlichtmann et al.)

--

 

SS

Schaltungssimulation (BSEI, EI06691) (Gräb/Schlichtmann)

O/O

 

Masterbereich: MSc-EI, MSCE, ICD

 

SS

Advanced Topics in Communication Electronics (MSCE, MSEI, EI79002)

?

WS

 

Aspects of Integrated Systems Technology & Design (MSCE, MSEI, EI5013) (Wurth)

--

WS

 

Electronic Design Automation (MSCE, MSEI, EI70610) (B. Li, Tseng)

--

WS

 

Design Methodology and Automation (ICD) (Schlichtmann) (Nov)

--

WS

SS

Machine Learning: Methods and Tools (MSCE, MSEI, EI71040) (Ecker)

O/O

WS

SS

SS

Mathematical Methods of Circuit Design (MSCE, MSEI, EI74042) (Gräb)

Simulation and Optimization of Analog Circuits (ICD) (Gräb) (Mai)

O/O

O/P

WS

 

Mixed Integer Programming and Graph Algorithms in Engineering Problems (MSCE, MSEI, EI71059) (Tseng)

--

WS

SS

Numerische Methoden der Elektrotechnik (MSEI, EI70440) (Schlichtmann oder Gräb)

O/P

WS

WS

SS

Seminar VLSI-Entwurfsverfahren (MSEI, EI7750) (Schlichtmann/Müller-Gritschneder)

Seminar on Topics in Electronic Design Automation (MSCE, EI77502) (Schlichtmann/Müller-Gritschneder)

O

WS

SS

Synthesis of Digital Systems (MSCE, MSEI, EI70640) (Müller-Gritschneder)

O/P

WS

 

Testing Digital Circuits (MSCE, MSEI, EI50141) (Otterstedt)

--

WS

 

Timing of Digital Circuits (MSCE, MSEI, EI70550) (B. Li, Zhang)

--

WS

SS

VHDL System Design Laboratory (MSCE, MSEI, EI7403) (Schlichtmann)

O/O

 

Die Spalte ganz rechts bezeichnet die Form der Vorlesung/Prüfung im SS 2021. O=online, P=physische Präsenz

The column on the very right denotes the type of course/exam in SS 2021. O=online, P=physical presence

 

MSE: Munich School of Engineering (TUM)

BSEEIT: Bachelor in Electrical Engineering and Information Technology (TUM-Asia)

ICD: Master of Science in Integrated Circuit Design (TUM-Asia)

MSCE: Master of Science in Communications Engineering (TUM)

MSEI: Master of Science in Elektrotechnik und Informationstechnik

BSEI: Bachelor of Science in Elektrotechnik und Informationstechnik

 

Aktuelle Infos zur Lehre/Current information on teaching: https://www.tum.de/die-tum/aktuelles/coronavirus/studium/, www.ei.tum.de