
Fifth Joint Operations Research Days
August 2728, 2007 
Swiss Federal Institute of Technology Zurich (ETH Zurich) 
Room HG G19.1 
Click here for directions to ETHZ. The main building is
marked RED in the map. Both rooms HG G19.1 and G60 (for the celebration
session) are on the "G" (second) floor of the main building. G19.1 is at
the northeast corner and G60 is at the central hall.
Organizing committee:
 Michel Bierlaire, EPFL
 Komei Fukuda, ETHZ and EPFL
 Jon Lee, IBM Research
 Thomas Liebling, EPFL
 HansJakob Lüthi, ETHZ
 Eleni Pratsini, IBM Research
Click
here to register.
Schedule
The following schedule is tentative and may be modified. Make sure
you consult it again just before the conference
For contributed talks, click on the author's name to access the
abstract
Monday August
27 
10:0010:30 
Coffee 
10:3012:10 
Contributed talks 
Room: HG G19.1 

Chair: Eleni Pratsini 

10:30 
Jon
Lee 
IBM T.J. Watson Research Center 
10:55 
Karl
Frauendorfer 
Institute for Operations Research and Computational Finance,
University of St. Gallen 
11:20 
Max
Fehr 
Institute for Operations Research (ETH Zuerich) 
11:45 
Ilaria
Vacca 
Transport and Mobility Laboratory, EPFL 
12:1013:30 
Lunch 

13:3017:15 
Celebration
for the 40th Anniversary of IFOR 
Room:HG G60 

Chair:HansJakob Lüthi 

13:30 
H.J. Lüthi 
IFOR 
13:40 
Brenda
Dietrich 
INFORMS President, and Director of Mathematical Sciences at IBM
T.J. Watson Research, USA 
14:10 
Martine
Labbé 
EURO President, and Université libre de Bruxelles, Belgium 
15:00 
Tatsuo
Oyama 
Vice President of the Operation Research Society of Japan, and
National Graduate Institute for Policy Studies 
15:30 
Daniel Costa 
President of Swiss Operation Research Society, and Nestlé
Lausanne/Parma 
16:15 
Shaping the future of OR in Switzerland 
17:30 
Cocktail 
Dozentenfoyer, floor J 
18:30 
Dinner 
Dozentenfoyer, floor J 
Tuesday August
28 
9:3010:20 
Contributed talks 
Room:HG G19.1 

Chair:Michel Bierlaire 

9:30 
Ola
Svensson 
IDSIA 
9:55 
Gautier
Stauffer 
IBM ZRL 
10:2010:50 
Coffee 

10:5012:05 
Contributed talks 
Room:HG G19.1 

Chair:Jon Lee 

10:50 
Niklaus
Eggenberg 
Transport and Mobility Laboratory, EPFL 
11:15 
Stephan
Bütikofer 
Universität Zürich, IOR 
11:40 
Vania
Dos Santos Eleuterio 
ETH Zurich 
12:0513:10 
Lunch 

13:1014:25 
Contributed talks 
Room:HG G19.1 

Chair:Komei Fukuda 

13:10 
Thomas
Robin 
Transport and Mobility Laboratory, EPFL 
13:35 
Abderrahim
Labbi 
IBM Zürich Research Center 
14:00 
Bernard
Ries 
ROSE, EPFL 
14:2514:55 
Coffee 

14:5515:45 
Contributed talks 
Room:HG G19.1 

Chair:Thomas Liebling 

14:55 
Rico
Zenklusen 
ETH Zurich 
15:20 
Sivan
Altinakar 
ROSE, EPFL 
We have prebooked some rooms in the following hotel. When you reserve,
mention code "IBM" to benefit from the conference rate.
 Hotel Sunnehus***
 Sonneggstr. 17
8006 Zürich Tel: +41 44 250 27 27 email: info@hotelsunnehus.ch http://www.hotelsunnehus.ch/
Very close to the ETH main building (HG). ETH rate 154.50 incl.
breakfast. 10 single rooms reserved for the conference. Please mention
code "IBM" to reserve until July 27.
 Hotel St. Josef***
 Tel. +41 44 250 57 57
email: info@stjosef.ch http://www.stjosef.ch/hotel/index_e.html
Close to the ETH main building (HG). ETH rate CHF 140. incl.
breakfast (+ city tax). 9 rooms reserved for the conference. Please
mention code "IBM" to reserve until August 10.
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.
Abstract submission is closed
Number of abstracts: 14
 Altinakar Sivan (ROSE, EPFL):
A reduction of cyclic interval edge coloring to interval edge
coloring
 joint work with: Wieslaw Kubiak The $k$interval edge
coloring problem consists of finding a coloring of the edges with colors
from 1 to $k$, such that for each node the colors of the edges adjacent
to it are all different and form an integer interval. This problem can
be extended to the $k$cyclic interval edge coloring problem, where
colors $k$ and 1 are considered consecutive. Such problems have
applications in nonpreemptive (cyclic) open shop scheduling. This work
aims at studying the relationship between these two problems, and
presents a reduction of the $k$cyclic interval edge coloring problem
with $k2\leq\delta\leq\Delta\leq k$ to the $k$interval edge coloring
problem, where $\delta$ and $\Delta$ are respectively the minimum and
maximum degree in the graph, and $k$ is the number of colors used. The
reduction is obtained by adding specific subgraphs to the graph of the
original cyclic problem, and it guarantees that if the original graph is
bipartite, then the resulting graph is bipartite as well.
 Bütikofer Stephan
(Universität Zürich, IOR): Globalizing a nonsmooth Newton method via
path search
 We give a framework for the globalization of a nonsmooth Newton
method for solving Lipschitz equations introduced by B. Kummer. We start
with recalling Kummers approach to convergence analysis of this method
and state his results for local convergence [1]. In a second part we
give a globalized version of this method. In our approach we use first a
monotone path search idea to control the descent. After elaborating the
single steps, we analyze and discuss the proof of global convergence
resp. of local superlinear or quadratic convergence of the algorithm. We
sketch also a nonmonotone version of the algorithm. In the last part we
discuss and illustrate the details of the general algorithm (e.g the
computation of a path) for some interesting examples and present results
from numerical tests. Reference: [1] D. Klatte and B. Kummer, “Nonsmooth
Equations in Optimization”, Kluwer, (DordrechtBostonLondon 2002).
 Dos Santos Eleuterio
Vania (ETH Zurich): Traffic Equilibrium Problem: a
comparison of the flow distribution in Beckmann and Nesterov & de
Palma models.
 We consider qualitative and quantitative differences between the
traffic equilibrium models of Beckmann (1956) and Nesterov & de
Palma (1998). We use large scale benchmark instances as well as real
data. For solving the traffic equilibrium model of Beckmann we use a
commercial package. For Nesterov & de Palma model, we design
algorithms based on smooth and non smooth methods from Nesterov
(2003/5). Since derived problems are multicommodity flow problems, the
algorithms’ numerical performance might be of independent interest. We
perform also sensitivity analysis of the solutions of both models. Joint
work with Fabian A. Chudak and Yurii Nesterov
 Eggenberg Niklaus (TRANSPOR,
EPFL): Column generation methods for disrupted airline
schedules
 We consider the recovery of an airline schedule after an unforeseen
event, commonly called disruption, that makes the planned schedule
unfeasible. In particular we consider the aircraft recovery problem for
a heterogeneous fleet of aircrafts, made of regular and reserve planes,
where the maintenance constraints are explicitly taken into account and
different maintenance constraints can be imposed. The aim is to find the
optimal combination of routes within a given makespan for each plane in
order to recover to the initial schedule, given the initial schedule and
the disrupted state of the planes. We propose a column generation scheme
based on a multicommodity network flow model, where each commodity
represents a plane, a dynamic programming algorithm to build the
underlying networks and a dynamic programming algorithm to solve the
pricing problem. This project arises from a collaboration between EPFL
and APM Technologies, which is a small company selling IT solutions to
airlines. We provide some computational results on real world instances
obtained from a medium size airline, Thomas Cook Airlines, one of APM
main customers.
 Fehr Max (Institute for Operations
Research (ETH Zuerich)): Joint allowance and electricity price
formation in the European Emission Trading Scheme
 Cap and Trade Systems have not least since the ratification of the
Kyoto Protocol in 2004 become popular environmental instruments. However
recent price development of carbon allowances in the EU Emission Trading
Scheme and it’s impact on European electricity prices exhibits the
importance of a clear understanding of such Trading Systems. To this end
we propose a stochastic multi period equilibrium model for joint
allowance and electricity price formation in the European Emission
Trading Scheme. Thereby particular focus is given on the influence of
market design on windfall profits, allowance prices and overall social
costs. Moreover it is shown that small changes to Cap and Trade Schemes
can prohibit windfall profits.
 Frauendorfer Karl
(Institute for Operations Research and Computational Finance, University
of St. Gallen): Valuation and Bidding of Hydro Power Plants in the
EEX
 We start with considering american call and put options with a
limited number of exercise rights. We apply stochastic multistage
programming and investigate the impact of the filtration to the accuracy
with respect to volatility, strike and delivery period. The value of
early exercisement of the american put will be assessed. We extend the
application to the electrical power industry and apply the valuation
concept to generalized Pilipovic price dynamics. We report on the
valuation of swing options, the associated profit &loss
distributions and risk measurement. Further, we focus on an approach
that evaluates bidding strategies for the optimal dispatching of hydro
plants. The sensitivity of the results subject to different mean
reversion and volatility coefficients is revealed. The numerical results
have been achieved with a software package that has been developed in
cooperation with large European power producers and traders.
 Labbi Abderrahim (IBM Zurich):
Transform Regression: A New Predictive Modeling Algorithm Inspired
by the Kolmogorov Superposition Theorem
 This talk will present a new automated statistical modeling
algorithm that draws inspiration from the Kolmogorov superposition
theorem. The algorithm addresses the need to develop statistical models
of the relationships between decision variables and outcomes for
problems in which the mathematical forms of the relationships are
unknown. Examples of such problems often involve predictions of human
behavior, such as marketing mix modeling to optimize advertising spend
across media and geographies, and customer propensity modeling to
optimize return on targeted marketing investment across a customer base.
This talk will present an automated statistical modeling technique that
has been developed that is wellsuited to these cases that is capable of
automatically modeling nonlinearities and crossproduct interactions.
 Lee Jon (IBM T.J. Watson Research
Center): Nonlinear Matroid Optimization and Experimental Design
 We study the problem of optimizing nonlinear objective functions
over matroids presented by oracles or explicitly. Such functions can be
interpreted as the balancing of multicriteria optimization. We provide
a combinatorial polynomial time algorithm for arbitrary oraclepresented
matroids, that makes repeated use of matroid intersection, and an
algebraic algorithm for vectorial matroids. Our work is partly motivated
by applications to minimumaberration modelfitting in experimental
design in statistics, which we discuss and demonstrate in detail. Joint
work with: Yael Berstein, Hugo MaruriAguilar, Shmuel Onn, Eva
Riccomagno, Robert Weismantel and Henry Wynn.
 Ries Bernard (ROSE, EPFL):
Mixed Graph Coloring
 We consider a coloring problem in mixed graphs (i.e. graphs
containing edges and arcs): we want to associate a color (integer) to
each vertex such that any two vertices linked by an edge have different
colors and the tail of an arc has a color strictly less than the head of
this arc. We present bounds on the mixed chromatic number and we give
some complexity results which strengthen former results.
 Robin Thomas (EPFL): Modeling
Human Perception of Facial Expressions by Discrete Choice Models
 Facial expression recognition is a hard and ambiguous problem in
computer vision. It is hard due to the wide variety of faces and the
wide variety of ways of representing the same expression. And it is
ambiguous because, even though common approaches treat it as a
classification problem, actually when looking at the same scene,
different people can feel a different expression. In this presentation,
we will show preliminary results obtained in an ongoing project of
Discrete Choice Modeling of human perception of facial expressions. This
new approach allows to exploit the mentioned heterogeneity of
perceptions in a population of "experts" interpreting a facial
expression, where an expert is somebody able to discern between
different facial expressions, i.e. any human.
 Stauffer Gautier (IBM ZRL):
A new algorithm for the weighted stable set problem in clawfree
graphs
 The weighted stable set problem in clawfree graphs is as
generalization of the matching problem and can be solved in polynomial
time. The current algortithms (Sbihi 80, Minty 80, Nakamura Tamura 01,
Schrijver 03) are based on the augmenting path property inherited from
matching. Lovasz and Plummer 86 proposed another type of algorithm based
on graph reductions but unfortunately, this approach can only deal with
the unweighted case. In this talk, we give a new algorithm based on
graph reductions that allows to reduce the problem to a weighted
matching problem, thus generalizing the approach by Lovasz and Plummer.
 Svensson Ola (IDSIA):
(In)approximability Results for PrecedenceConstrained Scheduling,
Sparsest Cut and Optimal Linear Arrangement
 We consider (uniform) sparsest cut, optimal linear arrangement and
the precedence constrained scheduling problem $1precsum w_j C_j$.
Understanding the approximability of these notorious problems is
considered a major open problem in complexity/scheduling theory. By
combining techniques from vertex cover and dimension theory of partial
orders we obtain the best known approximation ratios for all considered
classes of precedence constraints for the scheduling problem. We also
briefly discuss the first inapproximability results for the addressed
problems obtained by using the recent QuasiRandom PCP construction by
Khot. References: Ambühl, C., Mastrolilli, M., Mutsanas, N., and
Svensson, O., Approximating Scheduling with Precedence Constraints of
Low Fractional Dimension. In proceedings of IPCO, volume LNCS 4168,
pages 2839, Springer, 2007. Ambühl, C., Mastrolilli, M., and Svensson,
O., Inapproximability Results for Sparsest Cut, Optimal Linear
Arrangement, and Precedence Constraint Scheduling. To appear in
proceedings of FOCS, 2007.
 Vacca Ilaria (EPFL, TranspOR):
Optimization of Container Terminal Operations
 Over the last years, international seafreight container
transportation has grown dramatically and container terminals play
nowadays a keyrole in the global shipping network. The increased
competitiveness among terminals requires more and more efficiency in
container operations, both along the quayside and within the yard, in
order to minimize ship’s turnaround time. Operations research methods
and techniques are therefore worth being used in optimizing terminal
operations. In this work, we first give an overview of decision problems
which arise in the management of a container terminal (e.g. berth
allocation, crane scheduling, storage policies and strategies, transfer
operations) and we briefly describe models and methods presented in the
literature. Then, starting from a collaboration with some of the busiest
ports in Europe, we have identified some critical issues which will be
illustrated: in particular, we focus on the impact that gate operations
and transshipment operations have on the yard and we propose a new
approach to the yard management which takes into account these
interactions. We conclude with suggestions of possible research tracks
and open issues.
 Zenklusen Rico (ETH Zurich):
Estimation of small st reliabilities in acyclic networks
 In the classical st network reliability problem a fixed network G
is given including two designated vertices s and t (called terminals).
The edges are subject to independent random failure, and the task is to
compute the probability that s and t are connected in the resulting
network, which is known to be #Pcomplete. In this talk, I will discuss
the issue of approximating the st reliability in case of a directed
acyclic original network G. A specialized version of a MonteCarlo
algorithm given by Karp and Luby will be introduced and analyzed. For
the case of uniform edge failure probabilities, I will present a
worstcase bound on the number of samples that have to be drawn to
obtain an epsilondelta approximation, being sharper than the original
upper bound. Computational results on two types of random networks
(directed acyclic Delaunay graphs and a slightly modified version of a
classical random graph) with up to one million vertices are presented.
These results show the advantage of the introduced MonteCarlo approach
compared to direct simulation when small reliabilities have to be
estimated and demonstrate its applicability on largescale instances.
Furthermore, applications to spreading processes on networks will be
highlighted.
There is no registration fee. Registration will be confirmed on a first
comefirst served basis.
All participants, including speakers, must register using the following
registration form.
Registration deadline: August 20,
2007.
Today is December 01, 2007.
Sorry, the deadline is over.
Current number of registered participants: 67
 adult dating adult dating, http://datingadultclubs.com
 adult dating adult dating, http://datingadultclubs.com
 adult dating adult dating, http://adultdating.ads6x.com
 adult dating adult dating, http://adultdatingcls.com
 adult friends adult friends, http://adultfriendsin.com
 adult personals adult personals, http://adultpersonalsclubs.com
 Altinakar Sivan, EPFL, ROSE
 Antonini Gianluca, IBM Zurich Research
 Berrospi Cesar, IBM Zurich Research Laboratory
 bicurious wifes bicurious wifes, http://curiouswifes.com
 Bierlaire Michel, TRANSPOR, EPFL
 Boedi Richard, IBM Research
 Bütikofer Stephan, Universität Zürich, IOR
 ca swingers ca swingers, http://california.swingersmate.com
 Caimi Gabrio, ETH Zurich
 california swingers california swingers, http://california.ads6x.com
 Columbano Sebastiano, ETH Zurich
 Costa Daniel, President of Swiss Operation Research Society, and
Nestlé Lausanne/Parma
 couples swingers couples swingers, http://couplescplssex.com
 Cruz Mota Javier, TRANSPOR, EPFL
 Dietrich Brenda, IBM Research
 Dos Santos Eleuterio Vania, ETH Zurich
 Eggenberg Niklaus, TRANSPOR, EPFL
 Elisseeff Andre, IBM Research
 Foniok Jan, Charles University Prague / ETH Zürich
 Frauendorfer Karl, Univerrsity of St. Gallen
 Frejinger Emma, TRANSPOR, EPFL
 Fuchsberger Martin, ETH Zurich
 Fukuda Komei, ETH Zurich
 Gambardella Luca, IDSIA
 Guarisco Michael, ETH Zurich
 Heusler Lucas, IBM Zurich Research Laboratory
 Janner Gabriele, ETH Zürich
 Jones Colin, ETH Zurich
 Kall Peter, University of Zurich
 Klatte Diethard, University of Zurich
 Labbé Martine, EURO President, and Université libre de Bruxelles,
Belgium
 Latif Shahzad, Technische Universität HamburgHarburg
 Laumanns Marco, IFOR, ETH Zurich
 Lee Jon, IBM Watson Research Center, Yorktown NY
 Liebling Thomas, ROSO  EPFL
 Lüthi HansJakob, ETH Zurich
 Mastrolilli Monaldo, IDSIA
 Osorio Carolina, TRANSPOR, EPFL
 Oyama Tatsuo, Vice President of the Operation Research Society of
Japan, and National Graduate Institute for Policy Studies
 Pednault Edwin, IBM Watson Research Center, Yorktown NY
 Pratsini Eleni, IBM Zurich Research Lab
 Prodon Alain, EPFL
 Reiner Gerald, University of Neuchâtel
 Ries Bernard, ROSE, EPFL
 Robin Thomas, TRANSPOR, EPFL
 Rosta Vera, Renyi Institute of Mathematics
 Schimpel Ulrich, IBM Research, Zurich
 single women single women, http://www.uinlove.com
 Stauffer Gautier, IBM ZRL
 Sutter Reto, ETHZ
 Svensson Ola, IDSIA
 swingers swingers,
http://www.friendster.com/websearch.php?search=1&filter=network&q=looking+for+%22pleasantly+submissive%22+swingers+couple
 swingers clubs swingers clubs, http://swingersadultclubs.com
 swingers clubs swingers clubs, http://swingersadultclubs.com
 Tiemessen Harold, IBM Zurich Research Lab
 Vacca Ilaria, TRANSPOR, EPFL
 Vial JeanPhilippe, ORDECSYS and the University of Geneva
 von Bergen Silvia, University of Zurich
 Wagner Maik, FriedrichSchiller University of Jena, Germany
 Widmer Marino, Université de Fribourg  DIUF
 Zenklusen Rico, IFOR
