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

Ivo Nowak, Norman Breitfeld, E.M.T. Hendrix, Grégoire Njacheun-Njanzoua

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

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.
LanguageEnglish
Pages305-321
JournalJournal of Global Optimization
Volume72
Issue number2
DOIs
Publication statusPublished - Oct 2018

Fingerprint

Global optimization
Mixed Integer Nonlinear Programming
Global Optimization
Refinement
Branch-and-bound
Decomposition
Decompose
Column Generation
Search Trees
Outer Approximation
Python
Successive Approximation
Decomposition Method
Reformulation
Approximation Methods
Optimization Methods
Scheduling Problem
Numerical Results
Scheduling
Approximation

Keywords

  • Global optimization
  • Decomposition method
  • MINLP
  • Successive approximation
  • Column generation

Cite this

Nowak, Ivo ; Breitfeld, Norman ; Hendrix, E.M.T. ; Njacheun-Njanzoua, Grégoire. / Decomposition-based Inner- and Outer-Refinement Algorithms for Global Optimization. In: Journal of Global Optimization. 2018 ; Vol. 72, No. 2. pp. 305-321.
@article{8b2bcaf458ca4c19b1d57143328d8e74,
title = "Decomposition-based Inner- and Outer-Refinement Algorithms for Global Optimization",
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",
author = "Ivo Nowak and Norman Breitfeld and E.M.T. Hendrix and Gr{\'e}goire Njacheun-Njanzoua",
year = "2018",
month = "10",
doi = "10.1007/s10898-018-0633-2",
language = "English",
volume = "72",
pages = "305--321",
journal = "Journal of Global Optimization",
issn = "0925-5001",
publisher = "Springer Verlag",
number = "2",

}

Decomposition-based Inner- and Outer-Refinement Algorithms for Global Optimization. / Nowak, Ivo; Breitfeld, Norman; Hendrix, E.M.T.; Njacheun-Njanzoua, Grégoire.

In: Journal of Global Optimization, Vol. 72, No. 2, 10.2018, p. 305-321.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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

AU - Nowak, Ivo

AU - Breitfeld, Norman

AU - Hendrix, E.M.T.

AU - Njacheun-Njanzoua, Grégoire

PY - 2018/10

Y1 - 2018/10

N2 - 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.

AB - 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.

KW - Global optimization

KW - Decomposition method

KW - MINLP

KW - Successive approximation

KW - Column generation

U2 - 10.1007/s10898-018-0633-2

DO - 10.1007/s10898-018-0633-2

M3 - Article

VL - 72

SP - 305

EP - 321

JO - Journal of Global Optimization

T2 - Journal of Global Optimization

JF - Journal of Global Optimization

SN - 0925-5001

IS - 2

ER -