lattice-free convex sets

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

    On the relative strength of families of intersection cuts arising from pairs of tableau constraints in mixed integer programs

  • Yogesh Awate
  • Gérard Cornuéjols
  • Bertrand Guenin
  • Levent Tunçel
    • Categories (Mixed) Integer Linear Programming Tags , ,

    We compare the relative strength of valid inequalities for the integer hull of the feasible region of mixed integer linear programs with two equality constraints, two unrestricted integer variables and any number of nonnegative continuous variables. In particular, we prove that the closure of Type~2 triangle (resp. Type~3 triangle; quadrilateral) inequalities, are all within a … Read more