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
Tutorials (
Benjamin Peters);
Entry at LSF
Office Hours (
Benjamin Peters);
- Thu, 14:00-16:00, G02-205
On July 13th (i.e. on Monday before the exam), there will be an online Q&A session starting at 3 pm. If you are interested to attend, please write us a short e-mail, after which you will receive access details.
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.
The AMPL system
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