Advanced Solution Techniques for Combinatorial and Discrete Optimization Problems

Seminar for Master Students

 

Advisor: Michael Ritter
ECTS credits: 3

News

  • June 27, 2013: For the course "Case Studies Discrete Optimization" (that is affiliated with this seminar) there will be a one-day conference where all case studies teams present their projects and their results. If you are interested in some of the talks, you are invited to join us for this conference (or part of it). To celebrate the occasion, there will be a "conference dinner" at a nearby restaurant afterwards, and of course you are also welcome to join us there. If you want to come, we appreciate a short note (just mail m.ritterma.tum.de) so we can make sure that there are enough places for everyone at the restaurant. Details on the conference can be found on the conference website.
  • April 18, 2013: Dates for the talks have been fixed (with a few exceptions that may still change).
  • April 18, 2013: The first seminar session will be this Thursday, April 18th, at 14:00 in room MI 02.10.011.
  • Feb 11, 2013: The second round of registration on TUM-Online is live until Sunday, Feb 17.
  • Jan 28, 2013: Registration for the seminar has started on TUM-Online. Please register until this Sunday, Feb 3. If you also want to participate in the course Case Studies in Discrete Optimization, please e-mail me at michael.rittertum.de. You will then be given preference for the seminar (provided you actually sign up for the Case Studies until Feb 8, 2013).
  • More information on this seminar will be posted here shortly. More details on the seminar will also be presented at the meeting for this year's case studies courses on Feb 8th, 2013 at 2:15pm in room 02.04.011.

Topics

In this seminar, we will gain in-depth knowledge about practically relevant solution techniques for selected problems in combinatorial optimization. The seminar is geared primarily towards students taking the course "Case Studies in Discrete Optimization" (MA4512) during the summer term 2013, but is also open to other participants.

We will stress a thorough development of the theoretical background in addition to application specific aspects to complement the hands-on work that we will focus on in the case studies course. Topics will be selected according to participants' backgrounds and in particular with respect to the projects of the case studies course and hence are not fixed yet.

Talks and Schedule

The seminar sessions will take place Thursdays, 14:00 to 17:00, on the dates given below, in room MI 02.10.011, exceptions are mentioned in the table below. Here is a list of dates, topics and presenters, still subject to change.

Date and Time Topic Presenter
April 18, 14:00 Organisation and Introduction Michael Ritter and seminar participants
May 8 (Wednesday) Average Case Analysis for the Simplex Algorithm Barbara Peutler
May 8 (Wednesday) Symmetry Issues and Orbitopal Fixing Lisa Gerstner
May 16 The Traveling Salesman Problem
        Recent Progress in Approximation Algorithms Tanja Niels
        Polyhedral Studies by Example Pia Puchner
May 23, presumably 15:30 - 18:30 Column Generation, Branch & Price and Decomposition Patricia Jozefowicz
June 6 Metaheuristics by Example: Evolutionary Algorithms Saskia Schiele
June 6 Scheduling Problems: Different approximative approaches to a combinatorial problem Julia Baukmann
June 13 Mixed Integer Programming: Disjunctive Cuts, Gomory Mixed Integer Cuts and Beyond
        Introduction: Mixed Integer Programs, Why Gomory Cuts fail, Generalized Gomory Cuts Lucia Fogelstaller
        Disjunctive Cuts and Split Cuts, Split Cuts are not Sufficient, Alternative Cutting Plane Approaches Felix Zölls
June 20 SDP/SOCP/Copositive Programming
        Introduction: Basics of SDP, Examples for Combinatorial Optimization based on SDP, MaxCut Andreas Schmidt
        Relaxation and Cutting Planes based on SDP, Copositivity Cuts Marta Marí
June 27 MINLP: Mixed Integer Nonlinear Programming Moritz Ratzesberger
June 27 Extended Formulations Elisabeth Finhold
July 4 Speed-Up Techniques: Warm Start, ILP heuristics, and more Laura Velikonja
July 4 Presolve Techniques Felix Krisch
July 18 Semidefinite Programming and SDP-based relaxations Marta Marí

Requirements

  • Mandatory: Combinatorial Optimization MA4502 and/or Discrete Optimization MA3502
  • Recommended: (preferably during the summer term of 2013): Case Studies in Discrete Optimization MA4512

Literature

  • Cook, Cunningham, Pulleyblank, Schrijver: Combinatorial Optimization, Wiley Interscience, 1998.
  • Korte, Vygen: Combinatorial Optimization: Theory and Algorithms, Springer 2002.
  • Papadimitriou, Steiglitz: Combinatorial Optimization, Dover 2001.
  • Schrijver: Combinatorial Optimization. Polyhedra and Efficiency. Springer, 2003.
  • Jünger et al.: 50 Years of Integer Programming 1958-2008. Springer 2010
  • additional literature will be selected according to the topics