Questions tagged [total-unimodularity]
A totally unimodular matrix is a matrix for which every square non-singular submatrix is unimodular.
24
questions with no upvoted or accepted answers
5
votes
1
answer
413
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 ...
4
votes
0
answers
217
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$ ...
3
votes
1
answer
571
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 ...
1
vote
0
answers
136
views
Totally unimodular towards linear programming relaxation
I'm currently studying about totally unimodular.
I was reading this link: https://ostad.nit.ac.ir/upload/Integer_Programming_1.pdf, from page 38-41 and I came across the statement:
'It is clear that ...
1
vote
0
answers
120
views
What is an unimodular problem?
Given an optimization problem below:
$$ \min_{Y^m_{ij} \in \{0,1\}} \sum_{p \in P} \sum_{(i,j)\in A} \sum_{c \in C} n^c \rho_{ij}^{p,m(c)} X_{ij}^c\\
\text{where } X_{ij}^c \text{ solves:}\\
\min \...
1
vote
0
answers
68
views
Does adding linearly dependent columns to a totally unimodular matrix preserve total unimodilarity?
I was wondering the following. Given a totally unimodular matrix $A$ and a vector $b \in Im(A)$ is then the matrix $[A,b]$ totally unimodular too? My guess is no, since for total unimodilarity every ...
1
vote
1
answer
49
views
Is a TU matrix appended with smaller identity matrices still TU?
Let $A$ be a TU matrix of consecutive ones, and $I$ be an identity matrix.
We know a TU matrix appended to an identity matrix, e.g.,
$$\begin{bmatrix}
& & & | & & & \\
& A &...
1
vote
0
answers
100
views
Assume that $G$ is bipartite. Prove that all vertices of $Q_G$ are integral
Given $G=(V,E)$, let $\mathbb{R}^V$ be the set of all real vectors $x=(x_v)_{v\in V}$ where each component $x_v$ corresponds to a vertex $v\in V$. Let $Q_G$ be defined
$$Q_G:=\{x\in\mathbb{R}^V\;|\;...
1
vote
2
answers
206
views
Is the matrix totally unimodular?
Let $A=\begin{bmatrix}1&0&1&1&0&0&1&0&0\\0&1&0&1&0&0&0&0&0& \\0&0&1&1&1&0&0&0&0\\0&0&-1&-...
1
vote
0
answers
66
views
Properties of the value function generated by an integer progamming problem
Consider the following linear programming problem
max $w^\top x$ s.t.
$Ax\leq b, \,\,0\leq x\leq 1$,
where $x\in R^E, w \in\{0,1\}^E$, $A$ is a $\{0,\pm 1\}$ matrix and $b$ is a vector. Further ...
1
vote
1
answer
155
views
Prove that the matrix is totally unimodular, for any binary vector $a$
I need to prove that for every binary column vector $a\in\{0, 1\}^n$, the following matrix is totally unimodular:
$$ A =\left [ \begin{matrix}
I_n & a \\
a^T & 1 \\
\end{matrix} \...
1
vote
0
answers
40
views
Show that the following matrix or its corresponding system of constraints is Totally Unimodular (TU)
I have the following Integer Linear Program constraints:
\begin{align}
\sum_{c\in C}\sum_{i = 1}^{K^c} x_i^c(t) \leq \Lambda, \forall \: t \\
\sum_{t=0}^{H}\sum_{i = 1}^{K^c} x_i^c(t)\leq \Lambda^c, ...
1
vote
1
answer
270
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.
1
vote
0
answers
140
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 ...
1
vote
0
answers
68
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 ...
1
vote
0
answers
251
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
1
answer
701
views
Total unimodularity and partition of the rows
Theorem. A given matrix $A \in \mathbb{Z}^{m \times n}$ is totally unimodular iff for any $I \subset [m]$ there exist a partition of the set $I$, $(I_1, I_2)$, such that $$\sum_{i\in I_1}a_{i} - \sum_{...
1
vote
0
answers
107
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$,...
0
votes
0
answers
61
views
how to show a matrix is totally unimodular, 1-sum property
If $A, B \in \{0, 1, −1\}m×n$ are totally unimodular $(TU)$ matrices,
then show that the matrix
\begin{bmatrix}
A&0\\
0&B\end{bmatrix}
is also $TU$, where $O \in \{0\}$
m×n
is an all $0$’s ...
0
votes
0
answers
154
views
How to prove that the given matrix is totally unimodular?
I need to prove that if we concatenate a vector of ones to the bottom and to the right of the identity matrix, the resulting matrix is totally unimodular.
For example, for $2\times2$ identity matrix ...
0
votes
0
answers
66
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 ...
0
votes
0
answers
251
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 ...
0
votes
2
answers
246
views
Signing of a binary matrix to a totally unimodular matrix
I have the following binary matrix:
\begin{pmatrix}
1& 1& 1& 0 \\
0& 1& 1& 1\\
1& 0& 1& 1\\
1& 1& 0& 1\\
\end{pmatrix}
Definition: Signing a matrix ...
-1
votes
1
answer
28
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