1/2}-chvatal-gomory cuts

Algorithms to Separate {0,1/2}-Chvatal-Gomory Cuts

  • Arie M.C.A. Koster
  • Adrian Zymolka
  • Manuel Kutschka
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Cutting Plane Approaches Tags , ,

    Chvatal-Gomory cuts are among the most well-known classes of cutting planes for general integer linear programs (ILPs). In case the constraint multipliers are either 0 or 1/2, such cuts are known as {0, 1/2}-cuts. It has been proven by Caprara and Fischetti (1996) that separation of {0, 1/2}-cuts is NP-hard. In this paper, we study … Read more