期刊
OPTIMIZATION
卷 71, 期 15, 页码 4321-4366出版社
TAYLOR & FRANCIS LTD
DOI: 10.1080/02331934.2021.1939699
关键词
Bicriteria optimization; mixed-integer programming; approximation; rate of convergence
This paper proposes a new algorithm for approximating the Pareto frontier of bicriteria mixed-integer programs with convex constraints. By adaptively creating patches of solutions with shared assignments for discrete variables, the algorithm quickly converges to the true Pareto frontier. The algorithm's efficiency is demonstrated through numerical results and competitive performance with other state-of-the-art approaches.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据