Decomposition-based Inner- and Outer-Refinement Algorithms for Global Optimization

Ivo Nowak (), Norman Breitfeld (), Eligius M. T. Hendrix () and Grégoire Njacheun-Njanzoua ()
Additional contact information
Ivo Nowak: Hamburg University of Applied Sciences
Norman Breitfeld: Technische Universität Berlin
Eligius M. T. Hendrix: Universidad de Málaga
Grégoire Njacheun-Njanzoua: Hamburg University of Applied Sciences

Journal of Global Optimization, 2018, vol. 72, issue 2, No 8, 305-321

Abstract: Abstract Traditional deterministic global optimization methods are often based on a Branch-and-Bound (BB) search tree, which may grow rapidly, preventing the method to find a good solution. Motivated by decomposition-based inner approximation (column generation) methods for solving transport scheduling problems with over 100 million variables, we present a new deterministic decomposition-based successive approximation method for general modular and/or sparse MINLPs. The new method, called Decomposition-based Inner- and Outer-Refinement, is based on a block-separable reformulation of the model into sub-models. It generates inner- and outer-approximations using column generation, which are successively refined by solving many easier MINLP and MIP subproblems in parallel (using BB), instead of searching over one (global) BB search tree. We present preliminary numerical results with Decogo (Decomposition-based Global Optimizer), a new parallel decomposition MINLP solver implemented in Python and Pyomo.

Keywords: Global optimization; Decomposition method; MINLP; Successive approximation; Column generation (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

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

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

DOI: 10.1007/s10898-018-0633-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 ().