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 Add glp_exact to Sage's GLPK bindings #18764)
• a slow, exact one that can set the simplex basis (only InteractiveLPBackend fits the bill - from MixedIntegerLinearProgram: New backend using InteractiveLPProblem #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.

Depends on #18685
Depends on #18688
Depends on #20296

CC: @yuan-zhou @nathanncohen @dimpase

Component: numerical

Author: Matthias Koeppe, Yuan Zhou

Branch/Commit: u/yzh/hybrid_backend @ 50773ff

Issue created by migration from https://trac.sagemath.org/ticket/18735