next up previous
Next: About this document

MA618 Homework #7
Due Wednesday, April 19

  1. Problem (Gomory cuts are Chvátal-Gomory cuts), p. 85.
  2. Problem (Clique separation), p. 96. What you need to do is to assume you have a feasible non-integer solution tex2html_wrap_inline11 to the original constraints, and by solving a certain maximum-weight vertex-packing problem on a certain graph, determine whether or not tex2html_wrap_inline11 violates any of the clique inequalities.
  3. Problem (2-matching inequalities and Chvátal-Gomory cutting planes), p. 100.
  4. Problem (Exponential example for Branch-and-Bound), p. 106.

Carl Lee
Thu Apr 6 11:07:38 EDT 2000