SCoNDO III
## Students' Conference on Nonlinear and Discrete Optimization - 14. July 2012 |

# Acknowledgements

- 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.

# Organizers

The conference is organized byChristian 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 |

## 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

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 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 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.