4.6 Article

An adaptive patch approximation algorithm for bicriteria convex mixed-integer problems

Journal

OPTIMIZATION
Volume 71, Issue 15, Pages 4321-4366

Publisher

TAYLOR & FRANCIS LTD
DOI: 10.1080/02331934.2021.1939699

Keywords

Bicriteria optimization; mixed-integer programming; approximation; rate of convergence

Ask authors/readers for more resources

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.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.6
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available