Concepts and Algorithms of Optimization (WiSe 2018/2019)
Content
This course is obligatory 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, linear, and convex optimization.
Class Hours
Lectures (
Dr. Maximilian Merkert);
Entry at LSF
Tutorials (
Julia Lange);
Entry at LSF
Post-Exam Review
Students can review their examinations (winter term 2018/19) on April 15th, from 2 to 4 pm in room 02-215.
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.
The AMPL system
For MacOS, 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 (13.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 (20.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 (27.11.). For testing, we used the data file 5cycle.dat representing a graph that is a cycle of length 5.
- Parametric AMPL model color.mod for the graph (node) coloring problem. In the lecture (04.12.), we also discussed the improved model color_symbreak.mod that breaks some of the previous model's symmetry. As a testfile, we used RandGraph30.dat representing a random graph on 30 vertices.
- Parametric AMPL models hampath.mod and hamcycle.mod for the shortest Hamiltonian path problem and the shortest Hamiltonian cycle problem, respectively, from the lecture (11.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