Mixed integer nonlinear multiobjective optimization by outer approximations
Final Report Abstract
The aim of this project was to develop a deterministic algorithmic solution procedure for multiobjective mixed-integer nonlinear optimization problems. We realized such a procedure for multiobjective mixed-integer convex optimization problems, which were the main focus of this project, with the Hybrid Patch Decomposition algorithm (HyPaD). This algorithm decomposes the mixed-integer problem into certain continuous subproblems by fixing the values of the integer variables. For those continuous problems it iteratively computes weakly nondominated points using techniques from multiobjective continuous optimization. These points are used to compute and improve a global upper bound set for the overall nondominated set of the mixed-integer problem as well as lower bound sets for the nondominated sets of the continuous subproblems. These lower bound sets for the subproblems only yield a global lower bound set in case all possible integer fixings are enumerated. In order to avoid such a full enumeration - especially for a large number of integer variables - simultaneously a global lower bound set is computed. For this, we solve linear relaxations of the original mixed-integer problem that are iteratively refined. Scalarizations of these relaxations yield single-objective mixed-integer linear optimization problems for which fast solvers are available. Hence, the HyPaD algorithm combines techniques from multiobjective continuous and single-objective mixedinteger linear optimization for solving multiobjective mixed-integer convex optimization problems efficiently. Since all techniques within the algorithm work entirely in the criterion space, problems with a large number of optimization variables can be solved. Besides proving correctness and finiteness of the algorithm, extensive numerical tests have been performed as well. For this, we also developed a generator for test instances for multiobjective mixed-integer nonlinear optimization problems. With the multiobjective mixed-integer branch-and-bound algorithm MOMIBB, we even developed a solution procedure for multiobjective mixed-integer nonconvex optimization problems. This algorithm makes use of subproblems based on a geometric branch-andbound procedure in the decision space. Attainable points of subproblems are used to compute a global upper bound set. What is more, the algorithm computes lower bounds for the nondominated sets of each of the subproblems. Also for this algorithm, we proved correctness and finiteness and demonstrated its capabilities in numerical tests. An implementation of all algorithms developed in the scope of this project is publicly available on GitHub.
Publications
-
An approximation algorithm for multi-objective optimization problems using a box-coverage. Journal of Global Optimization, 83(2), 329-357.
Eichfelder, Gabriele & Warnow, Leo
-
A hybrid patch decomposition approach to compute an enclosure for multi-objective mixed-integer convex optimization problems. Mathematical Methods of Operations Research, 100(1), 291-320.
Eichfelder, Gabriele & Warnow, Leo
-
A Solver for Multiobjective Mixed-Integer Convex and Nonconvex Optimization. Journal of Optimization Theory and Applications, 203(2), 1736-1766.
Eichfelder, Gabriele; Stein, Oliver & Warnow, Leo
-
A test instance generator for multiobjective mixed-integer optimization. Mathematical Methods of Operations Research, 100(1), 385-410.
Eichfelder, Gabriele; Gerlach, Tobias & Warnow, Leo
-
Advancements in the computation of enclosures for multi-objective optimization problems. European Journal of Operational Research, 310(1), 315-327.
Eichfelder, Gabriele & Warnow, Leo
-
Using dual relaxations in multiobjective mixed-integer convex quadratic programming. Journal of Global Optimization, 92(1), 159-186.
De Santis, Marianna; Eichfelder, Gabriele; Patria, Daniele & Warnow, Leo
-
Computing an Approximation of the Non-Dominated Set of Multi-Objective Mixed-Integer Nonlinear Optimization Problems. Series on Computers and Operations Research, 423-474. World Scientific.
Eichfelder, Gabriele & Warnow, Leo
-
Test Instances for Multiobjective Mixed-Integer Nonlinear Optimization. Springer Optimization and Its Applications, 71-99. Springer Nature Switzerland.
Eichfelder, Gabriele; Gerlach, Tobias & Warnow, Leo
