SOURCE-SINK FLOWS WITH CAPACITY INSTALLATION IN BATCHES

We consider the problem of sending flow from a source to a destination where there are flow costs on each are and fixed costs toward the pur chase of capacity. Capacity can be purchased in batches of C units on each are. We show the problem to be NP-hard in general. If d is the qu antity to be shipped from the source to the destination, we give an al gorithm that solves the problem in time polynomial in the size of the graph but exponential in [d/C]. Thus, for bounded values of [d/C] the problem can be solved in polynomial time. This is useful since a simpl e heuristic gives a very good approximation of the optimal solution fo r large values of [d/C]. We also show a similar result to hold for the case when there are no flow costs but capacity can be purchased eithe r in batches of 1 unit or C units. The results characterizing optimal solutions with a minimum number of free arcs are used to obtain extend ed formulations in each of the two cases. The LP-relaxations of the ex tended formulations are shown to be stronger than the natural formulat ions considered by earlier authors, even with a family of strong valid inequalities added. (C) 1998 Elsevier Science B.V. All rights reserve d.