A branch‐and‐cut algorithm for the undirected selective traveling salesman problem | Zendy

Gendreau Michel | Zendy; Laporte Gilbert | Zendy; Semet Frédéric | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

A branch‐and‐cut algorithm for the undirected selective traveling salesman problem

Author(s) -

Gendreau Michel,

Laporte Gilbert,

Semet Frédéric

Publication year - 1998

Publication title -

networks

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.977

H-Index - 64

eISSN - 1097-0037

pISSN - 0028-3045

DOI - 10.1002/(sici)1097-0037(199812)32:4<263::aid-net3>3.0.co;2-q

Subject(s) - travelling salesman problem , undirected graph , combinatorics , mathematics , algorithm , graph , constant (computer programming) , computer science , programming language

The Selective Traveling Salesman Problem (STSP) is defined on a graph in which profits are associated with vertices and costs are associated with edges. Some vertices are compulsory. The aim is to construct a tour of maximal profit including all compulsory vertices and whose cost does not exceed a preset constant. We developed several classes of valid inequalities for the symmetric STSP and used them in a branch‐and‐cut algorithm. Depending on problem parameters, the proposed algorithm can solve instances involving up to 300 vertices. © 1998 John Wiley & Sons, Inc. Networks 32:263–273, 1998

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research