nonlinear cuts

Submodularity in conic quadratic mixed 0-1 optimization

  • Alper Atamturk
  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , , , , , ,

    We describe strong convex valid inequalities for conic quadratic mixed 0-1 optimization. These inequalities can be utilized for solving numerous practical nonlinear discrete optimization problems from value-at-risk minimization to queueing system design, from robust interdiction to assortment optimization through appropriate conic quadratic mixed 0-1 relaxations. The inequalities exploit the submodularity of the binary restrictions and … Read more

    Deriving the convex hull of a polynomial partitioning set through lifting and projection

  • Trang T. Nguyen
  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory Tags , ,

    Relaxations of the bilinear term, $x_1x_2=x_3$, play a central role in constructing relaxations of factorable functions. This is because they can be used directly to relax products of functions with known relaxations. In this paper, we provide a compact, closed-form description of the convex hull of this and other more general bivariate monomial terms (which … Read more

    Strong Valid Inequalities for Orthogonal Disjunctions and Bilinear Covering Sets

  • Kwanghun Chung
  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Global Optimization Theory Tags , , , ,

    In this paper, we develop a convexification tool that enables the construction of convex hulls for orthogonal disjunctive sets using convex extensions and disjunctive programming techniques. A distinguishing feature of our technique is that, unlike most applications of disjunctive programming, it does not require the introduction of new variables in the relaxation. We develop and … Read more