Opened 5 years ago
Last modified 4 years ago
#18735 new enhancement
MixedIntegerLinearProgram/HybridBackend: Reconstruct exact rational/algebraic basic solution
Reported by:  mkoeppe  Owned by:  

Priority:  major  Milestone:  sage7.4 
Component:  numerical  Keywords:  lp 
Cc:  yzh, ncohen, dimpase  Merged in:  
Authors:  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/mkoeppe/hybrid_backend (Commits)  Commit:  26dad9482713c0a1bc4999b61ce52ed1f109d432 
Dependencies:  #18685, #18688, #20296  Stopgaps: 
Description (last modified by )
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 basisstatus 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 basisstatus 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 interiorpointtosimplex crossover (a classical paper: http://www.caam.rice.edu/caam/trs/91/TR9132.pdf)
In MIP mode, could at least try to set the cleanedup numerical solution vector as a known solution, to speed up branchandcut in the exact solver.
Sounds like a big ticket; we'll do this step by step.
#18685 provides the necessary basisstatus functions (for the GLPK backend). #18688 provides a solverindependent interface to these functions. #18804 exposes basis status via backend dictionaries.
Change History (15)
comment:1 Changed 5 years ago by
 Cc dimpase added
comment:2 followup: ↓ 5 Changed 5 years ago by
comment:3 Changed 5 years ago by
 Description modified (diff)
On the other hand, a solverindependent way to get an optimal dual solution is very much welcome, as this is lacking currently, and often needed.
comment:4 Changed 5 years ago by
 Description modified (diff)
comment:5 in reply to: ↑ 2 ; followup: ↓ 6 Changed 5 years ago by
Replying to dimpase:
Is
ppl
(ppl
LP backend, which works with exact arithmetic) too slow for you?
Dima, ppl's implementation of the double description method is very good, but its LP solver is not suitable for problems of even moderate sizes.
comment:6 in reply to: ↑ 5 ; followup: ↓ 7 Changed 5 years ago by
Replying to mkoeppe:
Replying to dimpase:
Is
ppl
(ppl
LP backend, which works with exact arithmetic) too slow for you?Dima, ppl's implementation of the double description method is very good, but its LP solver is not suitable for problems of even moderate sizes.
Would you mind providing an example of PPL choking on an LP doable in exact arithmetic by another solver? We use PPL's LP solver in codesize_upper_bound(...,algorithm="LP")
and never saw a problem... (Although perhaps the difficulty from entry sizes dominate the the one from the dimension in this case).
comment:7 in reply to: ↑ 6 ; followup: ↓ 8 Changed 5 years ago by
Replying to dimpase:
Would you mind providing an example of PPL choking on an LP doable in exact arithmetic by another solver? We use PPL's LP solver in
codesize_upper_bound(...,algorithm="LP")
and never saw a problem... (Although perhaps the difficulty from entry sizes dominate the the one from the dimension in this case).
In our experiments here, we don't actually have numerical difficulties with floatingpoint based solvers; we just want to be sure that we have an exact optimal solution. With #18764 (glp_exact; please review) we have now run some tests to compare performance:
glp_simplex glp_simplex+glp_exact glp_simplex glp_exact +glp_exact ppl + reconstruction in Sage 10 4.20 51.92 7.78 207.07 289.00 11 5.08 58.49 9.43 3451.42 574.72 12 7.55 101.72 11.32 1252.91 808.73 13 7.21 279.08 13.57 1424.28 1019.95 14 8.41 562.97 15.91 7343.37 1628.54 15 13.10 550.46 18.48 3667.93 2550.94
As you can see, PPL is much slower than pure glp_exact, and orders of magnitudes slower than glp_simplex followed by glp_exact.
However, currently when we try to reconstruct the solution from the combinatorial basis information, Sage's super slow matrix functions over the rationals get us back to roughly the same order of magnitude as PPL.
It would be interesting to know how the solvers perform on the kind of LPs that you have in mind.
comment:8 in reply to: ↑ 7 Changed 5 years ago by
Replying to mkoeppe:
It would be interesting to know how the solvers perform on the kind of LPs that you have in mind.
LPs I get would be not possible to even enter into a solver without long integers/rationals. That's e.g. behind this function call:
sage: codesize_upper_bound(70,8,2,algorithm="LP") 9695943911863423
more explicitly, you can do
sage: v,p,r=delsarte_bound_hamming_space(70,8,2,return_data=True) sage: p Mixed Integer Program ( maximization, 71 variables, 148 constraints )
constrains of p
have entries as big as 112186277816662845432.
comment:9 Changed 5 years ago by
 Description modified (diff)
 Summary changed from MixedIntegerLinearProgram: Reconstruct exact rational basic solution to MixedIntegerLinearProgram: Reconstruct exact rational/algebraic basic solution
comment:10 Changed 5 years ago by
 Dependencies changed from #18685, #18688 to #18685, #18688, #20296
 Description modified (diff)
 Summary changed from MixedIntegerLinearProgram: Reconstruct exact rational/algebraic basic solution to MixedIntegerLinearProgram/HybridBackend: Reconstruct exact rational/algebraic basic solution
comment:11 Changed 5 years ago by
 Description modified (diff)
comment:12 Changed 5 years ago by
 Branch set to u/mkoeppe/hybrid_backend
comment:13 Changed 5 years ago by
 Commit set to 0b8b78af1c9efbc118513cfde612eccb0bf735a6
 Description modified (diff)
Last 10 new commits:
e2319b5  InteractiveLPBackend.get_variable_value: Guard against standardform transformations

e27f297  InteractiveLPBackend: Make base_ring an init argument

5b0954f  InteractiveLPBackend._variable_type_from_bounds: Add doctests

c4b93aa  InteractiveLPBackend: Fix oldstyle raise statements

b0a3c1c  GenericBackend: Add a missing '# optional  Nonexistent_LP_solver'

3770be0  default_mip_solver: Handle 'InteractiveLP'

d91c776  default_mip_solver, get_solver: Mention InteractiveLP in the documentation

eaede28  get_solver: Add optional base_ring argument

184249d  MixedIntegerLinearProgram: New base_ring init argument

0b8b78a  HybridBackend: first draft

comment:14 Changed 4 years ago by
 Commit changed from 0b8b78af1c9efbc118513cfde612eccb0bf735a6 to 26dad9482713c0a1bc4999b61ce52ed1f109d432
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
26dad94  HybridBackend: first draft

comment:15 Changed 4 years ago by
 Milestone changed from sage6.8 to sage7.4
Is
ppl
(ppl
LP backend, which works with exact arithmetic) too slow for you?