| The main decisions concerning the development of an offshore oil and/or gas field are: (1) how many, what types, and what sizes of production facilities should be used in the development of the field, (2) where should those facilities be located, and (3) how should a given number of wells among several candidate well sites be assigned to the selected facilities. Such a problem is known as the "offshore location-allocation problem" and is formulated here as a pure 0-1 integer programming model in which the objective is to minimize investments for the development of the field. A tree search procedure to find the optimal solution to this problem is developed. The most important elements of this procedure are the methods to find lower and upper bounds, a node simplification procedure, and a two-level branch and bound tree.;A lower bound is found by solving a Lagrangean relaxation of the original problem. The values for the multipliers in this relaxation are found by a dual ascent procedure. This bound is then tightened by adding a Benders inequality generated from model data. An upper bound is generated by constructing a feasible solution to the problem using the solution to the Lagrangean problem. The node simplification procedure is simply a dominance rule for fixing "free" location variables based on a lower bound for the cost savings associated with such decisions. These mechanisms were embedded in a two-level branch and bound tree. In the first level, the search is concentrated on the facility location decisions; whereas, in the second level, the search is conducted on the well assignment decisions.;Ten different examples, all with real data, were used to test the overall methodology. Duality gaps associated with the initial lower bounds and execution times appear to be remarkably small for the size and complexity of the examples. This methodology was compared with a state-of-the-art code specially designed for zero-one integer programming. Computational results indicate that the proposed methodology outperforms the other one, not only in execution time, but also in memory required. |
