arbitrary precision LP solver backend

[dimpase]

There is currently no arbitrary precision LP solver backend available. It is sorely missed in some coding theory -related LP computations, see #12418.

One option is to hook up PPL, another might be to hook up GLPK for this purpose. Both have the corresponding functionality, it's just not exposed (?) in P(C)ython for GLPK, and not hooked up as an LP backend in case of PPL.

To try this patch, apply attachment: trac_12533_arbitrary_precision_LP_solver_backend_for_5.3_vb.patch

Depends on #13646

CC: @sagetrac-jpang @kini @wdjoyner @nathanncohen @ppurka @vbraun @ptrrsn @dcoudert

Component: linear programming

Keywords: arbitrary precision

Author: Risan

Reviewer: David Coudert, Nathann Cohen, Dmitrii Pasechnik

Merged: sage-5.5.beta2

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

[dimpase]

comment:49

I do not understand a strange kludge with get_exact_variable_value vs get_variable_value. Why don't you implement get_ariable_value to return what get_exact_variable_value does?

Yes, something needs to be changed in the GenericBackend to accommodate this. Is it hard? It certainly needs a generic type then.

[dimpase]

comment:50

PPL must be listed among available backends in the INPUT section of MixedIntegerLinearProgram in mip.pyx.

Also, I noticed that get_min and get_max in mip.pyx currently return floats even for the PPL backend, which is plainly wrong, and needs to be fixed. This is actually very easy, see/apply the attached patch (which also fixes few similar things related to setting coefficients of the objective function).

[dimpase]

Attachment: 12533-fix_min_max.gz

fixing the imprecision bug in setting min/max of variables

[ptrrsn]

Description changed:

--- 
+++ 
@@ -1,3 +1,5 @@
 There is currently no arbitrary precision LP solver backend available. It is sorely missed in some coding theory -related LP computations, see  #12418.

 One option is to hook up [PPL](http://www.sagemath.org/doc/reference/sage/libs/ppl.html), another might be to hook up GLPK for this purpose. Both have the corresponding functionality, it's just not exposed (?) in P(C)ython for GLPK, and not hooked up as an LP backend in case of PPL.
+
+To try this patch, apply "trac_12533_arbitrary_precision_LP_solver_backend.patch" on Sage 5.1.

[ptrrsn]

comment:52

Hi,

Replying to @vbraun:

Generally speaking, looks good! There are a few nitpicks:

In #12553, I modified the PPL classes to derive from SageObject. This'll make it play nicer with the rest of Sage. Correspondingly you should override _repr_, not __repr__.

Could you explain what is the difference between them? I could not find any information about repr.

Also needs to dump the actual information of the MIP_problem or its useless in other doctests. Speaking of which, the method needs a doctest. Also, in English you'd say "A MIP" not "An MIP", but really the output should be more specific.

Ok, I have changed it. However, it is still not very specific because I could not get the constraint system information from the actual PPL object. There is constraints_begin() and constraints_end() methods in the actual PPL's MIP_Problem. However, I am not sure how to use them (they are const_iterators).

All expensive operations (that need to solve a LP, say) must be wrapped in sig_on/sig_off blocks. Be careful with exceptions thrown, use try/finally if necessary. Otherwise you'll get into expensive but untinterruptable computations...

Ok, I have fixed this.

Can we have a few less empty lines? No need for an empty line before and after the """ closing the docstring.

Yes, I have fixed them.

The INPUT: section should be formatted like

  - ``number`` (integer) -- description.

You often have only a single "-" between type and description.

Ok, fixed.

Coverage should be 100%:

[vbraun@volker-desktop hg]$ sage -coverage sage/numerical/backends/ppl_backend.pyx 
----------------------------------------------------------------------
sage/numerical/backends/ppl_backend.pyx
ERROR: Please add a `TestSuite(s).run()` doctest.
SCORE sage/numerical/backends/ppl_backend.pyx: 72% (24 of 33)

Missing documentation:
   * int add_variable(self, lower_bound=0.0, upper_bound=None, binary=False, continuous=True, integer=False, obj=0.0, name=None) except -1: """ Add a variable. This amounts to adding a new column to the matrix. By default, the variable is both positive and real. It has not been implemented for selecting the variable type yet. INPUT: - ``lower_bound`` - the lower bound of the variable (default: 0) - ``upper_bound`` - the upper bound of the variable (default: ``None``) - ``binary`` - ``True`` if the variable is binary (default: ``False``). - ``continuous`` - ``True`` if the variable is binary (default: ``True``). - ``integer`` - ``True`` if the variable is binary (default: ``False``). - ``obj`` - (optional) coefficient of this variable in the objective function (default: 0.0) - ``name`` - an optional name for the newly added variable (default: ``None``). OUTPUT: The index of the newly created variable EXAMPLE:: sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "PPL") sage: p.ncols() 0 sage: p.add_variable() 0 sage: p.ncols() 1 sage: p.add_variable(lower_bound=-2.0) 1 sage: p.add_variable(name='x',obj=1.0) 2 sage: p.col_name(2) 'x' sage: p.objective_coefficient(2) 1.00000000000000 """ for i in range(len(self.Matrix)):
   * int add_variables(self, int n, lower_bound=0.0, upper_bound=None, binary=False, continuous=True, integer=False, obj=0.0, names=None) except -1: """ Add ``n`` variables. This amounts to adding new columns to the matrix. By default, the variables are both positive and real. It has not been implemented for selecting the variable type yet. INPUT: - ``n`` - the number of new variables (must be > 0) - ``lower_bound`` - the lower bound of the variable (default: 0) - ``upper_bound`` - the upper bound of the variable (default: ``None``) - ``binary`` - ``True`` if the variable is binary (default: ``False``). - ``continuous`` - ``True`` if the variable is binary (default: ``True``). - ``integer`` - ``True`` if the variable is binary (default: ``False``). - ``obj`` - (optional) coefficient of all variables in the objective function (default: 0.0) - ``names`` - optional list of names (default: ``None``) OUTPUT: The index of the variable created last. EXAMPLE:: sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "PPL") sage: p.ncols() 0 sage: p.add_variables(5) 4 sage: p.ncols() 5 sage: p.add_variables(2, lower_bound=-2.0, names=['a','b']) 6 """ for k in range(n):
   * int solve(self) except -1: """ Solve the problem. .. NOTE:: This method raises ``MIPSolverException`` exceptions when the solution can not be computed for any reason (none exists, or the LP solver was not able to find it, etc...) EXAMPLE:: sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "PPL") sage: p.add_linear_constraints(5, 0, None) sage: p.add_col(range(5), range(5)) sage: p.solve() 0 sage: p.objective_coefficient(0,1) sage: p.solve() Traceback (most recent call last):

Missing doctests:
   * set_variable_type(self, int variable, int vtype):
   * set_verbosity(self, int level):
   * double get_objective_value(self):
   * double get_variable_value(self, int variable):
   * write_lp(self, char * name):
   * write_mps(self, char * name, int modern):

I have fixed the missing doctests by adding some doctests. However, the missing documentation error (all 3 of them) cannot be fixed although I have added enough documentations. I think the documentation detection system in sage probably contains bug (I am not sure) because the same things also happen when we test coverage on GLPK and Gurobi backend. The missing documentation error would only disappear if we removed "except -1" from each functions.

Finally, the ticket description should say which patch to apply for the sanity of the release manager.

Also, ptrrsn_1 should put his name on the trac author list (http://trac.sagemath.org) and populate the Author: field on the ticket.

Ok, done.

Thank you very much.

[ptrrsn]

comment:53

Hi,

Replying to @dimpase:

I do not understand a strange kludge with get_exact_variable_value vs get_variable_value. Why don't you implement get_ariable_value to return what get_exact_variable_value does?

Yes, something needs to be changed in the GenericBackend to accommodate this. Is it hard? It certainly needs a generic type then.

Ok, I have changed the GenericBackend and also GLPK Backend a bit to accomodate this. Now, we have only get_variable_value and get_objective_value.

Thank you.

[dimpase]

comment:55

Replying to @ptrrsn:

Replying to @vbraun:

Generally speaking, looks good! There are a few nitpicks:

In #12553, I modified the PPL classes to derive from SageObject. This'll make it play nicer with the rest of Sage. Correspondingly you should override _repr_, not __repr__.

Could you explain what is the difference between them? I could not find any information about repr.

I think Volker's #12553 depends on a slew of tickets that won't make it into 5.1. I'd like this to be kept for a later ticket than for now.

[dimpase]

comment:56

Replying to @ptrrsn:

Hi,

Replying to @dimpase:

I do not understand a strange kludge with get_exact_variable_value vs get_variable_value. Why don't you implement get_ariable_value to return what get_exact_variable_value does?

Yes, something needs to be changed in the GenericBackend to accommodate this. Is it hard? It certainly needs a generic type then.

Ok, I have changed the GenericBackend and also GLPK Backend a bit to accomodate this. Now, we have only get_variable_value and get_objective_value.

That's terrific! Nathann, could you have a look into this?

I understand that you also took care of 12533-fix_min_max.

Thank you.

[vbraun]

comment:57

Everything in Sage should derive from SageObject. See http://www.sagemath.org/doc/developer/coding_in_python.html#print-representation for more about the use of _repr_. The SageObject defines the double underscore methods (__repr__, a Python special method) and will try to dispatch them to the single-underscore
version (_repr_, a Sage convention).

Replying to @dimpase:

I think Volker's #12553 depends on a slew of tickets that won't make it into 5.1.

This ticket probably won't make it into 5.2. If progress is too slow for you then feel free to review my patches ;-)

[vbraun]

comment:58

Replying to @ptrrsn:

I think the documentation detection system in sage probably contains bug (I am not sure) because the same things also happen when we test coverage on GLPK and Gurobi backend. The missing documentation error would only disappear if we removed "except -1" from each functions.

Oh I didn't know that. Can you open a bug on trac so we don't forget about this issue?

[dimpase]

comment:59

Replying to @vbraun:

Replying to @dimpase:

I think Volker's #12553 depends on a slew of tickets that won't make it into 5.1.

This ticket probably won't make it into 5.2. If progress is too slow for you then feel free to review my patches ;-)

well, #12553 depends on so many patches that I got lost applying all of them manually. There should be a better way of dealing with this, say, putting the whole thing on github or bitbucket. It also depends upon a lot of patches that look too far from my areas of competence to have any say upon. In particular, #12553 depends upon

#11310 - Monkey-patch catchall `except:`

which is ear-marked sage-pending. By asking this ticket to depend upon #12553, you are effectively relegating it to sage-pending, aren't you?

[dimpase]

Description changed:

--- 
+++ 
@@ -2,4 +2,4 @@

 One option is to hook up [PPL](http://www.sagemath.org/doc/reference/sage/libs/ppl.html), another might be to hook up GLPK for this purpose. Both have the corresponding functionality, it's just not exposed (?) in P(C)ython for GLPK, and not hooked up as an LP backend in case of PPL.

-To try this patch, apply "trac_12533_arbitrary_precision_LP_solver_backend.patch" on Sage 5.1.
+To try this patch, apply "trac_12533_arbitrary_precision_LP_solver_backend.patch" on Sage 5.1 (or 5.2.rc0)

[dimpase]

comment:60

Still builds and works on Sage 5.2.rc0.

[dimpase]

Description changed:

--- 
+++ 
@@ -2,4 +2,4 @@

 One option is to hook up [PPL](http://www.sagemath.org/doc/reference/sage/libs/ppl.html), another might be to hook up GLPK for this purpose. Both have the corresponding functionality, it's just not exposed (?) in P(C)ython for GLPK, and not hooked up as an LP backend in case of PPL.

-To try this patch, apply "trac_12533_arbitrary_precision_LP_solver_backend.patch" on Sage 5.1 (or 5.2.rc0)
+To try this patch, apply ["trac_12533_arbitrary_precision_LP_solver_backend.patch"](https://github.com/sagemath/sage-prod/files/10654897/trac_12533_arbitrary_precision_LP_solver_backend.patch.gz) on Sage 5.1 (or 5.2.rc0)

[dimpase]

comment:62

the changes done to sage/numerical/backends/glpk_backend.pyx must also be done to the other affected LP backends.

Nathann (posted by Dima)

e.g. for Coin one should do:

diff --git a/sage/numerical/backends/coin_backend.pyx b/sage/numerical/backends/coin_backend.pyx
--- a/sage/numerical/backends/coin_backend.pyx
+++ b/sage/numerical/backends/coin_backend.pyx
@@ -770,7 +770,7 @@
         del self.model
         self.model = model

-    cpdef double get_objective_value(self):
+    cpdef get_objective_value(self):
         r"""
         Returns the value of the objective function.

@@ -797,7 +797,7 @@
         """
         return self.model.solver().getObjValue() + self.obj_constant_term

-    cpdef double get_variable_value(self, int variable):
+    cpdef get_variable_value(self, int variable):
         r"""
         Returns the value of a variable given by the solver.

[dimpase]

comment:63

Please see attached double_trouble_fixing.patch for fixes related to hardcoded double and 0.0. It also fixes several bugs in ppl_backend, namely absence of code dealing with obj_constant_term and

a bug in variable_lower_bound() and variable_upper_bound() preventing a possibility to set bounds to None.

[dimpase]

fixing hardcoded double and 0.0, etc

[ptrrsn]

Attachment: double_trouble_fixing.patch.gz

[ptrrsn]

comment:64

Attachment: trac_12533_arbitrary_precision_LP_solver_backend.patch.gz

[dimpase]

comment:65

Replying to @ptrrsn: Great, compiles on 5.4.beta0, thanks! By the way:

python `which cython` --cplus --old-style-globals --embed-positions --directive cdivision=True,autotestdict=False,fast_getattr=True -I/usr/local/src/sage/sage-5.4.beta0/devel/sage-main -o sage/libs/ppl.cpp sage/libs/ppl.pyx
warning: sage/libs/ppl.pyx:1925:97: local variable 'maximum' referenced before assignment
warning: sage/libs/ppl.pyx:1996:97: local variable 'minimum' referenced before assignment

Have you forgotten initialization there?

[vbraun]

comment:66

The "referenced before assignment" warning is invalid, see http://trac.cython.org/cython_trac/ticket/714. Its a tricky case because the code in question involves C++ call by reference, but Python of course only knows call by value.

[vbraun]

comment:67

patchbot: apply trac_12533_arbitrary_precision_LP_solver_backend.patch

[robertwb]

comment:68

patchbot: apply only trac_12533_arbitrary_precision_LP_solver_backend.patch

[ptrrsn]

Attachment: trac_12533_arbitrary_precision_LP_solver_backend_for_5.3.patch.gz

for sage 5.3

[ptrrsn]

Description changed:

--- 
+++ 
@@ -2,4 +2,4 @@

 One option is to hook up [PPL](http://www.sagemath.org/doc/reference/sage/libs/ppl.html), another might be to hook up GLPK for this purpose. Both have the corresponding functionality, it's just not exposed (?) in P(C)ython for GLPK, and not hooked up as an LP backend in case of PPL.

-To try this patch, apply ["trac_12533_arbitrary_precision_LP_solver_backend.patch"](https://github.com/sagemath/sage-prod/files/10654897/trac_12533_arbitrary_precision_LP_solver_backend.patch.gz) on Sage 5.1 (or 5.2.rc0)
+To try this patch, apply ["trac_12533_arbitrary_precision_LP_solver_backend_for_5.3.patch"](https://github.com/sagemath/sage-prod/files/10654898/trac_12533_arbitrary_precision_LP_solver_backend_for_5.3.patch.gz) on Sage 5.3

[ptrrsn]

Description changed:

[dimpase]

Changed work issues from see the latest comments to none

[dimpase]

Author: Risan

[dimpase]

Changed reviewer from David Coudert, Nathann Cohen to David Coudert, Nathann Cohen, Dmitrii Pasechnik

[dimpase]

comment:71

Works on 5.4.rc1, Linux and OSX 10.6. Positive review!

[jdemeyer]

Changed dependencies from 12553 to #12553

[vbraun]

Changed dependencies from #12553 to #12553, #13646

[vbraun]

comment:74

Rebased on top of #13646. No real changes were necessary.

[dimpase]

comment:75

Replying to @vbraun:

Rebased on top of #13646. No real changes were necessary.

But how can it be so? This backend does not compute in RDF, whereas in #13646 linear forms are RDF-hardcored?

[vbraun]

Updated patch

[vbraun]

comment:76

Attachment: trac_12533_arbitrary_precision_LP_solver_backend_for_5.3_vb.patch.gz

The coefficients are currently only converted to the base ring if the coercion system is required. For example:

sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable()
sage: x[1] - x[0]    # no coercion addition and negation only
x_0 -1 x_1
sage: 2 * x[1]       # ZZ(2) is coerced into the coefficient ring
2.0 x_0

It would be more consistent if coefficients were always converted into the base ring, but that would definitely require cooperation from the backends.

[dimpase]

comment:77

Replying to @vbraun:

The coefficients are currently only converted to the base ring if the coercion system is required.

But here RDF is the wrong ring to convert to. With your latest patch I get:

sage: p = MixedIntegerLinearProgram(solver='ppl')
sage: x = p.new_variable()
sage: 2 * x[1]
2.0 x_0
sage: 

which breaks the ppl backend, as 2.0 is RDF. How one is supposed to enter the system without the (wrong) conversion?

It would help a lot if you at least outline the functionality you need in backends to make this work properly in some detail.

[vbraun]

Changed dependencies from #12553, #13646 to #13646

[vbraun]

comment:78

You can always use the dictionary notation to avoid any coercions:

sage: p = MixedIntegerLinearProgram(solver='ppl')
sage: p({1:2})
2 x_1

Of course that is highly inconvenient. The backends just need a method base_ring(), say, that returns the base ring that the backend wants. But all backends need to be changed for that, obviously. Let's do this on another ticket, I've opened #13650 for this. How about you review #13646 and I'll write a patch in #13650 on top of this ticket.

[dimpase]

comment:79

Replying to @vbraun:

How about you review #13646 and I'll write a patch in #13650 on top of this ticket.

Sure, just let's figure out the best way to fix this. I just posted something on #13650 in this respect.

[dimpase]

Changed dependencies from #13646 to #13646, #13650

[dimpase]

Description changed:

--- 
+++ 
@@ -2,4 +2,4 @@

 One option is to hook up [PPL](http://www.sagemath.org/doc/reference/sage/libs/ppl.html), another might be to hook up GLPK for this purpose. Both have the corresponding functionality, it's just not exposed (?) in P(C)ython for GLPK, and not hooked up as an LP backend in case of PPL.

-To try this patch, apply ["trac_12533_arbitrary_precision_LP_solver_backend_for_5.3.patch"](https://github.com/sagemath/sage-prod/files/10654898/trac_12533_arbitrary_precision_LP_solver_backend_for_5.3.patch.gz) on Sage 5.3
+To try this patch, apply ["trac_12533_arbitrary_precision_LP_solver_backend_for_5.3_vb.patch"](https://github.com/sagemath/sage-prod/files/10654899/trac_12533_arbitrary_precision_LP_solver_backend_for_5.3_vb.patch.gz) on Sage 5.3

[dimpase]

Changed dependencies from #13646, #13650 to #13646

[dimpase]

comment:81

oops, #13650 is not a dependence, in the sense it must come come after this one.

To get the whole chain of patches right, apply #13646, then the current ticket (#12533), then #13650. Eventually, #12091 (when it's ready).

This is all for Sage 5.4.rc2.

[jdemeyer]

Description changed:

--- 
+++ 
@@ -2,4 +2,4 @@

 One option is to hook up [PPL](http://www.sagemath.org/doc/reference/sage/libs/ppl.html), another might be to hook up GLPK for this purpose. Both have the corresponding functionality, it's just not exposed (?) in P(C)ython for GLPK, and not hooked up as an LP backend in case of PPL.

-To try this patch, apply ["trac_12533_arbitrary_precision_LP_solver_backend_for_5.3_vb.patch"](https://github.com/sagemath/sage-prod/files/10654899/trac_12533_arbitrary_precision_LP_solver_backend_for_5.3_vb.patch.gz) on Sage 5.3
+To try this patch, **apply** [attachment: trac_12533_arbitrary_precision_LP_solver_backend_for_5.3_vb.patch](https://github.com/sagemath/sage-prod/files/10654899/trac_12533_arbitrary_precision_LP_solver_backend_for_5.3_vb.patch.gz)

[dimpase]

comment:84

in numerical/mip.pyx in show() there is (around line 701)

     cdef double c

which results in coefficients of constraints being converted into double before printing. And this is wrong for PPL backend. So one should just remove this declaration.

Volker, could you fold this into your patch on this ticket? Or somewhere else, e.g. in #12091?

[vbraun]

comment:85

It doesn't make sense here, you need the parents for constraints to keep the coefficients rational if solver='PPL'. I've added it to #12091.

[jdemeyer]

Merged: sage-5.5.beta2

[jdemeyer]

comment:87

This patch added a lot of

except ValueError, msg: 
    raise ValueError, msg 

blocks, what's the purpose of those? I plan to remove those in #15488.

[dimpase]

comment:88

Replying to @jdemeyer:

This patch added a lot of

except ValueError, msg: 
    raise ValueError, msg 

blocks, what's the purpose of those? I plan to remove those in #15488.

the author didn't have any prior cython experience, and this was overlooked by reviewers...