How do I solve combinatorial optimization problems

Combinatorial Optimization

WG Combinatorial Optimization

(V4 + Ü2)



content

Combinatorial optimization problems arise in many practical applications (e.g. flight planning, production planning, transport planning, shift planning, logistics).

After an introduction to various combinatorial optimization problems, general optimization methods (exact and heuristic methods) are presented and illustrated using practical examples. Then combinatorial optimization problems are dealt with, which can be formulated as linear programs and efficiently solved with the simplex method.

Keywords: branch-and-bound algorithms, constraint programming, dynamic programming, heuristics, local search, taboo search, genetic algorithms, ant algorithms, approximation algorithms with quality guarantee, linear programming, simplex methods, game theory, network flow problems

literature

  • E.H.L. Aarts, J.K. Lenstra: Local Search in Combinatorial Optimization, Wiley, 1997.
  • R.K. Ahuja, T.L. Magnanti, J.B. Orlin: Network Flows, Prentice Hall, 1993.
  • P. Brucker, S. Knust: Complex Scheduling, Springer, 2nd edition, 2012.
  • E. Burke, G. Kendall: Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, Springer, 2005.
  • V. Chvatal: Linear Programming, W.H. Freeman and Company, 1983.
  • J. Dreo, A. Petrowski, P. Siarry, E. Taillard: Metaheuristics for Hard Optimization: Methods and Case Studies, Springer, 2006.
  • M. Garey, D.S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, 1979.
  • M. Gendreau, J.-Y. Potvin: Handbook of Metaheuristics, Springer, 2010.
  • F. Glover, G.A. Cookingberger: Handbook of Metaheuristics, Kluwer, Boston, 2003.
  • F. Glover, M. Laguna: Tabu Search, Kluwer, Boston, 1997.
  • T. Grünert, S. Irnich: Optimization in Transport, Volume I: Basics, Shaker, 2005.
  • J. Kallrath: Mixed-integer optimization: Modeling in practice, Springer Spectrum 2013.
  • Z. Michalewicz, D.B. Fogel: How to Solve It: Modern Heuristics, Springer, 2004.
  • C.H. Papadimitriou, K. Steiglitz: Combinatorial Optimization, Prentice Hall, Englewood Cliffs, N.J., 1982.
  • C.R. Reeves: Modern Heuristic Techniques for Combinatorial Problems, Blackwell Scientific Publications, 1993.
  • E. Tsang: Foundations of Constraint Satisfaction, Academic Press, 1993.
  • R. Vanderbei: Linear Programming, Foundations and Extensions, Springer, 2001.

materials

software

To solve LP and MIP problems, the ZIB Optimization Suite is used in the exercises Zimpl, SCIP and SoPlex contains. These are freely available for academic use. The programs are installed on the CIP pool computers, but can also be used on your own computer.

In order to be able to run Zimpl or SCIP in all directories, you have to add the installation directory to the PATH variable. You can find a description of this e.g. B. here

participation

The event is intended for B.Sc. from the 3rd semester. Participation is open to all interested students from the computer science, mathematics, applied systems science and cognitive science courses.

Sham

The prerequisite for acquiring a certificate for the event is regular participation in the exercises, successful completion of the exercises (50% of the maximum points in theoretical and 50% of the maximum points in practical exercises) and successful completion of an examination (written exam) at the end of the Semester. All chapters of the lecture as well as the topics from the exercises are relevant for the exam.