If a matrix is totally unimodular (TU), then we know that $\text{\{}x| Ax\leq b \text{\}}$ is integral for all integral $b$'s. This is often used for convex hull proofs, but does the concept of TU has further applications?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
The reference: Model building in mathematical programming
Total unimodularity is a strong property that guarantees integer optimal solutions to an LP problem for all $c$ and integer $b$. Many IP models for which the matrix $A$ is not totally unimodular frequently (although not always) produce integer solutions to the optimal solution of the corresponding LP problem.
In particular, this often happens with the set packing, partitioning and covering problems. There is, therefore, great virtue in such a reformulation as the high computational costs associated with an IP problem over an LP problem is avoided. For example:
-
1$\begingroup$ yes this is the application of convex-hull proofs. But is TU simply a tool for proving convex-hulls or is it interesting also in other contexts? $\endgroup$ Commented Jan 12, 2021 at 9:24
-
$\begingroup$ @user3680510, I think, the main practical usage of the TU also mentioned in the above reference is reducing the solving time by reformulating some constraints. $\endgroup$– A.OmidiCommented Jan 12, 2021 at 12:38
-
$\begingroup$ yes i agree, but this is the reason of this question, since this is the only pratical and theoretical reason i know. $\endgroup$ Commented Jan 12, 2021 at 12:52