An adaptive patch approximation algorithm for bicriteria convex mixed-integer problems. (9th December 2022)

• Record Type: Journal Article
• Authors: Diessel, Erik
• Is Part Of: Optimization. Volume 71:Number 15(2022)
• Page Start: 4321
• Page End: 4366
• Publication Date: 2022-12-09
• Subjects: Bicriteria optimization -- mixed-integer programming -- approximation -- rate of convergence; 90C29 -- 90C11 -- 90C59 -- 90-08; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2021.1939699
• Languages: English
• ISSNs: 0233-1934

Abstract

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.