Gautier Stauffer, IBM Research Lab, Ruschlikon, Switzerland.

Wednesday, March 4, 14h30

In 1985 Roundy developed an approximate solution to the inventory control of a simple distribution system consisting of one warehouse and multiple retailers, where the retailers face continuous demands with constant rates. While his approach can be implemented efficiently and is guaranteed to be within 2% of optimality, the corresponding centralized solution lacks a simple analytical form that would allow practitioners to grasp the dynamics of the model under changes in the input. Moreover, in practice, for ease of implementation and/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. We will present in this talk a simple heuristic solution to this problem that is based on the application of the classical EOQ formula at each location and thus mimics a decentralized decision mechanism where each location behaves selfishly. The advantage of this simple solution is twofold: because it is based on the classical EOQ formula, it is very intuitive for practitioners and it is also straightforward to anticipate the effects of parameter changes; moreover, it is provably “close” to optimal (within 6% in average and within 27.5% in the worst case). Last but not least, since this heuristic mimics the common practice of decentralized decision making, our result proves that the price of anarchy (i.e. the optimality gap for selfish behavior) for this system is at most 1.275 (which is almost tight) and appears to be much better in average.

During this presentation I will also dedicate some time to talk about my other research activities concerning the stable set problem in claw-free graphs, since it might be of particular interest to the applied mathematics community at the Université of Bordeaux. In particular, I will mention two of my most important contributions in this area: the solution to Ben Rebea’s long-standing conjecture for the stable set polytope of quasi-line graphs, and a new algorithm for the weighted stable set problem in claw-free graphs (which generalizes previous results of Lóvasz and others).