Questions tagged [total-unimodularity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
58 views

total unimodularity of a matrix

Let G be the node-arc incidence matrix of a given directed network (rows of $G$ correspond to nodes and its columns correspond to arcs). Let $B_1,\dots, B_K$ denote a partition of the nodes of the ...
4
votes
0answers
84 views

Totally Unimodular matrix edited from ordinary matrix

Given a matrix $M\in\{0,1\}^{m\times n}$ is there an algorithm to tell if we can convert some of $1$s to $-1$s and make $M$ Totally Unimodular and output such a Totally Unimodular in polynomial in $mn$...
1
vote
1answer
170 views

Is this totally unimodular family?

Is it possible to prove this matrix family only contains totally unimodular matrices? The matrix has dimensions $\frac{3n(n-1)}2$ rows and $n+\frac{n(n-1)}2$ columns. To every pair $(i,i')$ with $1\...
1
vote
1answer
489 views

What does the basis of the null space of the constraint matrix of a flow problem look like?

Consider a directed graph $G=(V,\mathbb{A})$ and a set of flow constraints of the following form: $$ \sum_{(u,v)\in\mathbb{A}}x_{u,v} - \sum_{(v,u)\in \mathbb{A}}x_{v,u} = 0 \forall v \in V$$ ...
3
votes
1answer
500 views

Under what conditions does an Integer Programming problem run in polynomial time?

Given $AX\leq B$ where $A\in\Bbb Z^{m\times n}$,$B\in\Bbb Z^m$ finding $X\in\Bbb Z^n$ where $m\geq n$ is the integer programming problem. If $A$ is totally unimodular then the problem is solvable in ...
1
vote
0answers
463 views

Totally unimodular Matrices

A matrix is totally uni-modular if the determinant of any (square) sub-matrix is {+1, 0, -1}. My question is, "Is there a way to transform(linear or non) a general matrix into a totally uni-modular ...
9
votes
1answer
2k views

Inverse of a totally unimodular matrix

A unimodular matrix $M$ is a square integer matrix having determinant $+1$ or $−1$. A totally unimodular matrix (TU matrix) is a matrix for which every square non-singular submatrix is unimodular. A ...
8
votes
1answer
5k views

Proving that a binary matrix is totally unimodular

I'm working on a set of problems for which I can formulate binary integer programs. When I solve the linear relaxations of these problems, I always get integer solutions. I would like to prove that ...
15
votes
2answers
2k views

Has anyone implemented a recognition algorithm for totally unimodular matrices?

One of the consequences of Seymour's characterization of regular matroids is the existence of a polynomial time recognition algorithm for totally unimodular matrices (i.e. matrices for which every ...
3
votes
1answer
652 views

When is a triangular matrix totally unimodular?

I have an {0,1}, invertible, triangular matrix, that I would like to show to be totally unimodular. Are there any known results on the total unimodularity of classes of triangular matrices?