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
Filter by
Sorted by
Tagged with
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 ...
Rafael Colares's user avatar
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$ ...
user91360's user avatar
  • 1,221
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 ...
UniStuffz's user avatar
  • 932
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 ...
Michelle Gunawan's user avatar
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 \...
Michelle Gunawan's user avatar
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 ...
samabu's user avatar
  • 713
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 &...
mjsl's user avatar
  • 11
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\;|\;...
James Anderson's user avatar
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&-...
Alex's user avatar
  • 137
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 ...
user91360's user avatar
  • 1,221
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} \...
Daniel's user avatar
  • 558
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, ...
Dibbendu Roy's user avatar
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.
David's user avatar
  • 31
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 ...
Ozzy's user avatar
  • 387
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 ...
TheOppositeOfEuler's user avatar
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&...
KshMny's user avatar
  • 11
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_{...
1233023's user avatar
  • 543
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$,...
esv's user avatar
  • 21
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 ...
Dr.'s user avatar
  • 11
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 ...
Daniel's user avatar
  • 558
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 ...
Juan's user avatar
  • 35
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 ...
LSE_Student's user avatar
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 ...
Niranjana's user avatar
-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
Singh's user avatar
  • 1