Case Studies Discrete Optimization (MA4512)

combined lecture and project work course

supported through study contributions
polytop.png

 

Dozierende: Michael Ritter, Wolfgang Riedl, Paul Stursberg
weekly hours: 4 hours
ECTS credits: 7 (now officially confirmed!)

News

  • August 19th, 2013: In case you are interested in the results of the final evaluation, here are the results: MA_4512_Case_Studies:_Discrete_Optimization_DozentIn.pdf. The file may be accessed with the same login/password data that you can use to access the course materials. The results will also be published by Fachschaft MPI at some later time. Thank you for the great feedback and especially for your valuable comments - these will definitely help us improve the course.
  • Photos from both TUMMS and SCoNDO IV are available (with a password protection) at http://www-m9.ma.tum.de/material/fotos/tumms-2013 and http://www-m9.ma.tum.de/material/fotos/scondo-2013, respectively. The password is the same that you can use to access the protected material on this site.
  • June 23rd, 2013: Please remember to register for the exam in 'Case Studies (Discrete Optimization)' via TUMOnline no later than June 30th, 2013. Registration is mandatory for participation in the final workshop. If you have any problems registering, please contact us.
  • June 23rd, 2013: Details on the final workshop will be posted on the conference website at http://www-m9.ma.tum.de/SS2013/SCoNDO. Please refer to that site for important due dates regarding the conference.
  • Mar 25, 2013: Save the date: The final workshop for the case studies courses will be on Saturday, July 13th, while the poster presentation will be on Thursday, May 23rd. Please be sure to keep these days free, attendance is absolutely mandatory.
  • Mar 6, 2013: As part of an effort to offer master's courses in English, this website is in the process of being translated into English. In the meantime, please excuse the German/English language mix.
  • Feb 8, 2013: A slightly shortened version of the preliminary meeting's slides is available for download below.
  • Jan 28, 2013: This semester, we offer an optional companion seminar for the case studies, see here for further information.

Schedule

Preliminary Meeting

A preliminary meeting took place on February 8, 2013. A slightly shortened version of the slides used in the preliminary meeting covering most of the important information is available for download here. If you have any questions that are not answered on the slides nor on this website, please contact Michael Ritter at michael.rittertum.de.

Registration

Registration is possible until March 1st, 2013, it is mandatory and binding. To register, please write a short mail to michael.rittertum.de providing the following information:
  • last name, first name
  • curriculum (of your master's studies)
  • ranking of the projects (which do you find most interesting, which would be a good alternative etc.); please rank all five projects.
  • list of optimization related lectures that you have attended (for lectures from other faculties or univiersities, please give a short description of the topics covered so that we know about your expertise in the field)
  • programming skills (programming languages and other programming related skills)
  • persons you would like to work with as a team
  • If you are registered for the companion seminar please be sure to mention that in your mail.
After March 1st, we still have a limited number of places available for incomings from abroad and for master students coming from other universities and starting at TUM this summer.

Poster Presentation and Final Workshop

Please be sure to reserve the following dates (attendance is absolutely mandatory):
  • "TUMMS" on Thursday, May 23rd, 2013 (poster presentation, 12:00 to 15:00 hours)
  • final workshop on Saturday, July 13th, 2013 (whole day)
The final workshop is the last official date for the course. More information can be found on the conference website. Photos of these events are available (password-protected) at http://www-m9.ma.tum.de/material/fotos/tumms-2013 and http://www-m9.ma.tum.de/material/fotos/scondo-2013. For access, please use the same password that works for the materials on this site.

Course Schedule

The course is scheduled to take place Tuesdays and Fridays from 10:15 to 11:45 hours during the semester in room MI 00.09.022.

date time room topics
Fri, Feb 08 14:15 MI 02.04.011 preliminary meeting
Tue, Apr 16 10:15 - 11:45 MI 00.09.022 first meeting: teams and projects
Fri, Apr 19 10:15 - 11:45 MI 00.09.022 team presentations, project planning
Tue, Apr 23 10:15 - 11:45 MI 00.09.022 poster design
Fri, Apr 26 10:15 - 11:45 Uhr MI 00.09.022 presentation of project schedules
Tue, Apr 30 10:15 - 11:45 MI 00.09.022 case study: train unit assignment
Fri, May 03 10:15 - 11:45 MI 00.09.022 case study: train unit assignment
Tue, May 07 10:15 - 11:45 MI 00.09.022 case study: train unit assignment
Fri, May 10 no lecture ("Brückentag")
Tue, May 14 no lecture (SVV)
Wed, May 15 hand in posters for printing
Fri, May 17 10:15 - 11:45 MI 00.09.022 internal poster presentation
Tue, May 21 no lecture (holiday) — hand in posters for printing
Thu, May 23 12:00 - 15:00 MI main hall poster presentation at TUMMS
Fri, May 24 10:15 - 11:45 MI 00.09.022 case study: train unit assignment
Tue, May 28 10:15 - 11:45 MI 00.09.022 Cutting Plane Methods
Fri, May 31 no lecture ("Brückentag")
Tue, June 04 10:15 - 11:45 MI 00.09.022 SOS, Constraint Branching
Fri, June 07 10:15 - 11:45 MI 00.09.022 Slide Design
Tue, June 11 10:15 - 11:45 MI 00.09.022 Presentation, Symmetry Issues, Branching Rules
Fri, June 14 10:15 - 11:45 MI 00.09.022 Relaxation Techniques
Tue, June 18 10:15 - 11:45 MI 00.09.022 no lecture (prepare your midterm talks!)
Fri, June 21 10:15 - 11:45 MI 00.09.022 Feedback & Midterm Presentations I
Tue, June 25 10:15 - 11:45 MI 00.09.022 Feedback & Midterm Presentations II
Fri, June 28 10:15 - 11:45 MI 00.09.022 tba
Tue, July 02 10:15 - 11:45 MI 00.09.022 tba
Sat, Jul 13 tba HS 0606 (TUM Main Campus, Downtown Munich) Final Workshop

For detailed information on the final workshop, please see the conference website.

Slides and additional material

General

April 19, 2013: Project Planning

April 23, 2013: Poster Design

April 30, May 3, May 7, May 242013: Case Study

TrainUnitAssignment-ProblemDescription.pdf (informal) problem description
TrainUnitAssignment-FormalProblemDescription.pdf formal problem description
TUAP_task_graph_solution.pdf exercise sheet ont the task graph
slides-ILP.pdf introductory slides on the ILP formulation
slides_lagrange.pdf slides on Lagrangian relaxation
script-may-03.pdf notes on Lagrangian relaxation
slides-CG.pdf introductory slides on column generation
vortrag-bb.pdf slides on branch & bound
slides-heuristic.pdf slides on model roundup and heuristic
sheet-capacity-constraints.pdf worksheet on strengthening the capacity constraints
TrainUnitAssignment-Paper.pdf original paper

May 28, 2013: Cutting Plane Methods

galerie.pdf a gallery of cutting planes
cliques-antiholes-web-antiwebs.pdf Worksheet on "Cliques, Antiholes, Webs, Antiwebs"
handout-cliques-antiholes-web-antiwebs.pdf Students' Handout on "Cliques, Antiholes, Webs, Antiwebs"
odd-cycle-and-separation.pdf Worksheet on "Cliques, Odd Cycles and Separation"
handout-odd-cycle-and-separation.pdf Students' Handout on "Cliques, Odd Cycles and Separation"
wheel-inequalities.pdf Worksheet on "Odd Wheel Inequalities"
handout-wheel-inequalities.pdf Students' Handout on "Odd Wheel Inequalities"
outsideTemplateParadigm.pdf Worksheet on "Separation outside the Template Paradigm"
handout-outsideTemplateParadigm.pdf Students' Handout on "Separation outside the Template Paradigm"

June 4, 2013: Special Ordered Sets and Constraint Branching

script-jun-04.pdf Lecture notes for SOS and constraint branching
vortrag-sos2.pdf Slides for the introduction of SOS 2
slides-constraint-branching.pdf Slides for the introduction of constraint branching
ConstraintBranching-Arbeitsblatt.pdf Worksheet for constraint branching

June 7, 2013: Slide Design

presentation.pdf Slides on slide design
eon-Folien.pdf Students' redesigned slides

June 11, 2013: Branching and Symmetry Issues

auszug_pseudocost.pdf Worksheet on pseudocost branching
auszug_strong.pdf Worksheet on strong branching
paper-jun-11.pdf Original paper on branching strategies
slides-symmetry.pdf Slides on symmetry issues

June 14, 2013: Relaxation Techniques

slides-relaxation.pdf Slides on relaxation basics and notation
relaxation-methods-worksheets.pdf Worksheets on relaxation techniques
example-relaxation-methods.pdf Worksheets on ATSP-PC examples for relaxation techniques
slides_additive-bounding-procedure.pdf Slides on the additive bounding procedure and solutions for the examples

June 21 and 25, 2013: Mitdterm Presentations

Organization

  • For the midterm presentations, each team will have 20 minutes for the talk, including discussions.
  • You are completely free in your choice of presentation form, visual material (slides, blackboard, etc.).
  • Which team members actually give the presentation is also up to you to decide. In particular, there is no requirement that every team member must give part of the presentation (as opposed to the final presentation).
  • The language of your presentation can either be English or German (again, as opposed to the final presentation, where English will be mandatory).
  • You will receive a brief structured feedback from the audience immediately following your talk. If you wish, you can (as a team) also schedule a short feedback discussion with us.
  • We will record your talk on video for you to watch and enhance your presentation skills. Each talk will exclusively be available to the team giving the talk. If you do not wish for your talk to be recorded, please tell us until this Friday, June 14th.
  • No grades will be given for your midterm presentations, so you are completely free to experiment.

(Preliminary) Schedule

Friday, June 21  
  10:15 - 10:45 structured feedback and feedback forms
  10:45 - 11:05 talk "Operation Room Management"
  11:05 - 11:15 feedback
  11:15 - 11:35 talk "University Timetabling"
  11:35 - 11:45 feedback
Tuesday, June 25  
  10:15 - 10:35 talk "Flight Scheduling"
  10:35 - 10:45 feedback
  10:45 - 11:05 talk "Gear Train Optimization"
  11:05 - 11:15 feedback
  11:15 - 11:35 talk "Traffic Infrastructure"
  11:35 - 11:45 feedback

Project

Below, you will find a short description of each of the projects in this year's case studies. Your objective will generally consist of the following tasks: Based on some practical problem, develop a suitable abstraction and a mathematical model. Use extensive analysis of the problem and discrete and integer optimization tools to come up with an algorithmic approach for solving the problem. Implement your solution and analyze the results.

Gear Train Construction

The aim of this project is an automatized procedure for the construction of complex gear trains. There is a number of graph theoretical models for the functional representation of gear trains, some of which you will study during your work on this project. After adapting these models to the specific problem at hand, you will develop a mathematical programming model based on the graph theoretic representation and subsequently design an algorithm that can synthesize functional gear trains with respect to certain constraints (e.g. transmission ratios, number of gears, number of clutches, number of parts).

University Timetabling

Designing university timetables is a very complex problem with a multitude of different constraints, e.g. available rooms, distances between those, curricula of different degree programs, preferences of teaching staff, the sequence of courses within each day and within the week and many more. In this project, you will study existing approaches to university timetabling and extend them to account for additional constraints. You will also add flexibility to some of the constraints and develop/enhance an algorithm to solve the mathematical models for the generation of optimal timetables.

Flight Scheduling

In daily airport operations, there is a number of factors leading to minor (or sometimes major) deviations from the flight schedules. As many airports operate at the limit of their capacities, even minor discrepancies can lead to major disruptions for a number of other flight movements. Your task in this project is the design of an optimization model for flight scheduling that enhances robustness of the schedule against such irregularities and enables quick and effective reactions to limit the negative effects on other flights.

Traffic Flow Optimization

Traffic flow is usually modeled using complex network flow approaches, often with large networks. In addition to classical flow constraints these models have to take into account such factors as traffic lights, different street capacities, congestions and speed limits as well as the preferences of the traffic agents (working hours, preferred routes, recreational activities), which leads to complex interactions that make it very hard to predict the outcome of changes in such a network. Based on a complex traffic model, you will analyze the influence of certain changes in the network or the constraints governing agent behavior and try to predict optimal interventions leading to an enhanced traffic flow.

Operating Room Management

Operating rooms account for a large share of a clinic's profit as well as for a large share of it's costs. Using the operating room capacities (and the health personnel) as efficiently as possible is therefore essential for effective clinic management. Unfortunately, complex surgery usually has to deal with a number of uncertainties that it hard to predict exact times for the surgical procedures. Your goal in this project is to design an optimization model for the scheduling of operating rooms and personnel that accounts for these uncertainties while also minimizing idle times.