If I can show a polyhedron Y is an extended formulation of polyhedron X and every extreme point in Y is integral, does that automatically imply the projection of Y onto the variable space of X gives the convex hull of X? Thank you.

  • $\begingroup$ In your question conv X = X (since it is a polyhedron) and proj Y = X, so proj Y = conv X. But i don't think this was the real question, so could you please improve your question? $\endgroup$ – user3680510 Aug 11 '20 at 11:21
  • $\begingroup$ I am trying to find conv(X) but the description is not trivial and difficult to generalize. So I develop an extended formulation Y to represent X where conv(Y) = Y and the size of description is polynomial. Clearly Proj(Y) = X, so I am thinking whether Proj(conv(Y)) = conv(X). <- Did I just answer my own question? $\endgroup$ – Octavia Aug 11 '20 at 15:06
  • $\begingroup$ Can you please add what X and Y and conv X and conv Y are? $\endgroup$ – user3680510 Aug 11 '20 at 16:38
  • $\begingroup$ I just want to know in general for mixed-integer programming formulation, if my question does hold or not. X is a formulation, say Ax <=b , Y is an extended formulation Ax + By <= b. For x in X, there exists y such that Ax + By <= b. Are you asking for the specific constraints I am working on? $\endgroup$ – Octavia Aug 11 '20 at 17:02
  • $\begingroup$ I think you need to look up the definitions of the objects you are working with. The feasible set of a mixed integer program X is not a polyhedron, but conv X is a polyhedron. An extended formulation is defined for polyhedrons. So Y can be an extended formulation for conv X, but not for X. $\endgroup$ – user3680510 Aug 11 '20 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.