(104c) Tightening Discretization-Based MILP Models for the Pooling Problem Using Upper Bounds on Bilinear Terms

Discretization-based methods have been proposed for solving nonconvex optimization problems with bilinear terms. These methods convert the original nonconvex optimization problems into mixed-integer linear programs (MILPs); for example, Kolodziej et al. (Kolodziej et al. 2013) proposed global optimization algorithms for multiperiod blending problems based on solving MILPs resulted from discretization, Dey and Gupte (Dey and Gupte 2015) analyzed discretization-based MILP techniques to address bilinear terms in the pooling problem, and Ceccon and Misener (Ceccon and Misener 2022) implemented a discretization technique into an extensible solver for the pooling problem.

Compared to a wide range of studies related to methods to convert nonconvex optimization problems into MILPs, research on tightening the resulting MILP models is limited. In this talk, we present tightening constraints for the discretization-based MILP models for the pooling problem. We note one related work from Gupte et al. (Gupte et al. 2013), in which the authors presented the convex hull of the set resulted from binary expansion of one variable involved in the bilinear term by exploiting the underlying knapsack structure in the set. Different from Gupte et al., we study tightening constraints derived from upper bounds on bilinear term, which are commonly seen in models for Process Systems Engineering applications. We show that the constraints we propose are facet-defining, and present a full description of the convex hull of a mixed-integer set resulted from discretization of bilinear term.

We demonstrate the effectiveness of our constraints, showing computational results for MILP models derived from different formulations for (1) the pooling problem and (2) discretization-based pooling models. Computational results show that our methods reduce the computational time for MILP models on CPLEX 12.10. Finally, we note that while our methods are presented in the context of the pooling problem, they can be extended to address other nonconvex optimization problems with upper bounds on bilinear terms.

References

Ceccon, Francesco, and Ruth Misener. 2022. “Solving the Pooling Problem at Scale with Extensible Solver GALINI.” Computers & Chemical Engineering 159 (March): 107660. https://doi.org/10.1016/J.COMPCHEMENG.2022.107660.

Dey, Santanu S., and Akshay Gupte. 2015. “Analysis of MILP Techniques for the Pooling Problem.” Operations Research 63 (2): 412–27. https://doi.org/10.1287/opre.2015.1357.

Gupte, Akshay, Shabbir Ahmed, Myun Seok Cheon, and Santanu Dey. 2013. “Solving Mixed Integer Bilinear Problems Using MILP Formulations.” SIAM Journal on Optimization 23 (2): 721–44. https://doi.org/10.1137/110836183.

Kolodziej, Scott P., Ignacio E. Grossmann, Kevin C. Furman, and Nicolas W. Sawaya. 2013. “A Discretization-Based Approach for the Optimization of the Multiperiod Blend Scheduling Problem.” Computers and Chemical Engineering 53: 122–42. https://doi.org/10.1016/j.compchemeng.2013.01.016.