Adam N. Letchford

Printed in U.S.A. SEPARATING A SUPERCLASS OF COMB INEQUALITIES IN PLANAR GRAPHS (2008)

We give a simple O(n 3/2 log n) algorithm for finding a minimum weight odd circuit in planar graphs. By geometric duality, the same algorithm can be used to find minimum weight odd cuts. For general...

Exploiting planarity in separation routines for the symmetric traveling salesman problem (2008)

Many classes of valid and facet-inducing inequalities are known for the family of polytopes associated with the Symmetric Travelling Salesman Problem (STSP), including subtour elimination, 2-matching...

Letchford, Adam N., Pearson, Nicholas A.

At present, the most successful approach for solving large-scale instances of the Symmetric Traveling Salesman Problem to optimality is branch-and-cut. The success of branch-and-cut is due in large...

Good triangulations yield good tours (2008)

Letchford, Adam N., Pearson, Nicholas A.

Consider the following heuristic for planar Euclidean instances of the traveling salesman problem (TSP): select a subset of the edges which induces a planar graph, and solve either the TSP or its...

Separation algorithms for 0-1 knapsack polytopes (2008)

Konstantinos Kaparis, Adam N. Letchford

Valid inequalities for 0-1 knapsack polytopes often prove useful when tackling hard 0-1 Linear Programming problems. To use such inequalities effectively, one needs separation algorithms for them,...

Binary positive semidefinite matrices and associated integer polytopes (2008)

Sørensen, Michael Malmros, Letchford, Adam N.

On the separation of split cuts and related inequalities (2007)

Alberto Caprara, Adam N. Letchford

The split cuts of Cook, Kannan and Schrijver are general-purpose valid inequalities for integer programming which include a variety of other well-known cuts as special cases. To detect violated split...

On disjunctive cuts for combinatorial optimization (2007)

On the separation of split cuts and related inequalities (2007)

In the successful branch-and-cut approach to combinatorial optimization, linear inequalities are used as cutting planes within a branch-andbound framework. Although researchers often prefer to use...

Alberto Caprara, Adam N. Letchford

The split cuts of Cook, Kannan and Schrijver are general-purpose valid inequalities for integer programming which include a variety of other well-known cuts as special cases. To detect violated split...

Exploiting planarity in separation routines for the symmetric traveling salesman problem (2007)

Letchford, Adam. N., Pearson, Nicholas A.

At present, the most successful approach for solving large-scale instances of the Symmetric Traveling Salesman Problem to optimality is branch-and-cut. The success of branch-and-cut is due in large...

On the geometry of metrics embeddable in the real line (2007)

Letchford, Adam N., Seitz, Hanna, Theis, Dirk Oliver

For a fixed finite set $\{1,...,n\}$, we consider the set of metrics for which the metric space can be isometrically embedded in the real line. The convex hull of those metrics, $Q_n$, and its...

Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem (2007)

Kaparis, Konstantinos, Letchford, Adam N.

The 0-1 Multidimensional Knapsack Problem (0-1 MKP) is a well- known (and strongly N P -hard) combinatorial optimization problem with many applications. Up to now, the ma jority of upper bounding...

A Cutting Plane Algorithm for the Linear Arrangement Problem (2007)

Alberto Caprara, Adam N. Letchford

Given a graph G = (V, E) on n vertices, the Minimum Linear Arrangement Problem (MinLA) calls for a one-to-one function ψ: V → {1,..., n} which minimizes � {i,j}∈E |ψ(i) − ψ(j)|. MinLA is...

Odd minimum cut sets and b-matchings revisited (2006)

Letchford, Adam N., Theis, Dirk Oliver

The famous Padberg-Rao separation algorithm for b-matching polyhedra can be implemented to run in O(n^2m log(n^2/m)) time in the uncapacitated case, and in O(nm^2 log(n^2/m)) time in the capacitated...

Projection results for vehicle routing (2006)

Polynomial-time separation of a superclass of simple comb inequalities (2006)

A variety of integer programming formulations have been proposed for Vehicle Routing Problems (VRPs), including the so-called two- and three-index formulations, the set partitioning formulation, and...

Lisa K. Fleischer, Adam N. Letchford, Andrea Lodi

The comb inequalities are a well-known class of facet-inducing inequalities for the Traveling Salesman Problem, defined in terms of certain vertex sets called the handle and the teeth. We say that a...

Polynomial-time separation of a superclass of simple comb inequalities (2006)

Lisa K. Fleischer, Adam N. Letchford, Andrea Lodiffi

Abstract The comb inequalities are a well-known class of facet-inducing inequalities for the Traveling Salesman Problem, defined in terms of certain vertex sets called the handle and the teeth. We...

A Branch-and-Cut Algorithm for the Capacitated Open Vehicle Routing Problem (2006)

Letchford, Adam N., Lysgaard, Jens, Eglese, Richard W.

nullIn open vehicle routing problems, the vehicles are not required to return to the depot after completing service. In this paper, we present the first exact optimization algorithm for the open...

Good Triangulations Yield Good Tours (2005)

Exploiting planarity in separation routines for the symmetric traveling salesman problem (2005)

Consider the following heuristic for planar Euclidean instances of the Traveling Salesman Problem (TSP): select a subset of the edges which induces a planar graph, and solve either the TSP or its...

E.: A node-flow model for 1D stock cutting: Robust branch-cut-and-price (2005)

At present, the most successful approach to solving large-scale instances of the Symmetric Traveling Salesman Problem to optimality is branch-and-cut. The success of branch-and-cut is due in large...

Gleb Belov, Adam N. Letchford, Eduardo Uchoa

E.: A node-flow model for 1D stock cutting: Robust branch-cut-and-price (2005)

Gleb Belov, Adam N. Letchford, Eduardo Uchoa

Exploring the Relationship Between Max-Cut and Stable Set Relaxations (2004)

Monia Gi, Adam N. Letchford, Dipartimento Di Statistica

The max-cut and stable set problems are two fundamental N P-hard problems in combinatorial optimization. It has been known for a long time that any instance of the stable set problem can be easily...

Letters (2004)

Computing Good Allocations for Combinatorial Optimization Games (2004)

www.elsevier.com/locate/orl A fast algorithm for minimum weight odd circuits and cuts in planar graphs

Alberto Caprara, Michel X. Goemans, Adam N. Letchford

Much of the literature on cooperative games associated with combinatorial optimization problems is concerned with only one question: whether or not the core is empty. In this paper however we are...

An augment-and-branch-and-cut framework for mixed 0-1 programming (2003)

A New Branch-and-Cut Algorithm for the Capacitated Vehicle Routing Problem (2003)

Abstract. In recent years the branch-and-cut method, a synthesis of the classical branch-and-bound and cutting plane methods, has proven to be a highly successful approach to solving large-scale...

Jens Lysgaard, Adam N. Letchford, Richard W. Eglese

We present a new branch-and-cut algorithm for the capacitated vehicle routing problem (CVRP). The algorithm uses a variety of cutting planes, including capacity, framed capacity, generalized...

Binary Clutter Inequalities for Integer Programs (2003)

A new branch-and-cut algorithm for the capacitated vehicle routing problem (2003)

We introduce a new class of valid inequalities for general integer linear programs, called binary clutter (BC) inequalities. They include the {0, 1/2}-cuts of Caprara and Fischetti as a special case...

Adam N. Letchford, Jens Lysgaard, Richard W. Eglese

In open vehicle routing problems, the vehicles are not required to return to the depot after completing service. In this paper, we present the first exact optimization algorithm for the open version...

Strengthening chvátal-gomory cuts and gomory fractional cuts (2002)

Primal separation algorithms (2001)

Chvatal-Gomory and Gomory fractional cuts are well-known cutting planes for pure integer programming problems. Various methods for strengthening them are known, for example based on subadditive...

Primal cutting plane algorithms revisited (2001)

In a recent paper, the authors argued for a re-examination of primal cutting plane algorithms, in which cutting planes are used to enable a feasible solution to the original problem to be improved....

On the separation of maximally violated mod-k cuts (2000)

Dual fractional cutting plane algorithms, in which cutting planes are used to iteratively tighten a linear relaxation of an integer program, are well-known and form the basis of the highly successful...

Alberto Caprara, Matteo Fischetti, Adam N. Letchford

Abstract. Separation is of fundamental importance in cutting-plane based techniques for Integer Linear Programming (ILP). In recent decades, a considerable research effort has been devoted to the...

On the separation of maximally violated mod-k cuts (2000)

Alberto Caprara, Matteo Fischetti, Adam N. Letchford, Ax B

Separation is of fundamental importance in cutting-plane based techniques for Integer Linear Programming (ILP). In recent decades, a considerable research eort has been devoted to the denition of...

New Procedures in Branch and Cut for the Vehicle Routing Problem (1999)

Lysgaard, Jens, Letchford, Adam N., Eglese, Richard W.

A Branch and Cut algorithm for the Vehicle Routing Problem (1999)

Lysgaard, Jens, Letchford, Adam N., Eglese, Richard W.

On the Separation of Maximally Violated mod-k Cuts (Extended Abstract) (1998)

Alberto Caprara, Matteo Fischetti, Adam N. Letchford

Abstract Separation is of fundamental importance in cutting-plane based techniques for Integer Linear Programming (ILP). In recent decades, a considerable research effort has been devoted to the...

Polynomial-time separation of simple comb inequalities (1994)