Branch-and-Bound for Bi-objective Integer Programming
Sophie N. Parragh, Fabien Tricoire
INFORMS Journal on Computing · 2019 · Volume 31 · Issue 4
Abstract
In bi-objective integer optimization the optimal result corresponds to a set of nondominated solutions. We propose a generic bi-objective branch-and-bound algorithm that uses a problem-independent branching rule exploiting available integer solutions and takes advantage of integer objective coefficients. The developed algorithm is applied to bi-objective facility location problems and the bi-objective set covering problem, as well as to the bi-objective team orienteering problem with time windows. In the latter case, lower bound sets are computed by means of column generation. Comparison with state-of-the-art exact algorithms shows the effectiveness of the proposed branch-and-bound algorithm.
Keywords
branch-and-bound, integer programming, bi-objective optimization, branch-and-price, orienteering
Enable JavaScript for citation tools and additional paper interactions.