A 501(c)(3) non-profit organization Applied AI research for public benefit
CheAI Research Inc.

Ipopt misses the proven optimal water network in up to 44 % of random starts on six benchmarks

We proved the global optimum of six water-network benchmarks and counted how often a randomly started local solver returned a worse network.

Thinh D. Ho | CheAI Research Inc. | Research article | October 2021

Abstract

Water network synthesis is non-convex, because every contaminant balance multiplies an unknown flow by an unknown concentration. A local solver can therefore return a worse network without warning. We solved six literature benchmarks to a relative gap of 10-4 with the global solvers SCIP and Couenne, and a separate validator recomputed every reported network from its flows. Five published optima were reproduced within 0.003 %. The sixth, 139.3 t/h of freshwater, is infeasible on the open data, whose proven optimum is 139.700 t/h. From 200 predeclared random starts per benchmark, the local solver Ipopt reached the optimum from every feasible start on the three single-source networks and on the selection problem with its units fixed. It stopped at one worse objective value in 18.0 % of starts on a treatment network (23.5 % above the optimum) and in 44.0 % on a three-source network (3.38 % above). Bonmin chose wrong units in 7 of 50 starts, and Couenne 0.5.8 made three invalid optimality claims.

1. Introduction

Water network synthesis decides where the operations of a plant take water from other operations or treatment units instead of freshwater. Every mixer balance multiplies an unknown flow by an unknown concentration [1]. These bilinear terms make the problem non-convex, so a local solver can converge to a feasible network that is worse than the best one.

Global optimization proves the optimum of such networks [1, 2], and heuristics give local solvers good starting points [3, 4]. We found no measurement of how often a local solver misses from declared random starts, and by how much, on problems with a proven optimum. On six open benchmarks, Ipopt returned worse feasible objectives on two, in 18.0 % and 44.0 % of starts.

2. Methods

A benchmark was included only if a readable source gave its full data and its published optimum. B1 and B2 are multi-contaminant water-using networks [5, 6], transcribed from the tables reprinted in [7]. B3 is a single-contaminant network [8] with one regenerator of removal ratio 0.95, with targets from [9]. B4 (distributed effluent treatment), B5 (three freshwater sources) and B6 (treatment with unit selection) are MINLPLib instances [3, 4, 10]. B1, B2 and B3 each have one freshwater source.

All six were encoded in one superstructure (Figure 1) after [1]. The contaminant mass entering node n is

Mn,j = Σa fa Ci,j

where fa is the flow on an arc from node i and Ci,j is a fixed or variable concentration.

Line diagram of the superstructure with sources, effluents, water-using operations, treatment units and one discharge, connected by nine classes of arcs.
Figure 1. The superstructure has five node classes and nine arc classes.

SCIP 10.0 and Couenne 0.5.8 solved each benchmark to a relative gap of 10-4, and an optimum was accepted when both agreed. A separately written validator recomputed every concentration, balance and limit from the arc flows alone.

The protocol was fixed before any local solve. Each start drew every continuous variable uniformly between zero and its upper bound, and every binary as 0 or 1. Ipopt 3.13.2 [11] solved each benchmark from 200 starts with the MA57 linear solver, tolerance 10-8, at most 3000 iterations and 60 s. For B6 it used the optimal unit selection, and Bonmin 1.8.8 [12] solved the full mixed-integer problem from 50 starts. A run was global when the validator accepted it within a relative 10-4 of the optimum. Failed runs counted as misses. Intervals are Wilson 95 % intervals.

3. Results

3.1 One published optimum is infeasible

SCIP and Couenne proved the same optimum on all six benchmarks. Five matched the published value. On B2 both solvers proved a minimum freshwater of 139.700 t/h, 0.287 % above the published 139.3 t/h. Both proved the problem infeasible at 139.35 t/h, the upper end of the published rounding. A separately written model gave the same 139.700 t/h.

3.2 Worse feasible outcomes on B4 and B5

On B1, B2 and B3, Ipopt reached the global optimum from every start that ended feasible (Figure 2). The only B3 miss was one failed run. On B6 with the units fixed, Ipopt had no miss, which puts its miss rate below 1.9 % at 95 % confidence.

Ipopt missed in 36 of 200 starts on B4 (18.0 % [13.3, 23.9] %) and in 88 of 200 on B5 (44.0 % [37.3, 50.9] %). On each, all misses shared one worse objective value. On B4 it was 110.954 t/h of treated flow, 23.5 % above the optimum. On B5 it was 170.054 t/h, 3.38 % above. Ipopt reported "Optimal Solution Found" in every run on both benchmarks, misses included.

Two-panel plot. Left, miss rate with Wilson intervals for each run set, near zero except B4 Ipopt, B5 Ipopt and B6 Bonmin. Right, stacked bars of end points showing one worse value on B4 and B5 and two on B6 Bonmin.
Figure 2. Ipopt returns worse feasible objectives only on B4 and B5, with one observed worse value on each. (a) Share of starts that miss the optimum, with Wilson 95 % intervals. Open symbols show B3 under two stricter readings of the Ipopt exit message. (b) End points of the starts on the three run sets with misses.

On B3, only 122 of 200 runs ended with "Optimal Solution Found", yet the validator placed all 199 feasible runs at the optimum. A repeat of all 1250 runs reproduced every objective bit for bit.

3.3 Bonmin and Couenne

Bonmin returned a worse B6 network in 7 of 50 starts (14.0 % [7.0, 26.2] %), each with a wrong unit selection. Couenne 0.5.8 made three optimality claims that a validated network with a lower objective refuted. On the B4 MINLPLib file it reported a completed search at 90.95869, against 89.836065 from SCIP. It also failed to evaluate the original B6 file. SCIP gave the correct result in every case we could check. Two Couenne networks passed the validator only after slightly negative flows were set to zero.

3.4 Savings from regeneration

With its published regenerator, B3 needed 40.00 t/h of freshwater instead of 80.00 t/h (Figure 3). With an assumed regenerator of 95 % removal, no cost and no capacity limit, regeneration saved at most 40.3 %, 32.0 % and 56.2 % on B1, B2 and B5. These results rest on SCIP proofs and the validator.

Two-panel plot. Left, minimum freshwater of B1, B2, B3 and B5 under no reuse, reuse, regeneration-reuse and regeneration-recycling. Right, minimum freshwater against a cap on regenerated flow.
Figure 3. Regeneration halves the freshwater of B3 and, with an assumed regenerator, saves at most 56 % on the other benchmarks. (a) Minimum freshwater under four schemes. An asterisk marks the assumed regenerator. (b) Minimum freshwater with the regenerated flow capped at a fraction of its minimum.

4. Discussion

The miss rate ranged from none in 200 starts to 44 %. Where Ipopt missed, the loss mattered for design, at 23.5 % more treated water on B4 and 3.38 % more freshwater on B5. Its output gave no sign of the miss. B4 and B5 are the instances for which [3] and [4] built start-point heuristics. Our rates measure uniform random starts on the same instances.

B4 is a treatment network fed by fixed effluents. B5 has three sources of different quality and operations at fixed capacity. We did not test which of these features causes the misses.

Two checks caught errors that a single-solver workflow would have reported as results. The B2 optimum may rest on slightly different data than the reprinted table, and the validator refuted each invalid Couenne claim.

A few local starts suffice only when the miss rate is known and the starts are independent. At the B5 rate, all of 10 starts would miss with a chance of 0.4410 ≈ 2.7 × 10-4. For a new network the rate is unknown. SCIP proved each optimum in under 4 s, so a global solve was the more reliable and the faster safeguard.

5. Limitations

The rates hold for this encoding, uniform starts and Ipopt 3.13.2 with the settings above. Other starts or options can give other rates, and the Wilson intervals cover sampling error only. Ipopt reported convergence at the worse values, but they were not proven to be local optima. On B6, Ipopt and Bonmin differ in solver, problem and cost formulation, so the runs locate the misses but do not attribute them to unit selection. The Couenne failures are cases met, not a measured failure rate. The 10-start figure is arithmetic on the observed rate, not a tested result.

Optimality is a numerical certificate at a gap of 10-4 on the encoded model and its bounds. No reported optimum reached the artificial flow cap, but we did not test whether a larger cap admits a better network. The validator read the model's data, so it could not detect a wrong data value, and the original B2 source was not read. The NumPy version of the original runs was not recorded, and the solver versions of the regeneration records were added at export from the installed solvers. Timings come from single-threaded runs on one shared machine.

The benchmarks are small, with at most seven operations or five treatment units. One instance per class describes that benchmark, not its class, and only B3 combines water use with a regenerator. B3 is also a fixed-load encoding of a source model with fixed flowrates, and its rates describe this encoding only. The B1, B2 and B5 savings assume a regenerator of 95 % removal, and a capacity limit or a cost objective may reduce them. The model is steady-state, with fixed loads, perfect mixing, fixed removal ratios and no water loss in treatment. It has no energy, pumping or treatment-performance model. Finally, optimal networks need not be unique, so the comparisons use objective values, not networks.

6. Conclusions

On six benchmarks with proven global optima, Ipopt from random starts found the optimum from every feasible start on the three single-source networks. It stopped at a worse objective in 18.0 % of starts on a distributed-treatment network and 44.0 % on a three-source network, without warning. Bonmin chose wrong units in 7 of 50 starts. One published optimum is infeasible on its open data, and Couenne 0.5.8 made three invalid optimality claims. For networks of this size a global solve takes seconds, and its certificate is worth checking with a second solver and a recomputation from the flows.

References

  1. Karuppiah R, Grossmann IE. Global optimization for the synthesis of integrated water systems in chemical processes. Computers and Chemical Engineering 30, 650-673, 2006.
  2. Castro PM, Teles JP. Comparison of global optimization algorithms for the design of water-using networks. Computers and Chemical Engineering 52, 249-261, 2013.
  3. Castro PM, Matos HA, Novais AQ. An efficient heuristic procedure for the optimal design of wastewater treatment systems. Resources, Conservation and Recycling 50, 158-185, 2007.
  4. Teles JP, Castro PM, Novais AQ. MILP-based initialization strategies for the optimal design of water-using networks. Chemical Engineering Science 64, 3736-3752, 2009.
  5. Wang YP, Smith R. Wastewater minimisation. Chemical Engineering Science 49, 981-1006, 1994.
  6. Wang B, Feng X, Zhang Z. A design methodology for multiple-contaminant water networks with single internal water main. Computers and Chemical Engineering 27, 903-911, 2003.
  7. Li BH, Ren Y, Fei WY. A rapid design method for water-using system with multiple contaminants. Proceedings of FOCAPD 2004, paper 032_77, 2004.
  8. Kuo WCJ, Smith R. Design of water-using systems involving regeneration. Process Safety and Environmental Protection 76, 94-114, 1998.
  9. Liu JH, Li AH, Liu ZY. An effective method for targeting water-using networks of single contaminant involving regeneration reuse/recycling. Chemical Engineering Transactions 52, 829-834, 2016.
  10. MINLPLib. A library of mixed-integer and continuous nonlinear programming instances. Instances wastewater04m1, waterund08 and watertreatnd_flow. www.minlplib.org, accessed 2021-09-27.
  11. Wächter A, Biegler LT. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming 106, 25-57, 2006.
  12. Bonami P, Biegler LT, Conn AR, Cornuéjols G, Grossmann IE, Laird CD, et al. An algorithmic framework for convex mixed integer nonlinear programs. Discrete Optimization 5, 186-204, 2008.