Questions tagged [total-unimodularity]
The total-unimodularity tag has no usage guidance.
15 questions
0
votes
0
answers
39
views
Max-flow modeling with unified vehicle and commodity variables
I am working on a network flow problem that involves routing through a time-space network. The network consists of:
A single source node and a single demand node.
A fleet of vehicles with specified ...
- 101
1
vote
0
answers
59
views
Minimizing square roots with the consecutive ones property
Let $A=[a_{ik}]$ be a matrix with the consecutive ones property in each column, i.e. each column consists of a single consecutive block of $1$'s (with zeros everywhere else). Is there anything at all ...
- 4,049
2
votes
0
answers
96
views
Linear forms and the second Voronoi decomposition
This is not my area of expertise, so forgive me if the question is a bit naive. Given a collection of vectors $v_1,\ldots,v_d$ in $\mathbb{R}^n$ (with $d\geq n$), there is a corresponding set of ...
- 147
3
votes
0
answers
50
views
Modular counting of integral points under sparse non-negativity
Given a polyhedron
$$Ax\geq b$$
where every entry of $A,b$ are non-negative and $A\in\{0,1\}^{m\times n}$ and there are $O(1)$ (say $\leq8$) non-negative entries per row of $A$ is it possible to ...
- 13.9k
1
vote
2
answers
212
views
Examples of matrices with all subdeterminants bounded away from $0$
Does there exist examples of $m \times n$ matrices with $m > n$ with the property that the determinant of every $n \times n$ submatrix is at least $1$ in absolute value? (The $1$ can be replaced by ...
- 763
1
vote
0
answers
282
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 ...
- 393
4
votes
0
answers
94
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$...
- 13.9k
1
vote
1
answer
255
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\...
- 13.9k
4
votes
1
answer
2k
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 ...
- 13.9k
2
votes
1
answer
1k
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$$
...
- 31
9
votes
1
answer
3k
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 ...
- 93
1
vote
0
answers
628
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 ...
- 11
9
votes
1
answer
6k
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 ...
- 213
4
votes
1
answer
866
views
When is a triangular matrix totally unimodular?
I have a {0,1}, invertible, triangular matrix, that I would like to show is totally unimodular. Are there any known results on the total unimodularity of classes of triangular matrices?
- 1,182
16
votes
2
answers
3k
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 ...
- 12.7k