7
$\begingroup$

A problem I study reduces to whether the polyhedron $P=\{\mathbf{x}\mid A\mathbf{x}=\mathbf{1}, \mathbf{x}\geq0\}$ is integral ($A$ is a matrix with coefficients in $\{0,1\}$). I know that the unimodularity of $A$ is a sufficient condition, which has been useful for me. I want to know whether there is any weaker condition.

I read from a textbook that $P$ is integral if the system $A\mathbf{x}=\mathbf{1}, \mathbf{x}\geq0$ is totally dual integral (TDI), i.e., the minimum in

$\max\{\mathbf{c}^T\mathbf{x}\mid A\mathbf{x}=\mathbf{1}, \mathbf{x}\geq0\}=\min\{\mathbf{y}^T\cdot\mathbf{1}\mid \mathbf{y}^TA\geq \mathbf{c}^T\}$

has an integral optimum solution $\mathbf{y}$ for each integral $\mathbf{c}$ for which the minimum is finite.

This definition is too abstract for me. I wonder whether there is any characterization for this condition that I can use directly.

$\endgroup$

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.