A generic branch-and-cut algorithm for multiobjective optimization problems: Application to the multilabel traveling Salesman Problem

Nicolas Jozefowiez, Gilbert Laporte, Frédéric Semet

Research output: Contribution to journalArticle

18 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)554-564
Number of pages11
JournalINFORMS Journal on Computing
Issue number4
Publication statusPublished - Sep 2012


  • Algorithm
  • Cutting plane
  • Decision analysis
  • Integer
  • Multiple criteria
  • Networks-graphs
  • Programming
  • Traveling salesman

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Cite this