Fifth Joint Operations Research Days

Click here for the pictures of the event

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 north-east 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
• Hans-Jakob 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

Accomodation

We have pre-booked 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
e-mail: 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
e-mail: info@st-josef.ch
http://www.st-josef.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.

Abstract submission

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 non-preemptive (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 $k-2\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, (Dordrecht-Boston-London 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 (TRANSP-OR, 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 well-suited to these cases that is capable of automatically modeling nonlinearities and cross-product 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 multi-criteria optimization. We provide a combinatorial polynomial time algorithm for arbitrary oracle-presented matroids, that makes repeated use of matroid intersection, and an algebraic algorithm for vectorial matroids. Our work is partly motivated by applications to minimum-aberration model-fitting in experimental design in statistics, which we discuss and demonstrate in detail. Joint work with: Yael Berstein, Hugo Maruri-Aguilar, 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 claw-free graphs

The weighted stable set problem in claw-free 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 Precedence-Constrained Scheduling, Sparsest Cut and Optimal Linear Arrangement

We consider (uniform) sparsest cut, optimal linear arrangement and the precedence constrained scheduling problem $1|prec|sum 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 Quasi-Random 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 28-39, 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, Transp-OR): Optimization of Container Terminal Operations

Over the last years, international sea-freight container transportation has grown dramatically and container terminals play nowadays a key-role 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 s-t reliabilities in acyclic networks

In the classical s-t 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 #P-complete. In this talk, I will discuss the issue of approximating the s-t reliability in case of a directed acyclic original network G. A specialized version of a Monte-Carlo algorithm given by Karp and Luby will be introduced and analyzed. For the case of uniform edge failure probabilities, I will present a worst-case bound on the number of samples that have to be drawn to obtain an epsilon-delta 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 Monte-Carlo approach compared to direct simulation when small reliabilities have to be estimated and demonstrate its applicability on large-scale instances. Furthermore, applications to spreading processes on networks will be highlighted.

Registration

There is no registration fee. Registration will be confirmed on a first come-first 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.

Last Name:		Required field
First Name:		Required field
Email:		Required field
Affiliation:		Required field
Position:	(please select)Pre-doctoralPhD studentPost-docOther (professor, etc.)	Required field
Special request:
	To avoid spam, we have to ask you to copy the characters on the left. Click here for a new code

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
• bi-curious wifes bi-curious wifes, http://curiouswifes.com
• Bierlaire Michel, TRANSP-OR, EPFL
• Boedi Richard, IBM Research
• Bütikofer Stephan, Universität Zürich, IOR
• ca swingers ca swingers, http://california.swingers-mate.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, TRANSP-OR, EPFL
• Dietrich Brenda, IBM Research
• Dos Santos Eleuterio Vania, ETH Zurich
• Eggenberg Niklaus, TRANSP-OR, EPFL
• Elisseeff Andre, IBM Research
• Foniok Jan, Charles University Prague / ETH Zürich
• Frauendorfer Karl, Univerrsity of St. Gallen
• Frejinger Emma, TRANSP-OR, 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 Hamburg-Harburg
• Laumanns Marco, IFOR, ETH Zurich
• Lee Jon, IBM Watson Research Center, Yorktown NY
• Liebling Thomas, ROSO - EPFL
• Lüthi Hans-Jakob, ETH Zurich
• Mastrolilli Monaldo, IDSIA
• Osorio Carolina, TRANSP-OR, 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, TRANSP-OR, 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, TRANSP-OR, EPFL
• Vial Jean-Philippe, ORDECSYS and the University of Geneva
• von Bergen Silvia, University of Zurich
• Wagner Maik, Friedrich-Schiller University of Jena, Germany
• Widmer Marino, Université de Fribourg - DIUF
• Zenklusen Rico, IFOR