Multistage Benders' Decomposition applied to Multiperiod, Multicommodity Production, Distribution and Inventory System

Tone, K. (1979). Multistage Benders' Decomposition applied to Multiperiod, Multicommodity Production, Distribution and Inventory System. IIASA Working Paper. IIASA, Laxenburg, Austria: WP-79-045

Preview

Text WP-79-045.pdf Download (222kB) | Preview

Abstract

It has become more and more important for some industries to have an efficient program for their long range activities. Such a program usually means a production, distribution, and inventory plan of multicommodity over a multiperiod range. The network flow model is a standard way to represent the problem. Recent advances in the computational aspect of the generalized network (Glover et al. 1978:24, 1209-1220) gives us an indication of broader areas of application. However, the real world imposes complicated constraints upon us which can not be represented in the network models, not even in generalized network models.

In a previous paper (Tone 1977a:20, 77-93), the author tried a decomposition of network type constraints and nonnetwork type constraints (called pattern constraints) by using Benders' partitioning procedure (Benders 1962:4, 238-252). The computational experiments show that the decomposition technique works well.

In this paper, the author develops a method to handle the multiperiod problem, where the problems in each period are coupled with the succeeding one by the existence of the inventory activities. Our system is doubly decomposable; by the existence of the pattern constraints and by inventory activities. The algorithm consists of two parts, one for solving the network flow problem in each period and the other for solving the pattern and coupling constraints which may be called a master problem. Finite convergence is guaranteed.

Actions (login required)

View Item