id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,merged,author,reviewer,upstream,work_issues,branch,commit,dependencies,stopgaps
18735,MixedIntegerLinearProgram/HybridBackend: Reconstruct exact rational/algebraic basic solution,mkoeppe,,"Sometimes one can use a fast numerical LP solver to solve a problem to ""optimality"",
then reconstruct the primal and dual solution in rational arithmetic (or over whatever base_ring was used...) and in this way prove that this basis is indeed optimal.
`MixedIntegerLinearProgram` should support this mode of operation.
The current branch, on top of #20296, attempts to do this by implementing a `HybridBackend`, which delegates to two backends:
- a fast, possibly inexact backend (Gurobi or GLPK or even GLPK with glp_exact -- see #18764)
- a slow, exact one that can set the simplex basis (only `InteractiveLPBackend` fits the bill - from #20296)
Ideally, in pure LP mode, both backends would support the basis-status functions that can transplant the (hopefully) optimal (hopefully-)basis from the inexact LP to the exact LP.
If the inexact LP cannot provide a basis (because its ""basis"" is not a basis due to numerics, or because basis-status functions are not available), one could at least try to make use of the numerical solution vector and try to reconstruct a basis, like in interior-point-to-simplex crossover (a classical paper: http://www.caam.rice.edu/caam/trs/91/TR91-32.pdf)
In MIP mode, could at least try to set the cleaned-up numerical solution vector as a known solution, to speed up branch-and-cut in the exact solver.
Sounds like a big ticket; we'll do this step by step.
#18685 provides the necessary basis-status functions (for the GLPK backend).
#18688 provides a solver-independent interface to these functions.
#18804 exposes basis status via backend dictionaries.
",enhancement,needs_review,major,sage-9.5,numerical,,lp,yzh ncohen dimpase,,"Matthias Koeppe, Yuan Zhou",,N/A,,u/yzh/hybrid_backend,71ae94d57b06bd58a1cf02a9b286bcbe881a0fcc,"#18685, #18688, #20296",