What is the fastest known algorithm which solves an integer linear program with a totally unimodular coeffient matrix? Could you point me to some references?

I tried googling, but failed at finding a good answer and reference for this.

asked 21 Jan '11, 09:32

gphilip's gravatar image

gphilip
133
accept rate: 0%


The problem specified over at Theoretical Computer Science can be formulated as a transportation problem. If we ignore the second (greater than) constraint, it is clearly a transportation (Hitchcock) problem, where source i has supply n_i, sink j has some arbitrarily large demand (the sum of the n_i being an obvious candidate), and we use an extra dummy source node whose supply balances total supply with total demand and which has a zero-cost arc to every sink. To accommodate the second constraint (minimum flow of w into every sink), split each sink node into two nodes. The first one (I'll call it the original) has demand w and the second one (which I'll call the clone) has the original demand less w. Clone the arcs as well, but remove the arc from the dummy source to the original node (leave the arc from the dummy source to the clone).

Although this jacks up the size of the network, my guess is that a special-purpose algorithm for the transportation problem will be fastest.

link

answered 22 Jan '11, 19:32

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

@Paul : Thank you, let me check this out.

(23 Jan '11, 02:32) gphilip

Many specialized problems that can be formulated as LPs with TU matrices have specialized algorithms that are more efficient than algorithms for general problems. Min-cost network flow problems and special cases such as max flow, circulation, shortest path all fall in this class. For general TU problems, I don't know of anything faster than algorithms for general LPs, though. Anyone else know better?

For network flow problems, start with Ahuja, Magnanti, and Orlin's Network Flows book. Advances have almost surely been made since then, but that will give you an entry.

link

answered 21 Jan '11, 14:33

Matthew%20Saltzman's gravatar image

Matthew Salt... ♦
4.7k310
accept rate: 17%

I believe you are right, I am no expert in complexity for general TU either, but I am reasonable sure you end up in same result as standard LP. Special cases of TU is of course a different result.

(21 Jan '11, 21:32) Bo Jensen ♦

@Matthew : Thank you. I asked the same question over at the Theoretical CS place [1], and got a couple of answers that give more information.

[1] http://cstheory.stackexchange.com/q/4454/148

(22 Jan '11, 15:53) gphilip

All problems with TU constraint matrix can, in principle, be reduced to network problems (i.e. linear programs where the constraint matrix is the incidence matrix of a diagraph or its transpose). This is done via Seymour's decomposition theorem for TU matrices (i.e. all TU matrices can be constructed from network matrices using 1-sums,2-sums, and 3-sums). It is known that using this decomposition approach yields polytime algorithms (with network algorithms as subroutine), but I am not sure if the running time is better than just solving the problem with standard LP mehods. Schrijver's blue book has more on this.

link

answered 28 Jan '11, 17:31

Anonymous's gravatar image

Anonymous
211
accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231

Asked: 21 Jan '11, 09:32

Seen: 2,066 times

Last updated: 28 Jan '11, 17:31

OR-Exchange! Your site for questions, answers, and announcements about operations research.