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

Robert M. Curry, J. Cole Smith

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)484-498
Number of pages15
JournalIISE Transactions
Volume50
Issue number6
DOIs
StatePublished - Jun 3 2018
Externally publishedYes

Keywords

  • branch and price
  • maximum flow problem
  • Network optimization
  • semicontinuous variables

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering

Fingerprint Dive into the research topics of 'Models and algorithms for maximum flow problems having semicontinuous path flow constraints'. Together they form a unique fingerprint.

  • Cite this