Concepts and Algorithms of Optimization (WiSe 2019/2020)
Content
This course is designed for the study program Operations Research and Business Analytics. It aims at making the students familiar with the basic modelling concepts, structural results, and algorithmic principles of optimization. The focus will be on discrete and linear optimization.
Class Hours
Lectures (Dr. Maximilian Merkert); Entry at LSF
- Tue, 15:15-16:45, G02-109
- Fri, 11:15-12:45, G10-460
- Thu, 14:00-16:00, G02-205
Post-Exam Review
Students can review their examinations (summer term 2020) on October 22nd, from 2 to 4 pm in room G03-214.
Exam
The written examinations (summer term 2020) will take place on July 17th, from 3 to 4 pm.
Exercise Series
In the tutorials, solutions of the tasks given in the exercise series will be presented and discussed. It is highly recommended to prepare for the tutorials and participate actively in the discussions. Some of the solutions to the AMPL exercises can be found here.
- Tut 01 (18.10.19) Series 1
- Tut 02 (25.10.19) Series 2
- Tut 03 (01.11.19) Series 3
- Tut 04 (08.11.19) Series 4
- Tut 05 (15.11.19) Series 5
- Tut 06 (22.11.19) Series 6
- Tut 07 (29.11.19) Series 7
- Tut 08 (06.12.19) Series 8
- Tut 09 (13.12.19) Series 9
- Tut 10 (10.01.20) Series 10
- Tut 11 (21.01.20) Series 11
- Tut 12 (31.01.20) Series 12 and AMPL template
The AMPL system
- The software system for and a quickstart manual.
- Individual chapters of the AMPL book are freely available here,
- together with the AMPL Reference Manual.
An IDE is not included in the zip package but can be downloaded here.
AMPL Models
Here you can find AMPL models that have been discussed in class.
- First AMPL model maxflow0.mod from the lecture (19.11.), which we used to solve a max flow problem on a small graph with 4 nodes and 5 arcs.
- Parametric AMPL models maxflow.mod and mincostcirc.mod for the max flow problem and the min cost circulation problem, respectively, together with data files maxflow.dat, mincostcirc.dat corresponding to the the example instances from the lecture (26.11.). Additionally, some generally useful AMPL console commands are given in the script file scriptmaxflow.run. More detailed information can of course be found in the AMPL book.
- Parametric AMPL models stab.mod and clique.mod for the stable set and the clique problem, respectively, from the lecture (03.12.). For testing, we used the data file 5cycle.dat representing a graph that is a cycle of length 5.
- Testfiles RandGraph30.dat, RandGraph40.dat, RandGraph50.dat representing random graphs on 30, 40, and 50 vertices, respectively. We used them in the lecture (10.12.) for testing coloring models. The AMPL models themselves will be added after the turorial on December 13th.
- Parametric AMPL model color.mod for the graph (node) coloring problem. In the lecture (10.12.), we also discussed the improved model color_symbreak.mod that breaks some of the previous model's symmetry.
- Parametric AMPL models hampath.mod and hamcycle.mod for the shortest Hamiltonian path problem and the shortest Hamiltonian cycle problem, respectively, from the lecture (17.12.). For the former, hampath.dat provides a small test instance, whereas cities.dat is a real-world data set for the latter (though both can be used for the respective other problem as well with minor adjustments). Furthermore, a modification of hamcycle.mod led to model vehiclerouting.mod for the vehicle routing problem for a given number of vehicles as well as a maximum number of stops per tour.
Literature
- Reinhard Diestel: Graph Theory 5th edition 2016/17, Springer-Verlag.
- Robert Fourer, David M. Gay, Brian W. Kernighan: AMPL: A Modeling Language for Mathematical Programming.