On the use of overlapping convex hull relaxations to solve nonconvex MINLPs

Ouyang Wu (), Pavlo Muts (), Ivo Nowak () and Eligius M. T. Hendrix ()
Additional contact information
Ouyang Wu: HAW Hamburg
Pavlo Muts: HAW Hamburg
Ivo Nowak: HAW Hamburg
Eligius M. T. Hendrix: Universidad de Málaga

Journal of Global Optimization, 2025, vol. 91, issue 2, No 9, 415-436

Abstract: Abstract We present a novel relaxation for general nonconvex sparse MINLP problems, called overlapping convex hull relaxation (CHR). It is defined by replacing all nonlinear constraint sets by their convex hulls. If the convex hulls are disjunctive, e.g. if the MINLP is block-separable, the CHR is equivalent to the convex hull relaxation obtained by (standard) column generation (CG). The CHR can be used for computing an initial lower bound in the root node of a branch-and-bound algorithm, or for computing a start vector for a local-search-based MINLP heuristic. We describe a dynamic block and column generation (DBCG) MINLP algorithm to generate the CHR by dynamically adding aggregated blocks. The idea of adding aggregated blocks in the CHR is similar to the well-known cutting plane approach. Numerical experiments on nonconvex MINLP instances show that the duality gap can be significantly reduced with the results of CHRs. DBCG is implemented as part of the CG-MINLP framework Decogo, see https://decogo.readthedocs.io/en/latest/index.html .

Keywords: Decomposition method; Parallel computing; Column generation; Nonconvex optimization; Mixed-integer nonlinear programming (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-024-01376-2 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:91:y:2025:i:2:d:10.1007_s10898-024-01376-2

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

DOI: 10.1007/s10898-024-01376-2

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