Duality Approaches to Economic Lot-Sizing Games

Abstract

We consider the economic lot-sizing (ELS) game with general concave ordering cost. In this cooperative game, multiple retailers form a coalition by placing joint orders to a single supplier in order to reduce ordering cost. When both the inventory holding cost and backlogging cost are linear functions, it can be shown that the core of this game is non-empty. The main contribution of this paper is to show that a core allocation can be computed in polynomial time. Our approach is based on linear programming (LP) duality and is motivated by the work of Owen [19]. We suggest an integer programming formulation for the ELS problem and show that its LP relaxation admits zero integrality gap, which makes it possible to analyze the ELS game by using LP duality. We show that, there exists an optimal dual solution that defines an allocation in the core. An interesting feature of our approach is that it is not necessarily true that every optimal dual solution defines a core allocation. This is in contrast to the duality approach for other known cooperative games in the literature.