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

Event Details
  • Date/Time:
    • Wednesday February 3, 2010
      12:30 pm - 1:30 pm
  • Location: ISyE Groseclose Room 226A
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact
No contact information submitted.
Summaries

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

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

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.

Additional Information

In Campus Calendar
No
Groups

H. Milton Stewart School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
Categories
Seminar/Lecture/Colloquium
Keywords
probabilistic
Status
  • Created By: Anita Race
  • Workflow Status: Published
  • Created On: Jan 28, 2010 - 10:29am
  • Last Updated: Oct 7, 2016 - 9:49pm