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

作者：Jozefowiez Nicolas^*; Laporte Gilbert; Semet Frederic

来源：INFORMS Journal on Computing, 2012, 24(4): 554-564.

DOI：10.1287/ijoc.1110.0476

• decision analysis
• multiple criteria
• programming
• multiple criteria
• programming
• integer
• algorithm
• cutting plane
• networks-graphs
• traveling salesman

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 is an element of-constraint method.

• 出版日期2012