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.


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.