Show simple item record

dc.contributor.authorHaugland, Dag
dc.description.abstractThe pooling problem is a frequently studied extension of the traditional minimum cost flow problem, in which the composition of the flow is subject to restrictions. In a network consisting of three layers of nodes, the composition is given at the source layer. In the intermediate nodes, referred to as pools, the composition is a weighted average of the compositions in entering flow streams. The same is true at the sink layer, where upper bounds on the concentration of each component apply. Motivated by practical applications, and needs for heuristic methods for the standard pooling problem, the current work focuses on pooling problems where the flow graph is restricted to satisfy certain sparsity conditions. We consider in particular the requirements that each pool receives flow from at most one neighboring source, or sends flow to at most one neighboring sink. We prove that the pooling problem remains NP-hard after this and other similar extensions. It is also demonstrated how the single-flow constrained extensions can be modeled by means of mixed integer linear programming (MILP), without introducing bilinear terms. We also show that such MILP-models are useful for computing good feasible solutions to the original problem.en_US
dc.relation.ispartofProceedings of the 9th International Network Optimization Conference, INOC 2019
dc.rightsAttribution-NonCommercial-NoDerivs CC BY-NC-NDeng
dc.titlePooling Problems with Single-Flow Constraintsen_US
dc.typePeer reviewed
dc.rights.holderCopyright 2019 The Author(s)en_US
dc.identifier.citationIn: Darties, Poss M. Proceedings of the 9th International Network Optimization Conference, INOC 2019, 2019., 95-100

Files in this item


This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs CC BY-NC-ND
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs CC BY-NC-ND