Case Studies Discrete Optimization (MA4512)
combined lecture and project work course

polytop.png

Advisors: Michael Ritter, Roman Rischke, Kevin Schewior
weekly hours: 4 hours
ECTS credits: 7

News

  • Mar 23, 2016: The first meeting of the Case Studies Discrete Optimization (jointly with Case Studies Nonlinear Optimization) will take place on Monday, April 11th, at 16:00 at Interimshörsaal 2. Please be on time and plan for approximately 3 hours for this first meeting.
  • Mar 8, 2016: Confirmations notes have been sent out to all successful applicants. If you have not received a message from us, please let us know.
  • Mar 8, 2016: Registrations for the programming tutorial "Discrete Optimization" are accepted at https://ferienkurse.ma.tum.de. Participation is strongly recommended for all students taking part in the case studies course (or planning to do a thesis with us).
  • Feb 3, 2016: Registration to the Case Studies courses is now open, please see below for details. Registration will be possible until March 1st, 2016.
  • Jan 14, 2016: There will be a preliminary meeting for this course (jointly with "Case Studies Nonlinear Optimization" on February 3rd, 2016, at 16:15 hours in room MI 00.07.014.
  • Jan 18, 2016: We offer an optional companion seminar for the case studies, see here for further information.

There is a limit on the number of participants for this course with a small number of places being reserved for incomings from abroad and for students from other universities starting their master's courses at TUM this summer. If you want to participate in the case studies course, please register by writing an email to michael.rittertum.de no later than March 1st, 2016.

Schedule

Preliminary Meeting

slightly shortened version of the slides: pdf

A preliminary meeting will take place on February 3rd, 2016, at 16:15 hours in room MI 00.07.014. At this meeting, we will give you some information about the case studies courses in general, what to expect during the courses, this year's projects, important dates and the registration process. This is a joint meeting for both the "Case Studies Discrete Optimization" and the "Case Studies Nonlinear Optimization". If you cannot come to this meeting but would still like to take the course, some more information will be published here after the meeting. Please note that registration by March1st, 2016 is mandatory! If you have any questions that are not answered here or at the preliminary meeting, please contact Michael Ritter at michael.rittertum.de.

Registration

Registration is possible until March 1st, 2016, it is mandatory and binding. To register, please write a short mail to michael.rittertum.de providing the following information:
  • last name, first name
  • your master's program (Mathematics, Mathematics in Bioscience, Mathematics in Science and Engineering, Mathematical Finance and Actuarial Science, Mathematics in Operations Research, others)
  • list of optimization related lectures that you have attended (for lectures from other faculties or universities, 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, experience in using optimization software)
  • ranking of the projects (which do you find most interesting, which would be a good alternative etc.); please rank all projects.
  • persons you would like to work with as a team
  • any additional information that might be relevant for the choice of your project or your partners
  • 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. If this applies to you, please write an email to michael.rittertum.de. If not claimed, these places will be freed for applicants a few weeks before summer term starts. If this applies to you, we will inform you about that by email.

Poster Presentation and Final Workshop

Please be sure to reserve the following dates (attendance is absolutely mandatory):
  • Kickoff Meeting: Monday, April 11th, starting at 16:00 (duration: about 3 hours)
  • "TUMMS": presumably Friday, May 20th, 12:00 - 15:00
  • final workshop: presumably on Saturday, July 9th, 2016 (whole day)

Course Schedule

The course will take place on Mondays, 10:15 - 11:45 hours, and on Wednesdays, 14:00 - 15:30 hours during the semester. We will (usually) meet in room MI 00.09.022. Updated information will be posted here when available.

date time room topics
Fri, Feb 03 16:15 MI 00.07.014 preliminary meeting pdf
Mon, Apr 11 16:00 Interimshörsaal 2 kickoff meeting - assignment of teams and projects
Wed, Apr 13 14:00 MI 00.09.022 project planning and team presentations
Mon, Apr 18 10:15 MI 00.09.022 poster design
Wed, Apr 20 14:00 MI 00.09.022 case study 1
Mon, Apr 25 10:15 MI 00.09.022 case study 2
Wed, Apr 27 14:00 MI 00.09.022 case study 3
Mon, May 02 10:15 MI 00.09.022 internal poster presentation
Wed, May 04 14:00 MI 00.09.022 case study 4
Mon, May 09 23:59   hand in final poster, exhibition booth equipment and orders
Wed, May 11 14:00 MI 00.09.022 presentation skills
Fri, May 20 tba Magistrale TUMMS Poster Presentation
Wed, May 25 14:00 MI 00.09.022 feedback, midterm presentations part 1
Mon, May 30 10:15 MI 00.09.022 midterm presentations part 2
Sat, Jul 09th tba Garching-Hochbrück, Hörsaal 2, 0.01.17 Final Workshop

Materials

All materials for this course are provided on the moodle course page.

Project Summary

Examination Scheduling

Given the large number of students, exams and study programs, scheduling the exams at TUM is a challenging task. Exams should be non-overlapping, preferably with a few days between exams for each individual student. The number of rooms (and thus staff) needs to be minimized, some times of the day are not very popular with students and examiners, some exams require certain rooms or special equipment, enough time needs to be set aside for preparation - and the list goes on. Your task in this project is to meet with the exam scheduling team for the Garching campus of TUM, get an overview of all the hard and soft requirements and the objectives to be considered, and come up with a suitable mathematical model for scheduling the exams. You will then implement this model and test it on real data to see if you can come up with a schedule that is better than the status quo.

Optimal School Bus Routes

Transporting elementary and high school students to their school and back to their homes is usually achieved by a combination of existing public transport and specific school buses. Depending on the age of the students, the teaching times and the locations of their residences, a number of side constraints is to be observed: Transportation times may not be too long, students need to arrive on time but not too early, supervisors may have to accompany the transport, etc. The companies providing the transportation services may also have constraints such as working time constraints for the drivers or availability of suitable vehicles. In addition, there are often changes during the school year (such as rescheduling of classes, unavailability of buses or drivers on short notice, etc.), so the possibility of a fast rescheduling is particularly important. Of course, school buses are costly, thus an optimal planning of the bus routes is important to save the schools and the taxpayers money. In this project, you will meet with practitioners to get to know the relevant constraints, develop a suitable model, research algorithms and implement your solutions using real world data to come up with optimal routing and scheduling for a school bus network.

Scheduling and Logistics in Automobile Production

Modern production chains are often highly integrated and tightly scheduled. For this reason, failure of a single component regularly results in severe problems for a large number of production lines. A key feature of such complex systems is a tight integration of production scheduling and logistics. These systems arise regularly arise in industrial production, but also other fields. The aim of this project is to develop and implement a model that can help in case of disruptions, e.g. by rescheduling, relocating production to different plants or shipping parts or tools necessary to produce certain parts.

Scheduling in Smart Grids

In this project, we want to devise algorithms for offline scheduling problems that an operator of a smart grid faces. In order to improve the efficiency of production and distribution of energy, a smart grid enables automated communication between operator and users of the energy network. This aims at avoiding peak demand periods, which are usually very inefficient, because either energy needs to be stored or additional power plants need to be kept ready for these rather short peak demand periods. Both options require additional resource consumption, which one aims to minimize.

The communication process is enabled by smart metering technology, which communicates the user’s demand flexibility to the operator of the grid. For example, a user may want to charge an electric car after arriving home in the evening and wants the car fully charged by the next morning. When exactly the car is charged within this time window may be rather irrelevant for the user, but gives the grid operator flexibility to shift demand in order to balance out the demand profile. Smart metering systems transfer the power request together with a time window in which this request can be served to the operator.

The operator now tries to schedule all incoming requests so that all received requests are served within their time windows using minimum total energy cost. The energy cost of a certain time slot is a function depending on the total demand in this time slot. The total energy cost sums up the energy cost of all time slots within the planning horizon.

Online Deadline Scheduling

This project deals with tasks that arrive over time and whose accomplishment within a given time frame is essential. Such tasks can be found for instance in medical applications, where the treatment of patients is possibly quite urgent, or automotive applications, where danger has to be recognized in time. Still, minimizing the resource usage is a key objective for with respect to the economy, the environment, and the society. Thus, under the constraint of accomplishing all tasks in time, we would like to minimize the usage of resources, e.g., the number of machines or physicians in the hospital or the number of processors in a car, respectively. The aim of this project is to formalize the problem in possibly different ways, proposing criteria for “good” ways of scheduling tasks, and developing algorithms that compute schedules that meet the proposed criteria.