Opened 4 years ago

Last modified 3 years ago

#18735 new enhancement

MixedIntegerLinearProgram/HybridBackend: Reconstruct exact rational/algebraic basic solution

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-7.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 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.

Change History (15)

comment:1 Changed 4 years ago by mkoeppe

  • Cc dimpase added

comment:2 follow-up: Changed 4 years ago by dimpase

Is ppl (pplLP backend, which works with exact arithmetic) too slow for you?

comment:3 Changed 4 years ago by dimpase

  • Description modified (diff)

On the other hand, a solver-independent way to get an optimal dual solution is very much welcome, as this is lacking currently, and often needed.

comment:4 Changed 4 years ago by mkoeppe

  • Description modified (diff)

comment:5 in reply to: ↑ 2 ; follow-up: Changed 4 years ago by mkoeppe

Replying to dimpase:

Is ppl (pplLP 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 ; follow-up: Changed 4 years ago by dimpase

Replying to mkoeppe:

Replying to dimpase:

Is ppl (pplLP 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 ; follow-up: Changed 4 years ago by mkoeppe

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 floating-point 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.

Last edited 4 years ago by mkoeppe (previous) (diff)

comment:8 in reply to: ↑ 7 Changed 4 years ago by dimpase

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 4 years ago by mkoeppe

  • Description modified (diff)
  • Summary changed from MixedIntegerLinearProgram: Reconstruct exact rational basic solution to MixedIntegerLinearProgram: Reconstruct exact rational/algebraic basic solution

comment:10 Changed 4 years ago by mkoeppe

  • 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 4 years ago by mkoeppe

  • Description modified (diff)

comment:12 Changed 4 years ago by mkoeppe

  • Branch set to u/mkoeppe/hybrid_backend

comment:13 Changed 4 years ago by mkoeppe

  • Commit set to 0b8b78af1c9efbc118513cfde612eccb0bf735a6
  • Description modified (diff)

Last 10 new commits:

e2319b5InteractiveLPBackend.get_variable_value: Guard against standard-form transformations
e27f297InteractiveLPBackend: Make base_ring an init argument
5b0954fInteractiveLPBackend._variable_type_from_bounds: Add doctests
c4b93aaInteractiveLPBackend: Fix old-style raise statements
b0a3c1cGenericBackend: Add a missing '# optional - Nonexistent_LP_solver'
3770be0default_mip_solver: Handle 'InteractiveLP'
d91c776default_mip_solver, get_solver: Mention InteractiveLP in the documentation
eaede28get_solver: Add optional base_ring argument
184249dMixedIntegerLinearProgram: New base_ring init argument
0b8b78aHybridBackend: first draft

comment:14 Changed 3 years ago by git

  • Commit changed from 0b8b78af1c9efbc118513cfde612eccb0bf735a6 to 26dad9482713c0a1bc4999b61ce52ed1f109d432

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

26dad94HybridBackend: first draft

comment:15 Changed 3 years ago by mkoeppe

  • Milestone changed from sage-6.8 to sage-7.4
Note: See TracTickets for help on using tickets.