Strengthening Objective Cuts

Consider an integer program or combinatorial optimisation problem in which the goal is to minimise a linear cost function, say c^Tx.  Suppose one has solved some kind of relaxation of this problem (such as a linear or Lagrangian relaxation), and one has a lower bound L.  Obviously, the "objective cut" c^Tx >= L is satisfied by all solutions.  It is however likely to be completely useless as a cutting plane. A natural topic of study is whether one can strengthen objective cuts, in the hope of making them more useful. In fact, two kinds of strengthened objective cuts are already known. (For LP relaxations, it suffices to generate a Gomory cut from the objective row of the tableau. For Lagrangian relaxations, one can generate so-called Lagrange cuts.)  The purpose of this PhD is to study ways in which objective cuts can be further strengthened. A tantalising possibility is that strengthened Lagrange cuts could be used to create a new paradigm for integer programming and combinatorial optimisation, which we call "price-cut-and-branch".

Applicants for this research project need to have good qualifications in mathematics or a related discipline, and have experience with computer programming. Experience with LaTeX would also be desirable, but is not essential as training can be given.

For further information contact Trivikram Dokka or Adam Letchford.

Return to the Optimisation Research Group page.