Gomory Mixed Integer Cuts Are Optimal

Explore a lecture on the optimality of Gomory mixed integer cuts in combinatorial optimization. Delve into the theoretical justification for the empirical superiority of these cutting planes in mixed integer programming. Learn about the pure integer infinite group relaxation model proposed by Gomory and Johnson, and discover how Gomory mixed-integer cuts maximize the volume cut off from the nonnegative orthant. Examine the volume criterion in cyclic group problems and infinite Gomory-Johnson relaxations, and understand the proof of optimality for these cuts. Gain insights into the work of Marco Di Summa and his collaborators on this important topic in integer programming and combinatorial optimization.

Intro
What is a good cut?
The Gomory-Johnson relaxations
Valid functions
The volume criterion in the cyclic group problem
Optimal solution in the cyclic group problem
Rearranging the function values
Proof of optimality
The volume criterion in the infinite GJ relaxation
Proof sketch for the infinite GJ relaxation