Global optimization of MIQCPs with dynamic piecewise relaxations

Pedro A. Castillo Castillo, Pedro M. Castro () and Vladimir Mahalec
Additional contact information
Pedro A. Castillo Castillo: McMaster University
Pedro M. Castro: Universidade de Lisboa
Vladimir Mahalec: McMaster University

Journal of Global Optimization, 2018, vol. 71, issue 4, No 3, 716 pages

Abstract: Abstract We propose a new deterministic global optimization algorithm for solving mixed-integer bilinear programs. It relies on a two-stage decomposition strategy featuring mixed-integer linear programming relaxations to compute estimates of the global optimum, and constrained non-linear versions of the original non-convex mixed-integer nonlinear program to find feasible solutions. As an alternative to spatial branch-and-bound with bilinear envelopes, we use extensively piecewise relaxations for computing estimates and reducing variable domain through optimality-based bound tightening. The novelty is that the number of partitions, a critical tuning parameter affecting the quality of the relaxation and computational time, increases and decreases dynamically based on the computational requirements of the previous iteration. Specifically, the algorithm alternates between piecewise McCormick and normalized multiparametric disaggregation. When solving ten benchmark problems from the literature, we obtain the same or better optimality gaps than two commercial global optimization solvers.

Keywords: Mixed-integer nonlinear programming; Global optimization of quadratic programs with bilinear terms; Piecewise linear relaxations; Optimality-based bound tightening (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-018-0612-7 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:71:y:2018:i:4:d:10.1007_s10898-018-0612-7

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

DOI: 10.1007/s10898-018-0612-7

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 ().