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 $ $\...
sgk's user avatar
  • 33
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 ...
Michelle Gunawan's user avatar
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 ...
Mark L. Stone's user avatar