(A) lagrangian heuristic method for a multifacility capacity expansion model with conversion

Abstract

This thesis describes a multifacility capacity expansion model with conversion. Each facility type is used to satisfy a variety of deterministic demand over a finite number of discrete time periods. An example of the model is the cable sizing problem associated with the planning of communication network. Since the problem is NP-complete, it is time consumptive to find an exact optimum solution using ordinary mixed integer programming algorithm. We decompose the problem with respect to each facility, using the special Lagrangian relaxation technique of introducing integrated variables. The integrated variable is defined as the sum of independent variables. For each facility, the decomposed problem is solved by a dynamic programming method. We develop a heuristic method of constructing a good feasible solution from the solution of relaxed problems. Computational results show that the average tolerance is 2.66\%. Compared with the average tolerances of other problems, it is reasonable. And we successfully solve the realistic problems with large-sizes within reasonable computation times.