callback request

Search the site

Find out More

Current research

Research Project #1: 0-1 Quadratic Programs and Related Problems

Several important optimisation problems have a quadratic objective function, together with binary variables. This includes several problems arising in OR, such as certain facility location, project selection, network design and sports scheduling problems. There are however also applications in other fields, such as quantitative finance, statistics, computer science, statistical physics and computational biology.

Since these problems are theoretically "intractable" (i.e., NP-hard), sophisticated mathematical and computational techniques are needed to solve instances of realistic size to proven optimality or near-optimality.  The main technique that we have used so far is the so-called "polyhedral" technique, which enables one to derive strong valid linear inequalities, which can used to improve the performance of Linear Programming-based solvers.  Interestingly, some of the inequalities derived can be adapted to problems that, at first sight, do not appear to have quadratic aspects. This includes, for example, some network design and graph layout problems.  Another technique that we have used is dynamic programming.

So far, this research project has led to the following papers:

F. Djeumou Fomeni & A.N. Letchford (2014) A dynamic programming heuristic for the quadratic knapsack problem. INFORMS Journal on Computing, 26, 173-182.

F. Djeumou Fomeni, K. Kaparis & A.N. Letchford (2013) Cutting planes for RLT relaxations of mixed 0-1 polynomial programs. Submitted.

C. Feremans, M. Labbé, A.N. Letchford & J.J. Salazar (2011) On generalised network design polyhedra. Networks, 58, 125-136.

L. Galli & A.N. Letchford (2010) Small bipartite subgraph polytopes. Operations Research Letters, 38, 337-340.

L. Galli, K. Kaparis & A.N. Letchford (2012) Complexity results for the gap inequalities for the max-cut problem. Operations Research Letters, 40, 149-152.

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.

A.N. Letchford, G. Reinelt, H. Seitz & D.O. Theis (2010) On a class of metrics related to graph layout problems. Linear Algebra and Applications, 433, 1760-1777.

A.N. Letchford & M.M. Sørensen (2008) Binary positive semidefinite matrices and associated integer polytopes (extended abstract). In A. Lodi, A. Panconesi & G. Rinaldi (eds.) Integer Programming and Combinatorial Optimization XIII. Lecture Notes in Computer Science, vol. 5035. Berlin: Springer.

A.N. Letchford & M.M. Sørensen (2012) Binary positive semidefinite matrices and associated integer polytopes (full version). Mathematical Programming, 131, 253-271.

A.N. Letchford & M.M. Sørensen (2013) A new separation routine for the Boolean quadric and cut polytopes. Submitted.


Research Project #2: Convex Sets Associated with Non-Convex Quadratic Optimisation Problems

Some important optimisation problems have quadratic objective and/or constraint functions. If all such functions are convex, then the problems are likely to be reasonably easy to solve using existing methods.  Moreover, if all variables are binary, then even non-convex problems can be fairly easily "convexified" without affecting the optimal solution.  Unfortunately, non-convex problems with non-binary variables arise in some cases, particularly in engineering applications.  Such problems are very difficult in both theory and practice.  Moreover, one cannot use the standard "polyhedral" approach, since the convex hull of feasible solutions is typically not a polyhedron.  For this reason, one has to supplement traditional polyhedral theory with elements of convex analysis.  Moreover, convex programming tools, such as semidefinite programming and convex quadratic programming, are often more useful than traditional linear programming.

So far, this research project has led to the following papers:

S. Burer & A.N. Letchford (2009) On non-convex quadratic programming with box constraints. SIAM Journal on Optimization, 20, 1073-1089.

S. Burer & A.N. Letchford (2012) Non-convex mixed-integer nonlinear programming: a survey. Surveys in Operations Research and Management Science, 17, 97-106.

S. Burer & A.N. Letchford (2014) Unbounded convex sets for non-convex mixed-integer quadratic programming. Mathematical Programming, 143, 231-256.

L. Galli, K. Kaparis & A.N. Letchford (2011) Gap inequalities for non-convex mixed-integer quadratic programs. Operations Research Letters, 39, 297–300.

L. Galli & A.N. Letchford (2013) A compact variant of the QCR method for quadratically constrained quadratic 0-1 programs. Optimization Letters, to appear.

L. Galli & A.N. Letchford (2014) Improving the RLT relaxation of separable bilinear programs using cutting planes. In preparation.

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.

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.