Opened 3 years ago

Closed 22 months ago

Last modified 9 months ago

#12533 closed enhancement (fixed)

arbitrary precision LP solver backend

Reported by: dimpase Owned by: ncohen
Priority: major Milestone: sage-5.5
Component: linear programming Keywords: arbitrary precision, LP
Cc: jpang, kini, wdj, ncohen, ppurka, vbraun, ptrrsn_1, dcoudert Merged in: sage-5.5.beta2
Authors: Risan Reviewers: David Coudert, Nathann Cohen, Dmitrii Pasechnik
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #13646 Stopgaps:

Description (last modified by jdemeyer)

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 trac_12533_arbitrary_precision_LP_solver_backend_for_5.3_vb.patch

Attachments (9)

trac_12533_catch_ppl_exception.patch (7.8 KB) - added by vbraun 2 years ago.
Initial patch
trac_12533-rebased.patch (54.8 KB) - added by kini 2 years ago.
apply to $SAGE_ROOT/devel/sage
trac_12533-rebased.2.patch (56.0 KB) - added by kini 2 years ago.
apply to $SAGE_ROOT/devel/sage
trac_12533_arbitrary_precision_LP_solver_backend_for_5.1.patch (56.6 KB) - added by ptrrsn_1 2 years ago.
for Sage 5.1.beta1
12533-fix_min_max (3.8 KB) - added by dimpase 2 years ago.
fixing the imprecision bug in setting min/max of variables
double_trouble_fixing.patch (10.5 KB) - added by dimpase 2 years ago.
fixing hardcoded double and 0.0, etc
trac_12533_arbitrary_precision_LP_solver_backend.patch (64.8 KB) - added by ptrrsn_1 2 years ago.
trac_12533_arbitrary_precision_LP_solver_backend_for_5.3.patch (64.8 KB) - added by ptrrsn_1 23 months ago.
for sage 5.3
trac_12533_arbitrary_precision_LP_solver_backend_for_5.3_vb.patch (64.4 KB) - added by vbraun 23 months ago.
Updated patch

Download all attachments as: .zip

Change History (97)

comment:1 Changed 3 years ago by vbraun

The PPL Cython wrapper should be fully functional for LP solving, its just providing a different interface than the MixedIntegerLinearProgram. I always wanted to have this more integrated but I don't have to solve plain LP's often (at least not in that language).

comment:2 Changed 3 years ago by dimpase

  • Cc ptrrsn_1 added

comment:3 Changed 3 years ago by ptrrsn_1

The file trac_12533_arbitrary_precision_LP_solver_backend.patch is a PPL backend for MixedIntegerLinearProgram. It works for all MixedIntegerLinearProgram functions related to general LP (excluding integer LP and binary LP) listed in http://www.sagemath.org/doc/reference/sage/numerical/mip.html, except for set_binary, set_integer, set_real, write_lp, write_mps.

A new MixedIntegerLinearProgram with PPL as solver can be gotten by setting the solver parameter in MixedIntegerLinearProgramming's constructor to "PPL", e.g. MixedIntegerLinearProgram(solver = "PPL")

The additional feature of this backend is, it supports arbitrary precision calculations. We can get the exact optimal value by setting the exact parameter in solve method to True, i.e. p.solve(exact = True). Similarly, we can get the exact optimal solution by setting the exact parameter in get_values to True, i.e. p.get_values(exact = True, ...), which by default will return a vector over QQ. However, we can also opt for the usual format of the optimal solution, i.e. as a dictionary instead of a vector over QQ, by setting the as_vector parameter to False, e.g. p.get_values(exact = True, as_vector = False).

comment:4 follow-up: Changed 3 years ago by ncohen

  • Status changed from new to needs_info

Wow !!! Amazing patch !! O_o

Should this ticket be in "needs_review" state now ?

I have not looked deeply into your patch (well, your comment was posted 10 minutes ago :-P) and besides my 'Wow-Impressive Work" comment I had a question to ask : is PPL an optional package ? Some parts of your code behave as if it were

 	865	    elif solver == "PPL": 
 	866	        try: 
 	867	            from sage.numerical.backends.ppl_backend import PPLBackend 
 	868	            default_solver = solver 
 	869	        except ImportError: 
 	870	            raise ValueError("PPL is not available. Please refer to the documentation to install it.") 

But the line you added in module_list.py makes me think it is standard. Also, that line :

for s in ["CPLEX", "GUROBI", "Coin", "GLPK", "PPL"]: 

has no meaning : Sage tries to find the first solver available on the machine, and GLPK is always available. Many of your methods need to be doctested and/or documented. The comments # optional - Nonexistent_LP_solver should also be replaced either by #optional - PPL if PPL is optional, and plainly removed otherwise.

Wow. Impressive work :-) I hope I will be able to expose the GLPK function too at some point so that we would have some way to compare the results... But Wow... :-)

Nathann

comment:5 in reply to: ↑ 4 Changed 3 years ago by dimpase

Replying to ncohen:

865 elif solver == "PPL":

indeed, PPL is a standard package now (I guess this check for its availability stems from some early code, when it wasn't standard). So this check should be removed.

Then, it needs an example where one can see the benefit of the arbitrary precision (already an example with 2 variables should do). The example I got from the author (Hi, Risan!). I modified the last line, as it was following an old design:

p = MixedIntegerLinearProgram(solver = "PPL")
x = p.new_variable()
n = 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000
p.set_objective(10 * n * x[1] + 50 * n * x[2])
p.add_constraint(10 * n * x[1] + 2 * n * x[2], max = 40 * n)
p.add_constraint(15 * n * x[1] + 30 * n * x[2], max = 40 * n)
print p.solve()
print p.solve(exact=True)

is probably good enough.

Lastly, the parameter as_vector should be set to False by default, not to True, to be consistent with the other LP interfaces.

comment:6 Changed 2 years ago by ptrrsn_1

  • Status changed from needs_info to needs_review

Hi Mr. Nathann and Prof. Dima,

Thank you!

I have finished the documentation. In addition, I have removed the redundant codes and setting the as_vector to False by default (and also fixing some bugs). In the attachment is the latest version of it.

Now, the status was changed to Need Review.

Thank you

Risan

comment:7 Changed 2 years ago by dcoudert

  • Cc dcoudert added

I like this patch !!!

I add a brief look at the code, and I found some functions always returning True or always False in ppl_backend.pyx. I suppose it is because current version is still in devel phase (indeed it's a lot of work).

  cpdef bint is_variable_binary(self, int index): 
 	750	        """ 
 	751	        Test whether the given variable is of binary type. 
...
 	768	        """ 
 	769	        return False 
 	770	 
 	771	    cpdef bint is_variable_integer(self, int index): 
 	772	        """ 
 	773	        Test whether the given variable is of integer type. 
...
 	789	        """ 
 	790	        return False 
 	791	 
 	792	    cpdef bint is_variable_continuous(self, int index): 
 	793	        """ 
 	794	        Test whether the given variable is of continuous/real type. 
...
 	811	        """ 
 	812	        return True 
 	813

Also, you could mention somewhere that PPL does not provide access to dual variables (my understanding from the documentation).

Nice work.

comment:8 Changed 2 years ago by ncohen

David, it actually is because this solver does not support integer variables. It solves exactly, but only continuous problems. Hence these methods are actually no problem. I thought that p.new_variable(binary = True) should raise an exception, however. What this patch actually needs is a big and deep review, because it really is a very nice thing :-)

comment:9 follow-up: Changed 2 years ago by davidloeffler

  • Status changed from needs_review to needs_work

A couple of doctests fail on the current beta (see patchbot)

comment:10 in reply to: ↑ 9 Changed 2 years ago by dimpase

Replying to davidloeffler:

A couple of doctests fail on the current beta (see patchbot)

I have no clue where to look. Could you please provide a link?

comment:11 follow-up: Changed 2 years ago by kini

Dima - it's the big circular gray icon at the top of this page - i.e. http://patchbot.sagemath.org/ticket/12533/

I can fix this once I get to Portland if you want, also fix up some formatting issues.

comment:12 in reply to: ↑ 11 Changed 2 years ago by dimpase

Replying to kini:

Dima - it's the big circular gray icon at the top of this page - i.e. http://patchbot.sagemath.org/ticket/12533/

I can fix this once I get to Portland if you want, also fix up some formatting issues.

yeah, OK, indeed, I forgot...

By the way, IMHO the following doctest (in ppl.pyx) won't fly:

 	535	            sage: MIP_Problem(0) 
 	536	            <sage.libs.ppl.MIP_Problem object at 0x7fae10fab5b8> 

looks very dodgy.

comment:13 Changed 2 years ago by kini

Yeah, the memory address should be elided, of course.

comment:14 Changed 2 years ago by ptrrsn_1

  • Status changed from needs_work to needs_review

Thank you! I have fixed the doctesting errors.

comment:15 follow-up: Changed 2 years ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to needs_work

Hello,

I can install the patch on sage-5.0.beta8 and all long tests are OK (all involved files). The documentation is build correctly and displayed properly.

However, I did some test based on the example of the optimizing_point function and got a segfault...

sage: from sage.libs.ppl import Variable, Constraint_System, MIP_Problem 
sage: x = Variable(0) 
sage: y = Variable(1) 
sage: m = MIP_Problem() 
sage: m.add_space_dimensions_and_embed(2) 
sage: m.add_constraint(x >= 0) 
sage: m.add_constraint(y >= 0) 
sage: m.add_constraint(3 * x + 5 * y <= 10) 
sage: m.set_objective_function(x + y) 
sage: m.optimizing_point() 
[10/3, 0] 
sage: z = Variable(2)
sage: m.add_constraint(z >= -3)
terminate called after throwing an instance of 'std::invalid_argument'
  what():  PPL::MIP_Problem::add_constraint(c):
c.space_dimension() == 3 exceeds this->space_dimension == 2.
...
/path-to-sage/sage-5.0.beta8/spkg/bin/sage: line 308: 29045 Aborted                 (core dumped) sage-ipython "$@" -i

Some tests should be added somewhere.

This will be a great patch!

comment:16 in reply to: ↑ 15 ; follow-up: Changed 2 years ago by ptrrsn_1

  • Status changed from needs_work to needs_review

Replying to dcoudert:

Hello,

I can install the patch on sage-5.0.beta8 and all long tests are OK (all involved files). The documentation is build correctly and displayed properly.

However, I did some test based on the example of the optimizing_point function and got a segfault...

sage: from sage.libs.ppl import Variable, Constraint_System, MIP_Problem 
sage: x = Variable(0) 
sage: y = Variable(1) 
sage: m = MIP_Problem() 
sage: m.add_space_dimensions_and_embed(2) 
sage: m.add_constraint(x >= 0) 
sage: m.add_constraint(y >= 0) 
sage: m.add_constraint(3 * x + 5 * y <= 10) 
sage: m.set_objective_function(x + y) 
sage: m.optimizing_point() 
[10/3, 0] 
sage: z = Variable(2)
sage: m.add_constraint(z >= -3)
terminate called after throwing an instance of 'std::invalid_argument'
  what():  PPL::MIP_Problem::add_constraint(c):
c.space_dimension() == 3 exceeds this->space_dimension == 2.
...
/path-to-sage/sage-5.0.beta8/spkg/bin/sage: line 308: 29045 Aborted                 (core dumped) sage-ipython "$@" -i

Some tests should be added somewhere.

Hi, thanks for your feedback!

It is actually not a bug. The statement "m.add_space_dimensions_and_embed(2)" increases the space dimension of the MIP_Problem from 0 (default) to 2. However, z is a variable in the third dimension (the number 2 in "z = Variable(2)" means the dimension of this variable is 2, which means it is in the third dimension since the numbering starts from zero). Since the dimension of the variable exceeds the space dimension of the MIP_Problem, it gives error.

An extra line should be added to make it works: sage: z = Variable(2) sage: m.add_space_dimensions_and_embed(1) sage: m.add_constraint(z >= -3)

This will be a great patch!

Thank you!

comment:17 in reply to: ↑ 16 ; follow-up: Changed 2 years ago by dcoudert

It's not only giving an error, it crashed my sage session.

Wouldn't it be possible to add some test to prevent such behavior? I think it would be much smarter than a crash.

comment:18 in reply to: ↑ 17 Changed 2 years ago by ptrrsn_1

  • Status changed from needs_review to needs_work

Replying to dcoudert:

It's not only giving an error, it crashed my sage session. Wouldn't it be possible to add some test to prevent such behavior? I think it would be much smarter than a crash.

I see. Yes, it is indeed troublesome. Now I realize that I also have not given enough exception handling in many other parts. I will fix them.

Thank you.

comment:19 Changed 2 years ago by vbraun

Its a bit tricky because the PPL_Generator C++ class has a private ctor and declaring Cython exceptions while returning a const reference has a bug. I'm pretty sure we need to copy the returned PPL_Generator in optimize_point and other functions.

Also, can we make optimize_point return a PPL point and not a list of gmp rationals? We needlessly deviate from the PPL api here.

Changed 2 years ago by vbraun

Initial patch

comment:20 follow-ups: Changed 2 years ago by vbraun

I've added a patch that catches the C++ exceptions and shows how to work around Cython/C++ issues in optimizing_point().

Things that need to be done:

  • MIP_Problem should derive from _mutable_or_immutable just like the polyhedron class. All mutating methods need to check that the MIP_Problem is mutable.
  • Doctests should be added for all caught C++ exceptions (see PPL documentation for which methods can raise exceptions)

comment:21 in reply to: ↑ 20 Changed 2 years ago by ptrrsn_1

Replying to vbraun:

I've added a patch that catches the C++ exceptions and shows how to work around Cython/C++ issues in optimizing_point().

Wow, that is a great help. Thank you!

Last edited 2 years ago by ptrrsn_1 (previous) (diff)

comment:22 in reply to: ↑ 20 Changed 2 years ago by jdemeyer

Replying to vbraun:

Doctests should be added for all caught C++ exceptions

Absolutely!

comment:23 Changed 2 years ago by ptrrsn_1

  • Status changed from needs_work to needs_review

comment:24 follow-ups: Changed 2 years ago by ncohen

  • Status changed from needs_review to needs_work

Helloooooooo Risan !!!

I just went over your patch, and some comments follow. Thank you very much for the work you put into that ! :-)

ppl.pyx

  • MIP_Problem : PPL can only solve continuous Linear Programs, can't it ? In this case why "MIP_*", unless it means something different from "Mixed Integer Program" ?
  • MIP_Problem.optimization_mode() prints something but does not return anything
  • MIP_Problem returns dictionaries : in MixedIntegerLinearProgram? we raise an exception for unbounded/infeasible problems, and return the objective's value otherwise. Just mentionning it in case you may like it, of course that's totally up to you ! I still think it wou * ld be easier to return, for instance, a string (unbounded/infeasible) when the problem has no solution, and the result otherwise.
  • optimal_value does not only return the objective value, it also solves the problem ! I think the docstring should be updated --> if the users calls this function several times, are the computations made over and over ?
  • optimization_mode and set_optimization_mode : we often do both in a unique function, i.e. a method with optional arguments such that optimization_mode() returns the mode and optimization_mode(-1) defines it as a minimization problem. I just noticed that it was not the case at all for MixedIntegerLinearProgram? methods, but I think we ought to change that :-)
  • is_satisfiable : does it also solve the problem ? I mean, if users type "if p.is_satisfiable(): a = p.optimal_value()" does it solve it twice ? The docstrings should say something about that.
  • what is the difference between optimal_value and evaluate_objective_function ? In particular the code seems to be pretty similar, so one function should probably call the other if two are necessary
  • OK : by looking at the docstring I have no idea what it does or what the invariants are, but of course it may also be that I am not part of the intended audience for this class

sage/libs/ppl_ files

  • Are these files part of the ppl spkg ? If so they should not be modified by a patch, and the spkg itself should be updated.. That's really a lot of work for nothing, but that's how things are done here until we change it :-/

mip.pyx

  • Why would you have to add anything to get_values and solve ? The flags you add would create problems instantly if the backend solver is not PPL !! I think nothing needs to be changed in that file --> if the backend is ppl then the values returned will be exact, otherwise they will just be the usual ones. But I do not see why these functions should be changed O_o

ppl_backend.pyx

  • All functions should be documented/tested, even 'cutsom ones' like print_data. Actually sage -coverage <filename> should never have to complain :-)
  • same thing with init_mip
  • add_variable[s] say that the variable are positive by default. Are they indeed ?
  • "set_variable_type" -- I think the best is for this method's code to be something like "raise Exception('This backend does not handle integer variables ! Read the doc !')"
  • why do you keep "exact" in the names of your get_values functions ? It would be easier to name then get_values, as anyway all the values given by the ppl interface are exact ?!

Others

  • Is ppl.pyx part of the documentation ? At least ppl_backend is not, so you should add it to doc/en/reference/numerical.rst
  • Some "advertisement" should be added to the doc. In many places the solvers are listed (ok, perhaps we should only list them at *one* place), so that users can find out that *exact* answer are returned when the solver is ppl
  • Variables : are they automatically strictly positive ? This is the default in the MIP class (because it is the default of the API we interface), and if PPL acts any differently this would mean that results would be different according to whether PPL or GLPK is used as a backend !
  • The patch *does not apply* on 5.0-rc1, so I can not even check whether tests pass !

Thank you again :-)

Nathann

Changed 2 years ago by kini

apply to $SAGE_ROOT/devel/sage

comment:25 Changed 2 years ago by kini

I rebased Risan's patch to 5.0.rc1. I also removed trailing whitespace from the patch.

comment:26 in reply to: ↑ 24 ; follow-up: Changed 2 years ago by dimpase

Replying to ncohen:

Hell([o]*10) Nathann [!]*5

ppl.pyx

  • MIP_Problem : PPL can only solve continuous Linear Programs, can't it ? In this case why "MIP_*", unless it means something different from "Mixed Integer Program" ?

We only have MixedIntegerLinearProgram, but no LinearProgram, right? While the latter might be a meaningful addition, it is certainly beyond the scope of this ticket, I think...

[...]

  • The patch *does not apply* on 5.0-rc1, so I can not even check whether tests pass !

now it does, thanks to Keshav's rebasing.

Dima

comment:27 in reply to: ↑ 26 Changed 2 years ago by ncohen

We only have MixedIntegerLinearProgram, but no LinearProgram, right?

Indeed, but the file ppl.pyx (both code and documentation) contains many occurrences of "MIP" that are just misleading.

Nathann

comment:28 in reply to: ↑ 24 ; follow-ups: Changed 2 years ago by ptrrsn_1

Replying to ncohen:

Helloooooooo Risan !!!

Hi Mr. Nathann

I just went over your patch, and some comments follow. Thank you very much for the work you put into that ! :-)

Thank you for your review.

ppl.pyx

  • MIP_Problem : PPL can only solve continuous Linear Programs, can't it ? In this case why "MIP_*", unless it means something different from "Mixed Integer Program" ?

It was named MIP_Problem simply because it is derived from MIP_Problem class in PPL. Since this functionality belongs to PPL, I left the name unchanged.

  • MIP_Problem.optimization_mode() prints something but does not return anything

Fixed. Now it returns a string.

  • MIP_Problem returns dictionaries : in MixedIntegerLinearProgram? we raise an exception for unbounded/infeasible problems, and return the objective's value otherwise. Just mentionning it in case you may like it, of course that's totally up to you ! I still think it would be easier to return, for instance, a string (unbounded/infeasible) when the problem has no solution, and the result otherwise.

Fixed. Now it raises an error (ValueError?) when the problem has no solution. I think it is more consistent to the PPL MIP_Problem now.

  • optimal_value does not only return the objective value, it also solves the problem ! I think the docstring should be updated --> if the users calls this function several times, are the computations made over and over ?

Fixed. It does not solve the problem now.

  • optimization_mode and set_optimization_mode : we often do both in a unique function, i.e. a method with optional arguments such that optimization_mode() returns the mode and optimization_mode(-1) defines it as a minimization problem. I just noticed that it was not the case at all for MixedIntegerLinearProgram? methods, but I think we ought to change that :-)

This is made to be consistent with the implementation in PPL. In PPL, they used optimization_mode() and set_optimization_mode() instead of one function only :)

  • is_satisfiable : does it also solve the problem ? I mean, if users type "if p.is_satisfiable(): a = p.optimal_value()" does it solve it twice ? The docstrings should say something about that.

The is_satisfiable in my wrapper wraps exactly the is_satisfiable of PPL. After looking at the PPL implementation of this function, I guess it does not solve the problem.

  • what is the difference between optimal_value and evaluate_objective_function ? In particular the code seems to be pretty similar, so one function should probably call the other if two are necessary

Evaluate objective function return the evaluation of objective function on a given point (the parameter of the function). The optimal_value return the evaluation of objective function on the optimal solution.

  • OK : by looking at the docstring I have no idea what it does or what the invariants are, but of course it may also be that I am not part of the intended audience for this class

I think it was used for debugging (I'm not really sure too).

sage/libs/ppl_ files

  • Are these files part of the ppl spkg ? If so they should not be modified by a patch, and the spkg itself should be updated.. That's really a lot of work for nothing, but that's how things are done here until we change it :-/

The files pp_shim.cc and ppl_shim.hh are created by vbraun (cmiiw), I actually don't have any idea about them.

mip.pyx

  • Why would you have to add anything to get_values and solve ? The flags you add would create problems instantly if the backend solver is not PPL !! I think nothing needs to be changed in that file --> if the backend is ppl then the values returned will be exact, otherwise they will just be the usual ones. But I do not see why these functions should be changed O_o

Thanks, I have changed this part. No additional flags needed anymore.

ppl_backend.pyx

  • All functions should be documented/tested, even 'cutsom ones' like print_data . Actually sage -coverage <filename> should never have to complain :-)

oops, print_data is debugging function. I forgot to delete it. Now I have deleted it.

  • same thing with init_mip

It is documented now.

  • add_variable[s] say that the variable are positive by default. Are they indeed ?

Yes. They are. The lower_bound is set to 0.0 by default.

  • "set_variable_type" -- I think the best is for this method's code to be something like "raise Exception('This backend does not handle integer variables ! Read the doc !')"

Fixed.

  • why do you keep "exact" in the names of your get_values functions ? It would be easier to name then get_values, as anyway all the values given by the ppl interface are exact ?!

Fixed.

Others

  • Is ppl.pyx part of the documentation ? At least ppl_backend is not, so you should add it to doc/en/reference/numerical.rst
  • Some "advertisement" should be added to the doc. In many places the solvers are listed (ok, perhaps we should only list them at *one* place), so that users can find out that *exact* answer are returned when the solver is ppl

ok. I'm still working on them and I will update it later.

  • Variables : are they automatically strictly positive ? This is the default in the MIP class (because it is the default of the API we interface), and if PPL acts any differently this would mean that results would be different according to whether PPL or GLPK is used as a backend !

This is from GenericBackend? (and PPL Backend inherits from it) class: "cpdef int add_variable(self, lower_bound=0.0, ..." I think the variables are non-negative by default.

  • The patch *does not apply* on 5.0-rc1, so I can not even check whether tests pass !

Thank you again :-) Nathann

Thanks a lot again, Mr. Nathann :)

Risan

comment:29 Changed 2 years ago by ptrrsn_1

  • Status changed from needs_work to needs_review

comment:30 Changed 2 years ago by kini

  • Status changed from needs_review to needs_work
  • Work issues set to rebase on 5.1.beta0

I'll rebase this later

Changed 2 years ago by kini

apply to $SAGE_ROOT/devel/sage

comment:31 follow-up: Changed 2 years ago by kini

  • Status changed from needs_work to needs_review

patchbot: apply trac_12533-rebased.2.patch

comment:32 Changed 2 years ago by ncohen

(Does it fail to compile on beta1 or is it just me ? It applied fine though !)

comment:33 follow-up: Changed 2 years ago by ncohen

  • Status changed from needs_review to needs_info

comment:34 in reply to: ↑ 33 Changed 2 years ago by dimpase

Replying to ncohen: indeed, I also get

...
Error compiling Cython file:
------------------------------------------------------------
...
        if coeff is not None:
            self.objective_function[variable] = coeff;
        else:
            return self.objective_function[variable]

    cpdef  set_objective(self, list coeff):
          ^
------------------------------------------------------------

sage/numerical/backends/ppl_backend.pyx:273:11: Signature not compatible with previous declaration

Error compiling Cython file:
------------------------------------------------------------
...
    cpdef int add_variable(self, lower_bound=*, upper_bound=*, binary=*, continuous=*, integer=*, obj=*, name=*) except -1
    cpdef int add_variables(self, int, lower_bound=*, upper_bound=*, binary=*, continuous=*, integer=*, obj=*, names=*) except -1
    cpdef set_variable_type(self, int variable, int vtype)
    cpdef set_sense(self, int sense)
    cpdef objective_coefficient(self, int variable, coeff=*)
    cpdef set_objective(self, list coeff, double d=*)
                       ^
------------------------------------------------------------

sage/numerical/backends/generic_backend.pxd:14:24: Previous declaration is here
Error running command, failed with status 256.
Error installing modified sage library code.

comment:35 Changed 2 years ago by ptrrsn_1

  • Status changed from needs_info to needs_review

comment:36 follow-up: Changed 2 years ago by ptrrsn_1

Hi,

I have fixed the compilation error and some other incompatibilities with sage 5.1. If you are using sage 5.1, please use "trac_12533_arbitrary_precision_LP_solver_backend_for_5.1.patch". If you are using sage 5.0, please use "trac_12533_arbitrary_precision_LP_solver_backend.patch".

Thank you!

comment:37 in reply to: ↑ 31 Changed 2 years ago by ptrrsn_1

Replying to kini:

patchbot: apply trac_12533-rebased.2.patch

Btw, thanks for this! :)

comment:38 in reply to: ↑ 36 Changed 2 years ago by dimpase

Replying to ptrrsn_1:

Hi,

I have fixed the compilation error and some other incompatibilities with sage 5.1. If you are using sage 5.1, please use "trac_12533_arbitrary_precision_LP_solver_backend_for_5.1.patch". If you are using sage 5.0, please use "trac_12533_arbitrary_precision_LP_solver_backend.patch".

Thanks, it works now with the latest Sage beta (on OSX 10.6.8).

comment:39 in reply to: ↑ 28 ; follow-ups: Changed 2 years ago by ncohen

  • Status changed from needs_review to needs_work

Hi Mr. Nathann

Hello Mister Risan !!

  • MIP_Problem : PPL can only solve continuous Linear Programs, can't it ? In this case why "MIP_*", unless it means something different from "Mixed Integer Program" ?

It was named MIP_Problem simply because it is derived from MIP_Problem class in PPL. Since this functionality belongs to PPL, I left the name unchanged.

Oh. Then do you mean that PPL can solve integer programs too ? O_o If its name is MIP_problem, I guess it can... Well, why don't we expose it then ???

  • is_satisfiable : does it also solve the problem ? I mean, if users type "if p.is_satisfiable(): a = p.optimal_value()" does it solve it twice ? The docstrings should say something about that.

The is_satisfiable in my wrapper wraps exactly the is_satisfiable of PPL. After looking at the PPL implementation of this function, I guess it does not solve the problem.

Hmmmm.. I would be surprised if it were easier to check that the problem is satisfiable than to actually solve it. O_o. But then again, I am often surprised.

Evaluate objective function return the evaluation of objective function on a given point (the parameter of the function). The optimal_value return the evaluation of objective function on the optimal solution.

Right. I do not know what I could do with evaluate_objective_function, but if you think that it is useful...

  • OK : by looking at the docstring I have no idea what it does or what the invariants are, but of course it may also be that I am not part of the intended audience for this class

I think it was used for debugging (I'm not really sure too).

Well, then... What about removing it from the patch ?...

sage/libs/ppl_ files

The files pp_shim.cc and ppl_shim.hh are created by vbraun (cmiiw), I actually don't have any idea about them.

Ok, they seem to be included in Sage's source code, so it is actually ok to modify them

mip.pyx

  • Why would you have to add anything to get_values and solve ? The flags you add would create problems instantly if the backend solver is not PPL !! I think nothing needs to be changed in that file --> if the backend is ppl then the values returned will be exact, otherwise they will just be the usual ones. But I do not see why these functions should be changed O_o

Thanks, I have changed this part. No additional flags needed anymore.

Well. I saw that you now have two functions doing exactly the same thing following each other in the file : get_variable_value and get_exact_variable_value. As they seem to do the same thing (tell me if I am wrong) it should only appear once. If you want to have both available, one can be made to be a shortcut toward the other by typing in the code get_exact_variable_value = get_variable_value But why would you want to have both available ? In particular, why do you still modify the file mip.pyx ? As the function get_variable_value exists, there is no need to test whether the ppl solver is being used, or to have an exact variable, or to add things like that to the code :

import sys 
from sage.all import * 

ppl_backend.pyx

about documentation : I just remembered that you should also add a mention of ppl in the file doc/en/thematic_tutorials/linear_programming.rst near the other solvers.

  • "set_variable_type" -- I think the best is for this method's code to be something like "raise Exception('This backend does not handle integer variables ! Read the doc !')"

Fixed.

Well... But it the solver actually supports integer variables...

Others

  • Is ppl.pyx part of the documentation ? At least ppl_backend is not, so you should add it to doc/en/reference/numerical.rst

Well... This is not done in your new patch.

ok. I'm still working on them and I will update it later.

did you ?

Nathann

comment:40 in reply to: ↑ 28 Changed 2 years ago by ncohen

Oh, and I forgot to add that all import from the PPL libraries should be done in a .pxd file (like for ppl_backend.pxd) instead :-)

Nathann

comment:41 Changed 2 years ago by dimpase

  • Work issues changed from rebase on 5.1.beta0 to see the latest comments

Changed 2 years ago by ptrrsn_1

for Sage 5.1.beta1

comment:42 in reply to: ↑ 39 Changed 2 years ago by ptrrsn_1

Replying to ncohen:

Hi Mr. Nathann

Hello Mister Risan !!

Hi

  • MIP_Problem : PPL can only solve continuous Linear Programs, can't it ? In this case why "MIP_*", unless it means something different from "Mixed Integer Program" ?

It was named MIP_Problem simply because it is derived from MIP_Problem class in PPL. Since this functionality belongs to PPL, I left the name unchanged.

Oh. Then do you mean that PPL can solve integer programs too ? O_o If its name is MIP_problem, I guess it can... Well, why don't we expose it then ???

Because this patch is initially only intended to be an additional exact LP solver backend for general LP.

  • is_satisfiable : does it also solve the problem ? I mean, if users type "if p.is_satisfiable(): a = p.optimal_value()" does it solve it twice ? The docstrings should say something about that.

The is_satisfiable in my wrapper wraps exactly the is_satisfiable of PPL. After looking at the PPL implementation of this function, I guess it does not solve the problem.

Hmmmm.. I would be surprised if it were easier to check that the problem is satisfiable than to actually solve it. O_o. But then again, I am often surprised.

Hmm, I am not really sure about it either. It was not mentioned in the PPL documentation.

Evaluate objective function return the evaluation of objective function on a given point (the parameter of the function). The optimal_value return the evaluation of objective function on the optimal solution.

Right. I do not know what I could do with evaluate_objective_function, but if you think that it is useful...

  • OK : by looking at the docstring I have no idea what it does or what the invariants are, but of course it may also be that I am not part of the intended audience for this class

I think it was used for debugging (I'm not really sure too).

Well, then... What about removing it from the patch ?...

Hmm, after checking this again, I think it is not just for debugging purpose. For example: The MIP_Problem constructor will accept any kind of constraints (including strict inequalities which violate the invariants). However, there is no checking for this in the constructor, that is why the OK() can be used to check this.

sage/libs/ppl_ files

The files pp_shim.cc and ppl_shim.hh are created by vbraun (cmiiw), I actually don't have any idea about them.

Ok, they seem to be included in Sage's source code, so it is actually ok to modify them

mip.pyx

  • Why would you have to add anything to get_values and solve ? The flags you add would create problems instantly if the backend solver is not PPL !! I think nothing needs to be changed in that file --> if the backend is ppl then the values returned will be exact, otherwise they will just be the usual ones. But I do not see why these functions should be changed O_o

Thanks, I have changed this part. No additional flags needed anymore.

Well. I saw that you now have two functions doing exactly the same thing following each other in the file : get_variable_value and get_exact_variable_value. As they seem to do the same thing (tell me if I am wrong) it should only appear once. If you want to have both available, one can be made to be a shortcut toward the other by typing in the code get_exact_variable_value = get_variable_value But why would you want to have both available ?

I have changed the get_variable_value to raise notimplementederror. The reason I made new functions (get_exact_*) is because in generic_backend, the return type of get_variable_value and get_objective_value are fixed to be double. Since PPLBackend inherits these methods from GenericBackend?, the implementations of them inside PPLBackend should return doubles too... except if I modify the GenericBackend? class (change cdef double get_... to cdef get_...). What do you think?

In particular, why do you still modify the file mip.pyx ? As the function get_variable_value exists, there is no need to test whether the ppl solver is being used, or to have an exact variable, or to add things like that to the code :

import sys 
from sage.all import * 

ppl_backend.pyx

about documentation : I just remembered that you should also add a mention of ppl in the file doc/en/thematic_tutorials/linear_programming.rst near the other solvers.

  • "set_variable_type" -- I think the best is for this method's code to be something like "raise Exception('This backend does not handle integer variables ! Read the doc !')"

Fixed.

Well... But it the solver actually supports integer variables...

Others

  • Is ppl.pyx part of the documentation ? At least ppl_backend is not, so you should add it to doc/en/reference/numerical.rst

Well... This is not done in your new patch.

ok. I'm still working on them and I will update it later.

did you ?

Ok, fixed.

Nathann

comment:43 Changed 2 years ago by ptrrsn_1

  • Status changed from needs_work to needs_review

comment:44 in reply to: ↑ 39 Changed 2 years ago by dimpase

  • Reviewers changed from David Coudert to David Coudert, Nathann Cohen

Replying to ncohen: the name unchanged.

Oh. Then do you mean that PPL can solve integer programs too ? O_o If its name is MIP_problem, I guess it can... Well, why don't we expose it then ???

yes, this would be great, but this ought to be another ticket...

comment:45 Changed 2 years ago by vbraun

To the best of my knowledge PPL does not do integer programming. It technically works with integers (and an overall divisor) so that you can potentially use machine integers for speed. Though in Sage we only compile support for GMP/MPIR coefficients in. But you can't solve integer (or mixed integer) programs.

Also, Sage seems to have a MixedIntegerLinearProgram but no IntegerLinearProgram or just LinearProgram. Why is there no class hierarchy?

comment:46 Changed 2 years ago by vbraun

Never mind, I just looked up the PPL docs with respect to MIP_Problem.

comment:47 follow-up: Changed 2 years ago by vbraun

  • Dependencies set to 12553
  • Status changed from needs_review to needs_work

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__. 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.

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

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

The INPUT: section should be formatted like

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

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

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):

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.

comment:48 Changed 2 years ago by dimpase

Please also see a related #13142, which points out to the fact that show() would eventually need more work to be perfect for arbitrary precision.

comment:49 follow-up: Changed 2 years ago by 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.

Last edited 2 years ago by dimpase (previous) (diff)

comment:50 Changed 2 years ago by dimpase

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).

Last edited 2 years ago by dimpase (previous) (diff)

Changed 2 years ago by dimpase

fixing the imprecision bug in setting min/max of variables

comment:51 Changed 2 years ago by ptrrsn_1

  • Description modified (diff)

comment:52 in reply to: ↑ 47 ; follow-ups: Changed 2 years ago by ptrrsn_1

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.

comment:53 in reply to: ↑ 49 ; follow-up: Changed 2 years ago by ptrrsn_1

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.

comment:54 Changed 2 years ago by ptrrsn_1

  • Status changed from needs_work to needs_review

comment:55 in reply to: ↑ 52 ; follow-up: Changed 2 years ago by dimpase

Replying to ptrrsn_1:

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.

comment:56 in reply to: ↑ 53 Changed 2 years ago by dimpase

Replying to ptrrsn_1:

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.

comment:57 in reply to: ↑ 55 ; follow-up: Changed 2 years ago by vbraun

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 ;-)

comment:58 in reply to: ↑ 52 Changed 2 years ago by vbraun

Replying to ptrrsn_1:

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?

comment:59 in reply to: ↑ 57 Changed 2 years ago by dimpase

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?

Last edited 2 years ago by dimpase (previous) (diff)

comment:60 Changed 2 years ago by dimpase

  • Description modified (diff)
  • Status changed from needs_review to positive_review

Still builds and works on Sage 5.2.rc0.

comment:61 Changed 2 years ago by dimpase

  • Description modified (diff)

comment:62 Changed 2 years ago by dimpase

  • Status changed from positive_review to needs_work

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.
Last edited 2 years ago by dimpase (previous) (diff)

comment:63 Changed 2 years ago by dimpase

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.

Changed 2 years ago by dimpase

fixing hardcoded double and 0.0, etc

comment:64 follow-up: Changed 2 years ago by ptrrsn_1

  • Status changed from needs_work to needs_review

comment:65 in reply to: ↑ 64 Changed 2 years ago by dimpase

Replying to ptrrsn_1: 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?

comment:66 Changed 2 years ago by vbraun

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.

comment:67 Changed 2 years ago by vbraun

patchbot: apply trac_12533_arbitrary_precision_LP_solver_backend.patch

comment:68 Changed 2 years ago by robertwb

patchbot: apply only trac_12533_arbitrary_precision_LP_solver_backend.patch

Changed 23 months ago by ptrrsn_1

for sage 5.3

comment:69 Changed 23 months ago by ptrrsn_1

  • Description modified (diff)

comment:70 Changed 23 months ago by ptrrsn_1

  • Description modified (diff)

comment:71 Changed 23 months ago by dimpase

  • Authors set to Risan
  • Reviewers changed from David Coudert, Nathann Cohen to David Coudert, Nathann Cohen, Dmitrii Pasechnik
  • Status changed from needs_review to positive_review
  • Work issues see the latest comments deleted

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

comment:72 Changed 23 months ago by jdemeyer

  • Dependencies changed from 12553 to #12553
  • Milestone changed from sage-5.4 to sage-5.5

comment:73 Changed 23 months ago by jdemeyer

  • Milestone changed from sage-5.5 to sage-pending

comment:74 follow-up: Changed 23 months ago by vbraun

  • Dependencies changed from #12553 to #12553, #13646

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

comment:75 in reply to: ↑ 74 Changed 23 months ago by dimpase

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?

comment:76 follow-up: Changed 23 months ago by vbraun

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.

comment:77 in reply to: ↑ 76 Changed 23 months ago by dimpase

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.

comment:78 follow-up: Changed 23 months ago by vbraun

  • Dependencies changed from #12553, #13646 to #13646

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.

comment:79 in reply to: ↑ 78 Changed 23 months ago by dimpase

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.

comment:80 Changed 23 months ago by dimpase

  • Dependencies changed from #13646 to #13646, #13650
  • Description modified (diff)

comment:81 Changed 22 months ago by dimpase

  • Dependencies changed from #13646, #13650 to #13646

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.

comment:82 Changed 22 months ago by jdemeyer

  • Milestone changed from sage-pending to sage-5.5

comment:83 Changed 22 months ago by jdemeyer

  • Description modified (diff)

comment:84 Changed 22 months ago by dimpase

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?

comment:85 Changed 22 months ago by vbraun

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.

comment:86 Changed 22 months ago by jdemeyer

  • Merged in set to sage-5.5.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:87 follow-up: Changed 9 months ago by 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.

comment:88 in reply to: ↑ 87 Changed 9 months ago by dimpase

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

Note: See TracTickets for help on using tickets.