Dynamic evolution of economically preferred facilities

In a sustained development scenario, it is often the case that an investment is to be made over time in facilities that generate benefits. The benefits result from joint synergies between the facilities expressed as positive utilities specific to some subsets of facilities. As incremental budgets to finance fixed facility costs become available over time, additional facilities can be opened. The question is which facilities should be opened in order to guarantee that the overall benefit return over time is on the highest possible trajectory. This problem is common in situations such as ramping up a communication or transportation network where the facilities are hubs or service stations, or when introducing new technologies such as alternative fuels for cars and the facilities are fueling stations, or when expanding the production capacity with new machines, or when facilities are functions in a developing organization that is forced to make choices of where to invest limited funding. An intuitive strategy frequently used to evolve the set of facilities is a greedy approach that picks additional facilities which provide a highest rate of return on each budget increment. Such strategy is shown to have adverse impact by locking the system into future suboptimal solutions with total benefit that can be arbitrarily small compared to the optimal evolution sequence. It is shown here that the degree of suboptimality of such greedy strategy is extreme in that it can lead to the loss of the majority of future benefits. The main result here is the generation of the entire efficient frontier of optimal solution sets for different budget levels. This frontier contains information that guides the schedule of the optimal evolution of the set of facilities in future expansions. It is demonstrated that the efficient frontier forms a concave envelope, and the configurations on the frontier's breakpoints are nested. The efficient frontier is generated by efficient and strongly polynomial algorithms. For n potential facility locations and for subsets of positive benefits of total size m we find the breakpoints of the efficient frontier using a parametric minimum cut procedure in time , and all N configurations on the efficient frontier in time O(mn log n + N).