✦ LIBER ✦

A branch-and-cut algorithm for the preemptive swapping problem

✍ Scribed by Charles Bordenave; Michel Gendreau; G. Laporte

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 247 KB
Volume: 59
Category: Article
ISSN: 0028-3045
DOI: 10.1002/net.20447

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In the swapping problem (SP), every vertex of a complete graph may supply and demand an object of a known type. A vehicle of unit capacity starting and ending its tour at an arbitrary vertex is available for carrying objects of given types between vertices. The SP consists of determining a minimum cost route that allows the vehicle to satisfy every supply and demand. This article investigates the preemptive version of the SP in which the objects are allowed to be dropped at temporary locations along the route. The problem is modeled as a mixed integer linear program which is solved by branch‐and‐cut. Computational results on random geometric instances containing up to 100 vertices and eight object types are reported. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

📜 SIMILAR VOLUMES

A branch-and-cut algorithm for the nonpr

A branch-and-cut algorithm for the nonpreemptive swapping problem

✍ Charles Bordenave; Michel Gendreau; Gilbert Laporte 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB 👁 1 views

The preemptive swapping problem on a tre

The preemptive swapping problem on a tree

✍ Shoshana Anily; Michel Gendreau; Gilbert Laporte 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 237 KB 👁 1 views

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

A branch-and-cut algorithm for the undir

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

✍ Gendreau, Michel; Laporte, Gilbert; Semet, Fr�d�ric 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB 👁 2 views

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 p

A branch-and-cut algorithm for the k-edg

A branch-and-cut algorithm for the k-edge connected subgraph problem

✍ F. Bendali; I. Diarrassouba; A.R. Mahjoub; M. Didi Biha; J. Mailfert 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 301 KB 👁 1 views

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 👁 2 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.