7
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 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 ♦
    Commented 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$
    – Mark L. Stone
    Commented Sep 14, 2022 at 23:32
  • $\begingroup$ I think I'm missing something again. Isn't a basis matrix nonsingular by definition? $\endgroup$
    – prubin ♦
    Commented Sep 15, 2022 at 2:17

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\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$
    – Mark L. Stone
    Commented 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
    Commented 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$
    – ErlingMOSEK
    Commented Sep 15, 2022 at 4:45

Your Answer

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

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