pachaquis3s

## Answered question

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.

### Answer & Explanation

Xzavier Shelton

Beginner2022-07-01Added 26 answers

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?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?