Presentations

Michel Baes
Mirror-Descent Methods for Mixed-Integer Convex Problems
We study an algorithmic approach to this problem, postponing its hardness to the realization of an oracle. If this oracle can be realized in polynomial time, the problem can be solved in polynomial time as well. For problems with two integer variables, we show with a novel geometric construction how to implemented the oracle efficiently, that is, in O(ln(B)) approximate minimizations of f over the continuous variables, where B is a known bound on the absolute value of the integer variables. If times permits, we will show a few interesting extensions of our approach.

Stefan Woerner
Optimal Capacity and Safety Stock Allocation for Assembly Systems
Problems in supply chain management are usually classified according to their planning horizon as strategical, tactical, or operational. A common approach is to consider each class independently under simplifying assumptions about the other classes. This can obviously lead to suboptimal decisions since they do not exploit possible synergies.
Here we study the joint problem of optimal capacity and safety stock allocation, thus combining tactical and operational decisions. We consider assembly systems with base stock policies, periodic review, and capacity constraints. Multiple assembly systems can be connected via budget constraints for capacity allocation. Our objective is to minimize holding costs while satisfying beta-service level constraints for end items and joint budget constraints for capacity allocation. The assembly systems are evaluated via simulation.
We present an algorithm to approximate the jointly optimal capacity allocation and reorder points. To this end we introduce a set of convex approximations for the non-convex optimization problem and show how sample path derivatives can be computed analytically via infinitesimal perturbation analysis. The derivatives are used to compute the optimal solution of the convex approximations. By iteratively adapting the approximations of the problem we achieve good reorder points for the original problem. We demonstrate our approach on problem instances motivated by the semiconductor manufacturing network of IBM Microelectronics Division.

Simon Thevenin
Hybrid meta-heuristics for an order acceptance and scheduling problem with discretely controllable release dates
We are interested in the problem which consists in scheduling n jobs on a single machine with rejections and setup times. The objective is to minimize the sum of setup costs, rejection penalties, earliness penalties and tardiness penalties. In the order acceptance and scheduling problem, the manufacturer is allowed to cancel some orders if a rejection penalty is paid. It is particularly relevant in make to order production systems, which are often adopted by manufacturers of highly customizable goods. Indeed, in such a situation, it may be hard to process all received orders on time, and it makes sense to reject some of them to decrease the tardiness. We address here such a problem with controllable release dates, that is, release dates can be reduced if some earliness penalties are paid. The problem is NP hard, and we compare different heuristics to tackle it: a tabu search, a genetic algorithm and different ant methods.

Matteo Salani
Minimize time windows violation in routing problems
Automated route planning algorithms support decision makers in designing efficient and effective delivery plans. Anyway, in practical applications, the fulfillment of constraints is not as rigorous as in mathematical models. Human planners are able to elaborate solutions that violate some of the constraints in case this has a potential to result in a clear benefit.
Here, we propose an alternative model to deal with constraint violation. Fundamentally, it is an adaptation of the epsilon method for multi-criteria optimization which operates in the infeasible solution space (Cost;Violation). An advantage of the proposed model is that it does not over-burden the decision maker with an excessive number of parameters. To obtain an optimal solution of the presented model, we propose a non-trivial implementation of a branch-and-cut-and-price procedure. Furthermore, we introduce and discuss a novel embedded relaxation procedure which is efficiently used to identify unfeasible nodes of the search tree. A computational experience over a set of 120 instances is presented and optimal results on all instances are reported.

Nihat Engin Toklu
A Robust Multiple Ant Colony System Approach for Solving the Capacitated Vehicle Routing Problem with Uncertain Travel Costs (joint work with R. Montemanni and L.M. Gambardella)
Capacitated vehicle routing problem is a well-known problem in the field of transportation. According to this problem, there is a depot, where a certain product is stored; and there are customers at various locations, who wait for the deliveries of the various amounts of this product to them. The goal is to find the optimal (i.e. cheapest in terms of travel costs) routes for the available vehicles so that all of the delivery demands will be satisfied, without violating the product carrying capacity of any vehicle. In addition, we consider that there is uncertainty in travel costs. The uncertainty here represents the fact that it might not be possible to know the exact values of the travel costs because of difficult-to-predict factors like traffic jams, unfriendly weather conditions, etc. To solve this problem, we propose a multi-process metaheuristic approach: robust multiple ant colony system (RMACS). In RMACS, the robust optimization methodology of Bertsimas & Sim is used for handling the uncertainty. The RMACS approach simulates multiple ant colonies in parallel to solve the problem, each ant colony focusing on a different level of protection against the uncertainty. The colonies also share their solutions in runtime, so that no colony will propose a dominated solution. The results show that the concurrency and solution-sharing increase the quality of the generated solution pools.

Bilge Atasoy
Analysis of an itinerary-based airline fleet assignment model with passenger-choice driven recapture and pricing
There is an increasing interest for the integration of supply-demand interactions in airline schedule planning models. We work with an itinerary-based fleet assignment model where an itinerary choice model is explicitly integrated. The choice model represents the decision on pricing as well as the spill and recapture effects. We present a sensitivity analysis for the key assumptions of the demand model in order to quantify the added value of choice-based fleet assignment compared to leg-based fleet assignment. The model is solved with a local search heuristic which iterates over two sub-problems. We present a transformation of the problem which results with a convex formulation and is expected to increase the efficiency of the solution methodologies.

Jean Respen
Benchmark algorithms for a realistic loading problem
To deliver goods to car factories, the car manufacturer Renault is daily facing a complex truck loading problem where various goods must be packed into a truck such that they fulfill different constraints. As trucks can deliver goods to different factories on the same tour, classes of items have been defined, where a class is associated with a delivery point. As the number of items and the standard deviation of the sizes of the items are significant, no exact algorithm is competitive. We propose four local search methods, namely four tabu search algorithms. Results show that tabu search is competitive compared to the greedy heuristics developed by Renault.