William & Mary

Conic relaxations of combinatorial optimization problems

Topic description: This project involves using conic optimization to help solve hard combinatorial optimization problems.

A linear program is the problem of optimizing (maximizing or minimizing) a linear function over a set of linear constraints (inqequalities and/or equations). A generalization of linear programming is conic optimization which involves optimizing a linear function over linear constraints that are contained in some type of cone. For example, optimizing a linear function over linear constraints in the space of positive semidefinite matrices is a form of conic optimization called semidefinite programming.

Combinatorial optimization is the problem of optimizing a given function over a discrete, and often finite, feasible region. Famous combinatorial optimization problems include the Travelling Salesman Problem and various types of Matching problems. The applications of combinatorial optimization are widespread throughout industry and policy and active research areas include determining the best way to schedule flight crews on airlines and how to best match residency programs to residents. Although combinatorial optimization problems occur over a finite feasible region, the number of possible solutions is often huge, and sophisticated algorithms are required in order to efficiently solve the problems.

A standard method for solving difficult combinatorial optimization problems is to use a linear programming relaxation of an exact integer program. In the past 30 years, researchers have generalized this idea by using semidefinite programming relaxations to exact integer programs. Both linear and semidefinite programming relaxations have led to successful algorithms for solving combinatorial optimization problems, but several interesting open questions remain. Specific research projects in this topic area would investigate implementing codes that use rank-reduction to "round" the relaxations back to integral solutions, how duality in the various conic relaxations could help solve the combinatorial optimization problem or how second-order cone programming could be used to create new relaxations for combinatorial optimization problems.

Research opportunities:

Prerequisites: Math 211, Matlab and C/C++ programming skills.

Suggested prerequisites: Math 323, CSCI 303, and some numerical analysis background.

Contact: David Phillips