Vis enkel innførsel

dc.contributor.authorHaugland, Dag
dc.PublishedHaugland D: Pooling Problems with Single-Flow Constraints. In: Darties, Poss M. Network Optimization INOC 2019 9th International Network Optimization Conference, 2019. p. 95-100eng
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.rightsAttribution-NonCommercial-NoDerivs CC BY-NC-NDeng
dc.titlePooling Problems with Single-Flow Constraintsen_US
dc.typeConference object
dc.typePeer reviewed
dc.rights.holderCopyright 2019 The Author(s)en_US

Tilhørende fil(er)


Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel

Attribution-NonCommercial-NoDerivs CC BY-NC-ND
Med mindre annet er angitt, så er denne innførselen lisensiert som Attribution-NonCommercial-NoDerivs CC BY-NC-ND