Show simple item record

dc.contributor.authorChopra S.
dc.contributor.authorGilboa I.
dc.contributor.authorTrilochan Sastry S.
dc.date.accessioned2022-02-11T10:15:41Z
dc.date.available2022-02-11T10:15:41Z
dc.date.issued1998
dc.identifier.citationChopra, S., Gilboa, I., & Trilochan Sastry, S. (1998). Source sink flows with capacity installation in batches. Discrete Applied Mathematics, 85(3). https://doi.org/10.1016/S0166-218X(98)00024-9
dc.identifier.issn0166218X
dc.identifier.urihttps://www.doi.org/10.1016/S0166-218X(98)00024-9
dc.identifier.urihttp://hdl.handle.net/11718/25349
dc.description.abstractWe 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. � 1998 Elsevier Science B.V. All rights reserved.
dc.language.isoen_US
dc.publisherElsevier
dc.relation.ispartofDiscrete Applied Mathematics
dc.subjectInteger programming
dc.subjectMin cost flow
dc.titleSource sink flows with capacity installation in batches
dc.typeArticle
dc.rights.licenseCC BY-NC-ND
dc.contributor.affiliationJ.L. Kellogg Grad. Sch. of Mgmt., Northwestern University, Leverone Hall, 2001 Sheridan Road, Evanston, IL 60208-2001, United States
dc.contributor.affiliationIndian Institute of Management, Ahmedabad, India
dc.contributor.institutionauthorChopra, S., J.L. Kellogg Grad. Sch. of Mgmt., Northwestern University, Leverone Hall, 2001 Sheridan Road, Evanston, IL 60208-2001, United States
dc.contributor.institutionauthorGilboa, I., J.L. Kellogg Grad. Sch. of Mgmt., Northwestern University, Leverone Hall, 2001 Sheridan Road, Evanston, IL 60208-2001, United States
dc.contributor.institutionauthorTrilochan Sastry, S., Indian Institute of Management, Ahmedabad, India
dc.description.scopusid7202868637
dc.description.scopusid7004331788
dc.description.scopusid6504122281
dc.identifier.doi10.1016/S0166-218X(98)00024-9
dc.identifier.endpage192
dc.identifier.startpage165
dc.identifier.issue3
dc.identifier.volume85


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record