Cooperative multiobjective optimization with bounds on objective functions
- PDF / 678,863 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 32 Downloads / 194 Views
Cooperative multiobjective optimization with bounds on objective functions I. Kaliszewski1,2
· J. Miroforidis1
Received: 30 January 2019 / Accepted: 31 August 2020 © The Author(s) 2020
Abstract When solving large-scale multiobjective optimization problems, solvers can get stuck because of memory and/or time limitations. In such cases, one is left with no information on the distance to the best feasible solution, found before the optimization process has stopped, to the true Pareto optimal solution. In this work, we show how to provide such information. To this aim we make use of the concept of lower shells and upper shells, developed in our earlier works. No specific assumptions about the problems to be solved are made. We illustrate the proposed approach on biobjective multidimensional knapsack problems derived from singleobjective multidimensional knapsack problems in the Beasley OR Library. We address cases when a top-class commercial mixed-integer linear solver fails to provide Pareto optimal solutions attempted to be derived by scalarization. Keywords Multiobjective optimization · Pareto optimality · Two-sided Pareto front approximations
1 Introduction The ubiquitous access to more and more powerful computing platforms stimulates the appetite to solve more and more large optimization problems. However, various barriers (time and/or memory limits, ”the curse of dimensionality” in combinatorial problems) are the cause that in practice one is often left with suboptimal solutions. In such cases, the existence of lower and upper bounds on the exact solution is essential. The multiobjective optimization literature is rich with various approaches to this issue, cf. [14,15] for brief overviews. This work has been inspired by the fact that when solving large-scale multiobjective optimization (MO) problems, it can happen that Pareto optimal (efficient) solutions are not derived. The reasons for that can be twofold. When making use of heuristics, such as Evolutionary Multiobjective Optimization (EMO), or other, Pareto optimality of derived solutions is not guaranteed. When making use of exact methods, such as mixed-integer programming
B
J. Miroforidis [email protected]
1
Systems Research Institute, Polish Academy of Sciences, ul. Newelska 6, Warsaw 01-447, Poland
2
Warsaw School of Information Technology, ul. Newelska 6, Warsaw 01-447, Poland
123
Journal of Global Optimization
(MIP), solvers can reach memory limits, and, less often, time limits, before the optimal solution is found. In both cases, one is left with a feasible solution which may be believed to be Pareto optimal or close to Pareto optimality, but no information is offered about how wide the actual gap is (the Pareto suboptimality gap) between the image (in the objective space) of the feasible solution derived and the image (in the objective space) of the set of Pareto optimal solutions (the Pareto front). To cope with such unfavorable situations and to provide the lacking information, here we employ the general methodology devel
Data Loading...
