Opened 7 years ago

Last modified 3 months ago

#18735 needs_work enhancement

MixedIntegerLinearProgram/HybridBackend: Reconstruct exact rational/algebraic basic solution

Reported by: Matthias Köppe Owned by:
Priority: major Milestone: sage-9.8
Component: numerical Keywords: lp
Cc: Yuan Zhou, Nathann Cohen, Dima Pasechnik Merged in:
Authors: Matthias Koeppe, Yuan Zhou Reviewers:
Report Upstream: N/A Work issues:
Branch: u/yzh/hybrid_backend (Commits, GitHub, GitLab) Commit: 50773ff8f9f277b758a1023effbbb5dbeffb0168
Dependencies: #18685, #18688, #20296 Stopgaps:

Status badges

Description (last modified by Matthias Köppe)

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 (47)

comment:1 Changed 7 years ago by Matthias Köppe

Cc: Dima Pasechnik added

comment:2 Changed 7 years ago by Dima Pasechnik

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

comment:3 Changed 7 years ago by Dima Pasechnik

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 7 years ago by Matthias Köppe

Description: modified (diff)

comment:5 in reply to:  2 ; Changed 7 years ago by Matthias Köppe

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 ; Changed 7 years ago by Dima Pasechnik

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 ; Changed 7 years ago by Matthias Köppe

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 7 years ago by Matthias Köppe (previous) (diff)

comment:8 in reply to:  7 Changed 7 years ago by Dima Pasechnik

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 7 years ago by Matthias Köppe

Description: modified (diff)
Summary: MixedIntegerLinearProgram: Reconstruct exact rational basic solutionMixedIntegerLinearProgram: Reconstruct exact rational/algebraic basic solution

comment:10 Changed 7 years ago by Matthias Köppe

Dependencies: #18685, #18688#18685, #18688, #20296
Description: modified (diff)
Summary: MixedIntegerLinearProgram: Reconstruct exact rational/algebraic basic solutionMixedIntegerLinearProgram/HybridBackend: Reconstruct exact rational/algebraic basic solution

comment:11 Changed 7 years ago by Matthias Köppe

Description: modified (diff)

comment:12 Changed 7 years ago by Matthias Köppe

Branch: u/mkoeppe/hybrid_backend

comment:13 Changed 7 years ago by Matthias Köppe

Commit: 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 6 years ago by git

Commit: 0b8b78af1c9efbc118513cfde612eccb0bf735a626dad9482713c0a1bc4999b61ce52ed1f109d432

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

26dad94HybridBackend: first draft

comment:15 Changed 6 years ago by Matthias Köppe

Milestone: sage-6.8sage-7.4

comment:16 Changed 22 months ago by Yuan Zhou

Branch: u/mkoeppe/hybrid_backendu/yzh/hybrid_backend

comment:17 Changed 22 months ago by git

Commit: 26dad9482713c0a1bc4999b61ce52ed1f109d4325ee77381d3f8dad0b60137c1f08158ec5668b25e

Branch pushed to git repo; I updated commit sha1. New commits:

5ee7738change Cython to Python code

comment:18 Changed 22 months ago by git

Commit: 5ee77381d3f8dad0b60137c1f08158ec5668b25e3431fc483be2286e419a92b6c57e92e701cbffa3

Branch pushed to git repo; I updated commit sha1. New commits:

3431fc4HybridBackend heritage of GenericBackend

comment:19 Changed 22 months ago by Dima Pasechnik

Milestone: sage-7.4sage-9.3

comment:20 Changed 22 months ago by git

Commit: 3431fc483be2286e419a92b6c57e92e701cbffa3c1951c9ff301b12d3c5d9fda0bf5ed0a6def282a

Branch pushed to git repo; I updated commit sha1. New commits:

c1951c9fix docstring style

comment:21 Changed 22 months ago by git

Commit: c1951c9ff301b12d3c5d9fda0bf5ed0a6def282ac15aaac11e8e0650cdf8a1b6f25d4cb5b7b4af37

Branch pushed to git repo; I updated commit sha1. New commits:

e176757add method objective_constant_term()
c53b4e0make iterable coefficients a list so that each backend can loop over coefficients
c15aaacfix doctests

comment:22 Changed 22 months ago by git

Commit: c15aaac11e8e0650cdf8a1b6f25d4cb5b7b4af3744bcb393291d78669ba64ac53f5b490e9ae4de9c

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

3e4e7e9fix docstrings
69a9775warm-start interactive_backend.solve() by providing basic_variables
676c74fwarm-start LPProblemStandardForm.run_revised_simplex_method by providing basic_variables
44bcb39HybridBackend.solve() reconstruct exact solution

comment:23 Changed 22 months ago by Yuan Zhou

Authors: Yuan Zhou
Status: newneeds_review

comment:24 Changed 22 months ago by Yuan Zhou

Authors: Yuan ZhouMatthias Koeppe, Yuan Zhou

comment:25 Changed 22 months ago by Matthias Köppe

I don't like the changes to src/sage/numerical/interactive_simplex_method.py too much.

Instead of extending InteractiveLPProblemStandardForm.run_revised_simplex_method, I think it's better to use the "run_simplex_method" method of the current_dictionary (a revised dictionary) directly.

Same amount of code, but would avoid making interactive_simplex_method more complicated.

comment:26 Changed 22 months ago by git

Commit: 44bcb393291d78669ba64ac53f5b490e9ae4de9c1f9d00adeca30d58c8b23e66570e71d1b7723a4d

Branch pushed to git repo; I updated commit sha1. New commits:

5b19c41Revert "warm-start LPProblemStandardForm.run_revised_simplex_method by providing basic_variables"
1f9d00arevise interactive_backend.solve() given starting basis

comment:27 in reply to:  25 Changed 22 months ago by Yuan Zhou

Replying to mkoeppe:

I don't like the changes to src/sage/numerical/interactive_simplex_method.py too much.

Instead of extending InteractiveLPProblemStandardForm.run_revised_simplex_method, I think it's better to use the "run_simplex_method" method of the current_dictionary (a revised dictionary) directly.

Same amount of code, but would avoid making interactive_simplex_method more complicated.

Good idea. Done.

comment:28 Changed 22 months ago by Matthias Köppe

Also, I think it would be better to avoid changing the solve interface:

-    cpdef int solve(self) except -1:
+    cpdef int solve(self,  basic_variables=[]) except -1:

Setting an initial basis could be done in a new method perhaps called warmstart(basic_variables) or set_basis(basic_variables)

comment:29 Changed 22 months ago by Matthias Köppe

And note that generic backend already defines getter methods for the basis status is_variable_basic, is_variable_nonbasic_at_lower_bound, is_slack_variable_basic, is_slack_variable_nonbasic_at_lower_bound - all of which use variable/row indices.

So this interface:

+            ``basic_variables`` can be one of the following:
+
+            - a list of indices. The indices (starting at 1) correspond to that of the vector formed by `self.interactive_lp_problem().decision_variables()` and `self.interactive_lp_problem().slack_variables()`. Remark that `self.interactive_lp_problem()` can have more variables and constraints than that of `self` if `self` has free variables or `==` constraints.
+
+            - a list of the names of the variables in `self.interactive_lp_problem()`.

looks a bit out of place.

Last edited 22 months ago by Matthias Köppe (previous) (diff)

comment:30 in reply to:  29 Changed 22 months ago by Yuan Zhou

What would be a better input form? Remove the second option and take only a list of indices?

It is tricky because the indices here correspond to the variables in the interactive_lp_problem().standard_form(), and they not necessarily the same as the indices for is_variable_basic etc. which correspond to interactive_lp_problem(). See the following example.

from sage.numerical.backends.generic_backend import get_solver
h = get_solver(solver = ("InteractiveLP"))
h.add_variables(1, lower_bound=None, upper_bound=None);
h.add_variables(1, lower_bound=0, upper_bound=None);
h.add_linear_constraint([(0,2),(1,-1)],-1,None)
h.add_linear_constraint([(0,1),(1,-1)],None, 1)
h.add_linear_constraint([(0,1),(1,1)],2,2)
h.set_objective([0,-1])
lp = h.interactive_lp_problem(); view(lp)
st = lp.standard_form(); view(st)
R = st.coordinate_ring(); R

Replying to mkoeppe:

And note that generic backend already defines getter methods for the basis status is_variable_basic, is_variable_nonbasic_at_lower_bound, is_slack_variable_basic, is_slack_variable_nonbasic_at_lower_bound - all of which use variable/row indices.

So this interface:

+            ``basic_variables`` can be one of the following:
+
+            - a list of indices. The indices (starting at 1) correspond to that of the vector formed by `self.interactive_lp_problem().decision_variables()` and `self.interactive_lp_problem().slack_variables()`. Remark that `self.interactive_lp_problem()` can have more variables and constraints than that of `self` if `self` has free variables or `==` constraints.
+
+            - a list of the names of the variables in `self.interactive_lp_problem()`.

looks a bit out of place.

comment:31 Changed 22 months ago by Matthias Köppe

Status: needs_reviewneeds_work

comment:32 Changed 22 months ago by git

Commit: 1f9d00adeca30d58c8b23e66570e71d1b7723a4ddc36f82f2c31e9e0e414289d007b65c0fb4ce700

Branch pushed to git repo; I updated commit sha1. New commits:

dc36f82set InteractiveLPBackend.current_dictionary and warm start solve from there

comment:33 in reply to:  28 Changed 22 months ago by Yuan Zhou

Status: needs_workneeds_review

Replying to mkoeppe:

Also, I think it would be better to avoid changing the solve interface:

-    cpdef int solve(self) except -1:
+    cpdef int solve(self,  basic_variables=[]) except -1:

Setting an initial basis could be done in a new method perhaps called warmstart(basic_variables) or set_basis(basic_variables)

InteractiveLPBackend now has a new method set_dictionary and a new attribute current_dictionary. I didn't name it set_basis, to avoid confusion between the basic variables in a dictionary and those of the generic backend.

comment:34 Changed 22 months ago by Matthias Köppe

I still have concerns about the new interface as well. The problem now is that set_basis is not defined for any backend other than InteractiveLPBackend (and also its interface refers to internal details of that).

But more importantly, there should be at least one example that illustrates that this new backend does something useful.

comment:35 in reply to:  34 ; Changed 22 months ago by Yuan Zhou

Replying to mkoeppe:

I still have concerns about the new interface as well. The problem now is that set_basis is not defined for any backend other than InteractiveLPBackend (and also its interface refers to internal details of that).

Do you mean set_dictionary? It has a different interface than set_basis (in #18688 to be written) since the interactive_simplex_method is indeed very special in running the simplex method on the standard form where more auxiliary variables are introduced. I couldn't think of a way to unify InteractiveLPBackend.set_dictionary with other backends' set basis methods.

But more importantly, there should be at least one example that illustrates that this new backend does something useful.

True. The current implementation enables what the first paragraph of this ticket states, by using solver = ("GLPK", "InteractiveLP") as in the examples in solve. However, it is hard to argue with doctests that this new hybrid backend is useful. Shall we close the ticket with the tag "wontfix" as in #18804?

comment:36 in reply to:  35 Changed 22 months ago by Matthias Köppe

Replying to yzh:

Replying to mkoeppe:

I still have concerns about the new interface as well. The problem now is that set_basis is not defined for any backend other than InteractiveLPBackend (and also its interface refers to internal details of that).

Do you mean set_dictionary?

Yes, that's what I meant.

comment:37 Changed 21 months ago by Matthias Köppe

Milestone: sage-9.3sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

comment:38 Changed 20 months ago by git

Commit: dc36f82f2c31e9e0e414289d007b65c0fb4ce70071ae94d57b06bd58a1cf02a9b286bcbe881a0fcc

Branch pushed to git repo; I updated commit sha1. New commits:

71ae94dReplace not hasattr(self, 'xyz') by self.xyz is None

comment:39 Changed 17 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

Setting a new milestone for this ticket based on a cursory review.

comment:40 Changed 12 months ago by Dima Pasechnik

please rebase

comment:41 Changed 12 months ago by Dima Pasechnik

Status: needs_reviewneeds_work

comment:42 Changed 12 months ago by Matthias Köppe

Milestone: sage-9.5sage-9.6

comment:43 Changed 9 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:44 Changed 8 months ago by git

Commit: 71ae94d57b06bd58a1cf02a9b286bcbe881a0fccb6dd9abfa2d86658f109276b9e3ecf0ede77da3a

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

c4fb42badd method objective_constant_term()
c40ac50make iterable coefficients a list so that each backend can loop over coefficients
5abb5fefix docstrings
725b31dwarm-start interactive_backend.solve() by providing basic_variables
b323cd3warm-start LPProblemStandardForm.run_revised_simplex_method by providing basic_variables
084fd16HybridBackend.solve() reconstruct exact solution
b8042f6Revert "warm-start LPProblemStandardForm.run_revised_simplex_method by providing basic_variables"
0c4a3darevise interactive_backend.solve() given starting basis
3674768set InteractiveLPBackend.current_dictionary and warm start solve from there
b6dd9abReplace not hasattr(self, 'xyz') by self.xyz is None

comment:45 Changed 8 months ago by git

Commit: b6dd9abfa2d86658f109276b9e3ecf0ede77da3a1ab3f8678edfd2e8074685496dd16457f81350af

Branch pushed to git repo; I updated commit sha1. New commits:

1ab3f86fix double def in interactivelp_backend.pxd

comment:46 Changed 8 months ago by git

Commit: 1ab3f8678edfd2e8074685496dd16457f81350af50773ff8f9f277b758a1023effbbb5dbeffb0168

Branch pushed to git repo; I updated commit sha1. New commits:

50773fffix typo in docstring of variable_upper/lower_bound

comment:47 Changed 3 months ago by Matthias Köppe

Milestone: sage-9.7sage-9.8
Note: See TracTickets for help on using tickets.