Back to Search
Start Over
An adaptive patch approximation algorithm for bicriteria convex mixed-integer problems.
- Source :
-
Optimization . Dec2022, Vol. 71 Issue 15, p4321-4366. 46p. - Publication Year :
- 2022
-
Abstract
- Pareto frontiers of bicriteria continuous convex problems can be efficiently computed and optimal theoretical performance bounds have been established. In the case of bicriteria mixed-integer problems, the approximation of the Pareto frontier becomes, however, significantly harder. In this paper, we propose a new algorithm for approximating the Pareto frontier of bicriteria mixed-integer programs with convex constraints. Such Pareto frontiers are composed of patches of solutions with shared assignments for the discrete variables. By adaptively creating such a patchwork, our algorithm is able to create approximations that converge quickly to the true Pareto frontier. As a quality measure, we use the difference in hypervolume between the approximation and the true Pareto frontier. At least a certain number of patches is required to obtain an approximation with a given quality. This patch complexity gives a lower bound on the number of required computations. We show that our algorithm performs a number of optimization steps that are of a similar order as this lower bound. We provide an efficient MIP-based implementation of this algorithm. The efficiency of our algorithm is illustrated with numerical results showing that our algorithm has a strong theoretical performance guarantee while being competitive with other state-of-the-art approaches in practice. [ABSTRACT FROM AUTHOR]
- Subjects :
- *APPROXIMATION algorithms
*MIXED integer linear programming
Subjects
Details
- Language :
- English
- ISSN :
- 02331934
- Volume :
- 71
- Issue :
- 15
- Database :
- Academic Search Index
- Journal :
- Optimization
- Publication Type :
- Academic Journal
- Accession number :
- 160715462
- Full Text :
- https://doi.org/10.1080/02331934.2021.1939699