A branch-and-bound approach for sequencing expansion projects

The paper examines the problem of finding a sequence of a finite set of expansion projects to meet a deterministic demand projection at minimum discounted cost. As the general problem is NP-complete, it focuses on the case when the demand growth is in the exponential form, which is quite often found in applications of electric power generation, transportation, water resources and communication. The paper finds that projects’ annual costs are an effective ranking criteria for determining an optimal expansion sequence. As the annual cost for a project is a function of time or capacity level, an optimal expansion sequence can be obtained easily if dominance orders of the annual costs exist for all pairwise projects, which is likely to be the case for most practical problems. When the annual costs for the projects are in conditional order, a branch-and-bound algorithm has been developed to effectively reduce the searching range. The present extensive computational results show that the approach is very efficient compared with the other approaches and always solves the problem to optimum although the optimality of the approach still remains to be proven.