SVOR/ASRO 
General Assembly 
September 10 at 13.30 

Partners

Content
History


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
 HansJakob 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 comefirst 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 tourplanning 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. 
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.
16 abstracts  Philipp Baumann (University of Bern)
Title: Portfolioselection 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 smallinvestors specific constraints are met. We develop extensions to four portfolio selection models from the literature such that a piecewise constant transactioncost 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 EventBus 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 mixedbinary 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 wellchosen convex function. Due to this reformulation, we are able to improve the worstcase 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 PrimalDual 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 PrimalDual 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 NoWait Job Shop Abstract: While the optimal Job Insertion problem is NPcomplete in the classical Job Shop, it was shown by Klinkert & Gröflin (2007) that it is solvable in polynomial time in the NoWait 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 twolevel 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 ValueatRisk (Robust CVaR) as the robust risk measure corresponding to Conditional ValueatRisk (CVaR), and prove that it can be computed via its dual. We show how to compute optimalRobust CVaR portfolios in a portfolio management problem. We compare the optimalRobust CVaR and the optimalCVaR 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 decisionmaking "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) agentbased 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, multiagent 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 NPhard even if the number of constraints is fixed. However, if, in addition, the objective is the allone 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 gridconnected 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 batterypowered 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. 449454.
 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 globallyintegrated capability model. To address this trend, we need to build new tools for workforce management, inventory management, capacity management, work transitioning/routing,
multilingual/multicultural 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 crossorganizational 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 MaxPartitioning Problems Abstract: Any partitioning problem can be generalized to a maxvariant 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 NPhard for arbitrary weights. However, we explain how to derive polynomial time approximation schemes for these problems, that is, how to compute nearoptimal solutions in polynomial time.  Philipp Renner (Institute for Operations Research University of Zurich)
Title: Finding All PureStrategy 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 stateoftheart 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 purestrategy 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 allsolution methods can be applied to a wide variety of policyrelevant 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
3partition problem, where n items of size > 1/4 have to
be packed in a minimum number of bins of capacity one. The famous
KarmarkarKarp 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 threepermutationsconjecture 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 3partition 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 LPbased Approximation for Steiner Tree Abstract: The Steiner tree problem is one of the most fundamental NPhard 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,ZelikovskySODA’00]. All these algorithms are purely combinatorial. A longstanding open problem is whether there is an LPrelaxation for Steiner tree with integrality gap smaller than 2 [Vazirani,RajagopalanSODA’99].
In this talk, we consider an LPrelaxation 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: MultiObjective 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 regating 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 realtime 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 01 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
 AnnaLaura 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 righthand side we study a certain Lipschitz property, socalled calmness. We are interested in necessary and sufficient conditions for calmness of multivalued 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.
All participants, including speakers, must register using the following registration forms.
Registration deadline: August 25, 2010. Today is October 04, 2024. Sorry, the deadline is over.
Current number of registered participants: 37
Baumann  Philipp  Department of Business Administration, University of Bern  Bierlaire  Michel  Transport and Mobility Laboratory, EPFL  Bock  Adrian  EPFL  Boyacı  Burak  Urban Transport Systems Laboratory, EPFL  Brandinu  Gianluca  Department of Business Administration, University of Bern  Bürgisser  Michael  Institute for Operations Research, ETH Zurich  Bürgy  Reinhard  University of Fribourg  DIUF  Costa  Daniel  Nestlé Suisse  Eisenbrand  Friedrich  EPFL  Fink  Miloslawa  DIUF Université de Fribourg  Gallay  Olivier  Transport and Mobility Laboratory, EPFL  Glerum  Aurélie  Transport and Mobility Laboratory, EPFL  Gröflin  Heinz  University of Fribourg  DIUF  Hähnle  Nicolai  EPFL  Hürlimann  Tony  DIUF Université de Fribourg  Klaus  Lorenz  Institute for Operations Research, ETH Zurich  Kriett  Phillip  IDSIA, Lugano  Krishnapuram  Raghuram  IBM Research,India  Lade  Nicholas  EPFL  Laumanns  Marco  IBM Research  Zurich  Lüthi  HansJakob  Institute for Operations Research, ETH Zurich  Mastrolilli  Monaldo  IDSIA  Mojsilovic  Aleksandra  IBM Research  Nonner  Tim  IBM Research  Zurich  Pratsini  Eleni  IBM Research  Zurich  Rabta  Boualem  Entreprise Institute, University of Neuchâtel  Renner  Philipp  Institut für Operations Research (IOR) , University of Zürich  Rothvoß  Thomas  EPFL  Sanità  Laura  EPFL  Schäfer  Tobias  University of Bern  Trautmann  Norbert  University of Bern  Uldry  Marc  University of Fribourg  DIUF  VISWANATHAN  PREM KUMAR  ECOLE POLYTECHNIQUE FEDERALE DE LAUSANNE  Weismantel  Robert  Institute for Operations Research, ETH Zurich  Weyland  Dennis  IDSIA, Lugano  Wickström  AnnaLaura  Institut für Operations Research (IOR) , University of Zürich  Widmer  Marino  University of Fribourg  DIUF 
We have prebooked 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.nhhotels.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
