A Generic Branch‐and‐Cut Algorithm for Multiobjective Optimization Problems: Application to the Multilabel Traveling Salesman Problem

This paper describes a generic branch‐and‐cut algorithm applicable to the solution of multiobjective optimization problems for which a lower bound can be defined as a polynomially solvable multiobjective problem. The algorithm closely follows standard branch and cut except for the definition of the lower and upper bounds and some optional speed‐up mechanisms. It is applied to a routing problem called the multilabel traveling salesman problem, a variant of the traveling salesman problem in which labels are attributed to the edges. The goal is to find a Hamiltonian cycle that minimizes the tour length and the number of labels in the tour. Implementations of the generic multiobjective branch‐and‐cut algorithm and speed‐up mechanisms are described. Computational experiments are conducted, and the method is compared to the classical ε‐constraint method.