Skip to main content

Questions tagged [totally-unimodular]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4 votes
0 answers
43 views

Total Unimodularity of constraint matrix

Given a directed graph $G=(V,E)$, I have the following integer program- \begin{align} \max & \sum_{(u,v) \in E} \sum_{s \in S} w_{uv} z_{uv,s} + \sum_{v \in V} \sum_{s \in S} b_{v,s} x_{v,s} \\ \...
superhulk's user avatar
  • 223
8 votes
1 answer
1k views

Why do I get a binary solution even when I solve an LP problem with continuous variables?

I have a MILP in the following form maximize $${\bf c}^T{\bf x}$$ subject to $${\bf Ax}\le {\bf b}$$ Matrix ${\bf A}$ is a binary matrix, and very sparse. It is a larger matrix with 300 rows and 1000 ...
KGM's user avatar
  • 2,377
1 vote
0 answers
101 views

Converting a Linear Program with TU Constraint Matrix to a Nonlinear Convex Model: Solver Performance?

I'm currently working on a large Mixed Integer Program (MIP) where the constraint matrix is Totally Unimodular (TU), allowing me to model it as a Linear Program (LP) for efficiency, as total ...
graphtheory123's user avatar
4 votes
1 answer
244 views

Can we add a certain binary row to a matrix which preserves total unimodularity?

Suppose I have a matrix $A\in \{-1, 0, 1\}^{m\times n}$ which is Totally Unimodular (TU), and a vector $b^T \in \{-1, 0, 1\}^{1\times n}$ which has exactly one entry which is $1$ and exactly one entry ...
graphtheory123's user avatar
3 votes
1 answer
191 views

Assignment problem with mutually exclusive constraints has an integral polyhedron?

I have the following problem $\min \sum_{i\in I} \sum_{j \in J} c_{ij} x_{ij} $ $s.t. \sum_{j \in J} x_{ij} \leq b_i, \forall i \in I$ $\sum_{j \in S_l} x_{ij} \leq 1, \forall l \in L, i \in I $ $\...
sgk's user avatar
  • 33
3 votes
1 answer
119 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
7 votes
1 answer
307 views

Non-Integral Optimal Solutions of Totally Unimodular Linear Programs

If a Linear Program (LP) has Totally Unimodular constraint matrix, integer RHS vector, and has an optimal solution, then it has an integer optimal solution. But what about additional optimal solutions ...
Mark L. Stone's user avatar