Advanced Solution Techniques for Combinatorial and Discrete Optimization Problems
Seminar for Master Students
- 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.
TopicsIn 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 ScheduleThe 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í|
- Mandatory: Combinatorial Optimization MA4502 and/or Discrete Optimization MA3502
- Recommended: (preferably during the summer term of 2013): Case Studies in Discrete Optimization MA4512
- 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