On the optimum capacity of capacity expansion problems
In this paper we consider problems of the following type: Let E = { e <Subscript>1</Subscript>, e <Subscript>2</Subscript>,..., e <Subscript> n </Subscript> } be a finite set and <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$${\mathcal {F}}$$</EquationSource> </InlineEquation> be a family of subsets of E. For each element e <Subscript> i </Subscript> in E, c <Subscript> i </Subscript> is a given capacity and <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$${\mathcal {w}}$$</EquationSource> </InlineEquation> <Subscript> i </Subscript> is the cost of increasing capacity c <Subscript> i </Subscript> by one unit. It is assumed that we can expand the capacity of each element in E so that the capacity of family <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$${\mathcal {F}}$$</EquationSource> </InlineEquation> can be expanded to a level r. For each r, let f (r) be the efficient function with respect to the capacity r of family <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$${\mathcal {F}}$$</EquationSource> </InlineEquation> , and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$${\phi(r)}$$</EquationSource> </InlineEquation> be the cost function for expanding the capacity of family <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$${\mathcal {F}}$$</EquationSource> </InlineEquation> to r. The goal is to find the optimum capacity value r <Superscript>*</Superscript> and the corresponding expansion strategy so that the pure efficency function <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$${f(r^*)-\phi(r^*)}$$</EquationSource> </InlineEquation> is the largest. Firstly, we show that this problem can be solved efficiently by figuring out a series of bottleneck capacity expansion problem defined by paper (Yang and Chen, Acta Math Sci 22:207–212, 2002) if f (r) is a piecewise linear function. Then we consider two variations and prove that these problems can be solved in polynomial time under some conditions. Finally the optimum capacity for maximum flow expansion problem is discussed. We tackle it by constructing an auxiliary network and transforming the problem into a maximum cost circulation problem on the auxiliary network. Copyright Springer-Verlag 2007