multi-row cuts

Can cut generating functions be good and efficient?

  • Amitabh Basu
  • Sriram Sankaranarayanan
    • Categories Cutting Plane Approaches, Integer Programming, Polyhedra Tags , ,

    Making cut generating functions (CGFs) computationally viable is a central question in modern integer programming research. One would like to nd CGFs that are simultaneously good, i.e., there are good guarantees for the cutting planes they generate, and ecient, meaning that the values of the CGFs can be computed cheaply (with procedures that have some … Read more

    The Strength of Multi-row Aggregation Cuts for Sign-pattern Integer Programs

  • Santanu S. Dey
  • Andres Iroume
  • Guanyi Wang
    • Categories Cutting Plane Approaches Tags , ,

    In this paper, we study the strength of aggregation cuts for sign-pattern integer programs (IPs). Sign-pattern IPs are a generalization of packing IPs and are of the form {x \in Z^n | Ax = 0} where for a given column j, A_{ij} is either non-negative for all i or non-positive for all i. Our first … Read more