𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Gendreau, Michel; Laporte, Gilbert; Semet, Fr�d�ric

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
120 KB
Volume
32
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

A branch and cut algorithm for the Stein
A branch and cut algorithm for the Steiner problem in graphs
✍ Lucena, A.; Beasley, J. E. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 165 KB 👁 2 views

In this paper, we consider the Steiner problem in graphs, which is the problem of connecting together, at minimum cost, a number of vertices in an undirected graph with nonnegative edge costs. We use the formulation of this problem as a shortest spanning tree (SST) problem with additional constraint

Approximation algorithms for the capacit
Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries
✍ Shoshana Anily; Julien Bramel 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB

We consider the Capacitated Traveling Salesman Problem with Pickups and Deliveries (CTSPPD). This problem is characterized by a set of n pickup points and a set of n delivery points. A single product is available at the pickup points which must be brought to the delivery points. A vehicle of limited

A branch-and-cut algorithm for the resou
A branch-and-cut algorithm for the resource-constrained minimum-weight arborescence problem
✍ Fischetti, Matteo; Vigo, Daniele 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB 👁 1 views

In this paper, we present a branch-and-cut algorithm for the exact solution of an NP-hard extension of the well-known Minimum-Weight Arborescence (MWA) problem, in which resource constraints for each node are considered. This Resource-Constrained Minimum-Weight Arborescence (RMWA) problem arises, e.

A branch-and-cut algorithm for solving g
A branch-and-cut algorithm for solving generalized multiperiod Steiner problems in graphs
✍ Suhl, Uwe H.; Hilbert, Heinrich 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 163 KB 👁 1 views

Given is an undirected graph with positive or negative edge weights which represent a profit if an investment such as installing a gas pipe takes place in a given time period. A certain part of the graph may already be piped in previous periods. The task is to extend the piped subgraph in the most p

A branch-and-cut algorithm for solving a
A branch-and-cut algorithm for solving an intraring synchronous optical network design problem
✍ Lee, Youngho; Sherali, Hanif D.; Han, Junghee; Kim, Seong-in 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 133 KB 👁 1 views

In this paper, we deal with a network design problem arising from the deployment of synchronous optical networks (SONET), a standard of transmission using optical fiber technology. The problem is to find an optimal clustering of traffic demands in the network such that the total number of node assig