Optimization seminar

×

Modal title

Modal content

Autumn Semester 2010

Date / Time Speaker Title Location
20 September 2010
16:30-18:00
Prof. Dr. Ulrike Leopold-Wildburger
Universität Graz, Austria
Event Details

Optimization Seminar

Title Harvesting Behavior in a Simulated Lotka-Volterra Model - An Availability Fallacy
Speaker, Affiliation Prof. Dr. Ulrike Leopold-Wildburger, Universität Graz, Austria
Date, Time 20 September 2010, 16:30-18:00
Location HG G 19.1
Abstract For the analysis presented in this paper we use an experiment to study human behavior in a simulated environment based on a simple Lotka-Volterra predator-prey model. The aim is to maximize the profit of the harvest of prey and predator simultaneously and to study the influence of different harvesting strategies on the outcome in terms economic performance. The results of the empirical analysis show that the behavior of the participants is significantly dependent on the amount of available objects, independent of the revenue. Subjects perform efficiently according to the rules when valuable objects are prey, however behave significantly inefficient when high price objects are predator. Joint work with Stefan Pickl.
Assets Abstract pdffile_download
Harvesting Behavior in a Simulated Lotka-Volterra Model - An Availability Fallacyread_more
HG G 19.1
27 September 2010
16:30-18:00
Vladimir Shikhman
RWTH Aachen, Germany
Event Details

Optimization Seminar

Title Bilevel Optimization: on the Structure of the Feasible Set
Speaker, Affiliation Vladimir Shikhman, RWTH Aachen, Germany
Date, Time 27 September 2010, 16:30-18:00
Location HG G 19.1
Abstract We consider bilevel optimization from the optimistic point of view. Let the pair (x,y) denote the variables. The main difficulty in studying such problems lies in the fact that the lower level contains a global constraint. In fact, a point (x,y) is feasible if y solves a parametric optimization problem L(x). In this paper we restrict ourselves to the special case that the variable x is one-dimensional. We describe the generic structure of the feasible set M. Moreover, we discuss local reductions of the bilevel problem as well as corresponding optimality criteria. Finally, we point out typical problems that appear when trying to extend the ideas to higher dimensional x-dimensions. This will clarify the high intrinsic complexity of the general generic structure of the feasible set M and corresponding optimality conditions for the bilevel problem U. In collaboration with H. Th. Jongen.
Bilevel Optimization: on the Structure of the Feasible Setread_more
HG G 19.1
4 October 2010
16:30-18:00
Oliver Friedmann
Ludwig-Maximilians-Universität, München
Event Details

Optimization Seminar

Title A subexponential lower bound for the Random Facet algorithm for Parity Games
Speaker, Affiliation Oliver Friedmann, Ludwig-Maximilians-Universität, München
Date, Time 4 October 2010, 16:30-18:00
Location HG G 19.1
Abstract Parity Games form an intriguing family of infinite duration games whose solution is equivalent to the solution of important problems in automatic verification and automata theory. We present a family of parity games on which the Random Facet algorithm has an expected running time close to the subexponential upper bound. This is the first explicit construction for an LP-type problem on which the Random Facet algorithm is not polynomial.
A subexponential lower bound for the Random Facet algorithm for Parity Gamesread_more
HG G 19.1
18 October 2010
16:30-18:00
Dr. Jan Foniok
ETH Zurich, Switzerland
Event Details

Optimization Seminar

Title Combinatorial tools for linear complementarity problems
Speaker, Affiliation Dr. Jan Foniok, ETH Zurich, Switzerland
Date, Time 18 October 2010, 16:30-18:00
Location HG G 19.1
Abstract Linear complementarity problems (LCPs) unify linear and quadratic programs and bimatrix games. They are NP-hard in general, but we concentrate on special cases, where the input is restricted to matrices from some special class. An important case is the class of P-matrices. In this case, no hardness result is known (and NP-hardness is in some precise sense unlikely) but neither are polynomial-time algorithms. In order to analyse algorithms for linear complementarity problems, we introduce two kinds of combinatorial tools: oriented matroids and unique-sink orientations of hypercubes. I will discuss recent progress on this front. Various parts of the talk are based on joint work with subsets of the following: Komei Fukuda, Bernd Gärtner, Lorenz Klaus, Hans-Jakob Lüthi.
Combinatorial tools for linear complementarity problemsread_more
HG G 19.1
25 October 2010
16:30-18:00
Daniel Kuhn
Imperial College London, UK
Event Details

Optimization Seminar

Title Scenario free approximations to stochastic programming via decision rules
Speaker, Affiliation Daniel Kuhn, Imperial College London, UK
Date, Time 25 October 2010, 16:30-18:00
Location HG G 19.1
Abstract The standard approach to solve a multistage stochastic program is to approximate the stochastic process of the underlying random parameters by a scenario tree. This method suffers from the curse of dimensionality since scenario trees are known to grow exponentially with the number of decision stages. Instead of discretizing the stochastic process, one can alternatively approximate the recourse decisions by a linearly parameterized family of decision rules. This complementary approach is computationally attractive since the resulting approximate problems often scale polynomially with the number of decision stages. While this decision rule approximation provides a feasible solution and a conservative estimate of the true optimal value of the stochastic program, it can incur a substantial loss of optimality. In this talk we show that applying the decision rule approximation to the original as well as a dual version of the stochastic program yields upper and lower bounds on the true optimal value. The gap between the bounds estimates the approximation error. We also show that linear decision rules, which approximate the recourse decisions by linear functions of the random parameters, can solve an inventory problem from the literature with up to 80 stages at about 5% accuracy. However, linear decision rules can perform poorly if the true optimal recourse decisions are highly non-linear, as is often the case for stochastic programs with many random parameters per stage. In this case, we improve the approximation quality by using lifting techniques to optimize efficiently over a class of piecewise linear continuous decision rules. Short bio Daniel Kuhn is a lecturer in the Department of Computing at Imperial College London. Before taking up his lectureship, he held post-doctoral research fellowships at Imperial College and at Stanford University and was head of the derivatives research unit at the Institute for Operations Research and Computational Finance at the University of St. Gallen. He holds a diploma in Theoretical Physics from ETH Zurich and a PhD in Operations Research from University of St. Gallen. His current research interests are focused on the development of efficient computational methods for the solution of stochastic and robust optimization problems and the design of approximation schemes which ensure their computational tractability. This theoretical work is primarily application-driven, the main application areas being energy systems, finance and engineering.
Scenario free approximations to stochastic programming via decision rulesread_more
HG G 19.1
* 1 November 2010
16:30-18:00
Bart De Schutter
TU Delft, The Netherlands
Event Details

Optimization Seminar

Title Hierarchical MPC for intelligent vehicle-highway system
Speaker, Affiliation Bart De Schutter, TU Delft, The Netherlands
Date, Time 1 November 2010, 16:30-18:00
Location HG G 19.2!
Abstract We present an integrated traffic management and control approach for Intelligent Vehicle Highway Systems (IVHS). These IVHS consist of interacting roadside controllers and intelligent vehicles that are organized in platoons with short intra-platoon distances, and larger distances between platoons. All vehicles are assumed to be fully automated, i.e., throttle, braking, and steering commands are determined by an automated on-board controller. The proposed control approach is based on a hierarchical traffic management and control architecture for IVHS, and it also takes the connection and transition between the non-automated part of the road network and the IVHS into account. The proposed hierarchical architecture provides a scalable approach where at different levels of the hierarchy different temporal and spatial scales are taken into account. We detail how model predictive control (MPC) can be used at several levels of the control hierarchy, in particular, for the roadside controllers, the area controllers, and the regional controllers. The roadside controllers determine optimal speed limits and lane allocations as well as optimal release times for the platoons at the on-ramps. The area controllers provide area-wide dynamic route guidance for the platoons, while the regional controllers determine appropriate flows between areas. For each hierarchy we discuss appropriate models and the different optimization approaches that can be used. In particular, we show that for the area and regional controller, one can recast the MPC optimization problem into a mixed-integer linear problem. Short bio Bart De Schutter received the degree in electrotechnical-mechanical engineering in 1991 and the doctoral degree in Applied Sciences (summa cum laude with congratulations of the examination jury) in 1996, both at the K.U.Leuven, Belgium. After obtaining his PhD degree, he was a senior research assistant of the FWO-Flanders at the ESAT-SISTA research group of the K.U.Leuven. In 1998 he transferred to the Control Systems Engineering group of the Faculty of Information Technology and Systems of Delft University of Technology, The Netherlands. In 2003 the control groups of Delft University of Technology merged into the Delft Center for Systems and Control (DCSC). Currently, Bart De Schutter is a full professor at Delft Center for Systems and Control (DCSC) department of Delft University of Technology. Bart De Schutter was awarded the 1998 SIAM Richard C. DiPrima Prize and the 1999 K.U.Leuven Robert Stock Prize for his PhD thesis. He is associate editor of Automatica and of the IEEE Transactions on Intelligent Transportation Systems. He is also coordinator of the European FP7 STREP project Hierarchical and distributed model predictive control of large-scale complex systems (HD-MPC).
Hierarchical MPC for intelligent vehicle-highway systemread_more
HG G 19.2!
8 November 2010
16:30-18:00
Prof. Dr. Friedrich Eisenbrand
EPF Lausanne, Switzerland
Event Details

Optimization Seminar

Title Set Covering: Additive integrality gaps and discrepancy
Speaker, Affiliation Prof. Dr. Friedrich Eisenbrand, EPF Lausanne, Switzerland
Date, Time 8 November 2010, 16:30-18:00
Location HG G 19.1
Set Covering: Additive integrality gaps and discrepancy
HG G 19.1
15 November 2010
16:30-18:00
Prof. Dr. Michel Bierlaire
EPF Lausanne, Switzerland
Event Details

Optimization Seminar

Title A Heuristic for Nonlinear Global Optimization
Speaker, Affiliation Prof. Dr. Michel Bierlaire, EPF Lausanne, Switzerland
Date, Time 15 November 2010, 16:30-18:00
Location HG G 19.1
Abstract We present a heuristic for nonlinear global optimization combining a variable neighborhood search framework with a modified trust-region algorithm as local search. The proposed method presents the capability to prematurely interrupt the local search if the iterates are converging to a local minimum that has already been visited or if they are reaching an area where no significant improvement can be expected. The neighborhoods, as well as the neighbors selection procedure, are exploiting the curvature of the objective function. Numerical tests are performed on a set of unconstrained nonlinear problems from the literature. Results illustrate that the new method significantly outperforms existing heuristics from the literature in terms of success rate, CPU time, and number of function evaluations. Short bio Belgian, born in 1967, Michel Bierlaire holds a MSc and a PhD in Mathematical Sciences from the Facultés Universitaires Notre-Dame de la Paix, Namur, Belgium (University of Namur). Between 1995 and 1998, he was research associate and project manager at the Intelligent Transportation Systems Program of the Massachusetts Institute of Technology (Cambridge, Ma, USA). Between 1998 and 2006, he was a junior faculty in the Operations Research group ROSO within the Institute of Mathematics at EPFL. In 2006, he was appointed associate professor in the School of Architecture, Civil and Environmental Engineering at EPFL, where he became the director of the Transport and Mobility laboratory. Since 2009, he is the director of TraCE, the Transportation Center at EPFL. His main expertise is in the design, development and applications of models and algorithms for the design, analysis and management of transportation systems. Namely, he has been active in demand modeling (discrete choice models, estimation of origin-destination matrices) and Dynamic Traffic Management Systems.
A Heuristic for Nonlinear Global Optimizationread_more
HG G 19.1
22 November 2010
16:30-18:00
Prof. Dr. Karl Frauendorfer
University of St. Gallen, Switzerland
Event Details

Optimization Seminar

Title Riskadjusted Portfolio Optimization in the Energy Industry
Speaker, Affiliation Prof. Dr. Karl Frauendorfer, University of St. Gallen, Switzerland
Date, Time 22 November 2010, 16:30-18:00
Location HG G 19.1
Abstract The major type of electricity supply contracts, which is widely-used between industrial customers or big end customers and suppliers of electricity and/or natural gas, are full supply contract. The supplier is faced with a substantial financial risk that arise in particular through the price dynamics of hedge instruments and the mismatch between predicted load profile and hedging profile. In addition the supplier is exposed also to volume risks, as the predicted load schedule only represents an estimation of the uncertain electricity demand. In order to transfer this volume risk into a monetary quantity, the volume deviations have to be modeled appropriately and have to be priced according to the future price dynamics. The quantification of the relevant risk premia has to take place in line with the respective market. The investigated risk categories as well as appropriate evaluation techniques will be presented with application to real problem statements within the energy sector.
Riskadjusted Portfolio Optimization in the Energy Industryread_more
HG G 19.1
29 November 2010
16:30-18:00
Prof. Dr. François Margot
Tepper School of Business, Carnegie Mellon University
Event Details

Optimization Seminar

Title Natural Gas Storage: Valuation and Hedging
Speaker, Affiliation Prof. Dr. François Margot, Tepper School of Business, Carnegie Mellon University
Date, Time 29 November 2010, 16:30-18:00
Location HG G 19.1
Abstract A stochastic dynamic program is the problem of minimizing the expectation of the optimal value of a problem under stochastic uncertainty, problem that can be stated using a recurence relation. An optimal solution is a policy specifying the action to take in all situations. A lower bound on the optimal value can usually be obtained by Monte-Carlo simulation of any feasible policy. The generation of a tight upper bound is in general more difficult, but a framework developed by Brown, Smith and Sun (2010) can be used. As an illustration, we discuss its use for valuation and hedging of natural gas storage options. We show that heuristics used by traders for valuation are close to optimal, while we argue that their insistence of using futures price models with a large number of factor is unnecessary, even for financial hedging operations. References: G. Lai, F. Margot, N. Secomandi, "An Approximate Dynamic Programming Approach to Benchmark Practice-Based Heuristics for Natural Gas Storage Valuation", Operations Research 58 (2010), 564--582 http://wpweb2.tepper.cmu.edu/fmargot/PDF/ngstorage.pdf N. Secomandi, G. Lai, F. Margot, A. Scheller-Wolf, D. Seppi, "The Effect of Model Error on the Valuation and Hedging of Natural Gas Storage", Tepper Working Paper 2010-E71 (2010) http://wpweb2.tepper.cmu.edu/fmargot/PDF/NGStorageTrading.pdf
Natural Gas Storage: Valuation and Hedgingread_more
HG G 19.1
* 6 December 2010
17:30-18:15
Benjamin Hiller
Konrad-Zuse-Zentrum für Informationstechnik, Berlin
Event Details

Optimization Seminar

Title Online Optimization: Probabilistic Analysis and Algorithm Engineering
Speaker, Affiliation Benjamin Hiller, Konrad-Zuse-Zentrum für Informationstechnik, Berlin
Date, Time 6 December 2010, 17:30-18:15
Location HG G 19.1
Abstract In this talk I will give a not-so-brief overview on the work I did in my PhD thesis. The subject of my thesis was online optimization, which deals with decision making in an environment where the data describing the process to optimize becomes available over time, i.e. online. The first part of the thesis presents new optimization algorithms for the online control of complex real-world systems. In particular, we develop rigorous optimization algorithms based on Integer Programming for the scheduling of elevators in high rise buildings. We propose algorithms for destination call elevator systems, in which a passenger enters his desired destination floor already at his current floor. Based on extensive simulations, we find that our methods improve the performance in both applications, leading to shorter waiting times for the customers/passengers. The second part introduces a novel probabilistic analysis for online algorithms based on the notion of stochastic dominance. Using this approach we are able to show new results for paging and bin coloring algorithms. These results provide more detailed insights into the relative performance of online algorithms than existing approaches.
Online Optimization: Probabilistic Analysis and Algorithm Engineeringread_more
HG G 19.1
13 December 2010
16:30-18:00
Dr. Utz-Uwe Haus
ETH Zurich, Switzerland
Event Details

Optimization Seminar

Title Boolean models for cellular signaling: Construction, Falsification, Analysis, and Selecting Dynamic Alternatives
Speaker, Affiliation Dr. Utz-Uwe Haus, ETH Zurich, Switzerland
Date, Time 13 December 2010, 16:30-18:00
Location HG G 19.1
Abstract The ability of discrete models of cellular signaling processes to integrate qualitative information at different biological levels, from receptor-ligand coupling to transcription is becoming an essential tool for understanding complex signaling behavior. We propose a static and a dynamic Boolean approach to model biological signaling networks, and show how each can be used to answer relevant biological questions. The problems arising are NP-complete, but an interesting subclass is linear-time solvable, generalizing Tarjan’s SAT algorithm. For infeasible instances, structured relaxation and computation of all maximally feasible subsystems is discussed.
Boolean models for cellular signaling: Construction, Falsification, Analysis, and Selecting Dynamic Alternativesread_more
HG G 19.1
20 December 2010
16:30-18:00
Christian Wagner
ETH Zurich, Switzerland
Event Details

Optimization Seminar

Title Maximal lattice-free rational polyhedra: a proof of finiteness
Speaker, Affiliation Christian Wagner, ETH Zurich, Switzerland
Date, Time 20 December 2010, 16:30-18:00
Location HG G 19.1
Abstract A convex set with non-empty interior is maximal lattice-free if it is inclusion-maximal with respect to the property of not containing integer points in its interior. Maximal lattice-free convex sets are known to be polyhedra. Recently, it has been shown that, up to affine mappings preserving the integer lattice, the number of maximal lattice-free rational polyhedra of a given precision is finite. In this talk, I will explain the key steps of the proof and the underlying geometry.
Maximal lattice-free rational polyhedra: a proof of finitenessread_more
HG G 19.1

Notes: events marked with an asterisk (*) indicate that the time and/or location are different from the usual time and/or location and if you want you can subscribe to the iCal/ics Calender.

Organizers: Komei Fukuda, Bernd Gärtner, Diethard Klatte, Hans-Jakob Lüthi, John Lygeros, János Mayer, Manfred Morari, Karl Schmedders, Robert Weismantel

JavaScript has been disabled in your browser