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?

  • 2
    $\begingroup$ 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? $\endgroup$
    – prubin
    Sep 14, 2022 at 22:59
  • $\begingroup$ @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. $\endgroup$ Sep 14, 2022 at 23:32
  • $\begingroup$ I think I'm missing something again. Isn't a basis matrix nonsingular by definition? $\endgroup$
    – prubin
    Sep 15, 2022 at 2:17

1 Answer 1


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

  • $\begingroup$ Would presolve always eliminate the possibility of the basis singuularity I mentioned in my comment? Could non-integer solution ever be returned with full presolve on, combined with IPM without crossover? $\endgroup$ Sep 14, 2022 at 23:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    Sep 15, 2022 at 0:00
  • 3
    $\begingroup$ Since interior-point methods generates a solution that is a convex combination of all optimal vertex solutions then the solution will not be integral for all problems. Furthermore, no presolve to the best of my knowledge can make sure the problem has a unique optimal vertex solution then this holds even if you use presolve. $\endgroup$ Sep 15, 2022 at 4:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.