Author 
Message 
Spencer Fung science forum beginner
Joined: 01 Dec 2005
Posts: 2

Posted: Fri Dec 02, 2005 5:37 pm Post subject:
Total unimodularity



Hi all,
I am working on a 01 Integer programming problem, which in the form of Ax =
b. The problems I am dealing with has a special structure in the matrix A.
It definitely not a totally unimodular (TU) matrix, since we cannot find a
integer solution by Simplex. But when I do branchandbound (branching on
fractional value), after few iterations, an integer solution can be found by
Simplex method. I suspected that the matrix A is not TU, but it is very
close to TU. So, I have two questions,
1. Given any {0,1}matrix A, can we measure how close of A to be a TU
matrix?
2. Any fast implementation to check the total unimodularity?
Thank you.
Cheers,
Spencer 

Back to top 


Jannick Asmus science forum Guru
Joined: 25 Mar 2005
Posts: 312

Posted: Sat Jan 28, 2006 4:51 pm Post subject:
Re: Total unimodularity



On 02.12.2005 18:37, Spencer Fung wrote:
Quote:  Hi all,
I am working on a 01 Integer programming problem, which in the form of Ax =
b. The problems I am dealing with has a special structure in the matrix A.
It definitely not a totally unimodular (TU) matrix, since we cannot find a
integer solution by Simplex. But when I do branchandbound (branching on
fractional value), after few iterations, an integer solution can be found by
Simplex method. I suspected that the matrix A is not TU, but it is very
close to TU. So, I have two questions,
1. Given any {0,1}matrix A, can we measure how close of A to be a TU
matrix?
2. Any fast implementation to check the total unimodularity?
Thank you.
Cheers,
Spencer

I am not a specialist at this topic. Perhaps
http://en.wikipedia.org/wiki/Totally_unimodular_matrix and the links
therein can be helpful.
Best wishes,
J. 

Back to top 


Google


Back to top 



The time now is Fri Nov 17, 2017 10:55 pm  All times are GMT

