EconPapers    
Economics at your fingertips  
 

Source Sink Flows with Capacity Installation in Batches

Itzhak Gilboa, Sunil Chopra and S. Trilochan Sastri
Additional contact information
Sunil Chopra: Kellogg [Northwestern] - Kellogg School of Management [Northwestern University, Evanston] - Northwestern University [Evanston]

Post-Print from HAL

Abstract: 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 [d / C]. Thus, for bounded values of [d / C] 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 [d / C]. 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.

Keywords: min cost flow; Integer programming (search for similar items in EconPapers)
Date: 1998-07
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Published in Discrete Applied Mathematics, 1998, vol. 85, issue 3, pp. 165-192. ⟨10.1016/S0166-218X(98)00024-9⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-00753123

DOI: 10.1016/S0166-218X(98)00024-9

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().

 
Page updated 2025-03-22
Handle: RePEc:hal:journl:hal-00753123