On decomposition and multiobjective-based column and disjunctive cut generation for MINLP
- PDF / 2,109,676 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 40 Downloads / 207 Views
On decomposition and multiobjective‑based column and disjunctive cut generation for MINLP Pavlo Muts1 · Ivo Nowak1 · Eligius M. T. Hendrix2 Received: 6 February 2020 / Revised: 23 September 2020 / Accepted: 27 October 2020 © The Author(s) 2020
Abstract Most industrial optimization problems are sparse and can be formulated as blockseparable mixed-integer nonlinear programming (MINLP) problems, defined by linking low-dimensional sub-problems by (linear) coupling constraints. This paper investigates the potential of using decomposition and a novel multiobjective-based column and cut generation approach for solving nonconvex block-separable MINLPs, based on the so-called resource-constrained reformulation. Based on this approach, two decomposition-based inner- and outer-refinement algorithms are presented and preliminary numerical results with nonconvex MINLP instances are reported. Keywords Decomposition method · Parallel computing · Column generation · Nonconvex optimization · Global optimization · Mixed-integer nonlinear programming
1 Introduction Most real-world Mixed Integer Nonlinear Programming (MINLP) models are sparse, e.g. instances of the MINLPLib (Vigerske 2018). These models can be reformulated as block-separable problems, defined by low-dimensional sub-problems, which are coupled by a moderate number of linear global constraints. In this paper
* Ivo Nowak ivo.nowak@haw‑hamburg.de Pavlo Muts pavlo.muts@haw‑hamburg.de Eligius M. T. Hendrix [email protected] 1
Hamburg University of Applied Sciences, Hamburg, Germany
2
University of Malaga, Málaga, Spain
13
Vol.:(0123456789)
P. Muts et al.
we investigate the potential of solving block-separable MINLPs using a decomposition multi-tree approach. 1.1 Global optimization and decomposition methods Most global optimization methods can be divided into three approaches: 1. Sampling (point-based; Shapiro 2003), stochastic like Evolutionary Algorithms (Bäck 1996) or deterministic like DIRECT (Kolda et al. 2003); 2. Branch-and-Bound and variants (tree-based; Tawarmalani and Sahinidis 2005); 3. Successive Approximation (model-based), e.g. LP/MIP approximation (Kronqvist et al. 2016; Muts et al. 2020). Our focus is on Decomposition-based Successive Approximation, i.e. an approximation is improved by solving low-dimensional sub-problems. Decomposition is a very general approach that can be applied to convex optimization, as well as nonconvex optimization and discrete optimization. These methods are based on dividing a model into smaller sub-problems defined by local constraints, which can be solved in parallel. Then the results are used for updating a global master problem defined by global constraints, which is typically an LP, a MIP or a QP problem. The subproblems and the global master problem are alternatingly solved until some termination criterion is met. In the following, an overview on (deterministic) decomposition methods is given. 1.1.1 Lagrangian decomposition Many MINLP decomposition methods are based on solving a Lagrangian relaxation. It has b
Data Loading...
