Models and algorithms for maximum flow problems having semicontinuous path flow constraints

Robert M. Curry and J. Cole Smith

IISE Transactions, 2018, vol. 50, issue 6, 484-498

Abstract: This article considers a variation of the node- and arc-capacitated maximum flow problem having semicontinuous flow restrictions. A semicontinuous variable must either take a value of zero or belong in the interval [ℓ, u] for some 0 < ℓ ⩽ u. Of particular interest are problems in which the variables correspond to the amount of flow sent along an entire origin–destination path. We examine both static and dynamic variations of this problem. As opposed to solving a Mixed-Integer Programming (MIP) model, we propose a branch-and-price algorithm for the static version of this problem, including a specialized branching strategy that leverages the existence of cut-sets in a non-feasible solution. For the dynamic version of the problem, we present an exact MIP formulation along with a set of symmetry-breaking and subtour-elimination constraints to improve its solvability. We demonstrate the efficacy of our algorithms on a set of randomly generated test instances.

Date: 2018
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/24725854.2017.1415491 (text/html)
Access to full text is restricted to subscribers.

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:taf:uiiexx:v:50:y:2018:i:6:p:484-498

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/24725854.2017.1415491

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().