Eighth Joint Operations Research Days

For all information, contact Tony Hürlimann

Organizing committee:

• Michel Bierlaire, EPFL and SVOR/ASRO
• Daniel Costa, Nestlé and SVOR/ASRO
• Heinz Gröflin, U. Fribourg
• Tony Hürlimann, U. Fribourg
• Jon Lee, IBM Research
• Hans-Jakob Lüthi, ETHZ and SVOR/ASRO
• Eleni Pratsini, IBM Research

We invite members of IBM research staff and Swiss OR researchers to submit abstracts about their recent research. We strongly encourage PhD students to present their results.

There is no registration fee. Registration will be confirmed on a first come-first served basis.

Keynotes speakers

Prof. Robert Weismantel, ETHZ
	A Cutting Plane Theory for Mixed Integer Optimization Abstract: From a practical perspective, mixed integer optimization represents a very powerful modeling paradigm. Its modeling power, however, comes with a price. The presence of both integer and continuous variables results in a significant increase in complexity over the pure integer case with respect to geometric, algebraic,combinatorial and algorithmic properties. Specifically, the theory of cutting planes for mixed integer linear optimization is not yet at a similar level of development as in the pure integer case. The goal of this talk is to discuss four research directions that are expected to contribute to the development of this field of optimization. In particular, we examine a new geometric approach based on lattice point free polyhedra and use it for developing a cutting plane theory for mixed integer sets. We expect that these novel developments will shed some light on the additional complexity that goes along with mixing discrete and continuous variables.
Dr. Ruedi Hug, Cantaluppi and Hug, SA
	Transportation Logistics: Modelling and Optimization in Practice Abstract: In transportation optimization we are mostly confronted with heuristic algorithms. From a mathematical point of view this is not very exciting. However, in practice this kind of problems have to be solved every single day. In this presentation we will show and discuss three different solution strategies for the following transport optimization problems: In the first case we try to minimize the transportation cost for a cementmanufacturer with several production centers. In the second case, a big food distributer wants to reduce the number of distribution centers and warehouses. Therfore he needs to know the expected expansion of his transportation costs. The third case is a daily tour-planning problem for the delivery of clients from a central distribution center . At first glance it looks simple, but in the practice we have to handle different integration problems like the loading capacity, the drivers flexibility, etc.. Finally we explain how we see the role of Operations Research concerning the kind of problems presented.

Schedule

Thank you for submitting. The announced 16 talks and two keynote presentations have been scheduled Click here for the schedule. Please note that each speaker of a contributed talk has 20 minutes.

Abstracts

16 abstracts

Philipp Baumann (University of Bern)

Title: Portfolio-selection models for small investors

Abstract: We study the problem of investing a given amount of capital in stocks such that the risk is minimized, a certain rate of return is guaranteed and some small-investors specific constraints are met. We develop extensions to four portfolio selection models from the literature such that a piecewise constant transaction-cost function, minimum transaction units, and dividends are considered. In an experimental analysis, we apply each model from the perspective of a Swissquote client who wants to construct the portfolio from 239 Swiss stocks. We show that the models based on Young (1998) and Rockafellar and Uryasev (2000) outperform the others substantially in terms of computational effort. All models generate portfolios which on average yield higher returns than the Swiss Performance Index. However, the return of the Swiss Performance Index has a considerably lower variance.

Gianluca Brandinu (University of Bern)

Title: Scheduling of Event-Bus Tours

Abstract: The „Enchanted Journey“ is a daily event tour booked by Indian tourists. During 10 activities, the tour participants visit original locations of famous Bollywood films in Berne and the Bernese Oberland. The transportation between these locations is done by up to 5 busses. The tour of each bus starts and ends in Engelberg. For operating reasons, each location can be visited by at most one bus at a time. Further operative constraints include time windows for activities and precedence constraints between activities. The planning problem consists in computing a feasible schedule for each bus such that the weighted sum of the total distance travelled and the total waiting time is minimized. We present a formulation of this problem as a mixed-binary linear program which we have implemented in AMPL, and we report on computational results obtained from the Gurobi solver.

Michael Bürgisser (Institute for Operations Research, ETH Zurich)

Title: Reconstruction and extensions of the Hedge algorithm in the context of subgradient methods

Abstract: The Hedge algorithm, introduced by Freund and Schapire in 1996, is a method widely used in Machine Learning. We show that this method can be interpreted as a Mirror Descent scheme, that is, a particular subgradient method, for minimizing a well-chosen convex function. Due to this reformulation, we are able to improve the worst-case convergence result for the Hedge algorithm slightly. Recently, considering these methods from a new viewpoint, Nesterov has extended Mirror Descent schemes and has defined some Primal-Dual Subgradient methods for convex problems. Using the machinery provided by Nesterov, we derive new update rules for the Hedge algorithm. In our numerical experiments, these new update rules perform consistently better than the standard Hedge algorithm. As Arora and Kale showed in 2007, the underlying idea of the Hedge algorithm can be used to solve semidefinite optimization problems. We discuss some challenges of extending Primal-Dual Subgradient methods to semidefinite optimization problems and show some first results.

Reinhard Bürgy (University of Fribourg)

Title: An Efficient Algorithm for Optimal Job Insertion in the No-Wait Job Shop

Abstract: While the optimal Job Insertion problem is NP-complete in the classical Job Shop, it was shown by Klinkert & Gröflin (2007) that it is solvable in polynomial time in the No-Wait Job Shop (NWJS). We present here a highly efficient algorithm for this problem that finds an optimal insertion in O(n^2 * max{n,m*log d(J)}). The algorithm is based on a compact formulation of the NWJS and a characterization of all feasible insertions as stable sets (of prescribed cardinality) in a comparability graph. Numerical results are presented and some applications are discussed. This is joint work with Heinz Gröflin.

Apostolos Fertis (ETH Zurich)

Title: Robust Risk Management

Abstract: The expression of the coherent risk measures via the representation theorem shows that the optimization with a coherent risk measure criterion is a robust optimization problem. The objective function of such a problem is the expectation of the random discounted return rate for the financial position in consideration. However, the probability distribution describing the evolution of the economy has a two-level structure in many cases. The first level constitutes of the probability distribution over a set of scenarios, while the second level comprises of the probability distributions under the considered scenarios. The probability distributions under the scenarios are accurate, but the probability distribution over the scenarios is not known exactly. We propose a new class of risk measures, called robust risk measures, which take into consideration this uncertainty by applying a robust optimization approach in the first level and a traditional risk measure approach in the second level. We show that a robust risk measure is coherent or convex when the corresponding traditional risk measure is coherent or convex, respectively. We express the robust risk measures using the representation theorems for coherent and convex risk measures. We define Robust Conditional Value-at-Risk (Robust CVaR) as the robust risk measure corresponding to Conditional Value-at-Risk (CVaR), and prove that it can be computed via its dual. We show how to compute optimal-Robust CVaR portfolios in a portfolio management problem. We compare the optimal-Robust CVaR and the optimal-CVaR portfolios in a model constructed using real New York Stock Exchange (NYSE) and NASDAQ data from 2005 to 2010.

Olivier Gallay (Transport and Mobility Laboratory, EPFL)

Title: Centralized Versus Decentralized Control - A Solvable Stylized Model in Transportation Logistics

Abstract: To analyze the potential outcomes resulting from interaction between autonomous decision-making "smart parts" in logistics networks, we propose here an exactly solvable stylized model that is able to quantify how much the dynamics can be enhanced by (fully decentralized) agent-based mechanisms. Cost functions are introduced in order to compare the performances of centralized versus decentralized organization and we are able to conclude that for time horizons shorter than a critical value, multi-agent interactions generate smaller costs that an optimal effective central controller.

Nicolai Hähnle (EPFL DISOPT)

Title: Testing additive integrality gaps

Abstract: We consider the problem of testing whether the maximum additive integrality gap of a family of integer programs in standard form is bounded by a given constant. This can be viewed as a generalization of the integer rounding property, which can be tested in polynomial time if the number of constraints is fixed. It turns out that this generalization is NP-hard even if the number of constraints is fixed. However, if, in addition, the objective is the all-one vector, then one can test in polynomial time whether the additive gap is bounded by a constant. This is joint work with Friedrich Eisenbrand, Dömötör Pálvölgyi and Gennady Shmonin.

Phillip Kriett (IDSIA, Lugano)

Title: The unit commitment and economic dispatch problem in a residential microgrid

Abstract:

This study addresses the unit commitment and economic dispatch problem in a residential microgrid. The microgrid includes electrical and thermal loads, electrical and thermal storage devices, and electrical and thermal generation units which are typical for domestic applications. This study considers fluctuation in loads, in renewable energy resources, as well as in energy prices. These fluctuations are modeled by time series which are based on collected data. The microgrid operates in grid-connected mode and trading electricity with the main grid is possible. The electrical energy balance and the thermal energy balance are interdependent due to combined heat and power generation. Beside the stationary electrical and thermal energy storages, we model a battery-powered automobile as intermittent storage and load. Loads caused by certain domestic appliances are modeled as schedulable load jobs. The model results in a mixed integer nonlinear optimization problem which has been linearized and solved within a rolling horizon framework. Results for different pricing policies are compared.

• S.P.Chowdhury, P.Crossley, S.Chowdhury, 2009. Microgrids and active distribution networks, The Institution of Energy and Technology, London, UK.
• L.M. Costa, G.A. Kariniotakis, 2007. Stochastic Dynamic Programming Model for Optimal Use of Local Energy Resources in a Market Environment. IEEE Power Tech. 449-454.
• D. Livengood, R. Larson, 2009, The Energy Box: Locally Automated Optimal Control of Residential Electricity Usage. Service Science 1 (1).

Authors: Phillip Kriett – phillip@kriett.de, and Matteo Salani - matteo.salani@idsia.ch IDSIA, Lugano, Switzerland

Keywords: Microgrid, Unit Commitment, Economic Dispatch, Demand Side Management

Raghu Krishnapuram (IBM Research - India)

Title: Associate Director, Solutions

Abstract: Organizations are moving from a global delivery model to a globally-integrated capability model. To address this trend, we need to build new tools for workforce management, inventory management, capacity management, work transitioning/routing, multi-lingual/multi-cultural collaboration, knowledge management, and business contingency planning, and business adaptability and resiliency. In the new era, Organizations will need to use advanced analytics and optimization techniques for designing, building and managing products and service. New teniques need to be developed to allow and promote timely flow and use of appropriate information in the right form that will ensure robust, effective and timely decision making to meet operational and business outcome goals under normal as as well as disruptive conditions. This talk will outline some of the technical challenges involved in this scenario and outline some possible approaches.

Aleksandra Mojsilovic (IBM Research)

Title: Workforce Management Analytics

Abstract: In the early 2000s, as services became a larger and larger part of IBM’s revenue, it was recognized that the company must better manage its workforce, and more effectively and efficiently deploy its skilled resources to meet customers’ needs. IBM has made a significant investment in a cross-organizational workforce transformation effort, which adapted the knowledge from supply chain optimization, as well as developed novel algorithms to enable better workforce planning, management and deployment. This presentation will review several novel workforce management analytics/solutions from IBM Research Division, which were piloted or deployed within IBM services organization.

Tim Nonner (IBM Research - Zurich)

Title: Geometric Max-Partitioning Problems

Abstract: Any partitioning problem can be generalized to a max-variant by assigning weights to the elements that need to be partitioned. The cost of each set in a partition is then the maximal weight of any element contained in this set. Using this, the original problem can simply be described as the unweighted case. Naturally, adding weights makes any problem harder, and hence there is no hope to find good approximation algorithms in general. Therefore, we are interested in partitioning problems which are almost trivial in the unweighted case. Specifically, we consider the problems of partitioning interval graphs into cliques or independent sets, where a partition in independent sets is also known as a graph coloring. Both problems can easily be solved in polynomial time in the unweighted case, but become NP-hard for arbitrary weights. However, we explain how to derive polynomial time approximation schemes for these problems, that is, how to compute near-optimal solutions in polynomial time.

Philipp Renner (Institute for Operations Research University of Zurich)

Title: Finding All Pure-Strategy Equilibria in Static and Dynamic Games with Continuous Strategies

Abstract: Static and dynamic games are important tools for the analysis of strategic interactions among economic agents and have found many applications in economics. In many games equilibria can be described as solutions of polynomial equations. In this paper we describe state-of-the-art techniques for finding all solutions of polynomial systems of equations and illustrate these techniques by computing all equilibria of both static and dynamic games with continuous strategies. We compute the equilibrium manifold for a Bertrand pricing game in which the number of pure-strategy equilibria changes with the market size. Moreover, we apply these techniques to two stochastic dynamic games of industry competition and check for equilibrium uniqueness. Our examples show that the all-solution methods can be applied to a wide variety of policy-relevant models. Authors: Kenneth Judd, Philipp Renner and Karl Schmedders

Thomas Rothvoss (EPFL)

Title: Bin Packing via Discrepancy of Permutations

Abstract:

A well studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxation for this problem into an integral solution that requires at most O(log n) additional bins.

The three-permutations-conjecture of Beck is the following. Given any 3 permutations on n symbols, one can color the symbols red and blue, such that in any interval of any of those permutations, the number of red and blue symbols differs only by a constant. Beck's conjecture is well known in the field of discrepancy theory.

We establish a surprising connection between bin packing and Beck's conjecture: If the latter holds true, then the additive integrality gap of the 3-partition linear programming relaxation is bounded by a constant. This result indicates that improving approximability results for bin packing requires a better understanding of discrepancy theory.

This is joint work with Friedrich Eisenbrand and Doemoetoer Palvoelgyi.

Laura Sanità (EPFL)

Title: An Improved LP-based Approximation for Steiner Tree

Abstract: The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum weight tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from 2 to the current best 1.55 [Robins,Zelikovsky-SODA’00]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP-relaxation for Steiner tree with integrality gap smaller than 2 [Vazirani,Rajagopalan-SODA’99]. In this talk, we consider an LP-relaxation for the problem which is based on the notion of directed components, and we describe an approximation algorithm based on iterative randomized rounding of a fractional solution. We prove an approximation guarantee of 1.39 (improving over the previously best known factor of 1.55). As a byproduct of our analysis, we show that the integrality gap of our LP is at most 1.55, hence answering to the mentioned open question. Joint work with: Jaroslaw Byrka, Fabrizio Grandoni and Thomas Rothvoss.

PREM KUMAR VISWANATHAN (Transport and Mobility Laboratory, EPFL)

Title: Multi-Objective Airport Gate Assignment: Schedule Planning and Day of Operations

Abstract: In this paper, we consider the gate assignment for a large airline at its hub airport. The problem is considered in both modes – planning as well as operations. The first objective in planning mode assigns airport gates dynamically to scheduled flights based on daily origin and destination passenger flow data ensuring that maximum connection revenue is realized. The second objective aims to schedule flights to gates in as few manpower zones as possible. This would help reduce the operating costs for the airline. The third objective ensures that gate rest, i.e. the gate idle time between an outgoing and the next incoming flight, is kept to the maximum possible so that extent of re-gating is minimized in the eventuality of successive flight delays. One of the major contributions of this paper is gate assignment in the operations mode to account for real-time delays and disruptions to the planned schedule. This would entail making deviations to the existing assignment plan and retiming flights marginally in extreme situations when the existing gate infrastructure cannot handle all the flights. It is important that our solution technique is fast enough to produce this operational solution within a few seconds. We formulate these problems as mixed 0-1 integer program with a linear objective function and constraints. Due to the complexity in the problem size and formulation, we have resorted to relaxation for certain instances when a reasonable solution is not obtained within the time limit. Problem formulation for flight retiming in the operations mode has been borrowed from the concepts of resource constrained project scheduling. Implementation is done using OPL and computational results for actual data sets are presented. Keywords: Airport Gate Assignment; Scheduling; Mathematical Modelling

Anna-Laura Wickström (Institut für Operations Research (IOR) , University of Zürich)

Title: Characterizations for Calmness of Constraint Systems

Abstract: For the solution set mapping of a system of finitely many inequalities with perturbations on the right-hand side we study a certain Lipschitz property, so-called calmness. We are interested in necessary and sufficient conditions for calmness of multi-valued mappings (multifunctions) and we are particularly interested in constraint systems of standard nonlinear programs and of semidefinite programs. In this talk, recent results by Klatte and Kummer are recalled and then extended to the case of adding a fixed algebraic constraint to the perturbed system of inequalities.

Registration

All participants, including speakers, must register using the following registration forms.

Registration deadline: August 25, 2010.

Today is November 21, 2024.

Sorry, the deadline is over.

Current number of registered participants: 37

Accomodation

We have pre-booked some rooms in the following hotel. When you reserve, mention code "ORdays" to benefit from the conference rate.

NH Fribourg****
Grand Places 14
1700 Fribourg
phone: +41 26 351 91 91
www.nh-hotels.com
price Frs 170.--

Further information can be obtained at:
Fribourg Tourisme, Av.de la Gare 1
++41 26 350 11 11
www.fribourgtourisme.ch