Logo der Universität Wien

Past events:

Exact approach to solve the Capacitated Vehicle Routing Problem with Stochastic Demands and Restocking Policy

by Prof. Juan José Salazar González (Departamento de Matemáticas, Estadística e Investigación Operativa)

 

Date:          20th February 2018 - Time: 16:30 - 17:30

Location:      SR 14 (seminar room, 2. floor)
                   Uni Vienna 
                   (Oskar-Morgenstern-Platz 1, 1090 Vienna)

 

Abstract:

This talk considers a vehicle routing problem where the customer demands are stochastic variables. Due to uncertainty, along a route the vehicle may be unable to load all planned customers' demand. The vehicle has to return to the depot, unload and then resume its trip. In order to avoid unplanned return trips to the depot, one may decide to make some preventive return: even if it is not full, the vehicle returns to the depot, unload and resume its trip at the next customer. These preventive returns avoid visiting the same customer twice at the expense of possibly making an unneeded return. In this paper, we propose an exact procedure for designing routes to minimize the total expected cost of the routes. It consists of a branch-and-cut algorithm based on the L-shaped method for stochastic programs with binary first-stage variables. The talk provides lower bounds and cuts on the expected costs, and describes the results of computational analysis of a computer implementation on benchmark instances. Instances involving up to 100 customers have been solved to optimality.

 

 

 

This talk is based on a join research manuscript written with François Louveaux and that will appear in "Transportation Science".

 

 

Approximating The FCFS Stochastic Matching Model With Ohm's Law (Operations Research and Control Systems)

by Prof. Edward Kaplan (Yale School of Management, USA)

 

Date:          18th December 2017 - Time: 16:00 - 17:30

Location:      seminar room (DB gelb 03) 
                   TU Vienna 
                   (Wiedner Hauptstraße 8, wing B (yellow area), 3rd floor)

 

Abstract:

The FCFS stochastic matching model, where each server in an infinite sequence is matched to the first eligible customer from a second infinite sequence, developed from queueing problems addressed by Kaplan (1984) in the context of public housing assignments. The goal of this model is to determine the matching rates between eligible customer- and server-types, that is, the fraction of all matches that occur between type-i customers and type-j servers. This model was solved in a beautiful paper by Adan and Weiss (2012), but the resulting equation for the matching rates is quite complicated, involving the sum of permutation-specific terms over all permutations of the server-types. Here we develop an approximation for the matching rates based on Ohm's Law that in some cases reduces to exact results, and via analytical, numerical, and simulation examples is shown to be highly accurate. As our approximation only requires solving a system of linear equations, it provides an accurate and tractable alternative to the exact solution.

(joint work with Mohammad Fazel-Zarandi)


The Max-Cut problem: exact methods and heuristics based on quantum techniques (ISOR)

by Giovanni Rinaldi (IASI-CNR Rome)

 

Date:          11th December 2017 - Time: 16:45 - 17:45

Location:      Sky Lounge 
                   Faculty of Business, Economics and Statistics
                   (Oskar-Morgenstern-Platz 1, 1090 Vienna)

 

Abstract:

The Max-Cut problem is the one of finding a maximum weight cut in a weighted graph. Because of the its great interest among the optimizers, several approaches, also of a quite diverse nature, have been proposed to find good or provably good solutions, which makes it also very interesting as a benchmark problem for new algorithmic ideas. Very recently the problem has received a lot of attention since a dedicated hardware, based on quantum annealing, has been realized that yields good solution in amazingly short times for some particular instances (the Chimera graphs). We review some of the exact optimization algorithms today available and how they behave compared to the new quantum approach.


Numerical methods for Mathematical Programs with Complementarity Constraint (ISOR)

by Mounir Haddou (Univ. Rennes)

 

Date:           27th November 2017 - Time: 16:45 - 17:45

Location:      Hörsaal 7
                   Faculty of Business, Economics and Statistics
                   (Oskar-Morgenstern-Platz 1, 1090 Vienna)

 

Abstract:

Mathematical programs with complementarity constraint (MPCC) are nonlinear optimization problem over a possibly non-convex and non-connected domain. Most of the numerical methods for nonlinear optimization problems relies on solving first-/second- order optimality conditions, which fail to hold for MPCC in general.Some recent progress on MPCC-tailored optimality conditions,  allow to build efficient relaxation methods starting from Kadrani et al in 2009 and followed by Kanzow & Schwarz in 2010.We will discuss the weakest conditions needed to ensure convergence of these methods, present a new method with improved properties and present numerical comparison of these methods on a large number of test problems.


 

 

Unit Commitment under Market Equilibrium Constraints (joint work with Luce Brotcorne, Fabio D'Andreagiovanni and Jérôme De Boeck)

by Bernard Fortz (Univ. Lisbon)

 

Date:          20th November 2017 - Time: 16:45 - 17:45

Location:      Hörsaal 7
                   Faculty of Business, Economics and Statistics
                   (Oskar-Morgenstern-Platz 1, 1090 Vienna)

 

Abstract:

We consider an extension of the Unit Commitment problem with a second level of decisions ensuring that the produced quantities are cleared at market equilibrium. In their simplest form, market equilibrium constraints are equivalent to the first-order optimality conditions of a linear program. The UC in contrast is usually a mixed-integer nonlinear program (MINLP), that is linearized and solved with traditional Mixed Integer (linear) Programming (MIP) solvers. Taking a similar approach, we are faced to a bilevel optimization problem where the first level is a MIP and the second level linear.


 

 

Strategic Bidding for a Price-Maker Hydroelectric Producer (ISOR)

by Steffen Rebennack (KIT)

(joint work with Gregory Steeger and Timo Lohmann)

 

Date:           13th November 2017 - Time: 16:45 - 17:45

Location:      Hörsaal 7
                   Faculty of Business, Economics and Statistics
                   (Oskar-Morgenstern-Platz 1, 1090 Vienna)

 

Abstract:

In bid-based markets, energy producers seek bidding strategies that maximize their revenue. In this talk, we seek the maximum-revenue bidding schedule for a single price-maker hydroelectric producer. We assume the producer sells energy in the day-ahead electricity market and has the ability to impact the market-clearing price with its bids. Our approach models the price-maker hydroelectric producer's bidding decision via a combination of Stochastic Dual Dynamic Programming and Lagrangian relaxation. In this framework, we dualize the water balance equations, allowing an exact representation of the non-concave immediate revenue function, while preserving the concave shape of the future revenue function. We model inflow uncertainty and its stagewise dependence by a periodic autoregressive model. To demonstrate our approaches' utility, we model Honduras' electricity market assuming that the thermal producers act as price takers and that one price-maker hydro producer operates all of the hydroelectric plants.


 

 

Jahrestreffen der Arbeitsgruppe für Optimal Control (ÖGOR)

Ort: Hörsaal 5

Zeit: ab 14:00 Uhr

 

Programm:

- Begrüßung durch die Arbeitskreisleiter sowie den ÖGOR Präsidenten (Raimund Kovacevic)

- Gustav Feichtinger (TU Wien) und Reinhard Neck (AAU Klagenfurt): "An Overview of the Developments of Optimal Control with Economic Applications in Austria"

14:30-15:30 Georges Zaccour (HEC Montreal): "Non-Deceptive Counterfeiting and Consumer Welfare: A Differential Game Approach"

15:30-16:00 Kaffeepause

16:00-17:30:

- Johanna Grames (TU Wien): "Optimal investment and location decisions of a firm in a flood risk area using Impulse Control Theory"

- Franz Wirl (Universität Wien): "Relevant Insights in Economics and Management from Dynamic Modelling"

- Vladimir Veliov (TU Wien): "Some new developments in Model Predictive Control"


The max-cut-polytope and its set-completely-positive representations (ISOR)

by Florian Jarre (Univ. Düsseldorf)

 

Date:           23th October 2017 - Time: 16:45 - 17:45

Location:      Hörsaal 7
                   Faculty of Business, Economics and Statistics
                   (Oskar-Morgenstern-Platz 1, 1090 Vienna)

 

Abstract:

First, two different representations and inner and outer nonlinear approximations of the (real) max-cut polytope are discussed. Applications from digital communication lead to a complex analogue of the max-cut polytope, the complex "unit modulus lifting''. The definition of the complex unit modulus lifting is rather similar to its real counterpart, but it does not allow a generalization of triangle inequalities. Instead, for n=3, the semidefinite approximation is exact. Some relations to set-completely-positive representations in the real and in the complex case close the presentation.


 

 

Biased Random-Key Genetic Algorithms: Components, Evolutionary Dynamics and Applications

by Prof. Celso C. Ribeiro (Universidade Federal Fluminense, Rio de Janeiro, Brazil)

 

Date:           19th October 2017 - Time: 11:30 - 12:30

Location:      Seminarraum 6
                   Faculty of Business, Economics and Statistics
                   (Oskar-Morgenstern-Platz 1, 1090 Vienna)

 

Abstract:

A biased random-key genetic algorithm (BRKGA) is a general search procedure for finding optimal or near-optimal solutions to hard combinatorial optimization problems. It is derived from the random-key genetic algorithm of Bean (1994), differing in the way solutions are combined to produce offspring. BRKGAs have three key features that specialize genetic algorithms. First, a fixed chromosome encoding using a vector of N random keys over the real interval [0, 1), where the value of N depends on the instance of the optimization problem. Second, a well-defined evolutionary process adopting a parameterized uniform crossover to generate offspring and thus evolve the population. Third, the introduction of new chromosomes called mutants in place of the mutation operator usually found in evolutionary algorithms. Such features sim-plify and standardize the procedure with a set of self-contained tasks from which only one is problem-dependent: that of decoding a chromosome, i.e. using the keys to construct a solution to the underlying optimization problem, from which the objective function value or fitness can be computed. In this talk, we review the basic compo-nents of a BRKGA and introduce a framework for quick implementations of BRKGA heuristics. We then illustrate the application of this framework to a few case studies in network routing, load scheduling and data mining problems. We conclude with a brief review of other domains where BRKGAs have been applied.


 

 

Synchronized Worker and Vehicle Routing for Ground Handling at Airports (PROLOG/ PLIS)

by Rainer Kolisch (TUM)

 

Date:          4th October 2017 - Time: 17:30

Location:      Hörsaal 7
                   Faculty of Business, Economics and Statistics
                   (Oskar-Morgenstern-Platz 1, 1090 Vienna)

 

Abstract:

Based on the problem setting of a major ground handling company, we introduce a new problem, the vehicle routing problem with worker and vehicle synchronization (VRPWVS), which belongs to the class of vehicle routing problems with multiple synchronization constraints (VRPMSs). The VRPWVS deals with routing workers to tasks while meeting each task's time window and incor-porating each task's specific skill requirements. A worker uses vehicles to travel between tasks of different airplanes making movement synchronization in time and space necessary. In addition to movement, the VRPWVS is best characterized by the new concept of active load synchronization. For the problem, we propose a mixed integer linear programming (MILP) model based on the new concept of itinerary categories. To solve real world problems, we present a Hybrid Metaheuristic with Tabu Search, Guided Local Search and Large Neighborhood Search. We examine the per-formance of the MILP and the Hybrid Metaheuristic in computational experiments using data from Munich International Airport and achieve potential savings of 4:9 million Euros per year when comparing the results of the Hybrid Metaheuristic with those of the current planning proce-dure of the ground handling company.


 

 

Facility location with Bernoulli demands: optimization models and solution procedures (ISOR)

by Francisco Saldanha da Gana (Univ. Lisbon)

 

Date:          2th October 2017 - Time: 16:45 - 17:45

Location:      Hörsaal 7
                   Faculty of Business, Economics and Statistics
                   (Oskar-Morgenstern-Platz 1, 1090 Vienna)

 

Abstract:

This seminar focuses a two-stage stochastic discrete facility location problem involving a finite set of potential locations for the facilities and a set of customers with a demand described by a Bernoulli random variable. In other words, demand regards a service request and not a quantity of some commodity. The facilities are capacitated in terms of the number of customers they can serve. A here-and-now decision is to be made concerning the facilities to open and the (single) allocation of the customers to the selected facilities. Since this decision is made prior to knowing which customers are in fact calling for being served, a facility may end up facing a demand higher than its capacity. In this case, a recourse action is required that is assumed to be associated with outsourcing. Two outsourcing strategies are studied. In the first one—facility outsourcing— extra capacity is acquired for those facilities running out of capacity. In the second one— customer outsourcing—an external service provider is considered for fulfilling the missing capacity. The goal of the problem is to minimize the total setup cost for the facilities plus the expected service and outsourcing costs.
Modeling aspects and solution procedures that have been studied for the problem are discussed. A distinction is made between the homogeneous and the non-homogeneous cases. In the former setting, all customers have the same probability of requesting the service. This allows deriving compact mathematical programming formulations for the problem that can be tackled by an off-the-shelf optimization solver to solve to optimality instances of realistic size. In the latter, we must resort to approximations since the recourse function becomes intractable even for toy
instances of the problem.


 

 


Workforce Management in Delivery Operations
(ProLog/ PLIS Colloquium)

       by Maciek Nowak (Quinlan School of Business)

 

Date:           29th May 2017 - Time: 13:30

Location:      Hörsaal 12
                   Faculty of Business, Economics and Statistics
                   (Oskar-Morgenstern-Platz 1, 1090 Vienna)

Abstract:
Service quality and driver efficiency in the delivery industry may be enhanced by in-creasing the regularity with which a driver visits the same set of customers. However, effectively managing a workforce of drivers may increase travel distance, a traditional metric of the vehicle routing problem (VRP). This research evaluates the effect that workforce management has on routing costs, providing insight for managerial decision making. The analysis is presented in the context of the period vehicle rout-ing problem (PVRP), an extension of the VRP with vehicle routes constructed to ser-vice customers according to preset visit frequencies over an established period of time. We develop models to apply workforce management principles. Through a computational study with standard PVRP test cases and real-world delivery data, we show that multi-objective PVRP models can achieve a balance between workforce management and travel distance goals. With the proper parameters in place, work-force management principles may be successfully applied without sacrificing other operational objectives.


Exact Methods for Non-Hamiltonian Routing Problems (ISOR Colloquium)
       by Hande Yaman (Bilkent Univ.)

 

Date:           29th May 2017 - Time: 16:45 - 17:45

Location:      Hörsaal 7
                   Faculty of Business, Economics and Statistics
                   (Oskar-Morgenstern-Platz 1, 1090 Vienna)

Abstract:
The classical traveling salesman problem (TSP) seeks a Hamitonian cycle (a cycle that visits every node exactly once) of minimum cost. Even though early routing problems focus on finding Hamiltonian cycles, many routing applications also require the choice of nodes that are to be visited or the number of times a node is visited. In this talk, we present exact methods for three non-Hamiltonian routing problems; namely, the split delivery VRP, the time constrained maximal covering TSP and the VRP with roaming delivery locations. We propose an iterative approach to solve the split delivery VRP where a relaxation is tigthened at each iteration by adding new variables and constraints. For the time constrained maximal covering TSP, we give a new family of facet defining inequalities and use them in a branch-and-cut approach. Finally, we present a branch-and-price algorithm to solve the VRP with roaming delivery locations. This is joint work with O.E. Karasan, M. Savelsbergh and G. Ozbaygin.


Optimal insider control of stochastic partial differential equations,with applications to optimal harvesting and optimal insider portfolio under noisy observations (ORCOS Seminar)
       by Prof. Bernt  Øksendal (Department of Mathematics, University of Oslo)

 

Date:           9th May 2017 - Time: 16:30 - 18:00

Location:     seminar room (DB gelb 04) 
                 TU Vienna
                 wing B (yellow area), 4th floor
                 Wiedner Hauptstraße 8

Abstract:
We study the problem of optimal control with inside information of an SPDE (a stochastic evolution equation) driven by a Brownian motion and a Poisson random measure.  Our optimal control problem is new in two ways:

(i) The controller has access to inside information, i.e. access to information about a future state of the system,

(ii) The integro-differential operator of the SPDE might depend on the control.

In the first part of the paper, we formulate a sufficient and a necessary maximum principle for this type of control problem, in the following two cases:  

(a) The control is allowed to depend both on time t and on the space variable x.  

(b) The control is not allowed to depend on x.  

In the second part of the paper, we apply the results above to the problem of optimal control of an SDE system when the inside controller has only noisy observations of the state of the system. Using results from nonlinear filtering, we transform this noisy observation SDE inside control problem into a full observation SPDE insider control problem. The results are illustrated by explicit examples.

The presentation is based on joint works with Olfa Draouil, University of Tunis El Manar, Tunisia.


Optimized train speed profiles
(PLIS/ PROLOG Colloquium)

       by David Pisinger (DTU)

 

Date:           05.04.2017 - Time: 17:00

Location:      SE 15
                   Faculty of Business, Economics and Statistics
                   (Oskar-Morgenstern-Platz 1, 1090 Vienna)

 

 

Abstract:

We present a novel solution method to generate energy-efficient train speed profiles. As opposed to previous analytical methods, we propose a graph representation of the problem, making it possible to generate pareto-optimal train speed profiles by use of Dynamic Programming (DP). Instead of using uniform discretization of space, time or speed, we rely on an event-based decomposition that drastically reduces the search space. Moreover, we are able to handle speed limitations, passage point time windows, as well as various measures of robustness (buffer time, number of speed changes). Such additional constraints were difficult to handle by previous approaches. Based on an extensive number of real-life problem instances our benchmark shows that the proposed solution method is able to reduce the energy consumption by 3.3% on average compared to existing solutions. The computational times are very low, making it possible to handle unexpected changes in speed restrictions or timings by recalculating the schedule. This is a great advantage compared to static offline lookup tables.

(co-authors: Jørgen Thorlund Haahr)


Differential Games with incomplete asymmetric information on the initial condition
(ORCOS Seminar)

       by Prof. Marc Quincampoix (Universite de Bretagne Occidentale)

 

Date:           04.04.2017 - Time: 16:30-18:00

Location:      seminar room (DB geld 04)
                   (Wiedner Hauptstrasse 8, wing B (yellow area), 4th floor)
                   TU Wien

 

 

Abstract:

We investigate  a two-players zero-sum differential game with an incomplete information. The first player has a complete information on the initial state of the game while the second player as only an information of probabilistic nature : he knows a probability measure on the initial state. The existence of a value for such game was obtained only when the probability measure has a finite support. Such differential games with finite type incomplete information can be viewed as a generalization of the famous Aumann-Maschler theory for repeated games.

The main goal and novelty of the present work consists in obtaining and investigating a Hamilton Jacobi  Isaacs Equation satisfied by the upper and the lower values of the game. Since we obtain an uniqueness for such Hamilton Jacobi equation, as a byproduct, this gives the existence of a value of the differential game. Since the Hamilton Jacobi equation is naturally stated in the space of probability measures, we use the Wasserstein distance and some tools of optimal transport theory.


Mathematical optimization approaches for facility layout problems (ISOR Colloquium)
       by Miguel F. Anjos (PolyU Montreal)

 

Date:           20th March 2017 - Time: 16:45 - 17:45

Location:      Hörsaal 7
                   Faculty of Business, Economics and Statistics
                   (Oskar-Morgenstern-Platz 1, 1090 Vienna)

 

 

Abstract:

Facility layout problems are an important class of operations research problems that has been studied for several decades. Most variants of facility layout are NP-hard, therefore global optimal solutions are difficult or impossible to compute in reasonable time. Mathematical optimization approaches that guarantee global optimality of solutions or tight bounds on the global optimal value have nevertheless been successfully applied to several variants of facility layout. In this talk, we review three classes of layout problems, namely row layout, unequal-areas layout, and multifloor layout, and summarize the recent developments in applying mathematical optimization to these classes. We also present some of our latest research results. We also briefly discuss directions that remain open for future research.


Kick-Off Event:

Date:           13th March 2017 - Time: 15:00

Location:      Hörsaal 5
                   Faculty of Business, Economics and Statistics
                   (Oskar-Morgenstern-Platz 1, 1090 Vienna)

Guest:  Christian Blum, PhD (Artificial Intelligence Research Institute & Spanish National Research Council )

Topic:   CMSA: Taking profit from ILP solvers in the context of large problem instances

Link zur Einladung!

 

Abstract:
The combination of metaheuristics with complete techniques, such as integer linear programming (ILP) solvers, is one of the current lines of research in combinatorial optimization. The main aim behind such approaches is to exploit the complementary character of different optimization strategies in order to obtain robust algorithms that generate high-quality solutions in reasonable computation times. Given a combinatorial optimization problem, general purpose ILP solvers such as CPLEX are often highly efficient for solving instances up to a certain size which is problem-dependent. This is because they are built upon many years of research and they make use of efficient implementations of cutting edge ILP technologies. One of the motivations for the combination of metaheuristics with ILP solvers such as CPLEX is the aim of taking profit from the application of ILP solvers even when the considered problem instances are too large for applying these solvers directly. In this keynote talk we will present our most recent algorithmic development that resulted from the motivation outlined above: construct, merge, solve & adapt (CMSA). Moreover, we present our initial investigation on the relation of CMSA with large neighborhood search (LNS), which is one of the standard ways of combining local search with ILP solvers.

Faculty of Business, Economics and Statistics
University of Vienna
Oskar-Morgenstern-Platz 1
A-1090 Vienna


T: +43-1-4277-38092
F: 43-1-4277-838094
University of Vienna | Universitätsring 1 | 1010 Vienna | T +43-1-4277-0