Questions tagged [totally-unimodular]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
1 answer

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 $ $\...
3 votes
1 answer

Totally unimodular towards linear programming relaxation

I'm currently studying about totally unimodular. I was reading this link:, from page 38-41 and I came across the statement: 'It is clear that ...
7 votes
1 answer

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 ...