Experiences in Using a Decomposition Program

The problem concerned the production of oil from several different fields to meet a fixed overall target over a finite span of years. Typically we were concerned with seven different fields supplying three outlets (ports or refineries) over a span of twelve years. The problem was formulated as a linear program, the object being to meet the overall target and to maximize an expression representing the net profit over the time span being considered. It naturally decomposed into sub-problems because the linking equations between the various fields were quite few in number. Dantzig and Wolfe's Decomposition principle shows how to take advantage of the special structure of linear programming problems that can be considered as separate sub-problems with a relatively small number of linking equations. (Dantzig and Wolfe (1960), Dantzig and Wolfe (1961) and Dantzig (1963)). The linking equations are grouped together into what is known as the master problem, whilst each sub-problem contains the constraints and equations that can naturally be grouped together. In this problem the operations of each field under consideration were expressed in separate sub-problems. The constraints in the sub-problems deal with the construction of new production facilities in each of the years being considered. These facilities include new oil wells, and also plant such as gas/oil separators which are required to handle the oil once it has reached the surface. There are also equations representing the productive capacity of both existing and new wells, and constraints on the upper limits of the capacity of the field. A solution to a sub-problem is a way of operating a field, i.e. a set of annual productions with the corresponding investments required to make the productions possible. The master problem consists of the linking equations dealing with the supply of oil from the fields to the outlets. It also deals with the possibility of exploring for new oilfields. And, of course, it contains the main supply equations which say that the sum of productions from all the fields in any year must equal the overall target for that year.