TY - JOUR
T1 - Variable Bound Tightening and Valid Constraints for Multiperiod Blending
AU - Chen, Yifu
AU - Maravelias, Christos T.
N1 - Funding Information:
History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms—Continuous. Funding: This work was supported by the National Science Foundation [Grant CBET2026980]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2021.1140.
Publisher Copyright:
© 2022 INFORMS.
PY - 2022/7
Y1 - 2022/7
N2 - Multiperiod blending has a number of important applications in a range of industrial sectors. It is typically formulated as a nonconvex mixed integer nonlinear program (MINLP), which involves binary variables and bilinear terms. In this study, we first propose a reformulation of the constraints involving bilinear terms using lifting. We introduce a method for calculating tight bounds on the lifted variables calculated by aggregating multiple constraints. We propose valid constraints derived from the reformulation-linearization technique (RLT) that use the bounds on the lifted variables to further tighten the formulation. Computational results indicate our method can substantially reduce the solution time and optimality gap. Summary of Contribution: In this paper, we study the multiperiod blending problem, which has a number of important applications in a range of industrial sectors, such as refining, chemical production, mining, and wastewater management. Solving this problem efficiently leads to significant economic and environmental benefits. However, solving even medium-scale instances to global optimality remains challenging. To address this challenge, we propose a variable bound tightening algorithm and tightening constraints for multiperiod blending. Computational results show that our methods can substantially reduce the solution time and optimality gap.
AB - Multiperiod blending has a number of important applications in a range of industrial sectors. It is typically formulated as a nonconvex mixed integer nonlinear program (MINLP), which involves binary variables and bilinear terms. In this study, we first propose a reformulation of the constraints involving bilinear terms using lifting. We introduce a method for calculating tight bounds on the lifted variables calculated by aggregating multiple constraints. We propose valid constraints derived from the reformulation-linearization technique (RLT) that use the bounds on the lifted variables to further tighten the formulation. Computational results indicate our method can substantially reduce the solution time and optimality gap. Summary of Contribution: In this paper, we study the multiperiod blending problem, which has a number of important applications in a range of industrial sectors, such as refining, chemical production, mining, and wastewater management. Solving this problem efficiently leads to significant economic and environmental benefits. However, solving even medium-scale instances to global optimality remains challenging. To address this challenge, we propose a variable bound tightening algorithm and tightening constraints for multiperiod blending. Computational results show that our methods can substantially reduce the solution time and optimality gap.
KW - bilinear terms
KW - preprocessing
KW - reformulation-linearization technique
KW - variable lifting
UR - http://www.scopus.com/inward/record.url?scp=85139984012&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85139984012&partnerID=8YFLogxK
U2 - 10.1287/ijoc.2021.1140
DO - 10.1287/ijoc.2021.1140
M3 - Article
AN - SCOPUS:85139984012
SN - 1091-9856
VL - 34
SP - 2073
EP - 2090
JO - INFORMS Journal on Computing
JF - INFORMS Journal on Computing
IS - 4
ER -