Research Project #1: Polyhedra Associated with 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. In this project, the so-called "polyhedral" technique was applied, which involves the study of the convex hull of feasible solutions, viewed as a polyhedron. For each problem class considered, several families of provably strong valid linear inequalities were derived. These will be used
in future 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.
So far, this research project has led to the following papers:
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 (2011) Complexity results for the gap inequalities for the max-cut problem. Submitted to Operations Research Letters July 2011. Accepted subject to minor corrections September 2011.
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 (2010) Binary positive semidefinite matrices and associated integer polytopes (full version). Mathematical Programming, to appear.
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.
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 J. Opt., 20(2), 1073-1089.
L. Galli, K. Kaparis & A.N. Letchford (2011) Gap inequalities for non-convex mixed-integer quadratic programs. Oper. Res. Lett., 39(5), 297–300.
L. Galli & A.N. Letchford (2011) Reformulating mixed-integer quadratically constrained quadratic programs. Submitted.
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.
S. Burer & A.N. Letchford (2011) Unbounded convex sets for non-convex mixed-integer quadratic programs. Submitted.
