Polyhedral Relaxations for Optimal Pump Scheduling of Potable Water Distribution Networks

Byron Tasseff, Russell Bent, Carleton Coffrin, Clayton Barrows, Devon Sigler, Jonathan Stickel, Ahmed Zamzam, Yang Liu, Pascal Van Hentenryck

Research output: Contribution to journalArticlepeer-review

2 Scopus Citations

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.
Original languageAmerican English
Pages (from-to)1040-1063
Number of pages24
JournalINFORMS Journal on Computing
Volume36
Issue number4
DOIs
StatePublished - 2024

NREL Publication Number

  • NREL/JA-6A40-84136

Keywords

  • bound tightening
  • convex
  • network
  • nonconvex
  • polyhedral
  • relaxation
  • valid inequalities
  • water

Fingerprint

Dive into the research topics of 'Polyhedral Relaxations for Optimal Pump Scheduling of Potable Water Distribution Networks'. Together they form a unique fingerprint.

Cite this