Split Rank of Triangle and Quadrilateral Inequalities

Event Details
  • Date/Time:
    • Wednesday November 18, 2009
      11:00 am - 12:00 pm
  • Location: Executive classroom
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    $0.00
  • Extras:
Contact
Anita Race
H. Milton Stewart School of Industrial and Systems Engineering
Contact Anita Race
Summaries

Summary Sentence: Split Rank of Triangle and Quadrilateral Inequalities

Full Summary: Split Rank of Triangle and Quadrilateral Inequalities

TITLE: Split Rank of Triangle and Quadrilateral Inequalities

SPEAKER: Dr. Santanu Dey

ABSTRACT:

A simple relaxation of two rows of a simplex tableau is a mixed integer set consisting of two equations with two free integer variables and non-negative continuous variables. Recently Andersen et al. (2007) and Cornuejols and Margot (2008) showed that the facet-defining inequalities of this set are either split cuts or intersection cuts obtained from maximal lattice-free triangles and quadrilaterals. These new families of inequalities can be used to generate valid cutting planes from any two rows of a simplex tableau. Through a result by Cook et al. (1990) (and more recently in a generalization by Li and Richard (2008)) it is known that one particular class of facet-defining triangle inequality does not have a finite split rank, i.e., it cannot be obtained by repeated application of split cuts. In this talk, we show that all other facet-defining triangle and quadrilateral inequalities have a finite split-rank. The proof is constructive, i.e., for a given facet-defining triangle or quadrilateral inequality we present an explicit sequence of split inequalities that can be used to generate it.

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
facet-defining
Status
  • Created By: Anita Race
  • Workflow Status: Draft
  • Created On: Feb 16, 2010 - 9:48am
  • Last Updated: Oct 7, 2016 - 9:50pm