Sixth Joint Operations Research Days

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

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. Friedrich Eisenbrand, Ecole Polytechnique Fédérale de Lausanne
	Integer Programming and the Geometry of Numbers Integer programming is related to convex geometry as well as to algorithmic number theory, in particular to the algorithmic geometry of numbers. In this talk, I survey some classical and recent results in the interplay of integer programming and the geometry of numbers.
Prof. János Pach, Ecole Polytechnique Fédérale de Lausanne
	Conflict-free coloring Motivated by a frequency assignment problem in cellular telephone networks, Even et al. studied the following question. Given a set P of n points in general position in the plane, what is the smallest number of colors in a coloring of the elements of P with the property that any closed disk D with D∩ P≠∅ has an element whose color is not assigned to any other element of D∩ P. We refer to such a coloring as a conflict-free coloring of P with respect to disks. In the original application, the points correspond to base stations interconnected by a fixed backbone network. Each client continuously scans frequencies in search of a base station within its (circular) range with good reception. Once such a base station is found, the client establishes a radio link with it, using a frequency not shared by any other station within its range. Therefore, a conflict-free coloring of the points corresponds to an assignment of frequencies to the base stations, which enables every client to connect to a base station without interfering with the others. We survey some basic results related to conflict-free colorings, and outline some generalizations to graph and hypergraph colorings based on joint work with Gábor Tardos.
Prof. Karl H. Schmedders, University of Zürich
	Solving Dynamic Games Dynamic stochastic games with a discrete state space have become the dominating tool in the analysis of industries with heterogeneous firms. The applicability of these economic models to explain observed industry dynamics, however, has been greatly limited by the computational burden to calculate equilibria for these models. The reasons for this burden are two-fold. First, realistic industry descriptions give rise to models with large numbers of states and variables. Secondly, economists have traditionally applied numerical methods rooted in the motivation of Nash equilibria to solve these models, but these methods are not always well suited to compute equilibria. In this talk we examine a standard dynamic game model and show that the equilibrium conditions give rise to large nonlinear systems of equations or large complementarity problems. We argue that solvers implementing standard numerical methods, such as the software PATH, can easily solve large dynamic games.

Schedule

This schedule is tentative and may be modified later on.

Each talk (except the keynote presentations) has a slot of 20 minutes, including questions.

Abstracts

18 abstracts

Frédéric Babonneau (Ordecsys)

Title: A partitioning algorithm for the network loading problem

Abstract: We present a partitioning algorithm for the network loading problem (NLP). The NLP consists of installing least cost integer capacities on the arcs that are sufficient to handle a network flow that meets the demands. Our solution method is a Benders partitioning scheme. The master program is a pure integer programming problem in the space of capacities. The subproblem is a continuous optimization problem ; it tests whether the integer capacities generated by the master program is sufficient to support flows that meet the demands. It also computes supporting hyperplanes to the set of feasible fractional capacities. The subproblem makes it possible to construct a polyhedral relaxation of the set of feasible capacities while the master program looks for interesting integer solutions within that polyhedral relaxation. Since the effort of computing integer solutions is entirely left to a pure integer programming solver (CPLEX in our case), the main advantage of our solution method is its simplicity. It also appear to be efficient on some problems.

Boi Faltings (EPFL)

Title: Distributed Algorithms for Constraint Optimization

Abstract: We consider problems where multiple agents have to coordinate their decisions because of shared resources or other interdependencies, and this coordination problem can be formulated as a problem of constraint optimization. We survey distributed algorithms that allow such problems to be solved without a central authority.

Jan Foniok (ETH Zürich)

Title: Polynomial Pivoting for K-LCP: A Proof Using Unique-Sink Orientations

Abstract: Joint work with K. Fukuda, B. Gärtner, H.-J. Lüthi. Unique-sink orientations of cubes provide a simple combinatorial description of simple principal pivoting methods for the linear complementarity problem (LCP). It had been known that there exists a pivot rule for the simple principal pivoting method that takes only a linear number of pivots to solve the K-matrix LCP. Using unique-sink orientations, we were able to show that this is actually true for any pivot rule.

Radoslav Fulek (EPFL)

Title: Intersecting convex sets by rays

Abstract: What is the smallest number  t=t(n) such that for any collection of n pairwise disjoint convex sets in d-dimensional Euclidean space, there is a point such that any ray (half-line) emanating from it meets at most  sets of the collection? This question of Urrutia is closely related to the notion of regression depth introduced by Rousseeuw and Hubert (1996). We show the following: Given any collection C of n pairwise disjoint compact convex sets in d-dimensional Euclidean space, there exists a point p such that any ray emanating from p meets at most (dn+1)/(d+1) members of C. There exist collections of n pairwise disjoint (i) equal length segments or (ii) disks in the Euclidean plane such that from any point there is a ray that meets at least 2n/3-2 of them. We also determine the asymptotic behavior of t(n) when the convex bodies are fat and of roughly equal size.

Alexander Horch (ABB Corporate Research)

Title: The Challenge of Increasing Complexity in Production Optimization

Abstract: Today’s industries are more than ever enforced to lower their operational costs, largely due to a harder global competition. One related target is to ensure that the overall result of earlier isolated optimization tasks is “globally optimal”, i.e. the decisions done on different levels or in different process sections do not negate, or counteract, each other. This has created a trend and more importantly a need of increased information sharing between various decision-support systems. Inevitably, information sharing leads to more complex optimization systems as the models need to cover larger problem entities in order to merge previously separate optimization targets. Also, aspects earlier not considered may have to be included. Another complexity increase arises from the communication need between the tasks. The earlier isolated problems (e.g. machine-specific production planning) become networked, which means that not all goals can be derived from local facts alone, but at least some must be handled globally. Apart from the cultural change and integration challenges, it is very important to ensure that optimization methodologies can cope with the new demands. As no single strategy suffices to cover all industrial problem solutions – even within one plant – a system of optimization systems needs to be designed by combination of methods, partitioning of problems and modeling collaboration. Some strategies of combining solution methods will be shown, followed by project examples carried out at ABB Corporate Research. Finally, future challenges and opportunities are discussed.

Diethard Klatte (IOR, UZH)

Title: Generalized semi-infinite programs: reduction approach and a nonsmooth Newton method

Abstract: (in collaboration with Stephan Bütikofer IOR, UZH) We study nonlinear programs in finite dimensions with infinitely many inequality constraints, where the set of constraint indices depends on the state variables. Supposing strong regularity assumptions, the problem may be reduced to a standard nonlinear program with finitely many constraints, but now including some kind of nonsmoothness. We present this reduction procedure as well as convergence results and first numerical experiments for a nonsmooth Newton method for solving this type of models.

Monaldo Mastrolilli (IDSIA)

Title: (Acyclic) Job Shops are Hard to Approximate

Abstract: Understanding the approximability of the job shop problem is considered one of the most prominent open problems in scheduling theory. Even though the best approximation algorithms have worse than logarithmic performance guarantee, the only known inapproximability result says that it is NP-hard to approximate acyclic job shops within a factor less than~$5/4$. For every $epsilon >0$, we show that the (acyclic) job shop problem cannot be approximated within ratio $O(log^{1-epsilon} lb)$, unless $NP$ has quasi-polynomial Las-Vegas algorithms, and where $lb$ denotes a trivial lower bound on the optimal value. This almost matches the best known results for acyclic job shops, since an $ {O}(log^{1+epsilon} lb)$-approximate solution can be obtained in polynomial time for every $epsilon>0$. Recently, a PTAS was given for the job shop problem, where the number of machines emph{and} the number of operations per job are assumed to be constant. Under $P ot = NP$, and when the number $mu$ of operations per job is a constant, we provide an inapproximability result whose value grows with $mu$ to infinity. Moreover, we show that the problem with two machines has no PTAS, unless $NP$ has quasi-polynomial algorithms. These results show that the restrictions on the number of machines and operations per job are necessary to obtain a PTAS. Finally, we solve (negatively) an open question raised by Bansal et al., by showing that even the preemptive variant with three machines has no PTAS.

Roberto Montemanni (IDSIA)

Title: Heuristic construction of Constant GC-content DNA codes

Abstract: DNA codes are sets of words of fixed length n over the alphabet {A, C, G, T} which satisfy a number of combinatorial conditions. They have application in DNA computing, in DNA microarray technologies and as molecular bar codes. The combinatorial conditions considered are (i) minimum Hamming distance d, (ii) fixed GC content and, in some cases (iii) minimum distance d between any codeword and the reverse Watson-Crick complement of any codeword. The problem is to find DNA codes with the maximum number of codewords. The construction of DNA codes is studied from an algorithmic perspective. Four local search algorithms are developed and combined in a variable neighbourhood search framework. The algorithm has been run extensively. Over 254 problems considered, it was able to match or improve the best known lower bounds in 180 cases, with 52 new bests. (join work with D.H. Smith, University of Glamorgan, UK)

Domotor Palvolgyi (EPFL)

Title: Decomposability of polygon coverings

Abstract: A family of sets is a {em $k$-fold} covering of a point set if every point is contained in at least $k$ of the sets. A covering is {em decomposable} if the sets can be partitioned into two ($1$-fold) coverings. We say that a geometric set is {em cover-decomposable}, if there exists a $k$ such that every $k$-fold covering of {em any point set} in the plane by its translates is decomposable.\ We show which polygons are cover-decomposable. It turns out that every convex polygon is cover-decomposable and almost every concave polygon is not cover-decomposable.

Thomas Rothvoss (EPFL)

Title: A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation

Abstract: We present a polynomial time approximation scheme for the real-time scheduling problem with fixed priorities when resource augmentation is allowed. For a fixed epsilon > 0, our algorithm computes an assignment using at most (1+epsilon)*OPT +1 processors in polynomial time, which is feasible if the processors have speed 1+epsilon. This is joint work with Fritz Eisenbrand.

Gennady Shmonin (EPFL)

Title: Integer programming gaps

Abstract: We consider the problem of finding the maximum difference between the optimum value of ab integer program and its linear programming relaxation, as the right-hand side vector in the constraint matrix varies over a given polyhedron. It turns out that there is a polynomial algorithm for this problem if the number of variables is fixed.

Shakhar Smorodinsky (EPFL)

Title: Conflict-Free coloring made stronger

Abstract: In FOCS 2002, Even et al. showed that any set of $n$ discs in the plane can be Conflict-Free colored with a total of at most $O(\log n)$ colors. Namely, it can be colored with $O(\log n)$ colors such that for any (covered) point $p$ there is some disc whose color is distinct from all other colors of discs containing $p$. They also showed that this bound is asymptotically tight. We prove the following stronger result: Any set of $n$ discs in the plane can be colored with a total of at most $O(k \log n)$ colors such that for any point $p$ that is covered by at least $k$ discs, there are at least $k$ distinct discs each of which is colored by a color distinct from all other discs containing $p$ and for any point $p$ covered by at most $k$ discs, all discs covering $p$ are colored distinctively. We call such a coloring a {\em $k$-Strong Conflict-Free} coloring. We extend this result to pseudo-discs and arbitrary regions with linear union-complexity. Joint work with Elad Horev and Roi Krakovski

Gautier Stauffer (IBM )

Title: Decentralized decision making is close to optimal for one-warehouse multi-retailers systems

Abstract: Roundy developped in 1985 a centralized algorithm to manage efficiently (within 2% of optimality) the inventory of a simple distribution system consisting of one warehouse and many retailers, where the retailers are facing continuous demands with constant rates. In order to ensure near optimality of the global system, the retailers usually have to increase their own optimal inventory costs. In practice tough, for ease of implementation or for accounting purpose, decisions are often taken in a decentralized way and all the retailers and the central warehouse try to minimize their own inventory costs independently of the others. In this talk we show that in the continuous rate setting, this practical approach is ususally good (within 6% of optimal in average) and is provably close to optimal (within 1.2748 of optimal in the worst case).

Dharmashankar Subramanian (IBM Watson)

Title: A Novel Algorithm for stochastic Linear Programs with a Conditional-Value-at-Risk Objective and Conditional-value-at-risk Constraints

Abstract: Conditional-Value-at-Risk (CVaR), as a mathematical programming-friendly risk measure, was first introduced by Uryasev & Rockafellar (2000). Using a discrete sample-approximation of the underlying stochastic coefficients, they provided a linear reformulation for stochastic linear programs with CVaR objective/constraints, which can then be solved using general-purpose linear programming solvers. An important point to note in this reformulation is that the resulting number of additional decision variables & the number of additional constraints, scale linearly with the size of samples. More recently, Kunzi-Bay and Mayer (2006) presented a two-stage, stochastic programming interpretation of the above linear reformulation for the specific case of a CVaR Objective, and developed a computationally efficient algorithm, CVarMin, to address linear CVaR optimization in the objective function, observing an order of magnitude speed-up. We present a novel, computationally efficient algorithm for stochastic linear programs with both Conditional-Value-at-Risk (CVaR) Objective and Conditional-value-at-risk Constraints, retaining the above discrete sample-approximation of the stochastic coefficients. We start with a reformulation that is different from the above references, and iteratively construct and solve a sequence of compact-sized linear optimization problems. We also show that the resulting sequence converges to the true optimal solution of the sample-predicated linear program. The problem size in each iteration of the sequence is unaffected by the size of random samples, which makes it very efficient for large-scale problems. A comparison with the general-purpose linear reformulation of Uryasev & Rockafellar suggests at least an order of magnitude speed-up of computational time, and more improvement with increasing number of CVaR constraints and size of samples. Applications include practical problems, such as, portfolio optimization.

Maxim Sviridenko (IBM T.J. Watson Research Center)

Title: Approximation Algorithms for the One-Warehouse Multi-Retailer problem

Abstract: Deterministic inventory theory provides streamlined optimization models that attempt to capture tradeoffs in managing the flow of goods through a supply chain. We will consider two well-studied deterministic inventory models, called the {em one-warehouse multi-retailer problem} (OWMR) and its special case the {em joint replenishment problem} (JRP), and give approximation algorithms with improved performance guarantees; more specifically, we give a 1.8-approximation algorithm for both problems. Our results are based on an LP-rounding approach and improve previous results of Levi, Roundy and Shmoys. Our results also show strong integrality gaps for the corresponding linear programs.

Harold Tiemessen (IBM Research)

Title: Heuristics for Inventory Replenishment and Service Request Fulfillment in Spare Parts Networks

Abstract: Motivated by IBMs spare parts logistics, we present a distributed inventory network for spare parts where service requests can usually be solved from multiple local warehouses. We consider a single-item, multi-location, single-echelon model with service level constraints and centralized control. We discuss an inventory controller that consists of a decision rule for selecting the local warehouse that sends out a part to a waiting customer, and a heuristic for calculating replenishment orders. Replenishment orders are calculated by solving a simple but state-dependent LP model at carefully selected moments in time. What differentiates the proposed solution from many existing solutions is that we use stock level information from the entire network to jointly optimize replenishment decisions at all local warehouses. We have carried out simulation experiments to evaluate the proposed solution at different scenarios. We present and discuss the results and draw conclusions.

Norbert Trautmann (University of Bern)

Title: Resource Allocation Capabilities of Commercial Software Packages for Project Management: An Experimental Performance Analysis

Abstract: We report on the results of an experimental analysis where we have compared the resource allocation capabilities of recent versions of 5 commercial project management software packages against state-of-the-art solution methods from the literature. For our analysis, we have used 1560 RCPSP instances from the standard test set PSPLIB. The results indicate that using the automatic resource allocating feature of those packages may result in project durations that are considerably longer than necessary, in particular when the resource scarcity is high or when the number of activities is large.

Ilaria Vacca (EPFL)

Title: Two-stage column generation: a novel framework

Abstract: Column generation has been intensively used in the last decades to compute good quality lower bounds for combinatorial problems reformulated through Dantzig-Wolfe decomposition. In this work we propose a novel framework to cope with problems in which the structure of the original formulation, namely the presence of a combinatorial number of decision variables, does not allow for straightforward reformulation. The basic idea is to start from a meaningful subset of original variables, apply the DW reformulation to the subset, solve the reformulation with column generation and perform the explicit pricing on original variables retracing back the reformulation and using complementary-slackness conditions. The Discrete Split Delivery Vehicle Routing Problem with Time Windows (DSDVRPTW) is used as an illustration for the method, which provides a new exact approach to the problem. Preliminary computational experiments are reported. This is joint work with Matteo Salani.

Registration

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

Registration deadline: August 25, 2008.

Today is March 24, 2010.

Sorry, the deadline is over.

Last Name:		Required field
First Name:		Required field
Email:		Required field
Affiliation:		Required field
Position:	(please select) Pre-doctoral PhD student Post-doc Other (professor, etc.)	Required field
Special request:
Anti-spam:	Type the two words:Type what you hear:Incorrect. Try again.

Click here to submit an abstract.

Current number of registered participants: 47

Accomodation

EPFL-rates apply to the following hotels. Prices are indicative. Please contact the hotel for the exact rates.

In Lausanne

Swiss Youth Hotels

Bois-de-Vaux 36, 1007 Lausanne
tél: +41 21 626.02.22
fax: +41 21 626.02.26
adresse email: lausanne@youthhostel.ch
single: 78.00

Hôtel Elite

Avenue Ste-Luce 1
1003 Lausanne
tél: +41 21 320 23 61
fax: + 41 21 320 39 63
single: 117.00; double: 174.00

Hôtel Alagare

Minotel Suisse
Rue du Simplon 14
1006 Lausanne
tél: +41 21 617 92 52
fax: +41 21 617 92 55
single 105.00; double: 150.00

Hôtel Alpha-Palmiers

Fassbind Hotels
Rue du Petit.Chêne 34
1003 Lausanne
tél: +41 21 555 59 99
fax: +41 21 555 59 98
single: 158.00; double: 220.00

EPFL area

Hotel Pré-Fleuri***

Rue du Centre 1, 1025 St-Sulpice.
Email: prefleuri@bluewin.ch
Tél. 021 691 20 21
Fax 021 691 20 20
Price for a single room around CHF 150.-

Motel des Pierrettes** St-Sulpice

10 minutes walk to EPFL
Route cantonale 19, 1025 St-Sulpice
It has no web-site but you can call at +41 21 691 25 25.
It has no restaurant.
Price for a single room, around CHF 110.- (special price for EPFL hosts)

Hostellerie du Débarcadère

Chemin du Crêt 7, 1025 St-Sulpice,
It belongs to "Relais& Châteaux"
Web-site: www.debarcadere.ch
Price for a single room around CHF 170.- (special price for EPFL hosts)

Novotel Lausanne Bussigny

35, Route de Condémines, 1030 Bussigny
(15 minutes by car, no bus possibilities)
Price for a single room, around CHF 200.- (special price for EPFL hosts)

Transportation

The easiest way to get to EPFL is to take the train from Geneva Airport to Renens. In Renens, take the light-rail (called M1) towards Lausanne. There is a stop at EPFL. The travel time is about 1 hour.

A map of the bus and metro network can be found here and time tables are available at the Lausanne Transport web page. Note that tickets must be bought before departure in machines only accepting coins. The price for a one-way ticket from the center of Lausanne to EPFL is 2.80 Fr. (two zones) and most machines do not give back change.

Check the Swiss Federal Railways website.

To navigate within EPFL, use map.epfl.ch.

Consult also this page