Questions tagged [total-unimodularity]

A totally unimodular matrix is a matrix for which every square non-singular submatrix is unimodular.

Filter by
Sorted by
Tagged with
0
votes
0answers
27 views

Total unimodular matrices

I am trying to establish the following relationship. If $T$ is a $m \times n$ $TU$ matrix with the property that all rows of $T$ have the same number of non-zero entries and all entries $\geq 0$. Then ...
-1
votes
1answer
11 views

Proving a set has integer extreme points

The hint says to use TU Properties, but I don't know how to express P as a matrix to use the properties Any help is appreciated
0
votes
0answers
12 views

Checking for integral extreme points of polytopes characterized by non-TUM matrices?

We know that a sufficient condition on $A$ and $b$ for all vertices of $P=\left\{x \in \mathbb{R}^{n} | A x \leq b, x \geq 0\right\}$ to be integral is that $A$ is totally unimodular (TUM) and $b$ is ...
0
votes
2answers
59 views

Unimodular Matrix Inverse Proof Confusion

Regarding the proof of Lemma 2: Matrix $A$ is totally unimodular if and only if the matrix $[A |I]$ is TU, I do not understand the first step on permuting square submatrix of B to the desired form. ...
0
votes
1answer
71 views

Appending TU matrix with the identity or zero matrix still give us another TU matrix.

If $A$ was a totally unimodular matrix, then show the matrix obtained by augmenting with the identity matrix $[A|I]$ is TU. Also show the matrix obtained by augmenting with the zero matrix matrix [$A|...
1
vote
1answer
32 views

Total Unimodularity of set of equality and inequality constraints by partitioning of rows

Consider binary decision variables $x_{ij}$ and $y_j$ where $ i \in \{1,2,\ldots,I\}$ and $ j \in \{1,2,\ldots,J\}$ for fixed integers $I$ and $J$. Consider the following feasibility prolem: \begin{...
0
votes
0answers
36 views

Show that this matrix is Totally unimodular

Suppose we know that $A \in R^{n\times n}, B\in R^{n\times n}, \begin{bmatrix}a \\ A\end{bmatrix}\in R^{(n+1)\times n}$ and $[b \space B]\in R^{n\times(n+1)}$ are all total unimodular matrix. How can ...
1
vote
1answer
87 views

Making Matrix Totally Unimodular

Is there a way I can rewrite the following matrices to make the matrix (A) to be totally unimodular and still maintain the relevance of the equations. Thanks.
0
votes
1answer
107 views

How to prove that the matrix is totally unimodular?

I have the following matrix $$A=\pmatrix{1&0&0&0&0&0\\ 0&1&0&0&0&0\\ 0&0&1&0&0&0\\ 0&0&0&1&0&0\\0&0&0&0&...
1
vote
0answers
40 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 ...
0
votes
1answer
66 views

Is matrix $A$ totally unimodular?

Currently, I am looking at matrix $A$ and I am wondering if it is totally unimodular (TU). I would like to clarify if I truncate matrix $A$ such that the right hand side of the matrix is an identity ...
0
votes
0answers
119 views

Is this matrix TU?

Is the following matrix $A$ totally unimodular? $$A = \begin{pmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 0 &1 \end{pmatrix}$$ Recall that a matrix is ...
1
vote
1answer
76 views

General solution to linear program?

Source of the Problem The problem comes from an application in economics concerning trade between agents to maximize aggregate "wealth". More exactly, there are $m$ agents and $n$ groups and we ...
0
votes
1answer
97 views

Total Unimodularity in Integer QP

I have a Quadratic Programming problem with linear constraints. My objective is Quadratic-Convex, the constraint matrix is Totally Unimodular (similar to assignment or network flow problems), and the ...
1
vote
2answers
155 views

Is f1+f2 unimodal if f1 and f2 is monotonic?

I have recently encountered one programming problem which was reduced to find minimum value of function.Function f was sum of two functions f1 and f2 and f1 is strictly increasing and f2 is strictly ...
1
vote
1answer
611 views

If matrix $A$ is totally unimodular, then matrix $\begin{bmatrix} A &\pm A\end{bmatrix}$ is also totally unimodular

Given a totally unimodular matrix $A \in\{-1,0,1\}^{m\times n}$, show that the matrix $$\begin{bmatrix} A &\pm A\end{bmatrix}$$ is also totally unimodular. I want to prove that exchanging any two ...
0
votes
1answer
400 views

Consecutive One's and Identities, resulting on Totally Unimodular Matrix…

I'm trying to prove that a linear problem has integer extreme points. Looking at the matrix structures, I guess the easiest way to prove this is by showing that this matrix is totally unimodular. My ...
4
votes
1answer
190 views

Is this block matrix totally unimodular?

Suppose matrix $A \in \mathbb{R}^{m×n}$ has the consecutive ones property and, thus, is totally unimodular. Is the following block matrix also totally unimodular (TU)? $$B = \begin{pmatrix} A ...
0
votes
1answer
83 views

Minors of a particular matrix?

Take an $\frac{n(n-1)}2\times n$ matrix $M$ with $0/1$ entries each row distinct each row having two $1$s. Take an $\frac{n(n-1)}2\times \frac{n(n-1)}2$ matrix $N$ with $0/1$ entries each row ...
1
vote
2answers
416 views

A totally unimodular matrix

Is there a way to test whether the following rank-$6$ matrix is totally unimodular? $$\begin{bmatrix}1& 0& -1& 0& 0& 0& 0& 0\\0& 0& 0& 0& 1& 0& -1&...
1
vote
0answers
53 views

Does this property imply total unimodularity?

I have a matrix $M$ such that every entry in $M$ is $1,-1$ or $0$. My matrix also has the following property. Let $v_i$ and $v_j$ be two columns of $M$, and let $S$ be the set of row indices $s$ such ...
0
votes
1answer
114 views

Generating a totally unimodular matrix

Is there any method to randomly generate a totally unimodular matrix? Any algorithm or code will be appreciated.
1
vote
0answers
180 views

How to prove if the following matrix is totally unimodular (TU)?

I've already solved the linear relaxation of the problem and note that a relaxed version of the problem (without integral variables) results in integer solutions. \begin{matrix}1&1&0&0&...
1
vote
1answer
84 views

Is a matrix of subset indicator totally unimodular?

Let $S=\{1,\ldots, m\}$ and $A_1, \ldots, A_n$ be subsets of S. Let $B=(b_{ij})_{m\times n} = \{0,1\}_{m\times n}$ be a matrix such that $$ b_{ij}= \begin{cases} 1 & i \in A_j \\ ...
1
vote
1answer
384 views

Is this matrix totally unimodular?

Check whether the following matrix is totally unimodular. $$A=\pmatrix{0&0&0&1&0&0&0\\ 1&-1&0&0&1&0&1\\ 0&1&-1&-1&0&0&0\\ 0&...
1
vote
1answer
548 views

LP relaxation solves the integer program but the constraint matrix is not totally unimodular

I am solving an integer program (IP) whose constraint matrix is not totally unimodular (TU). The linear programming (LP) relaxation and the original IP always have the same optimal solution, or the LP ...
3
votes
1answer
341 views

Adapting a proof to show that a polyhedron has integer extreme points

Prove that the polyhedron $$P =\{(x_1, \ldots , x_m, x_{m+1}): 0\leq x_m \leq 1, 0 \leq x_i \leq x_{m+1} \text{ for } i = 1, \ldots , m \}$$ has integer extreme points. My Attempt: I have a similar ...
2
votes
1answer
668 views

Proof that the incidence matrix of a laminar family is TU.

A friend and I wrote a proof for this using the consecutive ones property that I haven't seen anywhere, so I thought I would share it here. $\textit{Def:}$ A matrix has the Total-Unimodularity (TU) ...
0
votes
1answer
316 views

Total Unimodularity and partition of the rows

I have a question regarding a theorem about total unimodularity and partition of the rows of a matrix. The theorem says that given a matrix $A \in \mathbb{Z}^{m\times n}$ , A is totally unimodular ...
2
votes
1answer
383 views

Prove that a certain block combination of totally unimodular matrices is totally unimodular

I conjecture the following. Given three rectangular matrices $A$, $B$ and $C$ such that the following two block matrices $ \begin{bmatrix} A & B \\ \end{bmatrix} $ and $ \begin{bmatrix} ...
1
vote
0answers
86 views

Block matrix containing incidence matrix of bipartite graph is TU?

I have the following question: Let A by a TU matrix, then the following matrix is TU $$ \begin{pmatrix}A&&-I\\-1&\cdots&-1\end{pmatrix} $$ i.e. the block matrix composed by $A$,...
1
vote
1answer
226 views

On the definition of totally unimodular matrix

I'm a bit confused about the definition of a totally unimodular matrix, since my lecture notes states that this matrix is not totally unimodular: $$\begin{pmatrix} 1 && 0 \\ 1 && -1 \...
4
votes
2answers
422 views

Is this block matrix also totally unimodular?

Suppose matrix $A\in \mathbb R^{m\times n}$ is totally unimodular (TUM). Is the following matrix also TUM? $$ \begin{pmatrix} A & 0 & 0 \\ 0 & A & 0 \\ ...
3
votes
0answers
176 views

Fourier Motzkin Elimination and totally unimodularity

Suppose $A\in \mathbb R^{m\times n}$ and $b\in \mathbb R^m$, and $A$ is totally unimodular (TUM). For the system $$Ax\leq b,$$ suppose I use Fourier-Motzkin elimination to eliminate first $k$ ...
0
votes
1answer
416 views

Adjacency matrix is totally unimodular

Prove that the adjacence matrix of a simple graph is totally unimodular... I know incidence matrices are totally unimodular because in every column there is a 1 and a -1... makes things easier. Any ...
2
votes
1answer
624 views

Show that matrix is totally unimodular

I want to show that this matrix is totally unimodular: \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & ...
4
votes
2answers
11k views

Prove that the matrix is totally unimodular

Is there any (theoretic) way I can prove the matrix is totally unimodular? I have tested it by Matlab and know it is TU, however I cannot prove it. ...
0
votes
1answer
563 views

Is the product of two totally unimodular matrices again totally unimodular?

For unimodular matrices this is the case. It seems reasonable that this is also the case for totally unimodular matrices, but I couldn't find a reference for this. Does someone know why it is true ...
4
votes
1answer
2k views

How to prove in a graph $G$, its incidence matrix $A$ is totally unimodular if and only if $G$ is a bipartite graph?

I'm learning network and transportation model. The question is not from my homework. I'm just curious about: In a graph $G$, its incidence matrix $A$ is totally unimodular if and only if $G$ is a ...
0
votes
1answer
1k views

Totally unimodular matrices and identity matrices

I know that if a matrix $A$ is Totally Unimodular (TU), then the matrix $(A\; I)$ is unimodular. Can I then say that the matrix $(A\; -I)$ is also TU? ($I$ is the identity block matrix)