Explore BrainMass

Showing a matrix is totally unimodular.

This problem was a sample exam question taken from a text book. This problem is about showing a matrix is TU.

This problem can be found in the Wolsey text book called "Integer Programming".

A useful resource is "Integer and Combinatorial optimization" by Wolsey and Nemhauser.


Solution Preview

Dear Friend,

According to the Theorem 2.7 in page 542 of the book "Integer and Combinatorial optimization":

A is a TU matrix if there exists a partition of columns of the matrix to J1 and J2 such that on each row the difference between the sum of the element of J1 and J2 is less or equal to 1.
According to ...

Solution Summary

A matrix is shown to be totally unimodular.