### Abstract

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 language | English |
---|---|

Pages (from-to) | 554-564 |

Number of pages | 11 |

Journal | INFORMS Journal on Computing |

Volume | 24 |

Issue number | 4 |

DOIs | |

Publication status | Published - Sep 2012 |

### Keywords

- 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

*INFORMS Journal on Computing*,

*24*(4), 554-564. https://doi.org/10.1287/ijoc.1110.0476