(74f) Cascading Knapsack Inequalities: Hidden Structure in Some Inventory-Production-Distribution Problems

In the last decade Mixed-Integer Programming solvers have evolved enormously contributing to the widespread application of optimization in real world problems in industry. Nonetheless, it is paramount for practitioners to have basic knowledge on how these solvers work and to be able to identify model structures, so one can take full advantage of the machinery at hand. In this paper we present a reformulation to a simple problem that appears as sub-problem in many supply chain models, and we show the advantage of using suitable mathematical structures in the form of cascading knapsack inequalities to solve it. Moreover, we introduce new reformulations to some special cases, producing tighter linear relaxation and faster solution times.

Specifically, in this paper we present and test reformulations to an inventory-production distribution problem that arises frequently as a subproblem in supply chain optimization models namely, the inventory-production-distribution problem (Lejeune and Margot, 2008; Chen, 2003; Chandra and Fisher, 1994). A company has several industrial plants producing parts that are shipped to its distribution centers to supply its customers. The production of parts per time period is known. The company wants to determine the best shipment schedule in order to satisfy the customer demands and avoid inventory shortfalls at the industrial plants, as well as at the distribution centers in the planning horizon. The customer demands are known in advance, and due to the company shipping policy the trucks must be loaded to full capacity. Additionally, we assume that the number of shipments per time period between each pair of plant-distribution center is limited to at most one, and that the number of trucks in each type of truck is unlimited.

We show that through an inventory reformulation in the above problem, the special structure of Cascading Knapsack Inequalities, hidden in the initial formulation, is identified. This structure is of great value as the knapsack inequalities have been studied since the beginning of the integer programming area (Parsons, 1969; Guignard and K., 1972; Balas, 1975) and nowadays all solvers have implemented very sophisticated techniques to exploit such structures (Atamturk and Savelsbergh, 2005; Ashford, 2007; Bixby and Rothberg, 2007). Besides, the cascading form allows us to derive tighter reformulations for some special cases. This in turn allows us to use an off-the-shelf MIP solver to solve instances that were out of reach by the Initial Model. Furthermore, capitalizing on this special structure, we propose tighter reformulations for some special cases of this problem, reducing further the solution times for a great number of instances. A main lesson of this work is that although we have nowadays sophisticated MIP solvers capable of solving problems never envisaged before, it is still paramount for the users of MIP solvers to have an understanding not only on the modeling but also on how the MIP solvers work if they are to be able to solve more challenging problems.

References

Ashford, R. 2007. Mixed integer programming: A historical perspective with xpress-mp. Annals Operations Research 149, 5 ?17.

Atamturk, A., M. Savelsbergh. 2005. Integer-programming software systems. Annals of Operations Research 140, 67?124.

Balas, E. 1975. Facets of Knapsack Polytope. Mathematical Programming 8, 146 ?164.

Bixby, R., E. Rothberg. 2007. Progress in computational mixed integer programming ? a look back from the other side of the tipping point. Annals of Operations Research 149, 37? 41.

Guignard, M. M., Spielberg K. 1972. Mixed-Integer Algorithms for (0,1) Knapsack Problem. IBM Journal of Research and Development 16, 424 ? 430.

Parsons, J. A. 1969. Branch and Bound Algorithms - Knapsack Problem. Journal of Systems Management 20, 35?37.