English only



Information
The 2010 Seminar of the "3ème cycle romand de Recherche Opérationnelle" will take place from Sunday January 17 to Thursday January 21 at hôtel de l'Europe, in Zinal, VS (directions). Organization: Michel Bierlaire Registration deadline: November 30, 2009. Today is June 29, 2010. Sorry, the deadline for registration is over. Lecturers
Tentative schedule
Registration
Sorry, the deadline for registration is over. Current number of registered participants: 46
Presentations
Presentations by PhD students will be organized. We use a purely combinatorial argument to show that simple principal pivot methods applied to linear complementarity problems with Kmatrices converge very quickly. The proof is conducted in the setting of oriented matroids. Joint work with Jan Foniok and Komei Fukuda. The huge development of communication facilities leads us to consider the vehicle routing and scheduling problem in a realtime fashion, where customer’s requests can be inserted to the currently planned routes as soon as they appear. We propose a heuristic solution method to manage the routes of a given vehicle fleet, while considering dynamic travel times. In such a context, the notion of diversion is a crucial issue. We study the kedgeconnected spanning subgraph problem in network design, e.g. connecting all vertices in a way that is resilient against k1 edge failures. Gabow, Goemans, Tardos & Williamson gave an elegant and simple LPbased algorithm for this problem with approximation ratio 1+2/k for unit costs. We show that the case of arbitrary costs behaves differently: for some fixed C > 1, and every k > 1, it is NPhard to approximate the problem better than C. For the multisubgraph version  where edges can be purchased arbitrarily many times  we conjecture a 1+constant/k approximation based on LPs. The natural LP coincides (up to scaling) with the HeldKarp TSP relaxation, and for this LP we give a new intricate extreme point family with exponentially small values and maximum degree V/2. Based on the paradigm “learning by doing” the environment, ATAG (Apprentissage de la théorie algorithmique des graphes) is intended to facilitate the teaching and training of the algorithmic graph theory. ATAG provides a userfriendly interface allowing editing, storing and retrieving of graphs together with the execution of various algorithms written in the script language “groovy”. Thus, ATAG contains several main tools such as: graph editing interface, script launcher, script debugger and command console. By simplifying the editing and handling of graphs, ATAG allows students to focus on the programming and the testing of algorithms. Moreover, the graphical facilities of ATAG are of great help for teaching and illustrating the behavior of various algorithms of the graph theory. The capabilities of ATAG are demonstrated by several relevant examples concerning some classic algorithms. Different kinds of products have to be delivered by silo trucks to several customers. Due to the trucks capacity, each order is split into one or more deliveries, which are supplied from a main depot (the factory) or sometimes from local depots located in railways stations. In order to solve this problem, various simple and complex constraints have to be satisfied. For example, drivers’ capabilities and availability need to be taken into account, trucks can only deliver some customers and can eventually be preloaded the previous day, the journey of each truck starts and ends at the factory, only trucks with filter can be fulfilled in railways stations. To reach the objective imposed by the company, which is to define a vehicle routing such that the number of different trucks supplying each individual customer is minimized, the problem is decomposed into three subproblems: 1) allocation of customers to a specific depot, 2) allocation of deliveries to trucks, 3) sequencing the deliveries per truck. These subproblems, modeled and solved with help of mixed integer linear programming, will be presented. The Discrete Split Delivery Vehicle Routing Problem with Time Windows (DSDVRPTW) consists of designing the optimal set of routes to serve, at least cost, a given set of customers while respecting constraints on vehicles’ capacity and customer time windows. The delivery request of a customer consists of several discrete items which cannot be split further. The problem belongs to the class of split delivery problems since each customer’s demand can be split in orders, i.e. feasible combinations of items, and each customer can be visited by more than one vehicle. In this work, we model the DSDVRPTW as a mixed integer linear program, assuming that all feasible orders are known in advance and that each vehicle can serve at most one order per customer. Remarkably, service time at customer’s location depends on the serviced combination of items, which is a modeling feature rarely found in literature. We present a branchandprice algorithm, analyzing the implications of the classical DantzigWolfe reformulation. Computational results on instances based on Solomon’s data set are discussed. Our concern is to obtain conic approximate tractable solutions of the global cost optimization problem in the electrical industry. Our aim is to take its combinatorial and/or stochastic nature into account. Two applications are investigated. The first is a hydro short term problem with numerous binary and quadratic constraints. It is reformulated using semidefinite programming. The second application is a mid term power system facing uncertainties. For this problem, an approximate conic programming setting is obtained, when using a probability measure on the offerdemand equilibrium at each time step. Solutions of such conic quadratic and semidefinite problems are solved using interior point methods. Typical results obtained with these approaches are reported. 