### 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 language | English (US) |
---|---|

Pages (from-to) | 484-498 |

Number of pages | 15 |

Journal | IISE Transactions |

Volume | 50 |

Issue number | 6 |

DOIs | |

State | Published - Jun 3 2018 |

Externally published | Yes |

### Keywords

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

### ASJC Scopus subject areas

- Industrial and Manufacturing Engineering