On the accurate detection of the Pareto frontier for bi-objective mixed integer linear problems

We propose a criterion space search algorithm for bi-objective mixed integer linear programming problems. The Pareto frontier of these problems can have a complex structure, as it can include isolated points, open, half-open and closed line segments. Therefore, its exact detection is an achievable though hard computational task. Our algorithm works by alternating the resolution of single objective mixed integer linear problems with bi-objective linear ones. Along the iterations of the algorithm, the non-dominated points and line segments found are stored in an ordered manner, using the tree data-structure proposed in Adelgren et al. (2018). The performance of the algorithm is improved using suitably defined cuts and related strategies.
Under specific assumptions, we can prove that the exact Pareto frontier can be detected in a finite number of iterations.
Experimental results on a test-bed of instances and a comparison with the Triangle Splitting Method Boland et al. (2015) is presented, showing the notably good performance of our approach in terms of accuracy of the Pareto frontier detected and in terms of efficiency for medium size instances.

Article

Download

View On the accurate detection of the Pareto frontier for bi-objective mixed integer linear problems