Publications

Journal Articles

• A.N. Letchford & S.D. Nasiri (2013) Compact formulations of the Steiner TSP and related problems. Eur. J. Oper. Res., 228, 83-92. (PDF)
• S. Burer & A.N. Letchford (2012) Non-convex mixed-integer nonlinear programming: a survey. Surveys in Oper. Res. and Mgmt. Sci., 17(2), 97-106. (PDF)
• L. Galli, K. Kaparis & A.N. Letchford (2012) Complexity results for the gap inequalities for the max-cut problem. Oper. Res. Lett., 40(3), 149-152. (PDF)
• A.N. Letchford & M.M. Sørensen (2012) Binary positive semidefinite matrices and associated integer polytopes. Math. Program., 131(1), 253-271. (PDF)
• A.N. Letchford & S.J. Miller (2012) Fast bounding procedures for large instances of the simple plant location problem. Comp. & Oper. Res., 39(5), 985-990. (PDF)
• A.N. Letchford, S. Pokutta & A.S. Schulz (2011) On the membership problem for the {0, 1/2}-closure. Oper. Res. Lett., 39(5), 301–304. (PDF)
• L. Galli, K. Kaparis & A.N. Letchford (2011) Gap inequalities for non-convex mixed-integer quadratic programs. Oper. Res. Lett., 39(5), 297–300. (PDF)
• C. Feremans, M. Labbé, A.N. Letchford & J.J. Salazar (2011) On generalised network design polyhedra. Networks, 58(2), 125-136. (PDF)
• M. Fortini, A.N. Letchford, A. Lodi & K.M. Wenger (2011) Computing compatible tours for the traveling salesman problem. Math. Program. Comput., 3(1), 59-78. (PDF)
• A. Caprara, A.N. Letchford & J.J. Salazar (2011) Decorous lower bounds for minimum linear arrangement. INFORMS J. Comput., 23(1), 26-40. (PDF)
• A.N. Letchford, G. Reinelt, H. Seitz & D.O. Theis (2010) On a class of metrics related to graph layout problems. Lin. Alg. Appl., 433(11-12), 1760-1777. (PDF)
• L. Galli & A.N. Letchford (2010) Small bipartite subgraph polytopes. Oper. Res. Lett., 38(5), 337-340. (PDF)
• K. Kaparis & A.N. Letchford (2010) Separation algorithms for 0-1 knapsack polytopes. Math. Program., 124(1-2), 69-91. (PDF)
• A. Caprara & A.N. Letchford (2010) New techniques for cost sharing in combinatorial optimization games. Math. Program., 124(1-2), 93-118. (PDF)
• S. Burer & A.N. Letchford (2009) On non-convex quadratic programming with box constraints. SIAM J. Opt., 20(2), 1073-1089. (PDF)
• M. Giandomenico, A.N. Letchford, F. Rossi & S. Smriglio (2009) An application of the Lovász-Schrijver M(K,K) operator to the stable set problem. Math. Program., 120(2), 381-401. (PDF)
• A.N. Letchford & A. Oukil (2009) Exploiting sparsity in pricing routines for the capacitated arc routing problem. Comp. & Oper. Res., 36(7), 2320-2327. (PDF)
• A.N. Letchford, G. Reinelt & D.O. Theis (2008) Odd minimum cut-sets and b-matchings revisited. SIAM J. Discr. Math., 22(4), 1480-1487. (PDF) © SIAM.
• A.N. Letchford & N.A. Pearson (2008) Exploiting planarity in separation routines for the symmetric traveling salesman problem. Discr. Opt., 5(2), 220-230. (PDF) © Elsevier.
• K. Kaparis & A.N. Letchford (2008) Local and global lifted cover inequalities for the multidimensional knapsack problem. Eur. J. Opl Res., 186(1), 91–103. (PDF) © Elsevier.
• A.N. Letchford & N.A. Pearson (2008) Good triangulations yield good tours. Comp. & Oper. Res., 35(2), 638-647. (PDF) © Elsevier.
• A.N. Letchford, J. Lysgaard & R.W. Eglese (2007) A branch-and-cut algorithm for the capacitated open vehicle routing problem. J. Opl Res. Soc., 58(12), 1642-1651. (PDF) © Palgrave.
• L.K. Fleischer, A.N. Letchford & A. Lodi (2006) Polynomial-time separation of a superclass of simple comb inequalities. Math. Oper. Res., 31(4), 696-713. (PDF) © INFORMS.
• M. Giandomenico & A.N. Letchford (2006) Exploring the relationship between max-cut and stable set relaxations. Math. Program., 106(1), 159-175. (PDF) © Springer.
• A.N. Letchford & J.J. Salazar (2006) Projection results for vehicle routing. Math. Program., 105(2-3), 251-274. (PDF) © Springer.
• A.N. Letchford & N.A. Pearson (2005) A fast algorithm for minimum weight odd circuits and cuts in planar graphs. Oper. Res. Lett., 33(6), 625-628. (PDF) © Elsevier.
• J. Lysgaard, A.N. Letchford & R.W. Eglese (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Program., 100(2), 423-445. (PDF) © Springer.
• A.N. Letchford & A. Lodi (2003) Primal separation algorithms. 4OR: Quart. J. of Oper. Res., 1(3), 209-224. (PDF) © Springer.
• A.N. Letchford (2003) Binary clutter inequalities for integer programs. Math. Program., 98(1-3), 201-221. (PDF) © Springer.
• A. Caprara & A.N. Letchford (2003) On the separation of split cuts and related inequalities. Math. Program., 94(2-3), 279-294. (PDF) © Springer.
• A.N. Letchford, R.W. Eglese & J. Lysgaard (2002) Multistars, partial multistars and the capacitated vehicle routing problem. Math. Program., 94(1), 21-40. (PDF) © Springer.
• A.N. Letchford & A. Lodi (2002) Primal cutting plane algorithms revisited. Math. Methods of Oper. Res., 56(1), 67-81. (PDF) © Springer.
• A.N. Letchford (2002) Totally tight Chvátal-Gomory cuts. Oper. Res. Lett., 30(2), 71-73. (PDF) © Elsevier.
• A.N. Letchford & A. Lodi (2002) Strengthening Chvátal-Gomory cuts and Gomory fractional cuts. Oper. Res. Lett., 30(2), 74-82. (PDF) © Elsevier.
• A.N. Letchford (2001) On disjunctive cuts for combinatorial optimization. J. of Comb. Opt., 5(3), 299-315. (PDF) © Springer.
• A.N. Letchford & A. Amaral (2001) Analysis of upper bounds for the pallet loading problem. Eur. J. Opl Res., 132(3), 582-593. (PDF) © Elsevier.
• A. Corberán, A.N. Letchford & J.M. Sanchis (2001) A cutting plane algorithm for the general routing problem. Math. Program., 90(2), 291-316. (PDF) © Springer.
• A.N. Letchford (2000) Separating a superclass of comb inequalities in planar graphs. Math. Oper. Res., 25(3), 443-454. (PDF) © INFORMS.
• A. Caprara, M. Fischetti & A.N. Letchford (2000) On the separation of maximally violated mod-k cuts. Math. Program., 87(1), 37-56. (PDF) © Springer.
• A.N. Letchford (1999) The general routing polyhedron: a unifying framework. Eur. J. Opl Res., 112(1), 122-133. (PDF) © Elsevier.
• A.N. Letchford & R.W. Eglese (1998) The rural postman problem with deadline classes. Eur. J. Opl Res., 105(3), 390-400. (PDF) © Elsevier.
• D.D. Clarke & A.N. Letchford (1998) Action rules extracted by machine induction from feature-coded self-reports. J. Soc. Beh. & Pers., 13(1), 33-50. (PDF) © Select Press.
• A.N. Letchford (1997) New inequalities for the general routing problem. Eur. J. Opl Res., 96(2), 317-322. (PDF) © Elsevier.
• A.N. Letchford (1996) Allocation of school bus contracts by integer programming. J. Opl Res. Soc., 47(3), 369-372. (PDF) © Palgrave.

Articles in Books

• L. Galli, K. Kaparis & A.N. Letchford (2012) Gap inequalities for the max-cut problem: a cutting-plane algorithm. In A.R. Mahjoub, V. Markakis, I. Milis & V.T. Paschos (eds.) Combinatorial Optimization. Lecture Notes in Computer Science, vol. 7422. Berlin: Springer. (PDF)
• M. Giandomenico, A.N. Letchford, F. Rossi & S. Smriglio (2011) An new approach to the stable set problem based on ellipsoids. In O. Günlük & G.J. Woeginger (eds.) Integer Programming and Combinatorial Optimization XV. Lecture Notes in Computer Science, vol. 6655. Heidelberg: Springer. (PDF)
• K. Kaparis & A.N. Letchford (2011) Cover inequalities. In J.J. Cochran et al. (eds.) Encyclopedia of Operations Research and Management Science, Volume 2, pp. 1074-1080. New York: Wiley. (PDF)
• A.N. Letchford & A. Lodi (2011) Mathematical programming approaches to the traveling salesman problem. In J.J. Cochran et al. (eds.) Encyclopedia of Operations Research and Management Science, volume 5, pp. 3125-3132. New York: Wiley. (PDF)
• A.N. Letchford (2010) Integer quadratic quasi-polyhedra. In F. Eisenbrand & B. Shepherd (eds.) Integer Programming and Combinatorial Optimization XIV. Lecture Notes in Computer Science, vol. 6080. Berlin: Springer. (PDF)
• A.N. Letchford & M.M. Sørensen (2008) Binary positive semidefinite matrices and associated integer polytopes. In A. Lodi, A. Panconesi & G. Rinaldi (eds.) Integer Programming and Combinatorial Optimization XIII. Lecture Notes in Computer Science, vol. 5035. Berlin: Springer. (PDF) © Springer.
• A.N. Letchford, G. Reinelt & D.O. Theis (2004) A faster exact separation algorithm for blossom inequalities. In G. Nemhauser & D. Bienstock (eds.) Integer Programming and Combinatorial Optimization X. Lecture Notes in Computer Science, vol. 3064. Berlin: Springer. (PDF)
• A.N. Letchford & A. Lodi (2003) An augment-and-branch-and-cut framework for mixed 0-1 programming. In M. Jünger, G. Reinelt & G. Rinaldi (eds.) Combinatorial Optimization: Eureka, You Shrink! Lecture Notes in Computer Science, vol. 2570. Berlin: Springer. (PDF) © Springer.
• A.N. Letchford & A. Lodi (2002) Polynomial-time separation of simple comb inequalities. In W.J. Cook & A.S. Schulz (eds.) Integer Programming and Combinatorial Optimization IX. Lecture Notes in Computer Science, vol. 2337. Berlin: Springer. (PDF) © Springer.
• R.W. Eglese & A.N. Letchford (2001) The general routing problem. In C.H. Floudas & P.M. Pardalos (eds.) Encyclopedia of Optimization, Vol. 2, pp. 206-207. Kluwer Academic Publishers. (PDF) Copyright now belongs to Springer.
• R.W. Eglese & A.N. Letchford (2000) Polyhedral theory for arc routing problems. In M. Dror (ed.) Arc Routing: Theory, Solutions and Applications. Kluwer Academic Publishers. (PDF) Copyright now belongs to Springer.
• A. Caprara, M. Fischetti & A.N. Letchford (1999) On the separation of maximally violated mod-k cuts. In G. Cornuéjols, R.E. Burkard & G.J. Woeginger (eds.) Integer Programming and Combinatorial Optimization VII. Lecture Notes in Computer Science, vol. 1610. Berlin: Springer. (PDF)

Editorials

• A. Clark, R.W. Eglese, A.N. Letchford & M.B. Wright (2008) Combinatorial optimisation (Editorial). Discrete Applied Math, 156(3), 289-290.
• J. Lee & A.N. Letchford (2007) Mixed integer programming (Editorial). Discrete Optimization, 4(1), 1-2.

Book Reviews

• A.N. Letchford (2012) Review of “The Linear Ordering Problem: Exact and Heuristic Methods in Combinatorial Optimization”. Interfaces, 42(3), 324-325.
• A.N. Letchford & A. Lodi (2007) Review of “The Traveling Salesman Problem: A Computational Study”. 4OR: Quart. J. of Oper. Res., 5(4), 315-317. (PDF) © Springer.
• A.N. Letchford (2004) Review of “Introduction to the Theory of Cooperative Games”. J. Opl Res. Soc., 55(7), 787-788. (PDF) © Palgrave.
• A.N. Letchford (2004) Review of “The Vehicle Routing Problem”. Oper. Res. Lett., 32, 392-393. (PDF) © Elsevier.
• A.N. Letchford (2002) Review of “Approximation Algorithms”. J. Opl Res. Soc., 53(7), 807-808. (PDF) © Palgrave.
• A.N. Letchford (2000) Review of "Model Building in Mathematical Programming". J. Opl Res. Soc., 51(10), 1212-1213. (PDF) © Palgrave.
• A.N. Letchford (2000) Review of "Theory of Linear and Integer Programming". J. Opl Res. Soc., 51(7), 892-893. (PDF) © Palgrave.

Mathematical Reviews

• #2828758 (2012): Projecting systems of linear inequalities with binary variables.
• #2828758 (2012): The Chvátal-Gomory closure of a strictly convex body.
• #2764343 (2011): Orbital branching.
• #2560536 (2011): On the Chvátal rank of linear relaxations of the stable set polytope.
• #2679998 (2011): On the dominant of the s-t cut polytope: vertices, facets and adjacency.
• #2609619 (2010): Extended formulations in combinatorial optimization.
• #2600658 (2010): Minimal inequalities for an infinite relaxation of integer programs.
• #2573497 (2010): Gear composition of stable set polytopes and G-perfection.
• #2533755 (2010): Coefficient strengthening: a tool for reformulating mixed-integer programs.
• #2511722 (2010): Applying mod-k-cuts for solving linear ordering problems.
• #2520406 (2009): MIR closures of polyhedral sets.
• #2505741 (2009): Generalized mixed integer rounding inequalities: facets for infinite group polyhedra.
• #2469128 (2009): A note on the continuous mixing set.
• #2437266 (2009): Local cuts revisited.
• #2411399 (2008): FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension.
• #2375482 (2008): Projected Chvátal-Gomory cuts for mixed integer linear programs.
• #2363379 (2008): On clique separators, nearly chordal graphs, and the maximum weight stable set problem.
• #2348000 (2008): A branch-and-cut algorithm for a resource-constrained scheduling problem.
• #2317860 (2008): New cutting-planes for the time and/or precedence-constrained ATSP and directed VRP.
• #2333324 (2007): Using critical sets to solve the maximum independent set problem.
• #2320128 (2007): Optimization with binet matrices.
• #2299689 (2007): A new min-cut max-flow ratio for multicommodity flows.
• #2292489 (2007): Using mixed-integer programming to solve power grid blackout problems.
• #2289774 (2007): Integer programming formulations for the two 4-hop constrained paths problem.

Other

• N. Bansal et al. (2013) Alberto Caprara (1968-2012): Scientific Contributions. Optima (Newsletter of the Mathematical Optimization Society), 91, 1-11.
• M. Giandomenico, A.N. Letchford, F. Rossi & S. Smriglio (2013) Approximating the Lovász theta function with the subgradient method. Elec. Notes in Discr. Math., 41, 157-164. (Special issue devoted to proceedings of INOC 2013.) (PDF)
• A. Caprara, A.N. Letchford & J.J. Salazar (2010) Lower bounds for the minimum linear arrangement of a graph. Elec. Notes in Discr. Math., 36, 843–849. (Special issue devoted to proceedings of ISCO 2010.)
• A.R.S. Amaral, A. Caprara, A.N. Letchford & J.J. Salazar (2008) A new lower bound for the minimum linear arrangement of a graph. Elec. Notes in Discr. Math., 30, 87-92. (Special issue devoted to proceedings of LAGOS 2007.)
• D.D. Clarke & A.N. Letchford (1995) Rules from behaviour: the use of a computational 'rule-finder' as a tool for social psychology. Newsletter of the British Psychological Society, Social Psychology Section, 33, 4-13.

Published Online

• S. Burer & A.N. Letchford (2012) Unbounded convex sets for non-convex mixed-integer quadratic programming. Published online in Math. Program. October 2012. (PDF)
• A.R.S. Amaral & A.N. Letchford (2012) A polyhedral approach to the single-row facility layout problem. Published online in Math. Program. March 2012. (PDF)

Accepted for Publication

• F. Djeumou Fomeni & A.N. Letchford (2013) A dynamic programming heuristic for the quadratic knapsack problem. To appear in INFORMS J. Comput. (PDF)

Accepted Subject to Revision

• L. Galli & A.N. Letchford: A compact variant of the QCR Method for 0-1 quadratically constrained quadratic programs. Submitted to Opt. Lett. May 2013. Accepted subject to revision June 2013. (original version)
• A.N. Letchford & S.J. Miller (2011) An aggressive reduction scheme for the simple plant location problem. Submitted to Eur. J. Oper. Res. November 2011. Accepted subject to revision April 2012. Revised March 2013. (revised version)

Submitted

• F. Djeumou Fomeni, K. Kaparis & A.N. Letchford: Cutting planes for first-level RLT relaxations of mixed 0-1 programs. Submitted to Oper. Res. May 2013. (PDF)
• A.N. Letchford & S.J. Miller: On the circulant inequalities for the simple plant location problem. Submitted to Discr. Opt. April 2012. (PDF)

In Preparation

• I. Aliev & A.N. Letchford: Scaled Gomory cuts and the geometry of numbers. (draft)
• K. Andersen, A.N. Letchford & R. Weismantel: On maximally violated cutting planes.
• T. Bektas, G. Ergodan & A.N. Letchford: Modelling fairness in exact algorithms for vehicle routing.
• F. Djeumou Fomeni, K. Kaparis & A.N. Letchford: A cut-and-branch algorithm for the quadratic knapsack problem.
• M. Giandomenico, A.N. Letchford, F. Rossi & S. Smriglio: An approach to the stable set problem based on ellipsoids. (Full version of 2011 IPCO paper.)
• A.N. Letchford & S.D. Nasiri: Pricing routines for vehicle routing with time windows on road networks. (draft)
• A.N. Letchford & J.J. Salazar: Stronger multi-commodity flow formulations of the capacitated vehicle routing problem. (draft)
• A.N. Letchford & M.M. Sørensen: A new separation routine for the Boolean quadric and cut polytopes. (draft)

PhD Thesis:

Polyhedral Results for Some Constrained Arc-Routing Problems.

Awarded at Lancaster University on 31st January 1997. Examines integer programming formulations, valid inequalities and algorithms for four 'Arc Routing Problems'.

Last update: June 2013.

Back to home page.