On piecewise linear approximations of bilinear terms: structural comparison of univariate and bivariate mixed-integer programming formulations

Andreas Bärmann (), Robert Burlacu (), Lukas Hager () and Thomas Kleinert ()
Additional contact information
Andreas Bärmann: Friedrich-Alexander-Universität Erlangen-Nürnberg
Robert Burlacu: Fraunhofer Institute for Integrated Circuits IIS
Lukas Hager: Friedrich-Alexander-Universität Erlangen-Nürnberg
Thomas Kleinert: Friedrich-Alexander-Universität Erlangen-Nürnberg

Journal of Global Optimization, 2023, vol. 85, issue 4, No 1, 789-819

Abstract: Abstract Bilinear terms naturally appear in many optimization problems. Their inherent non-convexity typically makes them challenging to solve. One approach to tackle this difficulty is to use bivariate piecewise linear approximations for each variable product, which can be represented via mixed-integer linear programming (MIP) formulations. Alternatively, one can reformulate the variable products as a sum of univariate functions. Each univariate function can again be approximated by a piecewise linear function and modelled via an MIP formulation. In the literature, heterogeneous results are reported concerning which approach works better in practice, but little theoretical analysis is provided. We fill this gap by structurally comparing bivariate and univariate approximations with respect to two criteria. First, we compare the number of simplices sufficient for an $$ \varepsilon $$ ε -approximation. We derive upper bounds for univariate approximations and compare them to a lower bound for bivariate approximations. We prove that for a small prescribed approximation error $$ \varepsilon $$ ε , univariate $$ \varepsilon $$ ε -approximations require fewer simplices than bivariate $$ \varepsilon $$ ε -approximations. The second criterion is the tightness of the continuous relaxations (CR) of corresponding sharp MIP formulations. Here, we prove that the CR of a bivariate MIP formulation describes the convex hull of a variable product, the so-called McCormick relaxation. In contrast, we show by a volume argument that the CRs corresponding to univariate approximations are strictly looser. This allows us to explain many of the computational effects observed in the literature and to give theoretical evidence on when to use which kind of approximation.

Keywords: Bilinear programming; Piecewise linear approximations; MIP formulations; Univariate reformulations; Convex relaxations; 90C20; 90C59; 90C11; 51A27; 15A63 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-022-01243-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:85:y:2023:i:4:d:10.1007_s10898-022-01243-y

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-022-01243-y

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().