Let be the convex hull of the points , and .
Exercise: Give a TDI system describing with and integral.
I know the following:
Many combinatorial min-max relations can be understood as a result of LP-duality
combined with integrality of optimal solutions on the primal and dual side.
Def: Let be a rational system of linear inequalities and let be the associated polyhedron. The system is Totally Dual Integral (TDI) if for every integral objective vector w, the minimum in the dual is attained by an integral vector (if the minimum is finite).
What I should do: I need to find a TDI system such that is the convex hull of the points and and that and are integral. So I think I probably should identify first.