TUM – TUM – Menü

 

 
SCoNDO III

Students' Conference on Nonlinear and Discrete Optimization - 14. July 2012

 

Acknowledgements

Organizers

The conference is organized by
Christian Böhm
Florian Lindemann
Andre Milzarek
Wolfgang Riedl
Michael Ritter
Paul Stursberg

Conference Program

Morning Sessions

The morning program consists of two sessions with two students' talks scheduled per session. Each talk will be 25 minutes plus discussion. There is a coffee break in between the two sessions.

9:00 a.m. conference opening
9:20 a.m. The Sightseeing Problem
10:00 a.m. Portfolio Optimization with Conditional Value at Risk
11:00 a.m. Decomposition Methods on a Smart Grid Optimization Model
11:40 p.m. Mathematical Optimization in Modern Traffic Control
12:20 p.m. guest talk Optimal University Scheduling by Pirmin Fontaine

Lunch break from 12:50 p.m. until 2:00 p.m.

Afternoon Sessions

There are two afternoon sessions featuring a total of four students' talks (25 minutes each, plus discussion) and an invited talk. There is a coffee break between the two sessions. Additionally, we will have a closing session for evaluation and presentation of certificates.

2:00 p.m. guest talk Housing Markets with Indifferences: A Tale of Two Mechanisms by Haris Aziz
2:30 p.m. Dynamic Heuristic Approach for Timber Transportation with Containers
3:10 p.m. Optimization in Video Reconstruction Problems
4:20 p.m. Routing with Constraints
5:00 p.m. An Inverse Problem to Localize Gas Clouds
5:40 p.m. evaluation, discussion and certificates

Conference Venue

The conference takes place at room 0606 at
Technische Universität München, Stammgelände
main building
Arcisstraße 21

Please remember to enter through the main entrance using your student ID if necessary (or stating that you want to visit the conference or the university library) as the other entrances will be closed on Saturday.


Stammgelände der Technischen Universität München, weitere Pläne und Anfahrtsbeschreibung im TUM-Roomfinder.

Parking is very limited in the area, thus public transport is recommended for getting to the conference venue. The closest subway stops are Theresienstraße (U2), Königsplatz (U2) and Odeonsplatz (U3/4/5/6), the closest bus stop is "Technische Universität" (bus 100). Please note that there is no S-Bahn traffic in the city center on weekends, see http://www.s-bahn-muenchen.de/s_muenchen/view/aktuell/presse/pi_we_sperrung_stamm.shtml  for more information.


Größere Karte anzeigen

Conference Dinner

We meet for conference dinner at 7:00 p.m. at "Lo Studente" , Schellingstraße 30, where tables are reserved for the conference dinner. The restaurant is within about 10 minutes walking distance from the conference venue.


Größere Karte anzeigen

Abstracts and Speakers

The Sightseeing Problem

Tillmann Gaida, Gabriel Guckenbiehl, Andreas Hussing, Katharina Juranek, Marco Ricci
The sightseeing problem is an extension of the team orienteering problem. Given preferences for specific sights in the exemplary city of Munich, a fixed number of days D, time per day T, a total budget B and a starting and ending point p, the goal is to determine D cycles through a subset of sights in order to maximize the total score of preferences. Besides respecting that time spent on sights and rides must not exceed the given limit, the extension of the team orienteering problem consists of an additional constraint that must be adhered to, i.e. money spent on sights must not exceed the given budget. In this talk we will present a solver using a variation of a heuristic by Chao, which originally was written for the team orienteering problem, and our visualization of the optimal tours.

Portfolio Optimization with Conditional Value at Risk

Florian Brandl, Peter Schneider, Christian Donner
Portfolio optimization always yields to a trade-off between profit maximization and risk minimization. Hence an optimal portfolio highly depends on the risk characterization. In contrast to Markowitz’ approach, the traditional approach in industry which assumes the variance as a suitable measurement for risk, we focused our work on the Conditional Value at Risk meaning the expected value of the (1-beta)-percent highest losses. Thereby, we fixed the drawback of punishing positive deviation of the expectation but have been confronted with a higher complexity for calculating the risk. This has been tackled by a linearization and a smoothing approach. Results will be presented in comparison to the Markowitz model and the DAX.

Decomposition Methods on a Smart Grid Optimization Model

Eva Bammann, Vincent Bates, Franziska Penk
Large mixed integer programs tend to be very time consuming to solve, even with commercial optimizers. With an improvement of running times in mind, we develop implementations of a Lagrangian Relaxation and a Bender’s Decomposition algorithm in Xpress. We compare their advantages, to each other as well as to an ordinary solution, by means of a time series DC Power Flow model. The motivation for this analysis lies in it’s real life application, as renewable energies will play a more important role in the future, but require structural changes of the energy grid.

Mathematical Optimization in Modern Traffic Control

Johannes Hofbauer, Ludwig Jäntschi, Michael Lintl, Jonas Wunderlich
With today's world becoming faster and faster, the resulting rising need for mobility cannot be faced only by constructing more and wider roads. Limited resources as well as the goal of environmental sustainability lead to a concept of more effective use of the given infrastructure. In our project, we examined the influence of a mathematical optimization on both urban and freeway traffic. Intending to minimize the total time spent by all road users in a certain system of junctions, we applied a Store-and-Forward approach to parts of Munich's "Moosacher Straße", a heavily traveled arterial thoroughfare. To analyze the positive effects of Nonlinear Optimal Ramp Metering, we looked at an actual freeway setting in Munich's surrounding area.

Optimal University Scheduling

guest talk by Pirmin Fontaine (Technische Universität München, Logistics & Supply Chain Management, TUM School of Management)
Schedules can be found in different kind of areas and because we try to use our time efficiently, these schedules should be optimized. At a university it's all the same. In the topic of university course timetabling one tries to assign weekly lectures to rooms and times. These lecture assignments should avoid conflicts in curricula and of course other constraints, like for instance that a teacher can only give one lecture at the same time or only one course can be held at the same time in one room. This talk will present an ILP-approach to solve the problem and present the positive result of the test with the data of the faculty of mathematics at TUM.

Housing Markets with Indifferences: a Tale of Two Mechanisms

guest talk by Haris Aziz (Technische Universität München, Decision Sciences and Systems, Department of Informatics)
The (Shapley-Scarf) housing market is a well-studied and fundamental model of an exchange economy. Each agent owns a single house and the goal is to reallocate the houses to the agents in a mutually beneficial and stable manner. Recently, Alcalde-Unzu and Molis [2011] and Jaramillo and Manjunath [2011] independently examined housing markets in which agents can express indifferences among houses.They proposed two important families of mechanisms, known as TTAS and TCR respectively. We formulate a family of mechanisms which not only includes TTAS and TCR but also satisfies many desirable properties of both families. As a corollary, we show that TCR is strict core selecting (if the strict core is non-empty). Finally, we settle an open question regarding the running time of the TTAS mechanism. Our study also raises a number of interesting research questions.

(joint work with Bart de Keijzer)

Dynamic Heuristic Approach for Timber Transportation with Containers

Christian Donner, Elisabeth Finhold, Valentin Göbel, Ludwig Jäntschi, Andrei Morozyuk
Changing the status-quo in timber transportation with separate specialized trucks for round logs and sawn lumber to container trucks suitable for both would yield a tremendous optimization potential in the routing of timber transports. Using task graphs the problem can be easily modeled but it comes along with the drawback of a high computational effort for finding exact solutions. Therefore we developed a heuristic approach related to the idea of column generation. Our concepts for a dynamic generation of empty container trips have been implemented and compared to existing research results and our implementation of a known model in matters of computation time and accuracy of the solution. Furthermore we justified why the column generation in the original sense has not been applicable.

Optimization in Video Reconstruction Problems

Benjamin Busam, Philipp Jarde, Dennis Klöckner, Patricia Rachinger, Marco Ricci
Digitization of videos tends to result in corrupted videos, as does, for example, filming with scratched lenses. The reconstruction of this or other lost pixel data can be done using nonlinear optimization methods. We solve these so-called video inpainting problems in two different ways. Initially, we use a total variation regularized model generalized from image inpainting; we solve this problem with an algorithm based on the alternating direction method. To reconstruct videos with changing defects, we utilize an algorithm based on patch matching techniques, which automatically localizes errors and corrects them using low rank matrix approximations. In our presentation, we discuss the different methods and compare their results.

Routing with Constraints

Stefan Franz, Bendix Koopmann, Karolina Kopyczynska, Jakob Lindorff Larsen
We investigated the problem of finding shortest paths w.r.t. the time and an additional cost bound, which leads to NP-hardness. Our practical background is a traffic network with the goal to find the fastest route from one station/node to another with the opportunity to use different means of transport, e.g. bus, taxi, bike or simply by foot while respecting the constraints. Different means have different costs. Thus, the most intuitive model is a multigraph with an edge for every mean of transport between two nodes which represents the stations resp. turnouts. But by modeling the transfer times within a station, every node is split into several nodes, one incoming and one outgoing for each mean of transport, which finally leads to a normal digraph. The problem is modeled as an ILP with minimizing time as objective, float constraints and additional constraints, e.g. the bound of total cost. We solve this problem via CPLEX and an own implemented SOS1-branching approach.

An Inverse Problem to Localize Gas Clouds

Jakob Ameres, Vera Bommer, Matija Hustić, Julia Wenzel
We consider a time-dependent advection-diffusion equation, in which we invert for an unknown initial condition. The problem can be interpreted as finding the initial distribution of a gas cloud from measurements taken after the gas has been released. This inverse problem embodies an optimization problem subject to a partial differential equation. By modifying a given MATLAB implementation we also constructed a realistic scenario for the TUM Campus Garching. Various new features have been explored including box-constraints preventing negative solutions, quantification of uncertainties and implementational speedup. As an extension we studied the inversion not only for an initial condition but for a persistent source of gas.

Research Unit M9


Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
Germany
phone:+49 89 289-16858
fax:+49 089 289-16859
sekretariat-m9ma.tum.de

Professors

Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

Prof. Dr. Stefan Weltge
Discrete Mathematics

News

Jan 25th, 2019
Case Studies 2019: Preliminary Meeting on Wed, Feb 6th, at 16:00 in room MI 03.06.011.