TITLE

The Covering Tour Problem

AUTHOR(S)
Gendreau, Michel; Laporte, Gilbert; Semet, Frédéric
PUB. DATE
July 1997
SOURCE
Operations Research;Jul/Aug97, Vol. 45 Issue 4, p568
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
The Covering Tour Problem (CTP) is defined on a graph G = (V ∪ W, E), where W is a set of vertices that must be covered. The CTP consists of determining a minimum length Hamiltonian cycle on a subset of V such that every vertex of W is within a prespecified distance from the cycle. The problem is first formulated as an integer linear program, polyhedral properties of several classes of constraints are investigated, and an exact branch-and-cut algorithm is developed. A heuristic is also described. Extensive computational results are presented.
ACCESSION #
9709304974

 

Related Articles

  • Polyhedral results and a Branch-and-cut algorithm for the $$k$$-cardinality tree problem. Simonetti, Luidi; da Cunha, Alexandre Salles; Lucena, Abilio // Mathematical Programming;Dec2013, Vol. 142 Issue 1/2, p511 

    Given an undirected graph $$G$$ with vertex and edge weights, the $$k$$ -cardinality tree problem asks for a minimum weight tree of $$G$$ containing exactly $$k$$ edges. In this paper we consider a directed graph reformulation of the problem and carry out a polyhedral investigation of the...

  • CLUSTERING BASED POLYHEDRAL CONIC FUNCTIONS ALGORITHM IN CLASSIFICATION. OZTURK, GURKAN; CIFTCI, MEHMET TAHIR // Journal of Industrial & Management Optimization;Jul2015, Vol. 11 Issue 3, p921 

    In this study, a new algorithm based on polyhedral conic func tions (PCFs) is developed to solve multi-class supervised data classiffication problems. The k PCFs are constructed for each class in order to separate it from the rest of the data set. The k-means algorithm is applied to find...

  • DCA based algorithms for multiple sequence alignment (MSA). Le Thi, Hoai; Pham Dinh, Tao; Belghiti, Moulay // Central European Journal of Operations Research;Sep2014, Vol. 22 Issue 3, p501 

    In the last years many techniques in bioinformatics have been developed for the central and complex problem of optimally aligning biological sequences. In this paper we propose a new optimization approach based on DC (Difference of Convex functions) programming and DC Algorithm (DCA) for the...

  • The traveling salesman problem with pickup and delivery: polyhedral results and a branch-and-cut algorithm. Dumitrescu, Irina; Ropke, Stefan; Cordeau, Jean-Fran�ois; Laporte, Gilbert // Mathematical Programming;Feb2010, Vol. 121 Issue 2, p269 

    The Traveling Salesman Problem with Pickup and Delivery (TSPPD) is defined on a graph containing pickup and delivery vertices between which there exists a one-to-one relationship. The problem consists of determining a minimum cost tour such that each pickup vertex is visited before its...

  • Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations. Rendl, Franz; Rinaldi, Giovanni; Wiegele, Angelika // Mathematical Programming;Feb2010, Vol. 121 Issue 2, p307 

    We present a method for finding exact solutions of Max-Cut, the problem of finding a cut of maximum weight in a weighted graph. We use a Branch-and-Bound setting that applies a dynamic version of the bundle method as bounding procedure. This approach uses Lagrangian duality to obtain a...

  • WAREHOUSE PROBLEM.  // Encyclopedia of Operations Research & Management Science;2001, p885 

    The entry defines the term warehouse problem as used in operations research and management science. The warehouse problem is determining the optimal pattern of purchases, storage, and sales for the next n months of a warehouse, which has fixed capacity and an initial stock of a certain product...

  • LP-BASED COMBINATORIAL PROBLEM SOLVING. Hoffman, K.; Padberg, M. // Annals of Operations Research;1985, Vol. 4 Issue 1-4, p145 

    A tutorial outline of the polyhedral theory that underlies linear programming (LP)-based combinatorial problem solving is given. Design aspects of a combinatorial problem solver are discussed in general terms. Three computational studies in combinatorial problem solving using the polyhedral...

  • On degeneracy in linear programming and related problems. George, Karen; Osborae, M. R. // Annals of Operations Research;1993, Vol. 46/47 Issue 1-4, p343 

    Methods related to Wolfe's recursive method for the resolution of degeneracy in linear programming are discussed, and a nonrecursive variant which works with probability one suggested. Numerical results for both nondegenerate problems and problems constructed to have degenerate optima are...

  • Semidefinite Programming Based Algorithms for the Sparsest Cut Problem. Meira, Luis A.A.; Miyazawa, Flávio K. // RAIRO -- Operations Research;Apr2011, Vol. 45 Issue 2, p75 

    In this paper we analyze a known relaxation for the Sparsest Cut problem based on positive semidefinite constraints, and we present a branch and bound algorithm and heuristics based on this relaxation. The relaxed formulation and the algorithms were tested on small and moderate sized instances....

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics