Search   Memberlist   Usergroups
 Page 1 of 1 [2 Posts]
Author Message
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 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.
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 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
Google

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [2 Posts]
 The time now is Sun Feb 17, 2019 2:20 pm | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics Total 35\$ 2layers+2soldermask+2silkscreen pcb prototype m... t2531998@126.com Control 0 Thu Jul 13, 2006 5:57 am Total 35\$ 2layers+2soldermask+2silkscreen pcb prototype m... t2531998@126.com Control 0 Thu Jul 13, 2006 5:57 am Total set of complex number is in a hemisphere? cyclomethane@gmail.com Math 0 Mon Jul 10, 2006 12:27 pm Total energy: E = gamma*m*c^2 (including potential energy) Peter Christensen Relativity 7 Mon Jul 03, 2006 1:40 pm 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.0121s ][ Queries: 20 (0.0021s) ][ GZIP on - Debug on ]