Selection of capacity expansion projects

The problem of determining a project slection schedule and a production-distribution-inventory schedule for each of a number of plants so as to meet the demands of multiregional markets at minimum discounted total cost during a discrete finite planning horizon is considered. The paper includes the possibility of using inventory and/or imports to delay the expansion decision at each producing region in a transportation network. Through a problem reduction algorithm, the Lagrangean relaxation problem strengthened by the addition of a surrogate constraint becomes a 0-1 mixed integer knapsack problem. Its optimal solution, given a set of Lagrangean multipliers, can be obtained by solving at most two generally smaller 0-1 pure integer knapsack problems. The bound is usually very tight. At each iteration of the subgradient method, the authors generate a primal feasible solution from the Lagrangean solution. The computational results indicate that the procedure is effective in solving large problems to within acceptable error tolerances.