1

Given two formulations P1 and P2 for the same integer programming (IP) problem, where Pi denotes the formulation for a problem and the corresponding polytope. We say that P1 is a stronger formulation than P2 if P1 ⊂ P2.

  1. Why do we prefer stronger formulations for IPs over weaker ones?
  2. Why is the convex hull of the feasible integer solutions the best formulation for an IP we can hope for?
  3. Why do we think we can solve an IP efficiently when we are given its convex hull representation?
  4. Why will it generally not be helpful to search for the convex hull representation of a problem?

http://am121.seas.harvard.edu/site/wp-content/uploads/2019/11/sec7-Student.pdf

hardmath
  • 37,015
user207558
  • 98
  • What have you tried? In addition, the link is broken because of the [1] at the end of the link –  Nov 04 '22 at 03:43
  • http://am121.seas.harvard.edu/site/wp-content/uploads/2019/11/sec7-Student.pdf – user207558 Nov 04 '22 at 03:45
  • You can Edit the body of your Question, and that is more appropriate than rewriting the link only in a Comment. Introduce a summary or relevant quote from the PDF to help Readers decide if the link is worth following. Your Question has problems in its current form. You ask multiple problems, without tying them together in the sense of explaining how solving one relates to the others. But generally one should not present Readers with even one problem without going into enough context to illuminate how much you have already digested the problem statement. – hardmath Nov 09 '22 at 16:52

0 Answers0