Dynamic evolution of economically preferred facilities

Abstract

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 $\mathrm{O}(\mathit{nm}\log \frac{n^2}{m})$, and all N configurations on the efficient frontier in time O(mn log n + N).

Introduction

The problem studied here is encountered in the development of a facility system where funds for opening facilities become available over time. Potential facilities manifest networking effect in the form of joint synergies expressed as positive benefits for some subsets of facilities. As incremental budgets to finance fixed facility costs become available, additional facilities can be opened and the overall benefit from the system grows. The problem is to determine which facilities should be opened in order to guarantee that the overall return over time is on the highest possible trajectory. This problem is common in situations such as ramping up a communication of 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 in a newly evolving 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 selects facilities to open as those that provide a highest rate of return on each budget increment. The determination of the set of facilities to be added subject to a fixed budget on the total facility costs is referred to as the maximum benefit problem with the goal of maximizing the utility, or benefit, of connections between all facilities in the set and subject to the limited budget constraint. The maximum benefit problem is NP-hard as it is equivalent to several well studied NP-hard problems including the problems of finding a maximum clique in a graph, and finding densest k-subgraph.

Witzgall and Saunders (1988) were the first to address the problem of evolving a set of facilities in a project of deciding on the locations of electronic mail facilities for the postal service during the 1980s. In that project, there is a positive benefit for each pair of facilities, and with added number of facilities the utility for all participants increases. This is similar to the effect of having a larger number of users connected to a telephone network increasing the utility for all users, at a quadratic rate in the number of users, as each of them can communicate with all users already on the network.

Beyond the objective of finding the best configuration of facilities for each given budget we are interested in the practical question of how to evolve the facility configurations over time, adding facilities as additional budget becomes available. Once a facility has been included, its fixed cost cannot be recouped by closing the facility, and therefore an open facility remains open for the entire planning horizon. Consequently, each selected set of facilities for a given budget is required to contain the previously selected set of facilities. We call this property the nestedness property. Our interest is in expanding the set of facilities over time, adding facilities as additional budget becomes available, while maintaining optimal return on investment in the form of maximum benefit-to-cost ratio.

Even if it were possible to compute the maximum benefit facility set for each given budget value, these optimal configurations for increasing budgets are not necessarily nested. Witzgall and Saunders introduced the concept of a preferred configuration. A preferred configuration is defined recursively as follows: a configuration is preferred if its marginal (or incremental) ratio of benefit-to-cost with respect to the previous preferred configuration is at least as great as that of all configurations for equal or greater budgets. To initialize this recursive definition, the empty set of cost 0 and benefit 0 is considered to be the first preferred configuration. The concave curve on which all preferred configurations reside is called the efficient frontier. There are no configurations that have a higher rate of return per unit budget than the efficient frontier configurations. We refer to the problem of finding the efficient frontier and the preferred configurations lying on it as the dynamic evolution problem.

Surprisingly, although evaluating the maximum benefit solution for a given specific budget is an NP-hard problem, computing the entire efficient frontier and the optimal sequence of nested facility sets can be executed in polynomial time.

The structure of the problem of locating electronic mail facilities, studied by Witzgall and Saunders (1988), is commonplace in sustainable development projects. The common thread in these applications is the need to ramp up the infrastructure (of facilities) in order to ensure the impact of the project in terms of sustained and effective benefit level.

• One major hurdle to introducing hydrogen fuel operated cars is the accessibility of refueling stations. Presently the availability of funds for opening refueling facilities is limited, leading to a restricted availability of such facilities, which in turn will inhibit the acceptance of the technology. While it may appear attractive to open those facilities that generate the largest return at a given point in time, this may not be the optimal strategy. There is a synergy between the locations of refueling stations as they determine the range of travel for hydrogen cars. In locating the current network of refueling facilities it is important to understand the benefit structure of those facilities and use an optimal evolution process for the planned growth of the network.

• The problem of evolving a product portfolio over time at Hewlett Packard (HP) has recently been studied by Feng et al. (2004) and reported in Zhang et al. (2005). HP business unit has thousands of active products. This large number has adverse effects in confusing customers and causing high product management costs. Yet, while a small subset of products generate most revenue, there are low revenue products appearing in customers’ orders jointly with high revenue ones. So the low revenue products cannot be removed from the portfolio as they provide benefit in terms of their synergy with high revenue products. The goal is to generate a highest revenue portfolio that does not exceed a prescribed limit on the number of product offerings and that will take into account the joint synergy between products. The efficient frontier in this case provides insight to the trade-offs involved by limiting the number of products in the portfolio. As management capabilities and support systems improve it becomes possible to increase the size of the offering while maintaining good order fulfillment performance. The question is then which products should be added to the portfolio offered, without removing currently offered products (as such removal may adversely affect customer service).

• A global mobile telephone network employs satellites and ground networks as part of its facilities. The key to the success of the system is in exploiting the synergy between the satellite facilities and the existing ground networks. The ability to connect users (telephone, fax), wherever they may be in the world, depends on the availability of ground networks or satellite positioning. With limited resources restricting the purchase of satellite facilities and ground networks, an issue of major concern is how schedule the future evolution of the network and which markets to focus on, so as to provide the best service to markets that guarantee the highest rate of return.

When confronting the problem of adding facilities subject to a given additional budget, the intuitive approach is to add those facilities that contribute most to the benefit of the current configuration. This greedy approach can lead to seriously adverse outcomes in the future, as seen in a simple example illustrated in Fig. 1 below. In this example all subsets that generate positive benefits are pairs of facilities. Therefore the problem can be presented as a graph with nodes as potential facilities, and edges for each pair that can generate positive benefit. The two facilities in the center numbered 1 and 2 have pairwise benefit of value M, where M represents a very large number. Facility 3 adds 1 unit of benefit to the first three. The same added benefit of 1 unit applies when adding facilities 4, … , k in this order, whereas adding any other facility contributes 1 − ϵ at most to any subset of {1, … , k}. (For the purpose of illustration in Fig. 1 k = 5 and n the number of potential facilities is equal to 10.) On the left side, adding any single facility to the first two from the set {k + 1, … , n} contributes 1 − ϵ to the total benefit, where ϵ represents a small positive number. Therefore none of these will be chosen in an effort to maximize the total immediate return whenever an incremental unit of budget is available.

We note that facilities k + 1, … , n form a clique (complete graph) where all pairwise benefits are M − ϵ each. In Fig. 1 these are facilities 6, 7, 8, 9, 10. Choosing these facilities as the first five facilities gives benefit of 10(M − ϵ), whereas maximizing the immediate benefit will lead to the inferior configuration of facilities {1, 2, 3, 4, 5} with total benefit of M + 3. So the latter greedy solution yields total benefit almost 10 times smaller than the benefit generated by following the optimal evolution of the facility configurations. This optimal solution, consisting of the set {6, 7, 8, 9, 10} is the first preferred configuration indicated on the efficient frontier, thus indicating that it is optimal to exclude facilities {1, … , k} for budgets that allow up to n − k facilities. For general value of k the greedy and optimal choices of configurations lead to benefits of M + (k − 2) and $\frac{1}{2}k(k-1)(M-ϵ)$, respectively. The ratio of the total benefit generated for k facilities by using the suboptimal greedy approach to the optimal benefit is then $\mathrm{O}(\frac{1}{k^2})$ resulting in the loss of the majority of the potential benefits.

We note briefly that the ratio of $\mathrm{O}(\frac{1}{k^2})$ achieved by the greedy is also the worst possible among all algorithms that choose to include the highest weight benefit pair. This is easy to see as any graph that has M as the highest benefit of a pair, can have total benefit on a subset of size k not exceeding $M\left(\begin{array}{c}k\hfill \\ 2\hfill \end{array}\right)$.

We formalize the notions of preferred and nested configurations using graph terminology. The input to the problem is a complete undirected hypergraph G = (V, E) where each edge in E, e ⊂ E, and with non-negative edge weight, w_e, corresponding to the respective benefit of subset e, and with non-negative fixed node costs, f_i, i ∈ V. (When each ∣e∣ = 2 then the hypergraph is referred to as graph.) For a subset V_H ⊆ V, let hypergraph H = (V_H, E_H) be the complete (clique) subgraph induced by V_H. The benefit-cost ratio, or the density of H, is defined as $\frac{W(E_H)}{C(V_H)}$ where $C(V_H)={\sum }_{v\in V_H}{f}_v$ and $W(E_H)={\sum }_{e\in E_H}{w}_e$. A commonly considered case is when all node weights are 1. In that case the “cost” represents the number of nodes in the clique and C(V_H) = ∣V_H∣.

For a given budget B, the maximum benefit problem is to determine D(B) = max{W(E_H): C(V_H) ⩽ B}. We call the function D(B) the benefit-budget graph or the density graph, and the ratio $\frac{D(B)}{B}$ is the corresponding density.

The efficient frontier is a concave envelope formed of the intersection of the set of all lines with the property that the density graph resides below the line. For any budget B the point (B, D(B)) lies on or below the concave piecewise linear function which forms the concave envelope of the density graph. A point on the envelope that has left derivative different from a right derivative is called a breakpoint (alternatively, breakpoints lie at the intersection of two line segments of the piecewise linear function.) The points corresponding to feasible configurations on the concave envelope are all preferred configurations.

For integer budgets and unit cost per location all preferred configurations (B, D(B)) satisfy D(B) = max{W(E_H):C(V_H) = B}. This is the case since for any configuration of cost <B there is another configuration of cost B with at least as high total benefit. Fig. 2 depicts a schematic description of a density graph. All points on the concave envelope are preferred configurations, and some of them are breakpoints. In the instance illustrated in Fig. 2, all the points of the density graph are preferred, except for the one corresponding to B = 1.

With the formalism above we define several related problems:

• Maximum benefit problem: Find D(B) for a given B.

• Densest k-subgraph problem: For G a graph, f_i = 1 for all i ∈ V, and w_ij = 1 for all edges [i, j] ∈ E, find D(k) for a given k.

• Maximum clique problem: Given an (incomplete) graph G = (V, E′) set w_ij = 1 for all edges [i, j] ∈ E′ and w_ij = 0 for [i, j] ∉ E′, and let f_i = 1 for all nodes i. The maximum clique problem is to find the largest k so that $D(k)=\left(\begin{array}{c}k\hfill \\ 2\hfill \end{array}\right)$.

• Maximum density subgraph, or densest subgraph: For f_i = 1 for all nodes i ∈ V, find k so that $\frac{D(k)}{k}$ is maximum.

• The dynamic evolution problem: Find the efficient frontier in the form of all preferred configurations and breakpoints.

The maximum benefit problem on a graph and the densest k-subgraph problem are identical except that the maximum benefit problem allows for arbitrary costs f_i. The maximum density subgraph problem does not specify the size of the subhypergraph and is polynomially solvable for graphs (see e.g. Goldberg, 1984) and for hypergraphs. The essence of our results is to demonstrate that the dynamic evolution problem is solvable efficiently and in the same complexity as solving the maximum density subgraph.

The breakpoints on the concave envelope have been used in other contexts previously. Barahona (2000) considered the problem of computing the concave envelope of the values of the minimum k-cut problem in a graph, as a function of k, and Ravi and Sinha (2002) used this concave envelope to get a 2-approximation algorithm for the minimum k-cut problem.

Our contributions here include the generation of the entire efficient frontier in polynomial time. That is, not only the breakpoints of the envelope, but also all configurations that lie on the envelope. Our work generalizes Witzgall and Saunders’ model in several ways. Witzgall and Saunders proved that when all edge weights are positive then the preferred configurations set is identical to the set of breakpoints which are nested, and can be found using a minimum cost network flow algorithm. We extend that in several ways: We allow pairs that have 0 pairwise benefits; we show that the set of preferred configurations contains (possibly strictly) the set of breakpoints; we generalize the subsets that generate benefits from pairs to arbitrary sized subsets; and we show that the breakpoints of the concave envelope of the benefit-budget graph are a set of nested preferred configurations, but there are other preferred configurations that lie on the efficient frontier; finally, we prove that all the breakpoints as well as all other preferred configurations can be enumerated using a parametric minimum cut procedure in polynomial time.

We further prove that the efficient frontier provides a sequence of nested preferred configurations that determines the optimal sequence of facility configurations’ expansion. The efficient frontier also provides useful upper bounds on the optimal value D(k) that can be used in devising approximation algorithms for the NP-hard problem of finding densest k-subgraph, as shown in Hochbaum (2006).

The complexity of our algorithm for finding all the breakpoints on the efficient frontier is $\mathrm{O}(\mathit{mn}\log \frac{n^2}{m})$ where n is the number of potential facility locations, and m is the size of all subsets with positive benefit. The complexity of finding all preferred configurations when there are N such configurations is O(mn log n + N). These are substantial improvements in both applicability and complexity compared to the work of Witzgall and Saunders (1988) who used the out-of-kilter algorithm in their approach.

The paper is organized as follows. In Section 2, we illustrate the concept of preferred configurations demonstrating that not all points (B, D(B)) are preferred, and not all preferred configurations are nested. This section provides further evidence to the failure of the greedy strategy and shows how the generation of the efficient frontier provides an optimal plan. Section 3 discusses the relationship of the dynamic evolution problem to the maximum clique problem, and shows that the efficient frontier may provide almost no information about the size of the maximum clique in the graph if the densest subgraph is the entire graph and n₁ = n. Section 4 contains the main algorithmic result for finding all nested preferred configurations. It describes how to generate the entire efficient frontier with a parametric minimum cut procedure and multiple optima for each cut. Guidelines for the use of the efficient frontier in evolving a facility set are provided in Section 5. Section 6 analyzes the complexity of the algorithm, and Section 7 describes the weighted densest subgraph problem showing that it is the smallest positive budget preferred configuration. We conclude in Section 8 with closing remarks and strategic suggestions for optimal dynamic evolution of a set of facilities.