|
|
| Place centrale > SB > IMA > ROSO > JORDays |
|
|
|
|
||
|
|
|
|
||
|
|
|
|
||
|
|
|
|
||
| anglais seulement | |
|
|||
|
|
|
|
||
September 14-15, 2006
Ecole Polytechnique Fédérale de Lausanne
organized by
The objective of these Operations Research Days is to exchange the current research topics addressed by OR groups of IBM Research, and OR Centers of Swiss Universities and Institutes of Technology. The motivation is to trigger new joint projects involving both Swiss institutions from academia and practice, and IBM. The program is currently being set up, and will be publicized on this page.
The organization is coordinated by M. Bierlaire (EPFL),K. Fukuda (ETHZ-EPFL), Th. Liebling (EPFL) and E. Pratsini (IBM-Research).
Plenary speakers
Dr Philippe Toint is full professor and director of the Department of Mathematics of the University of Namur,Belgium, co-director of the Numerical Analysis Research Unit, and director of the Transportation Research Group.
His research interests are smooth nonlinear optimization, with an emphasis on the algorithmic viewpoint, ranging from convergence theory to numerical considerations and software development ( LANCELOT, CUTEr, GALAHAD ), as well as practical and multidisciplinary applications of optimization techniques.
He is also interested in the analysis of transportation systems, including dynamic traffic modelling and demand estimation, as well as advanced behavioural models, with applications in regional, national and european strategic transportation planning.
Lecture: Trust region and filters: efficient tools for nonlinear programming
The lecture provides an introduction to trust region and filter methods for solving optimization problems which are nonlinear and not necessarily convex. The first type of method, now classical, presents significant theoretical and practical advantages, and can easily be adapted with many variants: problems with or without constraints, convex and nonconvex constraints, penalty and interior-point methods, approximative or unavailable derivatives, etc. The concept of filter is more recent, and can be viewed as a way to preserve the interesting properties of trust region methods, while making the algorithms less conservative (in many cases) to increase their efficiency without affecting their robustness. Advantages and drawbacks will be discussed for an audience of non-specialists in continuous optimization.
Dr Volker Kaibel is the deputy head of the department of optimization at Zuse-Institut, Berlin (ZIB), and visiting professor at TU Berlin. He is a member of the DFG Research Center Matheon, and of the DFG Research Group "Algorithms, Structure, Randomness".
His research interests are in integer programming, polyhedral combinatorics, combinatorial optimization, and discrete geometry.
Lecture: Breaking Symmetry in Integer Programmming
Todays's branch-and-cut algorithms for solving integer programs show a weak performance on symmetric models. Here, symmetry means that a large group operates on the variables in such a way that the objective function is constant along each orbit. Besides unnecessarily huge branch-and-bound trees, this leads also to poor linear programming bounds.
The lecture will survey approaches to overcome these difficulties. It will be focussed on polyhedral studies of orbitopes, which are polyhedra that arise as the convex hulls of sets of representatives of the orbits mentioned above. In particular, we will give a complete and non-redundant linear description of the convex hull of all zero- one matrices with exactly one one-entry per row, whose columns are sorted lexicographically.
Call for abstractsA total of 17 presentations will take place during the meeting. 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.
Please send your abstract by Email before August 15, 2006 to M. Bierlaire.
Schedule| Thursday | Friday | ||||||
| Start | End | Start | End | ||||
| 10:00 | 10:25 | Opening | 08:30 | 9:30 | Keynote: Philippe Toint | ||
| 10:25 | 11:05 | Michele Conforti | 9:30 | 9:55 | Diethard Klatte | ||
| 11:05 | 11:30 | Leonora Bianchi | 9:55 | 10:20 | Markus Ettl | ||
| 11:30 | 11:55 | Mike Bielser | 10:20 | 10:50 | Coffee | ||
| 11:55 | 13:45 | Lunch | 10:50 | 11:15 | Christophe Weibel | ||
| 13:45 | 14:45 | Keynote: Volker Kaibel | 11:15 | 11:40 | Fabian Chudak | ||
| 14:45 | 15:10 | Gabrio Caimi | 11:40 | 12:05 | Ola Svensson | ||
| 15:10 | 15:40 | Coffee | 12:05 | 13:55 | Lunch | ||
| 15:40 | 16:05 | Carolina Osorio | 13:55 | 14:20 | Monaldo Mastrolilli | ||
| 16:05 | 16:30 | Eric Cope | 14:20 | 14:45 | Ionut Aron | ||
| 16:30 | 16:55 | Bernard Ries | 14:45 | 15:15 | Coffee | ||
| 16:55 | 17:25 | Break | 15:15 | 16:15 | PROJECTS | ||
| 17:25 | 17:50 | Julien Thénié | |||||
| 17:50 | 18:15 | Heinz Groeflin | |||||
| 19:30 | Dinner |
AbstractsPolyhedral characterizations of some mixed-integer sets
We give a linear description of the convex hull of the set of feasible solutions of a mixed-integer model, which includes several moxed-integer sets that have been studied in the literature. The technique that we use shows the power of extended descriptions, i.e. linear descriptions that use more variables than the natural ones and also shows a novel application of properties of totally unimodular matrices. These results are joint with Laurence Wolsey, Marco Di Summa, Fritz Eisenbrand.
Ant colony optimization and local search for the probabilistic traveling salesman problem: A case study in stochastic combinatorial optimization
Stochastic Combinatorial Optimization Problems (SCOPs) are a wide class of combinatorial optimization problems under uncertainty, where part of the information about the problem data is unknown at the planning stage, but some knowledge about its probability distribution is assumed.
Optimization problems under uncertainty are complex and difficult,and often classical algorithmic approaches based on mathematical and dynamic programming are able to solve only very small problem instances. For this reason, in recent years metaheuristic algorithms such as Ant Colony Optimization, Evolutionary Computation, Simulated Annealing, Tabu Search and others,are emerging as successful alternatives to classical approaches.
Metaheuristics can address real-size SCOPs, and they are flexible, since they can be quite easily adapted to solve different SCOPs formulations, both static and dynamic. On the base of the current literature, we identify the following as the key open issues in solving SCOPs via metaheuristics: (1) the design and integration of ad hoc, fast and effective objective function approximations inside the optimization algorithm; (2) the estimation of the objective function by sampling when no closed-form expression for the objective function is available, and the study of methods to reduce the time complexity and noise inherent to this type of estimation; (3) the characterization of the efficiency of metaheuristic variants with respect to different levels of stochasticity in the problem instances. We have investigated the above issues by focusing in particular on a SCOP belonging to the class of vehicle routing problems: the Probabilistic Traveling Salesman Problem (PTSP). For the PTSP, we have considered the Ant Colony Optimization metaheuristic and efficient local search algorithms that can enhance its performance. We obtained state-of-the-art algorithms, that are effective particularly for instances above a certain level of stochasticity. If the level of stochasticity is low, it is more convenient to solve the problem as if it were deterministic. We have found that the performance of algorithmic variants based on ad hoc approximations is strongly correlated with the absolute error of the approximation, and the effect on local search of ad hoc approximations can be very degrading. The algorithmic variants based on an estimation of the objective function by sampling obtain worse results than using the exact objective function,when no local search is used, while the use of sampling-based local search is very effective for some group of instances.
Stochastic Extensions for Algebraic Languages (SEAL)
In general, today's algebraic modeling languages (e.g. AMPL or GAMS) designed to set up models of linear and/or nonlinear programming problems, do not provide any support to include random elements into those models. This is obviously needed to deal with multistage or chance constrained stochastic linear programming (SLP) problems.
This paper describes a set of modeling constructs that enable (or simplify) the formulation of an SLP model instance.
Finally, some examples are discussed to demonstrate the possibilities provided by the corresponding software tool SEAL, designed and implemented by the author to extend GAMS. If an SLP model instance written in SEAL should be solved, the system can generate an output file compatible with one of the input formats of the system SLP-IOR (by Kall and Mayer; available at our institute), a model management system providing various solvers for SLP problems.
Railway scheduling of a main station area
Currently, railway operators are increasing the frequencies of their trains. By condensing the timetable, scheduling times and exact itineraries of trains becomes increasingly difficult as the chosen schedule not only have to meet safety restrictions, but also guarantee some stability if delays occur. We address the problem of scheduling trains in railways stations for a given service intention and some additional constraints. We present a model and outline two algorithms. The scheduling possibilities for each single train are listed as nodes in a graph and are connected with edges if the simultaneous assignment is infeasible. A feasible solution correspond to a independent set with a cardinality equal to the number of train to schedule in this graph. The first algorithm searches for a feasible solution for the scheduling problem using a fixed point iteration. The initial solution is then amended by applying the second algorithm in order to increase the stability of the timetable. This algorithm is based on a local search optimization scheme.
Finite capacity queueing networks with blocking after service
Queueing network models have been widely applied as tools allowing the estimation of performance measures and the behavioural description of systems such as communication, production and software architecture networks. Queueing network models with finite capacity queues, where blocking may arise, allow a more realistic description of the system under study. In this talk we will present an approximation method developed to analyze open finite capacity queueing networks with blocking after service. The method decomposes the network into single queues that are analysed using revised arrival and service rates. Unlike pre-existing methods it preserves both the network topology and its configuration (number of queues and their capacity). It also explicitly models the blocking phase. Its comparison with other methods as well as its validation versus exact solutions on small networks will be discussed.
Bayesian Strategies for Dynamic Pricing in E-Commerce
E-business retailers have used dynamic pricing as a means of estimating aggregate customer demand response to price changes when this response is initially unknown. This study looks at dynamic pricing in the context of learning customer demand for information goods sold on the Internet. Because information goods can be replicated quickly at almost no cost, issues with inventory and production generally do not arise. Rather, the major concern in designing a dynamic pricing strategy in this setting is efficiently managing the exploration-exploitation trade-offs involved in price selection.
We introduce a nonparametric Bayesian model of demand uncertainty involving Dirichlet priors, which are very flexible and easy to elicit, and encode many natural assumptions about the dependence among various demand values. We provide both analytic formulas and efficient approximation methods for computing the posterior distributions after sales data have been observed. Within the framework of this Bayesian model, we investigate a set of heuristics for sequential pricing that are based on approximations of a dynamic programming formulation. These heuristics are shown to be efficient in terms of both performance and computation, and they are robust to various misspecifications of the prior
Graph coloring with cardinality constraints on the neighborhoods
We consider a few variations of the vertex coloring problem which consist essentially in imposing the number of occurrences of the different colors in a given collection P of subsets P_i of vertices. More precisely we are given an undirected graph G=(V,E) with n vertices and m edges. We have to find a partition of the vertex set of G such that in some generalized neighborhood of each vertex v, the number of occurrences of each color i is a given integer h(v,i). We give some NP-completeness results for very special classes of subproblems as well as some polynomially solvable cases concerning trees.
Stochastic programming with step decision rules
Stochastic programming with step decision rules, SPSDR, is an attempt to overcome the curse of computational complexity of multistage stochastic programming problems. SPSDR combines several techniques. The first idea is to work with independent experts. Each expert is confronted with a sample of scenarios drawn at random from the original stochastic process. The second idea is to have each expert work with step decision rules. The optimal decision rules of the individual experts are then averaged to form the final decision rule. The final solution is tested on a very large sample of scenarios. SPSDR is then tested against two alternative methods: regular stochastic programming on a problem with 3 stages and 2 recourses; robust optimization with affinely adjustable recourses on a 12-stage model. The performance of the new method turns out to be competitive on those examples, while it permits a tighter control on computational complexity than standard stochastic programming.
Insertion in Scheduling with Alternative Machines: A Theoretical Framework and Some Results
Insertion problems arise in scheduling when some activities are already sequenced, forming a "schedule", and additional activities, e.g. the operations of a job, have to be inserted into the schedule. Insertions are used extensively in heuristics as a mechanism to build or improve solutions, but it is only in the last years that the problem has been addressed as a scheduling problem of its own, starting with the work of Kis and Hertz on job insertion in the classical job shop (2003).
In a recent paper (EJOR on line 2006) of the author, jointly with A. Klinkert, a framework was presented that captures several types of insertions (e.g. activity, job and block insertion) in a variety of job shop problems, (e.g. the Multi-Processor-Task, the Blocking and the No-Wait Job Shop). A general insertion problem was defined for which were derived (i) a polyhedral description of the family of feasible insertions based on stable sets, (ii) a feasibility problem and its solution and (iii) a polynomial time procedure that computes a lower and upper bound and - in some insertion problems, an optimal solution - to the minimum makespan insertion problem.
In this talk, we examine the extension of the approach to the "flexible" case when alternative machines are present. While the extension is straightforward when machine flexibility is described in terms of modes, fewer results hold when machine flexibility is given in compact form by specifying for each operation a set of machines from which one is to be selected. In contrast to the case with no machine flexibility, the feasibility problem is proven to be NP-complete in general. Special cases are identified where a polyhedral description can be given and/or the feasibility problem can be handled.
Strong Lipschitz Stability of Solutions to Perturbed Convex Semi-Infinite Programs
In this talk, we consider convex optimization problems in finitely many variables with linear perturbations of the objective function and right-hand side perturbations of infinitely many inequality constraints. We are concerned with necessary and/or su±cient conditions for the local single-valuedness and Lipschitz continuity (also called strong Lipschitz stability) of the optimal set mapping S. In our setting, this is equivalent to the Aubin property (also called pseudo-Lipschitz continuity) of S. In particular, we provide a sufficient condition for strong Lipschitz stability. This condition consists of the Slater constraint qualification, together with some requirement in addition to the Karush-Kuhn-Tucker conditions. For linear semi-infinite problems, this sufficient condition turns out to be also a necessary one, and it is equivalent to other well-known stability concepts (Kojima-type stability, lower semicontinuity).
The Impact of Product Substitutions on Demand and Supply Planning
In today's competitive and dynamic business environment, companies need to continually evaluate the effectiveness of their supply chain and look for ways to transform business processes to achieve superior customer service and higher profitability. In this paper we propose a novel availability management process that incorporates demand shaping and profitable demand response to drive better operational efficiency through improved synchronization of supply and demand. We develop a nonlinear optimization model that determines dynamic, real-time sales recommendations based on current availability, price, performance and customer demand information. The solution procedure involves solving a master optimization problem and a slave problem in an iterative algorithm. The master problem generates an optimal build plan for a recommended set of product configurations. The slave problem utilizes column generation to determine new product configurations to be added to the existing set such that an overall financial objective is optimized. We apply the model in an assemble-to-order (ATO) manufacturing environment and demonstrate through numerical experiments how the proposed availability management system affects supply chain performance.
On the complexity of Minkowski sums of polytopes
Minkowski sums of polytopes arise in many different fields, such as mechanics, algebra and optimization. The objective of this talk is to discuss some questions about complexity of Minkowski sums of polytopes. Aside from computing algorithms, our main interest is to find for Minkowski sums analogues of McMullen's upper bound theorem. For instance, tight upper bounds for the number of vertices (or facets) of a Minkowski sum in terms of its summands. We discuss two particular cases for which we have exact knowledge. The first are zonotopes, which are sums of segments; The second are sums of polytopes with their duals, which have interesting properties under certain conditions. We introduce a conjecture we managed to prove for both of these cases.
Joint work with Komei Fukuda.
Crane Scheduling
We present an algorithm for scheduling cranes in a factory. The cranes operate on a single track and cannot bypass each other. Each job to be scheduled consists of a sequence of pickup and delivery stops at predetermined locations and a time window. We combine a local search heuristic for assigning jobs to cranes and sequencing them with a dynamic programming algorithm that finds an optimal space-time trajectory for each crane.
Joint work with Latife Genc and John Hooker from Carnegie Mellon University, USA.
Linear Complementarity for Infinite Games on Graphs
I am going to present some recent developments in algorithms for infinite games on finite graphs. The complexity of these games is a long standing open problem, because their decision versions are all members of the complexity class NP intersection coNP, but with an unknown PTIME-membership status. Our approach is based on subexponential randomization schemes for combinatorial linear programming and the generalized linear complementarity problem. In particular, we will see how to represent mean payoff games as standard and non-standard linear complementarity problems (LCPs). Based on these representations, we will derive a new pseudopolynomial algorithm and show that the problem satisfies the sufficient properties of the subexponential randomization schemes. Surprisingly, although the games are related to computer-aided verification, our methods for solving them are also able to solve a nontrivial subclass of P-matrix generalized linear complementarity problems (GLCPs), which we call D-matrix GLCPs. In general, P-matrix LCPs and GLCPs are not known to be polynomial, or even subexponential time solvable, even though NP-hardness would imply NP = coNP. The restriction to D-matrix GLCPs allows us to present a randomized algorithm with subexponential analysis. As an important application we show that simple stochastic games, a long standing problem in NP intersection coNP that is not known to be polynomial, is subsumed by D-matrix GLCPs.
Single machine precedence constrained scheduling
An instance of this problem consists of a set of jobs, each with a processing time and a weight. The objective is to schedule them on a single machine such that the sum of weighted completion times is minimized. What makes the problem hard is that there can be precedence constraints. A precedence constraint between jobs /u/ and /v/ requires job /u/ to be scheduled before job /v/. The best polynomial time approximation algorithms achieve a ratio of 2. Improving on this ratio is considered one of the ten most pressing open problems in scheduling. We prove a conjecture which implies that our scheduling problem is a special case of the minimum vertex cover problem. The proof of the conjecture also establishes a connection to the dimension theory of partial orders. This connection allows to improve on the approximation ratios of various special cases. (Joint work with Christoph Ambuehl and Ola Svensson)
Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovasz extension and non-smooth convex optimization
We consider convex relaxations of combinatorial optimization problems with submodular penalties. The relaxations are obtained very naturally through a novel use of the Lov\'asz extension of a submodular function. We also propose the use of simple and recent algorithms for non-smooth convex optimization due to Nesterov to approximately solve them. For the uncapacitated facility location problem with submodular penalties we design FPTAS for our relaxation that can be used to design approximation algorithms for the original problem for the metric case. In contrast to previous work of Hayrapetyan et al who introduced the problem, our algorithms are fast and simple and do not use the ellipsoid algorithm. We also consider more general set covering problems with submodular costs also introduced by Hayrapetyan et al and submodular minimization. The running time dependence on $\varepsilon$ of our algorithms is either $1/ \varepsilon $ or $1/\varepsilon ^{2}$. The slower ones ($1/\varepsilon ^{2}$) are very simple. The faster ones ($1/\varepsilon $) are more sophisticated and require that certain projections be easy to solve in the base polytope. These projections can generally be solved using submodular minimization as a subroutine; however for some important special cases, they can be solved much more efficiently, thus providing the fastest of our algorithms. This is joint work with Kiyohito Nagano from the University of Tokyo.
ProjectsHere is a list of projects that will be discussed during the Projects Session on Friday at 15:15 - 16:15. The purpose is to identify topics that are of mutual interest and investigate the possibility of collaboration between our institutions.
This is an on-going project at IBM Watson Research Lab. We'll discuss where we are currently with MINLP, what we are working on, and areas for collaboration. The work is done as open source. Information on the work can be found at: https://projects.coin-or.org/Bonmin.
Modeling:
Integer programming:
Heuristics:
Parallel computation:
Determining suitable metrics for services, quantifying risk in purely variable pricing contracts, fair allocation of costs across different customers or business units, and game-theoretic models of customer behavior under pricing contracts.
General Business Risk models: Investigation of appropriate risk measures and quantification techniques.
We investigate the use of causality with predictive models in order to assess the results of given actions. Such assessment is essential in many domains, including epidemiology, medicine, ecology, economy, sociology and business. Predictive models simply based on event correlations do not model mechanisms. They allow us to make predictions in a stationary environment (no change in the distribution of all the variables), but do not allow us to predict the consequence of given actions. For instance, smoking and coughing are both predictive of respiratory disease. One is a cause and the other a symptom. Acting on the cause can change the disease state, but not acting on the symptom. Thus it is extremely important to distinguish between causes and symptoms to predict the consequences of actions.
Inventory Management
Causal networks
Marketing Optimization
Risk (Applications in Supply Chains, Contracts, etc.)
Accomodation
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
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" and its web-site is: www.debarcadere.ch Price for a single room around CHF 170.- (special price for EPFL hosts)
If you come by car: 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)
Relevant linksUniversities
IBM
RegistrationThere 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
No more inscriptions.