# 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 which are not integer? Do any mainstream LP solvers ever return a non-integer optimal solution on such a problem? If so, can/does this happen if solved by 1) Simplex, 2a) Interior-Point with crossover, or 2b) Interior-Point without crossover?

Bottom line: Are you chancing it if you need an integer solution, but submit the problem as a continuous LP?

• I'm missing something. To be sure there is an integer optimum, you need the right hand side vector (call it $b$) to be integer. Assuming it is, $B^-1 b$ will be integer for any nonsingular square submatrix $B$ of your TUM constraint matrix $A$ -- so won't all corner point solutions be integer? That would seem to cover simplex and interior with crossover, wouldn't it?
– prubin
Sep 14, 2022 at 22:59
• @prubin I believe so (unless maybe problem is degenerate, basis is singular - I don't really understand the details on that - can Simplex or IPM with crossover get in that situation?) That still leaves the question of Interior-Point without crossover.- I guess don't use that if you want to make sure that the solver doesn't return non-integer solution. I edited to incorporate the integer requirement on RHS vector. Sep 14, 2022 at 23:32
• I think I'm missing something again. Isn't a basis matrix nonsingular by definition?
– prubin
Sep 15, 2022 at 2:17

With presolver and crossover both disabled, the SAS interior point algorithm returns $$x_{ij} = 1/n$$ for the (TU) problem of sending one unit of flow from node $$0$$ to node $$n+1$$ in a directed network with arcs $$(0,i)$$ and $$(i,n+1)$$ for $$i\in\{1,\dots,n\}$$ and all arc costs $$1$$.
• Not sure about basis singularity, but with a random network and constant $0$ objective, I consistently get fractional solutions from interior point with aggressive presolve and no crossover. Sep 15, 2022 at 0:00