*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
