EU directives set out targets for renewable electricity, heat and transport. Low carbon technologies (LCTs) such as heat pumps (HPs) and electric vehicles (EVs) are critical components of national climate action plans to respond to the need to decarbonise heating and transport. The rate of adoption of these LCTs and other technologies such as domestic photovoltaic (PV) generation is uncertain. The impact of geographic clustering, and the range of technology options for EVs and HPs further complicate the evaluation of the impacts on the low voltage (LV) electricity distribution network, and pose considerable challenges to the management and operation of distribution networks. In this paper we review design demands of LV networks in urban areas, focusing on the potential of PV for local energy communities. We describe a mixed Integer programming (MIP) model to support electricity smart grid upgrade decisions in the context of an energy community in an existing urban setting. We evaluate the MIP model on an adaption of an IEEE radial network benchmark instance augmented with geographic data, and present interesting computational results. We highlight potential research avenues to address uncertainty in the problem instances.
X-Heuristics & Agile Algorithms with Applications to Transportation, Logistics and Finance
Prof. Dr. Angel A. Juan (University of Bologna) | 23.1.2020 14:00 | SR5 OMP1
This presentation will introduce the ICSO@IN3 group at Barcelona and will provide an overview of the different research lines we have been exploring during the last years as well as the ones we are now addressing. In particular, a discussion of "x-heuristics" will be provided. This includes concepts such as biased-randomized algorithms (combination of skewed probability distributions with heuristics), simheuristics (combination of metaheuristics with simulation), learnheuristics (combination of metaheuristics with machine learning methods), and 'agile' optimization algorithms ('lightweight' algorithms that fall between heuristics and metaheuristics). Several applications of these concepts to different fields will be also reviewed, mainly in the area of computational transportation, logistics, production, smart cities, telecommunication systems, and finance.
Optimization of Distribution Logistics
Daniele Vigo (University of Bologna) | 14.1.2020 17:00 | Skylounge (12th floor) OMP1
Distribution Logistics is one of the main components of modern supply chains and witnessed a large increase in complexity and scale during the last few years. The huge increase in demand associated with e-commerce, coupled with the availability of new technologies and means of transport as well as the sustainability issues introduced a variety of new challenges to planners, decision makers and scientists. The aim of this talk is to briefly survey the main optimization problems arising in the design and operations of modern distribution systems and discuss the current state-of-the-art of the research towards their solution.
On the Optimal Trade-Off Between Sample Size and Precision of Supervision in Regression (ISOR Kolloquium)
Giorgio Gnecco (IMT Lucca) | 13.1.2020 16:45-17:45 | HS7 OMP1
In this talk, a variation of the classical linear regression model is presented, in which one is additionally given the possibility of controlling the conditional variance of the output given the input, by varying the computational time dedicated to supervise each training example, while fixing an upper bound on the total available computational time. Using this model and a large-sample approximation, the generalization error is minimized as a function of the computational time per example. Two main cases are considered in the analysis: in one case, the precision of the supervision increases less than proportionally when increasing the computational time per example; in the other one, it increases more than proportionally. The results of the analysis highlight, from a theoretical point of view, that increasing the number of data is not always beneficial, if it is feasible to collect a smaller number of more reliable data. Some numerical results validating the theory are presented, together with several extensions of the proposed framework to other optimization problems modeling the trade-off between sample size and precision of supervision.
ÖGOR - Jahrestagung 2019 (ausgewählte Vorträge)
Zeit: 22.11. ab 13:00 Ort: Universität für Bodenkultur
Seminarraum 1 des Guttenberghauses
Feistmantelstraße 4
1180 Wien
13:10 Dolores Romero Morales (Copenhagen Business School): On Learning from Complex Data with Mathematical Optimization13:55 Nikolaus Furian (TU Graz): Selected Cases of Vehicle Routing - From a Real World Application to a Machine Learning Based Approach for VRPTW15:15 Verleihung der ÖGOR Preise 2019 für Masterarbeiten und Dissertationen (gesponsert von der scc EDV-Beratung AG): Kurzpräsentation der Preisträger16:00 Hubert Kögl / Tobias Kreiter (scc EDV-Beratung AG / Uni Graz): Optimization as Decision Support Tool for tackling Planning Challenges of our Customers
Designing Low Voltage Electricity Distribution Networks to facilitate Low Carbon Technologies
Paula Carroll (UC Dublin) | 25.11.2019 16:45 - 17:45 | HS7 OMP1
Applications of deep reinforcement learning to dynamic vehicle routing problems
Jorge E Mendoza Giminez (HEC Montréal) | 21.11.2019 13:30 | SR13 OMP1
Deep reinforcement learning (DRL) has seen much recent success in tasks that in-volve sequential decision making under uncertainty. These tasks span a variety of domains, including natural language processing, image recognition, medical diagno-sis, and autonomous driving. In this talk, we discuss two applications of DRL to dy-namic vehicle routing problems. In the first application, we study the case of a ridehail company operating a fleet of autonomous electric taxis that serve requests arising randomly throughout a region. The operator is responsible for assigning taxis to requests, as well as repositioning and recharging the taxis in anticipation of future requests. We model the problem as a Markov decision process. We compare solution methods from classical approximate dynamic programming -- heuristic policies -- with those delivered by two DRL-based agents. In the second application, we propose a new modeling framework for vehicle routing problems in which the problems are represented as Atari-like games. This representation allows for the solution of these problems using recent celebrated strategies from DRL community. We describe the framework and demonstrate its application on the Vehicle Routing Problem with Sto-chastic Service Requests. We discuss the framework’s benefits and limitations, and we speculate on other problem variants for which it may be useful.
An ALNS heuristic for a single compartment municipal solid waste collection with multiple types of waste
An ALNS heuristic for a single compartment municipal solid waste collection with multiple types of waste
Jorge Luis Oyola Mendoza (Institucional de la Universidad San Ignacio de Loyola) | 08.11.2019 14:00 | SR 1 OMP 1
The talk is focussed on an ongoing collaboration project of col- leagues from Czech Republic, Colombia and Austria. A problem on waste collection, including heterogeneous eet size, schedulling and routing decisions, as well as the Adaptive Large Neighborhood Search, which is the proposed solution method for the problem. A real world dataset, which is one of the testcases, is discussed. The current state of the implementation and few aspects that require some further analysis are presented.
Variance-Based Extragradient Methods with Line Search for Stochastic Variational Inequalities
Philip Thompson (Univ. Cambridge) | 04.11.2019 16:45 - 17:45 | HS 7 OMP 1
In this paper, we propose dynamic sampled stochastic approximated (DS-SA) extragradient methods for stochastic variational inequalities (SVIs) that are robust with respect to an unknown Lipschitz constant $L$. We propose, to the best of our knowledge, the first provably convergent robust SA method with variance reduction, either for SVIs or stochastic optimization, assuming just an unbiased stochastic oracle within a large sample regime. This widens the applicability and improves, up to constants, the desired efficient acceleration of previous variance reduction methods, all of which still assume knowledge of $L$ (and, hence, are not robust against its estimate). Precisely, compared to the iteration and oracle complexities of $\mathcal{O}(\epsilon^{-2})$ of previous robust methods with a small stepsize policy, our robust method uses a DS-SA line search scheme obtaining the faster iteration complexity of $\mathcal{O}(\epsilon^{-1})$ with oracle complexity of $(\ln L)\mathcal{O}(d\epsilon^{-2})$ (up to log factors on $\epsilon^{-1}$) for a $d$-dimensional space. This matches, up to constants, the sample complexity of the sample average approximation estimator which does not assume additional problem information (such as $L$). Differently from previous robust methods for ill-conditioned problems, we allow an unbounded feasible set and an oracle with multiplicative noise (MN) whose variance is not necessarily uniformly bounded. These properties are appreciated in our complexity estimates which depend only on $L$ and local variances or fourth moments at solutions. The robustness and variance reduction properties of our DS-SA line search scheme come at the expense of nonmartingale-like dependencies (NMDs) due to the needed inner statistical estimation of a lower bound for $L$. In order to handle an NMD and an MN, our proofs rely on a novel iterative localization argument based on empirical process theory.
ÖGOR-Arbeitsgruppe "Operations Research in Health Care & Disaster Management" und Austrian Health Economics Association (ATHEA)
Termin:
Freitag, 25. Oktober 2019, 13.00 - 17.15 Uhr
Ort:
Universität Wien Oskar-Morgenstern-Platz 1, Hörsaal 15, 2. Stock A-1090 Wien
Ablauf:
13.00-13.15 Uhr Registrierung
13.15-13.30 Uhr Eröffnung
Session I: 13.30-15.00 Uhr
Sophie Parragh (Universität Linz), Walter J. Gutjahr (Universität Wien), Najmesadat Nazemi (Universität Linz), Fabien Tricoire (Universität Linz):
On integrating data uncertainty and multi-objective optimization: application to problems in disaster relief logistics
Klaus-Dieter Rest, Jan Zazgornik, Patrick Hirsch (Universität für Bodenkultur, Wien):
Challenges of the practical implementation of solution algorithms for routing and scheduling home health care staff using public transport at a Viennese service Provider
Session II: 15.30-17.00 Uhr
Miriam Reiss et al. (IHS, Wien): Einkünfte von Ärztinnen und Ärzten in Österreich – Eine Analyse anhand von Lohn- und Einkommensdaten
Gerald Reiner et al. (WU Wien): Disaster relief and rescue operations supported by drones
17.00-17.15 Uhr Zusammenfassung und Ausblick
Um Anmeldung per E-Mail (marion.rauner@univie.ac.at) wird gebeten.
INFORMS TSL Workshop 2019
Date: July 15-18, 2019
Location: Sky Lounge at the Faculty of Business, Economics and Statistics
The next INFORMS TSL Workshop will be held from July 15-18, 2019 at the University of Vienna. The topic of the workshop is "Transportation in the sharing economy". Sharing economy refers to collaborative consumption. It is typically organized through platforms that facilitate the exchange of goods or services. Given an increasing pressure to act economically and ecologically efficient, mechanisms that help to benefit from idle capacities are on the rise. Both transportation companies and heavy users of transportation services need to learn how to play in a world of shared idle capacities. We anticipate talks on various types of collaborations, crowd delivery, carsharing, carpooling, ridesharing, etc.
On mixed integer nonlinear optimization to interpret and visualize complex datasets
Vanesa Guerrero Lozano (Univ. Carlos 3 Madrid) | 17.06.2019 16:45 - 17:45 | HS 7 OMP1 (#1.303)
Extracting knowledge from data, such as dependencies, global underlying patterns or unusual behaviors, has become a crucial task for analysts to improve decision making. Nevertheless, the increase in data complexity has made, in some cases, the classic statistical models obsolete, and more sophisticated frameworks are thus needed. In this context, Mathematical Optimization plays an important role, both developing new models and algorithmic approaches as well as creating new frameworks, which gain insight into specific datasets' features and cope with nowadays requirements. In this talk, we discuss how mixed integer nonlinear programming helps to interpret and visualize data involving time-varying frequencies and proximities.
Two Resource Allocation Problems in Global Health
27.05.2019 16:45 - 17:45 | HS 7 OMP1 (#1.303)
This talk will focus on a resource allocation of healthcare resources in low and middle income countries. The talk is stimulated by consultancy work for a major donor of development aid. We will discuss two problems - one of balancing "vertical" investments in disease programmes (such as purchasing bednets for malaria) with investments which strengthen the health system as a whole (e.g. improving systems for vital registration); the other of deciding the correct balance of funding between a donor and a recipient. We will model these problems with quadratic and bilevel programmes respectively and discuss the structural behaviour of such models.
A Kernel Search Heuristic for the Multi-Vehicle Inventory Routing Problem (joint work with G. Guastaroba, D. L. Huerta-Muñoz, M. Grazia Speranza)
20.05.2019 16:45 - 17:45 | HS 7 OMP1 (#1.303)
We study an inventory routing problem where the goal is to determine an opti-mal distribution plan to replenish a set of customers, by routing a limited fleet ofcapacitated vehicles over a discrete planning horizon. Each customer consumes aper period quantity of products and have a maximum inventory capacity. Productscan be distributed by a supplier to the customers in advance compared to theirconsumption, provided that their inventory capacity is not violated. The goal is tominimize the total distribution cost, that comprises the routing and the inventorycosts. We develop a novel matheuristic approach to solve this problem. The algo-rithm is based on Kernel Search (KS), a heuristic framework that has been shownto find high-quality solutions for a number of combinatorial optimization problems.The basic idea of KS is to identify subsets of the decision variables and then solving,using a general-purpose solver, a sequence of Mixed-Integer linear Programs (MIPs),each one restricted to a subset of variables. Extensive computational experimentsare conducted on a very large set of benchmark instances. The results show thatKS outperforms state-of-the-art heuristic algorithms. It finds 103 new best-knownsolutions out of 240 large-scale instances.
An Exact Solution Framework for Multi-Trip Vehicle Routing Problems with Time Windows
13.05.2019 16:45 - 17:45 | HS 7 OMP1 (#1.303)
Multi-Trip Vehicle Routing Problems (MTVRP) generalize the well-known VRP by allowing vehicles to perform multiple trips per day. MTVRPs have received a lot of attention lately because of their relevance in real-life applications, e.g., in city logistics and last-mile delivery. Several variants of the MTVRP have been investigated in the literature, and a number of exact methods have been proposed. Nevertheless, the computational results currently available suggest that MTVRPs with different side-constraints require ad-hoc formulations and solution methods to be solved. Moreover, solving instances with just 25 customers can be out of reach for such solution methods. In this talk, we proposed an exact solution framework to address four different MTVRPs proposed in the literature. The exact solution framework is based on a novel formulation that has an exponential number of variables and constraints. It relies on column generation, column enumeration, and cutting plane. We show that this solution framework can solve instances with up to 50 customers of four MTVRP variants and outperforms the state-of-the-art methods from the literature.
Stable Matching Models with Applications to Junior Doctor Allocation and Children Adoption
Sergio García Quiles (Univ. Edinburgh) | 06.05.2019 17:00 - 17:45 | HS 7 OMP1 (#1.303)
In a stable matching problem, we are given two sets of agents, each of whom ranks some (or all) the members of the other set in order of preference, indicating their level of desire to be matched to each other. A solution to the problem is a pairing of all agents such that no two agents form a blocking pair, that is, a pair that are not currently matched together, but would prefer to be matched to each other rather than to their currently assigned partners. In this talk I will introduce new models for the Stable Marriage problem with Ties and Incomplete lists, with applications to pairing children with adoptive families, and for its many-to-one generalization, the Hospitals/Residents Problem with Ties, with applications to the allocation of junior doctors.
Turnpike properties and strict dissipativity for linear optimal control problems
Roberto Guglielmi (Gran Sasso Science Institute ) | 29.04.2019 16:45 - 18:00 | HS 7 OMP1 (#1.303)
Abstract: In the talk we present some recent results on the connection between turnpike behaviors and strict dissipativity properties for finite dimensional linear quadratic (LQ) optimal control problems. The focus is on providing characterizations of strict dissipativity and the newly introduced property of strict predissipativity in terms of the system matrices related to the LQ problem. These characterizations then lead to new necessary conditions for the turnpike properties under consideration, and thus eventually to necessary and sufficient conditions in terms of spectral criteria and matrix inequalities. In particular, the techniques allow to encompass the presence of state and input constraints. Finally, several examples illustrate the different turnpike behaviors of the system in the presence or absence of constraints. The talk is based on joint works with Lars Grüne from University ofBayreuth [1,2].
[1] L. Grüne and R. Guglielmi. Turnpike properties and strict dissipativity for discrete time linear quadratic optimal control problems. SIAM Journal on Control and Optimization (SICON), 1–21, 2018.
[2] L. Grüne and R. Guglielmi. Turnpike and strict dissipativity properties for continuous time linear quadratic optimal control problems. preprint, 2019.
Discrete midpoint convexity: a unifying framework for convexity on the integer lattice (joint work with S. Moriguchi, K. Murota and A. Tamura)
Fabio Tardella (Univ. Rome "La Sapienza") | 01.04.2019 17:00 - 18:00 | HS 7 OMP1 (#1.303)
For a function defined on a convex set in a Euclidean space, midpoint convexity is the property requiring that the value of the function at the midpoint of any line segment is not greater than the average of its values at the endpoints of the segment. Under very mild assumptions, midpoint convexity is a well-known characterization of ordinary convexity. A discrete version of midpoint convexity is proposed here for functions defined on the integer lattice. A discrete midpoint point convex function is characterized by a discrete version of midpoint convexity where the value of the function at the (possibly noninteger) midpoint is replaced by the average of the function values at the integer round-up and round-down of the midpoint. We show that discrete midpoint convexity has nice theoretical and algorithmic properties, including (pseudo) polynomial-time minimization under appropriate assumptions. Furthermore, by restricting the distance between the endpoints in the discrete midpoint convexity definition, one obtains new classes of discretely convex functions and a unifying framework for several well-known notions of discrete convexity and for the notion of submodularity over the integer lattice.
Efficient Computation of the Prokhorov Metric for Finitely Supported Distributions (joint work with C. Drescher and J. Schwinn)
Ralf Werner (Univ. Augsburg) | 18.03.2019 17:00 - 18:00 | HS 7 OMP1 (#1.303)
On the space of probability measures on a metric Polish space, the Prokhorov metric is among the most popular distances between probability distributions. As it is the sole metric equivalent to the weak topology without further assumptions, it is usually mainly considered from a theoretical point of view. In this presentation, we want to highlight that although the definition of the Prokhorov metric seems rather stodgy, its computation is noticeably not more involved than the computation of the much more popular Wasserstein metric. For this purpose, we investigate the computation of the Prokhorov metric for finitely supported distributions. We especially compare our approach to the only other related work by Garel and Masse (2009). Specifically, we demonstrate that their fixed point approach fails for specific problems, while their max flow approach can be significantly improved. By distinguishing different settings, we are able to provide algorithms with proven correctness, together with worst case complexities. We conclude with a quasilinear algorithm for the most important case of real numbers with the usual metric. If time allows we will also briefly cover known and unknown inequalities concerning the Prokhorov metric, as well as its asymptotic behavior. Finally, we also shed some light on the connection of the Prokhorov metric to the Wasserstein infinity metric.
"The (Data) Science of Time: From Music to the Heart"
Date and Time: 17.01.2019 16:30 - 18:30
Location: BIG Lecture Hall, Universitätsring 1
The explosion of data in the music industry and technological developments in musical instruments that can record performance nuances have made possible modern investigations into intangible properties of music such as expressivity.
How do musicians shape performances? How are masterful interpretations crafted? What are the decisions that define a performance? What is the process of musicking: performing and listening? These have all become quantifiable and subject to scientific probing.
The consequent ability to capture and model the rhythmic variations of performance transfers to other music-like systems like the human heart. This enables descriptions of individual experiences of cardiac arrhythmias, personalised diagnoses, and disease or risk stratification.
Elaine Chew will present and discuss mathematical models of time, timing and temporal structure in music and heart data, with demonstrations at a piano.
We would like to thank our sponsors Bösendorfer and VCOR!
Further Informations: HERE!
Workshop on Optimization, Game Theory, and Data Analysis 2018 (OGDA 2018)
Date: December 20-21
The Workshop on Optimization, Game Theory, and Data Analysis 2018 (OGDA 2018) will be held at the University of Vienna from 20-21 December 2018 in order to celebrate the 60th birthday of Immanuel Bomze. The scientific program will consist of invited talks given by some of his collaborators, thus reflecting Manuel's broad scientific interests and activities and his numerous contributions to various areas of applied mathematics. A panel discussion will be organized as well. Participation is free of charge, but registration until December, 7 is required due to a limited number of admissions.
VIENNA WORKSHOP ON COMPUTATIONAL OPTIMIZATION
Date: December 17.-19.
Location: Sky Lounge at the Faculty of Business, Economics and Statistics
The Vienna Workshop of Computational Optimization 2018 (VWCO18) will be held at the University of Vienna from 17.-19. December 2018. The program will include eight plenary talks and a number of contributed presentations. Participation is free of charge, but registration is required due to a limited number of admissions.
Recommender Systems and their Effects [ISOR]
by Jakub Marecek (IBM Dublin)
Date: 12th November 2018 - Time: 16.45 - 17.45
Location: HS 7
Uni Vienna
(Oskar-Morgenstern-Platz 1, 1090 Vienna)
Abstract:
Recommender systems are widely used in settings, where actions impact the recommendations, which in turn have impact on the actions. For an example of such a closed-loop setting, consider navigation systems, which use information about travel times to recommend a route. If the particular navigation system is used widely enough, the recommendation may impact the future traffic state, possibly rendering the recommendation suboptimal from both the point of view of the driver and the society as a whole. Similar effects can be illustrated on the recommendations of restaurants. If a small bistro without a table reservation system becomes top ranked, many customers may arrive at its door and get turned down, leading to poor reviews. Further, there can be issues related to priming, for example when the reviews suggest the place is not touristy. Several problems arise, including the recovery of unbiased user models in the presence of recommenders and developing recommenders that allow for some guarantees on the closed-loop behaviour of the system.
Robust network optimization against uncertain demands [ISOR]
by Maria Grazia Scutellà (Univ. Pisa)
Date: 15th October 2018 - Time: 16.45 - 17.45
Location: HS 7
Uni Vienna
(Oskar-Morgenstern-Platz 1, 1090 Vienna)
Abstract:
The Gamma-Robustness paradigm, by Bertsimas and Sim, has been
extensively applied due to the good trade-off between offered level of
robustness and computational tractability. This is true, in particular,
in network application contexts where the service provided to the final
users is a critical issue, and therefore the uncertainty which usually
characterizes some user parameters should be carefully taken into account.
In this seminar, after an overview on the classical Gamma-Robustness
approach, some Gamma-Robustness extensions which have been recently
proposed in the literature in order to capture specific problem
characteristics, and/or peculiar uncertainty structures, will be presented.
Then, the use of Gamma-Robustness extensions will be illustrated in a
Health Care application context, where uncertainty in user requests may
be particularly critical: the Home Care problem under uncertain demands.
The Home Care application addresses several aspects involved in planning
home care services, such as the scheduling of patient requests over a
multiple-day time horizon, the caregiver-to-patient assignment, and the
caregiver routing. In this context, cancellation of requests and
additional demand for known or new patients are very frequent. Thus,
managing user demand uncertainty is of paramount importance in limiting
service disruptions that might occur when such events realize. The
uncertainty of patient demands is addressed via a non-standard
Gamma-Robustness approach, by jointly considering assignment, scheduling
and routing decisions. The results of a wide experimentation on robust
instances generated starting from a publicly available data set, and
comprising real world Home Care instances, are reported. Future avenues
of research are discussed.
On phenomenon of Immobility in study of convex Optimization problems (joint work with Olga Kostyukova (National Academy of Sciences, Belarus))
by Tatiana Tchemisova Cordeiro (Univ. Aveiro)
Date: 8th October 2018 - Time: 16.45 - 17.45
Location: HS 7
Uni Vienna
(Oskar-Morgenstern-Platz 1, 1090 Vienna)
Abstract:
In this paper, we are concerned with convex problems of infinite Optimization, namely problems of convex Semi-Infinite Programming (SIP), linear problems of Semidefinite Programming (SDP), and linear Copositive Programming (LCP) problems that are closely related. Semi-Infinite Programming deals with extremal problems that consist in minimization of an objective function of finitely many variables in a set described by an infinite system of constraints. SIP models appear in different fields of modern science and engineering where it is necessary to simulate a behavior of complex processes whose models contain at least one inequality constraint for each value of some parameter (for example, time) varying in a given compact domain. In SDP, an objective function is minimized under the condition that some matrix valued function is positive semidefinite. When the objective function is linear and the matrix valued function is an affine combination of some symmetric matrices, we get a convex problem. There are many applications of SDP models to combinatorial optimization, control theory, approximation theory, etc. Copositive Programming is a relatively new field of Conic Optimization, which is most actively developing in recent years. A general problem of LCP consists in optimizing over the cone of matrices which are positively semidefined on the non-negative orthant (so-called copositive matrices). Optimality conditions for Optimization problems are of special interest both from theoretical and practical points of view. A special attention is devoted to the results that do not need additional conditions on the constraints, so called constraint qualifications (CQ). In the talk, we present our recent results on optimality for convex Semi-Infinite Programming and apply them to problems of linear SDP and LCP. Our approach is based on the notions of immobile indices and their immobility orders for problems of LSIP and LCP and of a subspace of immobile indices for problems of linear SDP. We show how these concepts can be used to obtain new CQ-free optimality conditions for the considered classes of Optimization problems.
Externalities, optimization and regulation in queues [ISOR]
by Moshe Haviv (HU Jerusalem)
Date: 01th October 2018 - Time: 16.45 - 17.45
Location: HS 7
Uni Vienna
(Oskar-Morgenstern-Platz 1, 1090 Vienna)
Abstract:
The academic research on queues deals mostly with waiting. Yet, the
externalities, namely the added waiting time an arrival inflicts on
others, are of no less, if not of more, importance. The talk will deal
mostly with how the analysis of externalities leads to the socially
optimal behavior, while solving queueing dilemmas such as whether or not to
join a queue, when to arrive to a queue, or from which server to seek
service at. Customers, being selfish, do not mind the externalities they
impose on others. We show how in queues too, internalizing the
externalities leads to self regulation. In this setting selecting the
service regime is one of the tools in one's arsenal. (Joint work with
Binyamin Oz)
before winter term 2018
The Nutritious Supply Chain: Optimizing Humanitarian Food Aid (VCOR)
by Dick den Hertog(Univ. Tilburg)
Date: 18th June 2018 - Time: tba (approximately between 13:00 and 15:00)
Location: tba
Uni Vienna
(Oskar-Morgenstern-Platz 1, 1090 Vienna)
Abstract:
The UN World Food Programme (WFP) is the largest humanitarian agency fighting hunger worldwide, reaching around 80 million people with food assistance in 75 countries each year. To deal with the operational complexities inherent to its mandate, WFP has been developing tools to assist their decision makers with integrating the supply chain decisions across departments and functional areas. This presentation describes a mixed integer linear programming model that simultaneously optimizes the food basket to be delivered, the sourcing plan, the routing plan, and the transfer modality of a long-term recovery operation for each month in a pre-defined time horizon. By connecting traditional supply chain elements to nutritional objectives, we made significant breakthroughs in the operational excellence of WFP’s most complex operations, such as Iraq and Yemen. We show how we used optimization to reduce the operational costs in Iraq by 17%, while still supplying 98% of the nutritional targets. Additionally, we show how we are using optimization in Yemen to manage the scale-up of the existing operation from three to six million beneficiaries.
Co-authors: Koen Peters, Hein Fleuren, Mirjana Kavelj, Sérgio Silva, Rui Gonçalves, Ozlem Ergun, Mallory Soldner
Robust Nonlinear Optimization with Convex Uncertainty
by Dick den Hertog(Univ. Tilburg)
Date: 18th June 2018 - Time: 16:45-17:45
Location: HS 7 (lecture room)
Uni Vienna
(Oskar-Morgenstern-Platz 1, 1090 Vienna)
Abstract:
Robust Optimization is a popular approach to treat uncertainty in optimization problems. Finding a computationally tractable formulation of the robust counterpart of an optimization problem is key in being able to apply this approach. In the first part of the presentation we will give an introduction to Robust Optimization. Although techniques for finding a robust counterpart are available for many types of constraints, no general techniques exist for functions that are convex in the uncertain parameter. Such constraints are, however, common in, e.g., quadratic optimization and geometric programming problems. In the second part of this presentation, we provide a systematic way to construct a safe approximation to the robust counterpart of a nonlinear uncertain inequality that is convex in the uncertain parameters for a polyhedral uncertainty set. We use duality theory as well as adjustable robust optimization techniques to obtain this approximation. We also propose a general purpose method to strengthen the obtained approximation by using nonlinear decision rules for the introduced auxiliary adjustable variables. We show the quality of the approximations by performing several numerical experiments.
First order algorithms for constrained optimization problems in Machine Learning (ISOR)
by Francesco Rinaldi (Univ. Padova)
Date: 14th Mai2018 - Time: 16:45-17:45
Location: HS 7 (lecture room)
Uni Vienna
(Oskar-Morgenstern-Platz 1, 1090 Vienna)
Abstract:
Thanks to the advent of the "Big Data era", simple iterative first-order optimization approaches for constrained convex optimization have re-gained popularity in the last few years. In the talk, we first review a few classic methods (i.e., conditional and projected gradient method) in the context of Big Data applications. Then, we discuss both theoretical and computational aspects of some new active-set variants for those classic methods. Finally, we examine current challenges and future research perspectives.
Sensitivity Analysis for Convex Separable Optimization over Integral Polymatroids (ISOR)
by Tobias Harks(Univ. Augsburg)
Date: 7th Mai2018 - Time: 16:45-17:45
Location: HS 7 (lecture room)
Uni Vienna
(Oskar-Morgenstern-Platz 1, 1090 Vienna)
Abstract:
The talk will discuss the sensitivity of optimal solutions of convex separable optimization problems over an integral polymatroid base polytope with respect to parameters determining both the cost of each element and the polytope. Under convexity and a regularity assumption on the functional dependency of the cost function with respect to the parameters, it is shown show that reoptimization after a change in parameters can be done by elementary local operations. I will show that these sensitivity results can be applied to a new class of non-cooperative games played on integral polymatroid base polytopes in order to compute pure Nash equilibria.
Rates of convergence for the Krasnoselskii-Mann fixed point iteration (ISOR)
by Roberto Cominetti (Univ. A. Ibanez, Santiago de Chile)
Date: 23th April 2018 - Time: 16:45-17:45
Location: HS 7 (lecture room)
Uni Vienna
(Oskar-Morgenstern-Platz 1, 1090 Vienna)
Abstract:
We analyze the convergence of an inexact version of the classical Krasnoselskii-Mann iteration for computing fixed points of nonexpansive maps in Banach spaces. Our main result establishes a new metric bound for the fixed-point residuals, from which we derive their rate of convergence as well as the convergence of the iterates towards a fixed point. To this end we consider a nested family of optimal transport problems that provide a recursive bound for the distance between the iterates. These recursive bounds are in turn interpreted as expected rewards for an underlying Markov chain, which leads to explicit rates of convergence. In the case of the exact iteration we show that these bounds are tight by building a nonexpansive map that attains them with equality, and we deduce that the optimal constant of asymptotic regularity is exactly $1/\sqrt{\pi}$. The results are extended to continuous time to study the asymptotics of non-autonomous evolution equations governed by nonexpansive operators.
Instance Spaces for Objective Assessment of Algorithms and Benchmark Test Suites
by Kate Smith-Miles (University of Melbourne)
Date: 20th April 2018 - Time: 15:00
Location: 188/2 (seminar room)
TU Vienna
(Favoritenstrasse 9-11, Stiege 3, 4.OG, grüner Bereich)
Abstract:
Objective assessment of algorithm performance is notoriously difficult, with conclusions often inadvertently biased towards the chosen test instances. Rather than reporting average performance of algorithms across a set of chosen instances, we discuss a new methodology to enable the strengths and weaknesses of different algorithms to be compared across a broader generalised instance space. Initially developed for combinatorial optimisation, the methodology has recently been extended for machine learning classification, and to ask whether the UCI repository and OpenML are sufficient as benchmark test suites. Results will be presented to demonstrate: (i) how pockets of the instance space can be found where algorithm performance varies significantly from the average performance of an algorithm; (ii) how the properties of the instances can be used to predict algorithm performance on previously unseen instances with high accuracy; (iii) how the relative strengths and weaknesses of each algorithm can be visualized and measured objectively; and (iv) how new test instances can be generated to fill the instance space and offer greater insights into algorithmic power.
Branch & Price based algorithms for some variants of the Two-Echelon Vehicle Routing Problem with Time Windows
by Prof. Tom Van Woensel (Technische Universiteit Eindhoven)
Date: 22th March 2018 - Time: 10:00
Location: SR 3 (seminar room)
Uni Wien
(Oskar-Morgenstern-Platz 1, 1090 Wien)
Abstract:
This presentation discusses the two-echelon capacitated vehicle routing problem with time windows. The first echelon consists of transferring freight from depots to inter-mediate facilities (i.e., satellites), while the second echelon consists of transferring freight from these facilities to the final customers, within their time windows. We proBtion, paths are defined over both first and second echelon tours, and (2) in the other one, the first and second echelon paths are decomposed. Branch-and-price based algorithms are developed for both formulations. We compare both formula-tions and solution methods on a comprehensive set of instances and are able to solve instances upto 5 satellites and 100 customers to optimality. One extension to-wards multi-commodity products is also discussed in detail.
On the invariance of the maximum (ISOR)
by Prof. Joergen Weibull (HHS Sweden)
Date: 19th March 2018 - Time: 16:45-17:45
Location: Skylounge (12th floor)
Uni Vienna
(Oskar-Morgenstern-Platz 1, 1090 Vienna)
Abstract:
Many models in economics, transportation research and engineering involve probabilistic selection of one alternative or unit from a finite set; the selected alternative being the consumption bundle with the highest utility to a consumer, the production method with the lowest cost for a producer, the firm with the highest productivity in a competitive market, etc. The consumer chooses the alternative with the highest utility, the producer the production method with the lowest cost, the market the firm with the highest productivity, etc. The analyst is interested in the selection probabilities and in the probability distribution for the value of the selected alternative. We say that the random vector associated with the alternatives at hand has the invariance property if the distribution of the value of any given alternative, conditional on that alternative being selected, is the same for all alternatives. We show that this invariance property holds if and only if the marginal distributions of the components of the random vector, representing the alternatives, are positive powers of each other. We illustrate the analytical power of the invariance property by way of examples. We also show how it generalizes the pioneering work of McFadden (1974) on multinomial logit models, in which the random components are assumed to be additive and the random terms Gumbel distributed. We show that the same qualitative results, with closed-form selection probabilities, hold for a wide class of random selection processes without such structural and parametric assumptions.
Games, Dynamics and Optimization GDO2018 conference
Date: 13.- 15.3.2018
Location: Oskar-Morgenstern-Platz 1, 1090 Wien
The aim of this conference is to bring together excellent researchers interested in dynamical system approaches to Optimization and Games.
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.