×

Source sink flows with capacity installation in batches. (English) Zbl 0908.90117

Summary: We consider the problem of sending flow from a source to a destination where there are flow costs on each arc and fixed costs toward the purchase of capacity. Capacity can be purchased in batches of \(C\) units on each arc. We show the problem to be NP-hard in general. If \(d\) is the quantity to be shipped from the source to the destination, we give an algorithm that solves the problem in time polynomial in the size of the graph but exponential in \(\lfloor d/C\rfloor\). Thus, for bounded values of \(\lfloor d/C\rfloor\) the problem can be solved in polynomial time. This is useful since a simple heuristic gives a very good approximation of the optimal solution for large values of \(\lfloor d/C\rfloor\). We also show a similar result to hold for the case when there are no flow costs but capacity can be purchased either in batches of 1 unit or \(C\) units. The results characterizing optimal solutions with a minimum number of free arcs are used to obtain extended formulations in each of the two cases. The LP-relaxations of the extended formulations are shown to be stronger than the natural formulations considered by earlier authors, even with a family of strong valid inequalities added.

MSC:

90B10 Deterministic network models in operations research
90C10 Integer programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows: Theory, Algorithms, and Applications (1993), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 1201.90001
[2] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), North-Holland: North-Holland Amsterdam · Zbl 1134.05001
[3] D. Bienstock, S. Chopra, O. Günlük, C. Y. Tsai, Minimum cost capacity installation for multicommodity network flows, Math. Programming 81, 177-199.; D. Bienstock, S. Chopra, O. Günlük, C. Y. Tsai, Minimum cost capacity installation for multicommodity network flows, Math. Programming 81, 177-199. · Zbl 0922.90064
[4] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W. H. Freeman and Company: W. H. Freeman and Company New York · Zbl 0411.68039
[5] J. M. Y. Leung, T. L. Magnanti, R. Vachani, Facets and algorithms for capacitated lot sizing, Math. Programming 45, 331-359.; J. M. Y. Leung, T. L. Magnanti, R. Vachani, Facets and algorithms for capacitated lot sizing, Math. Programming 45, 331-359. · Zbl 0681.90060
[6] Magnanti, T. L.; Mirchandani, P., Shortest paths, single origin-destination network design and associated polyhedra, Networks, 23, 2, 103-121 (1993) · Zbl 0791.90064
[7] Magnanti, T. L.; Mirchandani, P.; Vachani, R., Modeling and solving the two facility capacitated network loading problem, Oper. Res., 43, 1, 142-157 (1995) · Zbl 0830.90051
[8] Pochet, Y.; Wolsey, L. A., Lot sizing with constant batches: Formulation and valid inequalities, Math. Oper. Res., 18, 767-785 (1993) · Zbl 0808.90058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.