Professor Adam Letchford FORS

Professor

Research Overview

Professor Letchford's research is in optimisation, i.e., finding the best solution to problems that have a huge (possibly infinite) number of solutions.  Optimisation is an inter-disciplinary subject, lying at the interface between Operational Research, Computer Science, Applied Mathematics and Engineering.Professor Letchford concentrates mainly on methods for solving optimisation problems to proven optimality, rather than heuristic methods.  He also has a particular interest in combinatorial optimisation problems, i.e., problems in which variables are restricted to take integer (whole-number) values.

An aggressive reduction scheme for the simple plant location problem
Letchford, A., Miller, S. 1/05/2014 In: European Journal of Operational Research. 234, 3, p. 674-682. 9 p.
Journal article

A compact variant of the QCR method for quadratically constrained quadratic 0-1 programs
Galli, L., Letchford, A. 04/2014 In: Optimization Letters. 8, 4, p. 1213-1224. 12 p.
Journal article

Unbounded convex sets for non-convex mixed-integer quadratic programming
Burer, S., Letchford, A. 1/02/2014 In: Mathematical Programming. 143, 1-2, p. 231-256. 26 p.
Journal article

A dynamic programming heuristic for the quadratic knapsack problem
Djeumou Fomeni, F., Letchford, A. 02/2014 In: INFORMS Journal on Computing. 26, 1, p. 173-182. 10 p.
Journal article

Iterated Chvatal-Gomory cuts and the geometry of numbers
Aliev, I., Letchford, A. 2014 In: SIAM Journal on Optimization.
Journal article

Pricing routines for vehicle routing with time windows on road networks
Letchford, A., Nasiri, S.D. 2014 Lancaster University : The Department of Management Science, 20 p.
Working paper

A polyhedral approach to the single row facility layout problem
Amaral, A.R.S., Letchford, A. 10/2013 In: Mathematical Programming. 141, 1-2, p. 453-477. 25 p.
Journal article

Compact formulations for the Steiner Traveling Salesman Problem and related problems
Letchford, A., Dehghan Nasiri, S. 2013 In: European Journal of Operational Research. 228, 1, p. 83-92. 10 p.
Journal article

Fast bounding procedures for large instances of the simple plant location problem
Letchford, A.N., Miller, S.J. 05/2012 In: Computers and Operations Research. 39, 5, p. 985-990. 6 p.
Journal article

Complexity results for the gap inequalities for the max-cut problem
Galli, L., Kaparis, K., Letchford, A.N. 05/2012 In: Operations Research Letters. 40, 3, p. 149-152. 4 p.
Journal article

Binary positive semidefinite matrices and associated integer polytopes
Letchford, A.N., Sorensen, M.M. 02/2012 In: Mathematical Programming. 131, 1-2, p. 253-271. 19 p.
Journal article

Gap inequalities for the max-cut problem: a cutting-plane algorithm
Galli, L., Kaparis, K., Letchford, A. 2012 In: Combinatorial Optimization. Berlin : Springer p. 178-188. 11 p.
Chapter (peer-reviewed)

Review of “The Chvátal-Gomory closure of a strictly convex body”.
Letchford, A. 2012 In: Mathematical Reviews.
Book/Film/Article review

A new separation algorithm for the Boolean quadric and cut polytopes
Letchford, A. 2012
Conference paper

Cutting planes for a stochastic network loading problem
Letchford, A. 2012
Conference paper

On the gap inequalities for the max-cut problem
Letchford, A. 2012
Conference paper

Non-convex mixed-integer nonlinear programming: a survey
Burer, S., Letchford, A. 2012 In: Surveys in Operations Research and Management Science. 17, 2, p. 97-106. 10 p.
Journal article

Review of “The Linear Ordering Problem: Exact and Heuristic Methods in Combinatorial Optimization”
Letchford, A. 2012 In: Interfaces. 42, 3, 2 p.
Book/Film/Article review

A polyhedral approach to the single-row facility layout problem
Letchford, A. 2012
Conference paper

Review of “Projecting systems of linear inequalities with binary variables”
Letchford, A. 2012 In: Mathematical Reviews.
Book/Film/Article review

Generalised network design polyhedra
Feremans, C., Labbé, M., Letchford, A.N., Salazar-González, J. 09/2011 In: Networks. 58, 2, p. 125-136. 12 p.
Journal article

On the membership problem for the {0, 1/2}-closure
Letchford, A.N., Pokutta, S., Schulz, A. 09/2011 In: Operations Research Letters. 39, 5, p. 301-304. 4 p.
Journal article

Cover Inequalities
Kaparis, K., Letchford, A.N. 02/2011 In: Wiley Encyclopedia of Operations Research and Management Science. Wiley
Entry for encyclopedia/dictionary

A polyhedral approach to the single row facility layout problem
Letchford, A.N., Amaral, A. 2011 Lancaster University : The Department of Management Science
Working paper

A New Approach to the Stable Set Problem Based on Ellipsoids
Giandomenico, M., Letchford, A.N., Rossi, F., Smriglio, S. 2011 Lancaster University : The Department of Management Science
Working paper

Reformulating mixed-integer quadratically constrained quadratic programs
Galli, L., Letchford, A.N. 2011 Lancaster University : The Department of Management Science, 23 p.
Working paper

An approach to the stable set problem based on ellipsoids
Giandomenico, M., Letchford, A.N., Rossi, F., Smriglio, S. 2011 In: Integer Programming and Combinatorial Optimization. Berlin : Springer p. 223-234. 12 p.
Chapter (peer-reviewed)

Computing compatible tours for the traveling salesman problem
Fortini, M., Letchford, A.N., Lodi, A., Wenger, K.M. 2011 In: Mathematical Programming Computation. 3, 1, p. 59-78. 20 p.
Journal article

Decorous lower bounds for minimum linear arrangement
Caprara, A., Letchford, A.N., Salazar, J.J. 2011 In: INFORMS Journal on Computing. 23, 1, p. 26-40. 15 p.
Journal article

Mathematical programming approaches to the traveling salesman problem
Letchford, A.N., Lodi, A. 2011 In: Wiley Encyclopedia of Operations Research and Management Science. John Wiley and Sons Ltd
Entry for encyclopedia/dictionary

Review of “Orbital branching”
Letchford, A. 2011 In: Mathematical Reviews.
Book/Film/Article review

Review of “On the Chvátal rank of linear relaxations of the stable set polytope”
Letchford, A. 2011 In: Mathematical Reviews.
Book/Film/Article review

Review of “On the dominant of the s-t cut polytope: vertices, facets and adjacency”
Letchford, A. 2011 In: Mathematical Reviews.
Book/Film/Article review

Gap inequalities for non-convex mixed-integer quadratic programs
Galli, L., Kaparis, K., Letchford, A.N. 2011 In: Operations Research Letters. 39, 5, p. 297-300. 4 p.
Journal article

Some unbounded convex sets arising in non-convex MIQP
Letchford, A. 2011
Conference paper

Convex hulls for non-convex mixed-integer quadratic programs
Letchford, A. 2011
Conference paper

Separation algorithms for 0-1 knapsack polytopes
Kaparis, K., Letchford, A. 07/2010 In: Mathematical Programming. 124, 1-2, p. 69-91. 23 p.
Journal article

Review of "Applying mod-k-cuts for solving linear ordering problems"
Letchford, A.N. 2010 In: Mathematical Reviews.
Book/Film/Article review

Review of "Coefficient strengthening: a tool for reformulating mixed-integer programs"
Letchford, A.N. 2010 In: Mathematical Reviews.
Book/Film/Article review

Review of "Gear composition of stable set polytopes and G-perfection"
Letchford, A.N. 2010 In: Mathematical Reviews.
Book/Film/Article review

Review of "Minimal inequalities for an infinite relaxation of integer programs"
Letchford, A.N. 2010 In: Mathematical Reviews.
Book/Film/Article review

Review of "Extended formulations in combinatorial optimization"
Letchford, A.N. 2010 In: Mathematical Reviews.
Book/Film/Article review

On a class of metrics related to graph layout problems
Letchford, A.N., Reinelt, G., Seitz, H., Theis, D.O. 2010 In: Linear Algebra and its Applications. 433, 11-12, p. 1760-1777. 18 p.
Journal article

Small bipartite subgraph polytopes
Galli, L., Letchford, A.N. 2010 In: Operations Research Letters. 38, 5, p. 337-340. 4 p.
Journal article

Integer quadratic quasi-polyhedra
Letchford, A.N. 2010 In: Integer Programming and Combinatorial Optimization. Berlin : Springer p. 258-270. 13 p.
Chapter (peer-reviewed)

The Compatible Tour Heuristic for the Symmetric Traveling Salesman Problem
Fortini, M., Letchford, A.N., Lodi, A., Wenger, K.M. 2010 Lancaster University : The Department of Management Science
Working paper

New techniques for cost sharing in combinatorial optimization games
Caprara, A., Letchford, A.N. 2010 In: Mathematical Programming. 124, 1-2, p. 93-118. 26 p.
Journal article

Generalised network design polyhedra
Letchford, A. 2010
Conference paper

Review of "A note on the continuous mixing sets"
Letchford, A.N. 2009 In: Mathematical Reviews.
Book/Film/Article review

Review of "Generalized mixed integer rounding inequalities: facets for infinite group polyhedra
Letchford, A.N. 2009 In: Mathematical Reviews.
Book/Film/Article review

Review of "MIR closures of polyhedral sets"
Letchford, A.N. 2009 In: Mathematical Reviews.
Book/Film/Article review

On non-convex quadratic programming with box constraints
Burer, S., Letchford, A.N. 2009 In: SIAM Journal on Optimization. 20, 2, p. 1073-1089. 17 p.
Journal article

Review of "Local cuts revisited"
Letchford, A.N. 2009 In: Mathematical Reviews.
Book/Film/Article review

Exploiting sparsity in pricing routines for the capacitated arc routing problem
Letchford, A.N., Oukil, A. 2009 In: Computers and Operations Research. 36, 7, p. 2320-2327. 8 p.
Journal article

An application of the Lovasz-Schrijver M(K,K) operator to the stable set problem
Giandomenico, M., Letchford, A.N., Rossi, F., Smriglio, S. 2009 In: Mathematical Programming. 120, 2, p. 381-401. 21 p.
Journal article

A branch-and-cut algorithm for single-row facility layout problems
Letchford, A. 2009
Conference paper

A polyhedral approach to single-row facility layout problems
Letchford, A. 2009
Conference paper

Knapsack-based cutting planes for the max-cut problem
Letchford, A. 2009
Conference paper

Local and global lifted cover inequalities for the multidimensional knapsack problem
Kaparis, K., Letchford, A.N. 1/04/2008 In: European Journal of Operational Research. 186, 1, p. 91-103. 13 p.
Journal article

Review of "FPTAS for optimizing polynomials over the mixed-integar points of polytopes in fixed dimension"
Letchford, A.N. 2008 In: Mathematical Reviews.
Book/Film/Article review

Review of "New cutting-planes for the time and/or precedence-constrained ATSP and directed VRP"
Letchford, A.N. 2008 In: Mathematical Reviews.
Book/Film/Article review

Review of "A branch-and-cut algorithm for a resource-constrained scheduling problem"
Letchford, A.N. 2008 In: Mathematical Reviews.
Book/Film/Article review

Review of "On clique separators, nearly chordal graphs and the maximum weight stable set problem"
Letchford, A.N. 2008 In: Mathematical Reviews.
Book/Film/Article review

Review of "Projected Chvátal-Gomory cuts for mixed integer linear programs"
Letchford, A.N. 2008 In: Mathematical Reviews.
Book/Film/Article review

Binary positive semidefinite matrices and associated integer polytopes
Letchford, A.N., Sorensen, M.M. 2008 In: Integer Programming and Combinatorial Optimization. Berlin : Springer p. 125-139. 15 p.
Chapter (peer-reviewed)

Preface: Combinatorial optimization
Clark, A., Eglese, R., Letchford, A., Wright, M. 2008 In: Discrete Applied Mathematics. 156, 3, 2 p.
Editorial

The traveling salesman problem: a book review
Letchford, A.N., Lodi, A. 12/2007 In: 4OR: A Quarterly Journal of Operations Research. 5, 4, 3 p.
Book/Film/Article review

Exploiting planarity in separation routines for the symmetric travelling salesman problem
Letchford, A.N., Pearson, N. 2008 In: Discrete Optimization. 5, 2, p. 220-230. 11 p.
Journal article

Good triangulations yield good tours
Letchford, A.N., Pearson, N. 2008 In: Computers and Operations Research. 35, 2, p. 638-647. 10 p.
Journal article

Odd minimum cut-sets and b-matchings revisited
Letchford, A.N., Reinelt, G., Theis, D.O. 2008 In: SIAM Journal of Discrete Mathematics. 22, 4, p. 1480-1487. 8 p.
Journal article

Separation algorithms for 0-1 knapsack polytopes
Letchford, A. 2008
Conference paper

On mixed-integer quadratic programming with box constraints
Letchford, A. 2008
Conference paper

Binary positive semidefinite matrices and associated integer polytopes
Letchford, A. 2008
Conference paper

The max-cut and max-clique problems: linear versus semidefinite programming
Letchford, A. 2008
Conference paper

Separation algorithms for 0-1 knapsack polytopes
Letchford, A. 2008
Conference paper

Editorial: Mixed integer programming
Lee, J., Letchford, A.N. 1/03/2007 In: Discrete Optimization. 4, 1, 2 p.
Editorial

Review of "Using critical sets to solve the maximum independent set problem"
Letchford, A.N. 2007 In: Mathematical Reviews.
Book/Film/Article review

Review of "Integer programming formulations for the two 4-hop constrained paths problem"
Letchford, A.N. 2007 In: Mathematical Reviews.
Book/Film/Article review

Review of "Using mixed-integer programming to solve power grid blackout problems"
Letchford, A.N. 2007 In: Mathematical Reviews.
Book/Film/Article review

Review of "A new min-cut max-flow ratio for multicommodity flows"
Letchford, A.N. 2007 In: Mathematical Reviews.
Book/Film/Article review

A branch-and-cut-algorithm for the capacitated open vehicle routing problem
Letchford, A.N., Lysgaard, J., Eglese, R.W. 2007 In: Journal of the Operational Research Society. 58, 12, p. 1642-1651. 10 p.
Journal article

Review of "Optimization with binet matrices"
Letchford, A.N. 2007 In: Mathematical Reviews.
Book/Film/Article review

Exploring the relationship between max-cut and stable set relaxations
Giandomenico, M., Letchford, A.N. 03/2006 In: Mathematical Programming. 106, 1, p. 159-175. 17 p.
Journal article

A branch-and-cut algorithm for the capacitated open vehicle routing problem
Letchford, A.N., Lysgaard, J., Eglese, R.W. 2006 Lancaster University : The Department of Management Science
Working paper

Polynomial-time separation of a superclass of simple comb inequalities
Fleischer, L.K., Letchford, A.N., Lodi, A. 2006 In: Mathematics of Operations Research. 31, 4, p. 696-713. 18 p.
Journal article

Projection results for vehicle routing
Letchford, A.N., Salazar, J.J. 2006 In: Mathematical Programming. 105, 2-3, p. 251-274. 24 p.
Journal article

Computing good allocations for combinatorial optimization games
Caprara, A., Letchford, A.N. 2005 Lancaster University : The Department of Management Science
Working paper

Exploiting planarity in separation routines for the symmetric travelling salesman problem
Letchford, A.N., Pearson, N. 2005 Lancaster University : The Department of Management Science
Working paper

A fast algorithm for minimum weight odd cuts and circuits in planar graphs
Letchford, A.N., Pearson, N. 2005 In: Operations Research Letters. 33, 6, p. 625-628. 4 p.
Journal article

Review of "The Vehicle Routing Problem"
Letchford, A.N. 07/2004 In: Operations Research Letters. 32, 4, 2 p.
Book/Film/Article review

Review of "Introduction to the Theory of Cooperative Games"
Letchford, A.N. 2004 In: Journal of the Operational Research Society. 55, 7, 2 p.
Book/Film/Article review

A faster exact separation algorithm for blossom inequalities
Letchford, A.N., Reinelt, G., Theis, D.O. 2004 In: Integer Programming and Combinatorial Optimization. Berlin : Springer p. 19-52. 34 p.
Chapter (peer-reviewed)

A new branch-and-cut algorithm for the capacitated vehicle routing problem
Letchford, A.N., Eglese, R.W., Lysgaard, J. 2004 In: Mathematical Programming. 100, 2, p. 423-445. 23 p.
Journal article

Primal separation algorithms
Lodi, A., Letchford, A.N. 2003 In: 4OR: A Quarterly Journal of Operations Research. 1, 3, p. 209-224. 16 p.
Journal article

Binary clutter inequalities for integer programs
Letchford, A.N. 2003 In: Mathematical Programming. 98, 1-3, p. 201-221. 21 p.
Journal article

An augment-and-branch-and-cut framework for mixed 0-1 programming
Letchford, A.N., Lodi, A. 2003 In: Combinatorial Optimization. Berlin : Springer p. 119-133. 15 p.
Chapter (peer-reviewed)

On the separation of split cuts and related inequalities
Caprara, A., Letchford, A.N. 2003 In: Mathematical Programming. 94, 2-3, p. 279-294. 16 p.
Journal article

Polynomial-time separation of simple comb inequalities
Letchford, A.N., Lodi, A. 2003 Lancaster University : The Department of Management Science
Working paper

A new branch-and-cut algorithm for capacitated vehicle routing problems
Eglese, R.W., Letchford, A.N., Lysgaard, J. 2003 Lancaster University : The Department of Management Science
Working paper

Review of "Approximation Algorithms"
Letchford, A.N. 07/2002 In: Journal of the Operational Research Society. 53, 7, 2 p.
Book/Film/Article review

Multistars, partial multistars and the capacitated vehicle routing problem
Lysgaard, J., Eglese, R.W., Letchford, A.N. 2002 In: Mathematical Programming. 94, 1, p. 21-40. 20 p.
Journal article

Primal cutting plane algorithms revisited
Letchford, A.N., Lodi, A. 2002 In: Mathematical Methods of Operational Research. 56, 1, p. 67-81. 15 p.
Journal article

Polynomial-time separation of simple comb inequalities
Lodi, A., Letchford, A.N. 2002 In: Integer Programming and Combinatorial Optimization. Berlin : Springer p. 93-108. 16 p.
Chapter (peer-reviewed)

Strengthening Chvatal-Gomory cuts and Gomory fractional cuts
Letchford, A.N., Lodi, A. 2002 In: Operations Research Letters. 30, 2, p. 74-82. 9 p.
Journal article

Totally tight Chvatal-Gomory cuts
Letchford, A.N. 2002 In: Operations Research Letters. 30, 2, p. 71-73. 3 p.
Journal article

Binary clutter inequalities for integer programs
Letchford, A.N. 2002 Lancaster University : The Department of Management Science
Working paper

On disjunctive cuts for combinatorial optimization
Letchford, A.N. 2001 In: Journal of Combinatorial Optimization. 5, 3, p. 299-315. 17 p.
Journal article

The general routing problem
Letchford, A.N., Eglese, R.W. 2001 In: Encyclopedia of Optimization, Vol II (E - Integer). Kluwer Academic Publishers 2 p.
Entry for encyclopedia/dictionary

A cutting plane algorithm for the general routing problem
Corberan, A., Sanchis, J.M., Letchford, A.N. 2001 In: Mathematical Programming. 90, 2, p. 291-316. 26 p.
Journal article

Analysis of upper bounds for the pallet loading problem
Letchford, A.N., Amaral, A.R.S. 2001 In: European Journal of Operational Research. 132, 3, p. 582-593. 12 p.
Journal article

Review of "Theory of Linear and Integer Programming"
Letchford, A.N. 2000 In: Journal of the Operational Research Society. 51, 7, 2 p.
Book/Film/Article review

Review of "Model Building in Mathematical Programming"
Letchford, A.N. 2000 In: Journal of the Operational Research Society. 51, 10, 2 p.
Book/Film/Article review

Separating a superclass of comb inequalities in planar graphs
Letchford, A.N. 2000 In: Mathematics of Operations Research. 25, 3, p. 443-454. 12 p.
Journal article

On the separation of maximally violated mod-k cuts
Caprara, A., Fischetti, M., Letchford, A.N. 2000 In: Mathematical Programming. 87, 1, p. 37-56. 20 p.
Journal article

Polyhedral theory for arc routing problems
Eglese, R.W., Letchford, A.N. 2000 In: Arc Routing. Dordrecht : Kluwer Academic Publishers p. 199-230. 32 p.
Chapter (peer-reviewed)

On the separation of maximally violated mod-k cuts
Caprara, A., Fischetti, M., Letchford, A.N. 1999 In: Integer Programming and Combinatorial Optimization. Berlin : Springer p. 87-98. 12 p.
Chapter (peer-reviewed)

The general routing polyhedron: a unifying framework
Letchford, A.N. 1999 In: European Journal of Operational Research. 112, 1, p. 122-133. 12 p.
Journal article

Action rules extracted by machine induction from feature-coded self reports
Letchford, A.N., Clarke, D.D. 1998 In: Journal of Social Behaviour and Personality. 13, p. 33-50. 18 p.
Journal article

The rural postman problem with deadline classes
Eglese, R.W., Letchford, A.N. 1998 In: European Journal of Operational Research. 105, 3, p. 390-400. 11 p.
Journal article

New inequalities for the general routing problem
Letchford, A.N. 1997 In: European Journal of Operational Research. 96, 2, p. 317-322. 6 p.
Journal article

Allocation of school bus contracts by integer programming
Letchford, A.N. 1996 In: Journal of the Operational Research Society. 47, 3, p. 369-372. 4 p.
Journal article

Rules from behaviour: the use of a computational 'rule-finder'as a tool for social psychology
Clarke, D.D., Letchford, A.N. 1995 In: British Psychological Society Social Psychology Section Newsletter. 33, 10 p.
Letter