A heuristic approach to a class of node-capacitated maximum flow problems

Robert M. Curry, J. Cole Smith

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The node-capacitated maximum flow problem (NCMFP) seeks to determine a set of flows that maximize the total flow from a source s to a terminal t without violating any node- or arc-capacity constraints. The maximum allowable amount of flow on an arc is limited by its capacity. We also assume that each node has a non-negative capacity, and each unit of flow on an arc consumes a positive amount of capacity at the out-going node. Such problems arise in wireless sensor network optimization. Whereas this problem has traditionally been solved as a linear program (LP), we present a heuristic augmenting-flow algorithm that avoids solving any LPs to determine a quality NCMFP solution. Our approach iteratively identifies and augments flows along a combination of cycles and paths. We present computational results for comparing our heuristic with an LP for solving the NCMFP over a set of random test instances and detail future research directions.

Original languageEnglish (US)
Title of host publicationProceedings of the 2020 IISE Annual Conference
EditorsL. Cromarty, R. Shirwaiker, P. Wang
PublisherInstitute of Industrial and Systems Engineers, IISE
Pages890-895
Number of pages6
ISBN (Electronic)9781713827818
StatePublished - 2020
Event2020 Institute of Industrial and Systems Engineers Annual Conference and Expo, IISE 2020 - Virtual, Online, United States
Duration: Nov 1 2020Nov 3 2020

Publication series

NameProceedings of the 2020 IISE Annual Conference

Conference

Conference2020 Institute of Industrial and Systems Engineers Annual Conference and Expo, IISE 2020
Country/TerritoryUnited States
CityVirtual, Online
Period11/1/2011/3/20

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Industrial and Manufacturing Engineering

Fingerprint

Dive into the research topics of 'A heuristic approach to a class of node-capacitated maximum flow problems'. Together they form a unique fingerprint.

Cite this