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