Polyhedral Relaxations for Optimal Pump Scheduling of Potable Water Distribution Networks

Byron Tasseff (), Russell Bent (), Carleton Coffrin (), Clayton Barrows (), Devon Sigler (), Jonathan Stickel (), Ahmed S. Zamzam (), Yang Liu () and Pascal Van Hentenryck ()
Additional contact information
Byron Tasseff: Los Alamos National Laboratory, Los Alamos, New Mexico 87545
Russell Bent: Los Alamos National Laboratory, Los Alamos, New Mexico 87545
Carleton Coffrin: Los Alamos National Laboratory, Los Alamos, New Mexico 87545
Clayton Barrows: National Renewable Energy Laboratory, Golden, Colorado 80401
Devon Sigler: National Renewable Energy Laboratory, Golden, Colorado 80401
Jonathan Stickel: National Renewable Energy Laboratory, Golden, Colorado 80401
Ahmed S. Zamzam: National Renewable Energy Laboratory, Golden, Colorado 80401
Yang Liu: Stanford University, Stanford, California 94305
Pascal Van Hentenryck: Georgia Institute of Technology, Atlanta, Georgia 30332

INFORMS Journal on Computing, 2024, vol. 36, issue 4, 1040-1063

Abstract: The classic pump scheduling or optimal water flow (OWF) problem for water distribution networks (WDNs) minimizes the cost of power consumption for a given WDN over a fixed time horizon. In its exact form, the OWF is a computationally challenging mixed-integer nonlinear program (MINLP). It is complicated by nonlinear equality constraints that model network physics, discrete variables that model operational controls, and intertemporal constraints that model changes to storage devices. To address the computational challenges of the OWF, this paper develops tight polyhedral relaxations of the original MINLP, derives novel valid inequalities (or cuts) using duality theory, and implements novel optimization-based bound tightening and cut generation procedures. The efficacy of each new method is rigorously evaluated by measuring empirical improvements in OWF primal and dual bounds over 45 literature instances. The evaluation suggests that our relaxation improvements, model strengthening techniques, and a thoughtfully selected polyhedral relaxation partitioning scheme can substantially improve OWF primal and dual bounds, especially when compared with similar relaxation-based techniques that do not leverage these new methods.

Keywords: bound tightening; convex; network; nonconvex; polyhedral; relaxation; valid inequalities; water (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0233 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:36:y:2024:i:4:p:1040-1063

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().