Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/318654 
Year of Publication: 
2024
Citation: 
[Journal:] Journal of Global Optimization [ISSN:] 1573-2916 [Volume:] 91 [Issue:] 2 [Publisher:] Springer US [Place:] New York [Year:] 2024 [Pages:] 415-436
Publisher: 
Springer US, New York
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 .
Subjects: 
Decomposition method
Parallel computing
Column generation
Nonconvex optimization
Mixed-integer nonlinear programming
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version
Appears in Collections:

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.