pachaquis3s

2022-06-30

Let $P\subseteq {\mathbb{R}}^{2}$ be the convex hull of the points $\left(0,0\right)$, $\left(3,1\right)$ and $\left(-1,2\right)$.
Exercise: Give a TDI system $Ax\le b$ describing $P$ with $A$ and $b$ integral.
I know the following:
Many combinatorial min-max relations can be understood as a result of LP-duality
$max\left\{{w}^{T}x:Ax\le b\right\}=min\left\{{y}^{T}b:{y}^{T}A={w}^{T},y\ge 0\right\}$
combined with integrality of optimal solutions on the primal and dual side.
Def: Let $Ax\le b$ be a rational system of linear inequalities and let $P:=\left\{x:Ax\le b\right\}$ be the associated polyhedron. The system $Ax\le b$ is Totally Dual Integral (TDI) if for every integral objective vector w, the minimum in the dual is attained by an integral vector $y$ (if the minimum is finite).
What I should do: I need to find a TDI system $Ax\le x$ such that $P=\left\{x:Ax\le b\right\}$ is the convex hull of the points $\left(0,0\right),\left(3,1\right)$ and $\left(-1,2\right)$ and that $A$ and $b$ are integral. So I think I probably should identify $P$ first.

Xzavier Shelton

You need to find three lines: one that intersects (0,0) and (3,1); one that intersects (0,0) and (-1,2); and the line that intersect (-1,2).
Then you should be able to find the matrix A and the corresponding vector b.
For the first line for example you have: ${x}_{1}=a{x}_{2}+b$, where $a=\frac{1}{3}$ and $b=0$.
That is how you identify $P$.

Do you have a similar question?