186.835 Mathematical Programming This course is in all assigned curricula part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_21",{id:"j_id_21",showEffect:"fade",hideEffect:"fade",target:"isAllSteop"});});This course is in at least 1 assigned curriculum part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_23",{id:"j_id_23",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});}); 2024S 2023S 2022S 2021S 2020S 2019S 2018S 2017S 2016S 2015S 2014S 2013S 2012S

2023S, VU, 2.0h, 3.0EC

Properties

• Semester hours: 2.0
• Credits: 3.0
• Type: VU Lecture and Exercise
• Format: Hybrid

Learning outcomes

After successful completion of the course, students are able to

• overview the area of mathematical optimization with focus on mixed integer linear programming (MIP),
• model both academic and real world decision problems as MIPs,
• theoretically analyze and compare different MIP formulations for a problem,
• understand common methodology for solving MIPs,
• develop practical solution algorithms using state-of-the-art MIP frameworks.

Subject of course

• Overview on mathematical optimization (focus on mixed integer linear models, but also discussing non-deterministic models)
• Modeling (real world) problems as MIPs (basic techniques, modeling with exponentially many constraints and/or variables)
• Solution methods for MIPs
- Cutting plane method, branch-and-cut
- Decomposition approaches (Lagrangian decomposition, Dantzig-Wolfe decomposition) and corresponding solution methods (subgradient method, column generation, branch-and-price)
• Theory of valid inequalities and further theoretical concepts
- (Strong) valid inequalities (Chvatal-Gomory cuts, Gomory cuts, cover cuts, theoretical concepts such as dominance, redundancy, facet-defining cuts)
- "Well-solved" problems (properties, total unimodularity, optimization = separation)
• Stochastic and robust optimization
• Further issues in MIP computation and components of modern MIP solvers (presolving, primal heuristics, symmetry, frameworks)

Teaching methods

• Lecture (attendance optional - recordings from previous years available)
• Introduction to the usage of state-of-the-art MIP solver frameworks (Gurobi, CPLEX)
• Homework exercises
• Programming exercises

Mode of examination

Immanent

Estimated effort:

Hours | Purpose
20       | Lecture
15       | Homework exercises
25       | Programming exercise
15       | Exam preparation and exam
--------------------------------------
75       | Overall

Course dates

DayTimeDateLocationDescription
Wed16:00 - 18:0001.03.2023 - 28.06.2023FAV Hörsaal 2 Mathematical Programming
Wed16:00 - 19:0028.06.2023EI 10 Fritz Paschke HS - UIW Prüfung Mathematical Programming
Mathematical Programming - Single appointments
DayDateTimeLocationDescription
Wed01.03.202316:00 - 18:00FAV Hörsaal 2 Mathematical Programming
Wed08.03.202316:00 - 18:00FAV Hörsaal 2 Mathematical Programming
Wed15.03.202316:00 - 18:00FAV Hörsaal 2 Mathematical Programming
Wed22.03.202316:00 - 18:00FAV Hörsaal 2 Mathematical Programming
Wed29.03.202316:00 - 18:00FAV Hörsaal 2 Mathematical Programming
Wed19.04.202316:00 - 18:00FAV Hörsaal 2 Mathematical Programming
Wed26.04.202316:00 - 18:00FAV Hörsaal 2 Mathematical Programming
Wed03.05.202316:00 - 18:00FAV Hörsaal 2 Mathematical Programming
Wed10.05.202316:00 - 18:00FAV Hörsaal 2 Mathematical Programming
Wed17.05.202316:00 - 18:00FAV Hörsaal 2 Mathematical Programming
Wed24.05.202316:00 - 18:00FAV Hörsaal 2 Mathematical Programming
Wed31.05.202316:00 - 18:00FAV Hörsaal 2 Mathematical Programming
Wed07.06.202316:00 - 18:00FAV Hörsaal 2 Mathematical Programming
Wed14.06.202316:00 - 18:00FAV Hörsaal 2 Mathematical Programming
Wed21.06.202316:00 - 18:00FAV Hörsaal 2 Mathematical Programming
Wed28.06.202316:00 - 18:00FAV Hörsaal 2 Mathematical Programming
Wed28.06.202316:00 - 19:00EI 10 Fritz Paschke HS - UIW Prüfung Mathematical Programming

Examination modalities

• Homework exercises (max. 20 points): Exercises are done at home and solutions are uploaded in TUWEL.
• Programming Exercises (max. 40 points): Different MIP formulations for a specified optimization problem are designed and implemented. You can (optionally) join in groups of two. Your solutions are uploaded in TUWEL.
• Written exam (max. 40 points)

The grade you receive depends on the total points collected for all tasks, but you need at least 30 points in the exercise part (including homework and programming exercises) and at least 20 points in the written exam to get a positive grade. The final grade is obtained by the following mapping:

1: 88 - 100 points
2: 75 - 87.5
3: 63 - 74.5
4: 50 - 62.5
5: 0 - 49.5

Exams

DayTimeDateRoomMode of examinationApplication timeApplication modeExam
Wed17:00 - 20:0026.06.2024FAV Hörsaal 1 Helmut Veith - INF written12.06.2024 00:00 - 25.06.2024 23:58TISSExam

Course registration

Begin End Deregistration end
13.02.2023 00:01 29.03.2023 23:59 31.03.2023 23:59

Curricula

Study CodeObligationSemesterPrecon.Info
066 504 Master programme Embedded Systems Not specified
066 645 Data Science Not specified
066 646 Computational Science and Engineering Not specified
066 926 Business Informatics Mandatory elective
066 931 Logic and Computation Mandatory elective
066 932 Visual Computing Mandatory elective
066 937 Software Engineering & Internet Computing Mandatory elective

Literature

all material is available in TUWEL

Previous knowledge

• Basic knowledge of (integer) linear programming (modeling, LP based Branch-and-Bound), e.g., as taught in Algorithmics
• Knowledge of basic algorithms and data structures
• Programming skills in some language, e.g., Java, C++, Python
• Basic knowledge of linear algebra and graph theory

English