Students' Conference on Nonlinear and Discrete Optimization - 14. July 2012
- The courses Case Studies Discrete Optimization and Case Studies Nonlinear Optimization have been supported through study contributions %SBICON%.
- The workshop is supported by the department of mathematics of Technische Universität München and by the International Graduate School of Science and Engineering.
OrganizersThe conference is organized by
|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|
|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|
Technische Universität München, Stammgelände
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
Größere Karte anzeigen
Abstracts and Speakers
The Sightseeing ProblemTillmann 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 RiskFlorian 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 ModelEva 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 Benders 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 its 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 ControlJohannes 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 Schedulingguest 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 Mechanismsguest 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  and Jaramillo and Manjunath  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 ContainersChristian 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 ProblemsBenjamin 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 ConstraintsStefan 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 CloudsJakob 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.