A proximal-point outer approximation algorithm
- PDF / 767,022 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 80 Downloads / 191 Views
A proximal-point outer approximation algorithm Massimo De Mauri1
· Joris Gillis1 · Jan Swevers1 · Goele Pipeleers1
Received: 3 May 2019 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Many engineering and scientific applications, e.g. resource allocation, control of hybrid systems, scheduling, etc., require the solution of mixed-integer non-linear problems (MINLPs). Problems of such class combine the high computational burden arising from considering discrete variables with the complexity of non-linear functions. As a consequence, the development of algorithms able to efficiently solve medium-large MINLPs is still an interesting field of research. In the last decades, several approaches to tackle MINLPs have been developed. Some of such approaches, usually defined as exact methods, aim at finding a globally optimal solution for a given MINLP at expense of a long execution time, while others, generally defined as heuristics, aim at discovering suboptimal feasible solutions in the shortest time possible. Among the various proposed paradigms, outer approximation (OA) and feasibility pump (FP), respectively as exact method and as heuristic, deserve a special mention for the number of relevant publications and successful implementations related to them. In this paper we present a new exact method for convex mixed-integer non-linear programming called proximal outer approximation (POA). POA blends the fundamental ideas behind FP into the general OA scheme that attepts to yield faster and more robust convergence with respect to OA while retaining the good performances in terms of fast generation of feasible solutions of FP. Keywords Feasibility pump · Linear outer approximation · Mixed-integer non-linear optimization · Mixed-integer programming
Introduction Mixed-Integer non-linear programming is a branch of numerical optimization that deals with optimization problems in which some of the variables are only allowed
B 1
Massimo De Mauri [email protected] MECO Research Team, Department Mechanical Engineering, KU Leuven and Flanders Make - DMMS_M, Leuven, Belgium
123
M. De Mauri et al.
to take values within a certain discrete set and either or both the objective-function and the constraints are non-linear. Mixed-integer non-linear problems (MINLPs) are very commonly encountered in scientific and engineering applications and numerous efforts have been spent on the development of efficient solution algorithms for them [1–5]. However, MINLPs are still particularly computationally expensive to solve. In practice, MINLPs are much harder to solve than both Non-Linear Problems (NLPs) and Mixed-Integer Linear Problems (MILPs). Therefore, Duran and Grossmann in 1986 [1] proposed an algorithm, called outer approximation (OA), that finds an optimal point for the given convex MINLP via the solution of an alternating sequence of MILPs and NLPs [3,6–8]. After almost forty years, the algorithmic ideas of the original OA method are still at the core of some of the most competitive MINLP solu
Data Loading...
