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

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.