FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Combinatorics
Total unimodularity
Post new topic   Reply to topic Page 1 of 1 [2 Posts] View previous topic :: View next topic
Author Message
Spencer Fung
science forum beginner


Joined: 01 Dec 2005
Posts: 2

PostPosted: Fri Dec 02, 2005 5:37 pm    Post subject: Total unimodularity Reply with quote

Hi all,

I am working on a 0-1 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 branch-and-bound (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

PostPosted: Sat Jan 28, 2006 4:51 pm    Post subject: Re: Total unimodularity Reply with quote

On 02.12.2005 18:37, Spencer Fung wrote:
Quote:
Hi all,

I am working on a 0-1 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 branch-and-bound (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
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [2 Posts] View previous topic :: View next topic
The time now is Mon Aug 21, 2017 11:55 pm | All times are GMT
Forum index » Science and Technology » Math » Combinatorics
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Total 35$ 2layers+2soldermask+2silkscreen pcb prototype m... t2531998@126.com Control 0 Thu Jul 13, 2006 5:57 am
No new posts Total 35$ 2layers+2soldermask+2silkscreen pcb prototype m... t2531998@126.com Control 0 Thu Jul 13, 2006 5:57 am
No new posts Total set of complex number is in a hemisphere? cyclomethane@gmail.com Math 0 Mon Jul 10, 2006 12:27 pm
No new posts Total energy: E = gamma*m*c^2 (including potential energy) Peter Christensen Relativity 7 Mon Jul 03, 2006 1:40 pm
No new posts modeling total probability less than 1 cagdas.ozgenc@gmail.com Math 5 Mon Jul 03, 2006 1:32 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0608s ][ Queries: 16 (0.0465s) ][ GZIP on - Debug on ]