TITLE: A probabilistic comparison of split, triangle and quadrilateral cuts for two row mix-integer programs

SPEAKER: Qie He

ABSTRACT:

Despite the elegant theory of cuts for mixed-integer programs with two rows and two integer variables derived from triangle and quadrilateral integer-free bodies, there has been only limited computational evidence that these cuts are capable of giving better results than those derived from simple splits, i.e. Gomory cuts which are derived from a single row. In this paper, we show that under a certain probabilistic model, a cut coefficient derived from a simple split is likely to be stronger than that derived from a triangle and as strong as that derived from a quadrilateral. Furthermore, we use our probabilistic model to compare the volume cut off from the linear relaxation by a split cut and a type 1 triangle cut. We empirically demonstrate that the probability that the split cut cuts off more volume than the triangle cut is quite high when the number of continuous variables is large.

This is a joint work with Shabbir Ahmed and George Nemhauser.