(392bi) Deducing Bounds from Multilinear Constraints By Systematic Factoring

Multilinear expressions commonly arise in nonconvex optimization problems. They appear in applications as diverse as property balances in pooling problems [1] and pixels in image restoration [2], and they are also introduced in the factorable reformulation technique [3] and reformulation-linearization technique [4] for constructing convex relaxations. Accordingly, extensive effort has been devoted to convexifying multilinear expressions [5-7]. However, the question of tractably deducing implied variable bounds from multilinear constraints is not as well studied. In this work, we introduce a systematic factoring algorithm to compute bounds which does not require auxiliary variables or constraints. We provide a graph interpretation of the procedure and discuss its complexity as a function of graph topology. In addition, we highlight considerations influencing the effectiveness of our algorithm for real-world industrial problems and present computational results on publicly available benchmark instances.

References:

[1] R. Misener and C. A. Floudas. Appl. Comput. Math. 8(1) (2009), 3-22.

[2] Y. Crama and E. Rodríguez-Heck. Discrete Optim. 25 (2017), 28-47.

[3] G. P. McCormick. Math. Program. 10(1) (1976), 147-175.

[4] H. D. Sherali and W. P. Adams. A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems (1999).

[5] X. Bao, A. Khajavirad, N. V. Sahinidis, and M. Tawarmalani. Math. Program. Comput. 7(1) (2015), 1-37.

[6] A. Del Pia and A. Khajavirad. Math. Program. Comput. 12 (2020), 165-191.

[7] C. Cardonha, A. Raghunathan, D. Bergman and C. Nohra. INFORMS J. Comput. (2025).