Seventh Joint Operations Research Days

September 3-4, 2009
Hotel De la Paix in Lugano Switzerland
		SVOR General Assembly: September 3rd at 17.00

Organizing committee:

• Michel Bierlaire, EPFL and SVOR
• Daniel Costa, SVOR
• Komei Fukuda, ETHZ
• Luca Maria Gambardella, IDSIA and SVOR
• Jon Lee, IBM Research
• Hans Jakob Lüthi, ETHZ and SVOR
• Eleni Pratsini, IBM Research

We invite members of Swiss OR researchers and IBM research staff 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.

UPDATE: Final Program

Keynotes speakers

Prof. Silvano Martello, DEIS, University of Bologna
	Assignment Problems: At the Roots of Combinatorial Optimization In 1955 H. W. Kuhn published the Hungarian algorithm, the first polynomial-time algorithm for the assignment problem. In the next fifty years assignment problems attracted hundreds of researchers. Their studies accompanied and sometimes anticipated the development of Combinatorial Optimization, producing fundamental contributions to all algorithmic techniques in use nowadays. We review the most important assignment problems (linear, quadratic, bottleneck) and the most relevant results in this area. We also show that a recently discovered paper dated 1851 contains a solution method that appears to anticipate by one century the discovery of the Hungarian algorithm. Talk partially based on Assignment Problems by R. Burkard, M. Dell'Amico and S. Martello (SIAM, 2009) http://www.assignmentproblems.com
Prof. Alberto Marchetti Spaccamela, Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza"
	Multiprocessor real-time scheduling: algorithms and complexity A real-time task system consists of a finite number of tasks, each of which generates an infinite sequence of recurring jobs with the same processing requirement characterized by a deadline. We distinguish two main classes of task systems, periodic and sporadic task systems, which differ in the generation of job sequences recurrence scheme. There is given one or multiple processors, each of which can process only one job at the time. Now, each job must be executed by the system, possibly with preemptions and migration, before its deadline. A task system is said to be feasible if there exists a schedule such that each job completes its execution requirement before its deadline. We review complexity results for different variation of the problem. In the hope of overcoming hardness results, we also discuss different relaxations of the problem. The above is joint work with V. Bonifaci, H.L. Chan, N.Megow, S.Stiller

Abstracts

16 abstracts

Michel Baes (IFOR / ETH Zurich)

Title: Accelerating fast gradient methods for semidefinite optimization

Abstract: Semidefinite optimization problems constitute a special class of symmetric programming, and have nowadays a very wide spectrum of applications, for instance in the relaxation of NP-hard combinatorial problems. Usually, these semidefinite optimization problems are solved using the heavy machinery of interior-point methods, limiting the size of the instances that are tractable in practice. Alternatively, one can use simpler first-order optimization methods, where only the value and a subgradient of the objective function are available. We show that, provided that the required accuracy is not too extreme, some first-order methods are in theory and in practice (much) faster than interior-point methods for very large-scale problems. These efficient first-order methods require at every iteration the computation of a subgradient of the objective and two projections of an appropriate vector on some appropriate set. By performing approximate projections with approximate subgradients, we can decrease significantly the iteration cost. We have developed a new theoretical framework to understand how accurately each of these approximations must be done. Essentially, we can afford to compute the subgradient and to solve one of the two projection problems very coarsely.

Khaoula BESBES (laboratoire d’optimisation et de gestion industrielle et de la qualité, Institut Supérieur de gestio)

Title: A Tabu Search approach to minimize makespan in a blocking flow-shop with transportation

Abstract: Key words: Flow-shop, Tabu Search, Blocking, Transportation robot In this paper, we address the flow-shop problem with blocking and a single transportation robot. The objective is to find a feasible selection on both machine operations and robot moves that minimizes the makespan. This problem reflects the reality of real production situations better than the classical flowshop where it has been assumed that the buffer space between machines is unlimited and where the transportation time between machines was ignored. Recently, many researchers proposed exact and heuristic algorithms for the flow-shop problem with blocking [1,2,8] or for the flow-shop problem with transportation [4]. Few researchers have considered simultaneously blocking and transportation [7,9]. It also has been shown that the problem is NP-Hard [5,10] and that with the blocking conditions, only permutation schedules are possible [7]. In this work, we propose a tabu search approach to minimize makespan in a blocking flow-shop with transportation. Our approach is based on a two stage procedure based on tabu search[7], where in the outer stage a selection on machine operations is made and in the inner stage a selection on robot moves is made. We show that when the machine processing time is much bigger than the robot transportation time, the optimal solution for the outer stage is also the optimal solution for the problem. Thus, we limit our resolution to the outer stage. We propose to test the performance of three Neighborhoods used with the classical permutation flow-shop [6]. The three algorithms are as follow: - In the first algorithm, the neighborhood Z (Π, ε) generated by moves outside blocks is used. - In the second algorithm, the neighborhood X (Π), generated by moves inside blocks is used. - In the third algorithm, a combination of both is used To test and compare our algorithms, 24 families of problems are generated where the number of machines {3,5,7,10} and the number of jobs {5,10,15,20,25,30}. The machine processing times are generated randomly from the interval [50,100] and the robot operation times are generated randomly from the interval [5,10]. Experimental results show that algorithm three performs better than the other two algorithms. Bibliography [1] N.N.K Abadi (1995). Flow-shop scheduling problems with no-wait and blocking environment A mathematical programming approach. University of Toronto, Canada. [2] P. Bruker, S. Heitman and J. Hurink (2002). Flow-shop problem with intermediate buffers. Faculty of Mathematical Science, memorandum n°1625, University of Twente, The Netherland. [3] F. Glover (1990). Tabu search: A tutorial. Interfaces 20:74 – 94. [4] J. Hurink and S. Knust (1999): Makespan minimization for flow-shop problems with transportation times and a single robot. Preprint submitted to Elsevier preprint. [5] N.G Hall and C. Sriskazndarajah (1996). A survey of machine scheduling problems with blocking and No-Wait in process. Operations Research 44: 535-550 [6] E. Nowicki and C. Smutnicki (1996) . A fast tabu search algorithm fort he permutation flow-shop scheduling problem [7] S. khalfallah (2003) . Le problème d’ordonnacement dans une cellule robotisée avec prise en charge de l’interblocage et du transport. PHd Thesis, Ecole Centrale de Paris 29-2003. [8] D.P. Rankoni (2004). A note on constructive heuristics for the flow-shop problem with blocking. International Journal of Production Economics 87: 39-48 [9] A. Soukhal, P.Martineau (2005). Resolution of scheduling problem in a flow-shop robotic cell. European Journal of Operations Research 161: 62-72 [10] A. Soukhal, A.Oulamara and P. Martineau (2005). Complexity of flow-shop scheduling problems with transportation constraints. European Journal of Operations Research 161: 32- 41

Mike Bielser (IOR, University of Zurich)

Title: SEAL

Abstract: In general, algebraic modeling languages (e.g. AMPL or GAMS) have been designed to model DETERMINISTIC linear and/or nonlinear programming problems. They do not provide support to include random elements in those models. This is obviously needed to deal with multistage or chance constrained stochastic linear programming (SLP) problems. This paper describes a new modeling language specifically designed to specify SLP model instances. Some examples are shown to demonstrate the possibilities provided by the corresponding modeling language SEAL. Finally, the interface between SEAL and SLP-IOR (by Kall and Mayer; available at our institute), a model management system providing various solvers for SLP problems, is discussed. Keywords: - random entries in LP's - modeling languages - stochastic programming

Richard Boedi (IBM)

Title: Symmetric Linear Programs

Abstract: Usually, symmetries are very welcomed in many scientific areas. However, in linear and integer programming, the reverse seems to be true. In practice, highly symmetric integer programs often turn out to be particularly hard to solve. The problem is that branch-and-bound or branch-and-cut algorithms, which are commonly used to solve integer programs, work efficiently only if the bulk of the branches of the search tree can be pruned. Since symmetry in integer programs usually entails many equivalent solutions, the branches belonging to these solutions cannot be pruned, which leads to a very poor performance of the algorithm. Only in the last few years first efforts were made to tackle this irritating problem. In 2002, Margot presented an algorithm that cuts feasible integer points without changing the optimal value of the problem. Improvements and generalizations of this basic idea can be found in later papers of Margot. Linderoth et al. concentrate on improving branching methods for packing and covering integer problems by using information about the symmetries of the integer programs. Another interesting approach to these kind of problems has been developed by Kaibel and Pfetsch. These authors introduce special polyhedra, called orbitopes, which they use to remove redundant branches of the search tree. Friedman's fundamental domains are also aimed at avoiding the evaluation of redundant solutions. For selected integer programs like generalized bin-packing problems there exists a completely different idea how to deal with symmetries. Instead of eliminating the effects of symmetry during the branch-and-bound process, the authors exclude symmetry already in the formulation of the problem by choosing an appropriate representation for feasible packings. All ideas in the aforementioned papers finally rely on the branch-and-bound algorithm, or they are only applicable to selected problems. In contrast to this optimizational or specialized point of view, we want to approach the topic from a more general and algebraic angle and detach ourselves from the classical optimization methods like branch-and-bound. In this talk we will examine symmetries of linear programs in their natural environment, the field of group theory. Our main objective aims at a better understanding of the role of symmetry in the context of linear and integer programming. We give a proof that any given permutation group is the symmetry group of some LP.

Reinhard Bürgy (University of Fribourg)

Title: The Flexible Blocking Job Shop with Transfer and Set-up Times

Abstract: The Flexible Blocking Job Shop (FBJS) considered here is a job shop scheduling problem characterized by the availability of alternative machines for each operation and the absence of buffers. The latter implies that a job, after completing an operation, has to remain on the machine until its next operation starts. Additional features are sequence-dependent transfer and set-up times, the first for passing a job from a machine to the next, the second for change-over on a machine from an operation to the next. The objective is to assign machines and schedule the operations in order to minimize the makespan. We give a problem formulation in a disjunctive graph and develop a heuristic local search approach. A feasible neighborhood is constructed, where typically a critical operation is moved (keeping or changing its machine) together with some other operations whose moves are ”implied”. For this purpose, we develop the theoretical framework of job insertion with local flexibility, based on earlier work of Gröflin and Klinkert on insertion. A tabu search that consistently generates feasible neighbor solutions is then proposed and tested on a larger test set. Numerical results support the validity of our approach and establish first benchmarks for the FBJS. This is joint work with Heinz Gröflin and Dinh Nguyen Pham.

Niklaus Eggenberg (EPFL ENAC Transp-OR)

Title: Uncertainty Feature Optimization for the Airline Scheduling Problem

Abstract: In this paper, we present an application to the Airline Scheduling Problem (ASP) of the Uncertainty Feature Optimization (UFO) framework which combines both a proactive scheduling algorithm and a reactive recovery algorithm used for re-optimization when disruptions occur. We show that re-timing some flights of the original schedule allows for more delay absorption. This means that the solution is robust against some delays. Additionally, in case of severe disruption requiring reoptimization, the retiming increases the performance of the recovery algorithm: the number of disrupted passengers, and thus associated compensation costs, are reduced. We provide computational results for the public data of an European airline provided for the ROADEF Challenge 2009(http://challenge.roadef.org/2009/index.en.htm)

Andreas Klinkert (Zurich University of Applied Sciences, Institute of Data Analysis and Process Design)

Title: Multi-Skill Staff Rostering in Airport Ground Handling

Abstract: Staff scheduling and rostering typically involves a number of hierarchical subproblems including demand modeling, shift design, days-off scheduling, lines of work construction and staff assignment. When solving highly constrained large-scale rostering problems it is usually not computationally practical to deal simultaneously with all these tasks, and decomposing the problem into several separate modules is typical for most real-world solutions. The problem considered here focuses on the days-off scheduling phase of the rostering process, and has been tackled in the context of an industrial project in the airport ground handling business. The main concern in days-off scheduling is to determine the off-work days for each staff member over the rostering planning horizon. In general, there are two categories of constraints to be considered. The first type is related to the individual line of work of each employee and originates from industrial regulations, labor contract, workplace agreements and individual preferences. The second type of constraints refers to the different days of the planning horizon and is concerned with satisfying the required daily staffing levels for each shift. According to the setting in our project, we assume that the required shifts and their staffing levels for each day have been determined prior to the days-off scheduling phase. Furthermore we assume a multi-skill staff environment where shifts can only be assigned to employees with appropriate skills. Staffing level constraints have to assure that on each day there are enough workers with appropriate skills for every shift. An integer programming model has been developed to determine optimized days-off schedules, taking into account skill-specific staffing requirements and numerous constraints related to the design of the individual lines of work. According to the specific needs of the industrial project partner, a separation has been made between hard and soft constraints, and the latter have been dualized and managed through the objective function. The developed model successfully solves the complex large-scale problems posed by the industrial project partner. Typical problem dimensions are in the range of 500 - 800 staff members, 100 - 300 shifts per day and up to 50 different skill combinations, yielding model sizes of more than 100'000 binary variables and constraints. The CPLEX 11.0 solver is able to find high quality solutions within a few hours which clearly outperform the sophisticated solutions constructed manually by the experts at the planning department of the ground handling company.

Marco Laumanns (IFOR, ETH Zurich)

Title: Robust Operations Planning in Infrastructure Networks

Abstract: Operators of transportation infrastructure systems face the key conflict between efficiency (resource utilization) and effectiveness (service quality). While cost pressure and increasing load urge ever higher capacity utilization, the operation necessarily becomes more vulnerable to disturbances when less reserves are available. In this talk, I will overview ongoing work at IFOR of how to integrate robustness into operations planning of infrastructure networks such as railway and electricity networks. I will then introduce the concept of adaptive robustness and demonstrate, using the example of container terminals, how adaptivity can reduce the resources (here quay cranes) required for stable operation (to process a given number periodically calling vessels with uncertain arrival times within their service time contraints). The developed model is a large-scale LP that bridges gap between discrete stochastic control and (infinite-stage) stochastic programming.

Jon Lee (IBM TJ Watson Research Center)

Title: Parametric Nonlinear Discrete Optimization

Abstract: I will discuss work refining the boundary between tractable and intractable classes of nonlinear discrete optimization, via the model max/min { f(WX) : X in S }, where mainly S is a well-described set of points in Z^n and W is a matrix having few rows and entries that are small in some sense. A motivation is multi-objective optimization, where the rows of W describe somelinear objectives that are traded off against one another via f. This is joint work with Y. Berstein, S. Onn, R. Weismantel, and others.

Alberto Marchetti-Spaccamela (Sapienza, Universita' di Roma)

Title: Multiprocessor real-time scheduling: algorithms and complexity

Abstract: A real-time task system consists of a finite number of tasks, each of which generates an infinite sequence of recurring jobs with the same processing requirement characterized by a deadline. There is given one or multiple processors, each of which can process only one job at the time; each job must be executed by the system, possibly with preemptions and migration, before its deadline. A task system is said to be feasible if there exists a schedule such that each job completes its execution requirement before its deadline. We distinguish two main classes of task systems, periodic and sporadic task systems, which differ in the generation of job sequences recurrence scheme. In the periodic version of the problem the period T(i) of task i denotes the exact lenght of the time interval between the release dates of two successive jobs of the same task. In the sporadic version of the problem the period denotes the minimal separation time before the next invocation of a task will be released. Therefore a sporadic task system may generate infinitely many different collections of jobs during different executions. We review recent complexity results for periodic and sporadic task systems. In the hope of overcoming hardness results, we also discuss special cases and different relaxations of the problem. The talk is based on joint work with S.Baruah, V. Bonifaci, H.L. Chan, N.Megow, S.Stiller

Monaldo Mastrolilli (IDSIA)

Title: Precedence Constraint Scheduling: Connections to Dimension Theory of Partial Orders and Inapproxima

Abstract: We consider the single machine scheduling problem to minimize the weighted sum of completion times under precedence constrains. In a series of recent papers it was established that this scheduling problem is a special case of minimum weighted vertex cover. In this talk we show that the vertex cover graph associated to the scheduling problem is exactly the graph of incomparable pairs defined in dimension theory of partial orders. Exploiting this relationship allows us to present a framework for obtaining $(2-2/f)$-approximation algorithms provided that the set of precedence constraints has fractional dimension~$f$. Our approach yields the best known approximation ratios for all previously considered special classes of precedence constraints, and it provides the first results for bounded degree and interval dimension~$2$ orders.

Nikos Mutsanas (IDSIA)

Title: Approximating Single Machine Scheduling with Scenarios

Abstract: In the field of robust optimization, the goal is to provide solutions to combinatorial problems that hedge against variations of the numerical parameters. This constitutes an effort to design algorithms that are applicable in the presence of uncertainty in the definition of the instance. We study the single machine scheduling problem with the objective to minimize the weighted sum of completion times. We model uncertainty by replacing the vector of numerical values in the description of the instance by a set of possible vectors, called scenarios. The goal is to find the schedule with minimum value in the worst-case scenario. We first show that the general problem is intractable by proving that it cannot be approximated within $O(\log^{1-\epsilon}n)$ for any $\epsilon>0$, unless NP has quasi-polynomial algorithms. We then study more tractable special cases and obtain an LP based $2$-approximation algorithm for the unweighted case. We show that our analysis is tight by providing a matching lower bound on the integrality gap of the LP. Moreover, we prove that the unweighted version is NP-hard to approximate within a factor less than 6/5. We conclude by presenting a polynomial time algorithm based on dynamic programming for the case when the number of scenarios and the values of the instance are bounded by some constant.

Evanthia Papadopoulou (University of Lugano)

Title: Geometric min-cuts, higher order Voronoi diagrams, and net aware VLSI critical area extraction for o

Abstract: We address the problem of computing critical area for open faults (opens) in a circuit layout in the presence of multilayer loops and redundant interconnects. The extraction of critical area is the main computational bottleneck in predicting yield loss for a VLSI design due to random manufacturing defects. We first model the problem as a graph problem and we solve it efficiently by exploiting its geometric nature. To model open faults we formulate a geometric version of the classic min-cut problem in graphs. Then the critical area extraction problem gets reduced to the construction of a generalized Voronoi diagram for opens that is based on concepts of higher order Voronoi diagrams and the Hausdorff Voronoi diagram. The approach expands the Voronoi critical area computation paradigm with the ability to accurately compute critical area for missing material defects even in the presence of loops and redundant interconnects spanning over multiple layers. The generalized Voronoi diagrams used in the solution are combinatorial structures of independent interest.

Matteo Salani (EPFL, Transport and Mobility Laboratory)

Title: Ambush avoidance in vehicle routing

Abstract: Vehicle ambush avoidance in urban environments is crucial to both peace-time and war-time goals. Unsafe routing prejudices successful humanitarian shipments through troubled areas with a history of hijacking, diplomatic security for high-profile VIPs, valuable transfers between banks, and military supply transport through insurgency zones. In this talk, we address the problem of ambush avoidance of vehicle routes delivering valuables to credit institutes. We first describe a model in which the attacker is considered as a feature of the environment, adapting the main concepts of hazardous material transportation. Secondly, we present a model in which the attacker’s incentives is modeled, as is the case in game-theoretic modeling of ambush. The model results in a two steps approach based on a minmax linear program and an enumeration procedure.

Silvia von Bergen (IOR, University of Zurich)

Title: Stochastic DEA Models with Risk Constraints

Abstract: Data Envelopment Analysis (DEA) is a technique for determining the relative efficiency of Decision Making Units (DMU) which transform multiple inputs into multiple outputs. In this talk the main focus is on efficiency evaluation of DMUs where the underlying transformation process is supposed to be stochastic (e.g. transformation of deterministic inputs into stochastic outputs). So far, the presence of stochastic data has usually been handled by using chance-constrained DEA models. The approach discussed here is based on risk functions. Compared to deterministic DEA models the violation of the frontier constraints is now allowed, but measured by a risk function and bounded by a parameter.

Dennis Weyland (IDSIA)

Title: Search Heuristics for Stochastic Vehicle Routing Problems

Abstract: The field of Combinatorial Optimization under Uncertainty has received increasing attention within the last years. Using uncertain and dynamic information in the problem formulation, more realistic models of real world problems can be generated. One common way for the representation of the uncertainty is to use probability distributions as input parameters, leading to Stochastic Combinatorial Optimization Problems. In this talk we focus on search heuristics for Stochastic Vehicle Routing Problems. We present some new results and discuss recent developments in this field.

Registration

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

Registration deadline: July 26, 2009.

Today is August 01, 2010.

Sorry, the deadline is over.

Click here to submit an abstract.

Current number of registered participants: 43

Accomodation

Since the conference takes place at the Hotel De la Paix, we suggest the participants to stay at this same Hotel. The following options are available
(prices are per night per room and include breakfast):

* single room: 160 CHF
* double room: 225 CHF


We kindly ask the participants to make their reservation themselves, before 31 July 2009, by faxing this form to Hotel de la Paix

Transportation

You may find all necessary travel information here.