Multi-Tree Decomposition Methods for Large-Scale Mixed Integer Nonlinear Optimization

Ivo Nowak (), Pavlo Muts () and Eligius M. T. Hendrix ()
Additional contact information
Ivo Nowak: Hamburg University of Applied Sciences
Pavlo Muts: Hamburg University of Applied Sciences
Eligius M. T. Hendrix: University of Malaga

A chapter in Large Scale Optimization in Supply Chains and Smart Manufacturing, 2019, pp 27-58 from Springer

Abstract: Abstract Most industrial optimization problems are sparse and can be formulated as block-separable mixed-integer nonlinear programming Mixed integer nonlinear programming (MINLP) problems, defined by linking low-dimensional sub-problems by (linear) coupling constraints. Decomposition methods solve a block-separable MINLP by alternately solving master problems and sub-problems. In practice, decomposition methods are sometimes the only possibility to compute high-quality solutions of large-scale optimization problems. However, efficient implementations may require expert knowledge and problem-specific features. Recently, there is renewed interest in making these methods accessible to general users by developing generic decomposition frameworks and modelling support. The focus of this chapter is on so-called multi-tree decomposition methods, which iteratively approximate the feasible area without using a single (global) branch-and-bound tree, i.e. branch-and-bound is only used for solving sub-problems. After an introduction, we describe first outer approximation (OA) decomposition methods, Outer approximation including the adaptive, multivariate partitioning (AMP) Adaptive, Multivariate Partitioning (AMP) algorithm and the novel decomposition-based outer approximation (DECOA) algorithm Decomposition-based outer approximation (DECOA) . This is followed by a description of multi-tree methods using a reduced master problem for solving large-scale industrial optimization problems. The first method to be described applies parallel column generation Column generation (CG) and iterative fixing for solving nonconvex transport optimization problems with several hundred millions of variables and constraints. The second method is based on a novel approach combining CG and compact outer approximation. The last methodology to be discussed is the general Benders decomposition method Benders decomposition method for globally solving large nonconvex stochastic programs using a reduced mixed-integer programming (MIP) master problem.

Date: 2019
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spochp:978-3-030-22788-3_2

Ordering information: This item can be ordered from
http://www.springer.com/9783030227883

DOI: 10.1007/978-3-030-22788-3_2

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().