elementary closures

On the Relative Strength of Different Generalizations of Split Cuts

  • Sanjeeb Dash
  • Oktay Gunluk
  • Marco Molinaro
    • Categories Cutting Plane Approaches Tags , ,

    Split cuts are among the most important and well-understood cuts for general mixed-integer programs. In this paper we consider some recent generalizations of split cuts and compare their relative strength. More precisely, we compare the elementary closures of {split}, {cross}, {crooked cross} and general {multi-branch split cuts} as well as cuts obtained from multi-row and … Read more

    Lifting Inequalities: A framework for generating strong cuts in nonlinear programs

  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories Global Optimization, Integer Programming, Nonlinear Optimization Tags , , , , ,

    In this paper, we propose lifting techniques for generating strong cuts for nonlinear programs that are globally-valid. The theory is geometric and provides intuition into lifting-based cut generation procedures. As a special case, we find short proofs of earlier results on lifting techniques for mixed-integer programs. Using convex extensions, we obtain conditions that allow sequence-independent … Read more