Research

Publications

Submitted

  • Intersection cuts for nonlinear integer programming: convexification techniques for structured sets.
    S. Modaresi, M. R. Kilinc and J. P. Vielma. Submitted for publication, 2013.       [PDF]

    We study the generalization of split and intersection cuts from Mixed Integer Linear Programming to the realm of Mixed Integer Non-linear Programming. Constructing such cuts requires calculating the convex hull of the difference of two convex sets with specific geometric structures. We introduce two techniques to give precise characterizations of such convex hulls and use them to construct split and intersection cuts for several classes of sets. In particular, we give simple formulas for split cuts for essentially all convex quadratic sets and for intersection cuts for a wide variety of convex quadratic sets.


  • Split Cuts and Extended Formulations for Mixed Integer Conic Quadratic Programming.
    S. Modaresi, M. R. Kilinc and J. P. Vielma. Submitted for publication, 2013.       [PDF]

    We study split cuts and extended formulations for Mixed Integer Conic Quadratic Programming (MICQP) and their relation to the Conic Mixed Integer Rounding (CMIR) cuts. We show that the CMIR is a linear split cut for the polyhedral portion of an extended formulation of a quadratic set and that it can be weaker than the nonlinear split cut of the same quadratic set. However, we also show that by exploiting the power of their extended formulation, families of CMIRs can be significantly stronger than the associated family of nonlinear split cuts.


Working Paper

  • Cuts for Mixed Integer Quadratic and Conic Quadratic Programming.
    S. Modaresi and J. P. Vielma.


Presentations

  • Intersection Cuts for Nonlinear Integer Programming.
    INFORMS Annual Meeting, Minneapolis, MN, October 2013.       [PDF]


  • Split Cuts and Extended Formulations for Second-order Conic Programming
    INFORMS Annual Meeting, Minneapolis, MN, October 2013.       [PDF]


  • Representability of Disjunctive Cuts for Mixed Integer Nonlinear Programming.
    INFORMS Annual Meeting, Phoenix, AZ, October 2012.       [PDF]


  • Computational Effectiveness of Split Cuts for Second-order Conic Programming
    INFORMS Annual Meeting, Phoenix, AZ, October 2012.       [PDF]


  • Split Cuts for Conic Programming
    Workshop on Mixed Integer Programming, Davis, CA, July 2012 (Poster).       [PDF]