#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 )
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)
Change History (97)
comment:1 Changed 10 years ago by
comment:2 Changed 10 years ago by
- Cc ptrrsn_1 added
comment:3 Changed 10 years ago by
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: ↓ 5 Changed 10 years ago by
- 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 10 years ago by
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 10 years ago by
- 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 10 years ago by
- 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 10 years ago by
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: ↓ 10 Changed 10 years ago by
- 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 10 years ago by
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: ↓ 12 Changed 10 years ago by
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 10 years ago by
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 10 years ago by
Yeah, the memory address should be elided, of course.
comment:14 Changed 10 years ago by
- Status changed from needs_work to needs_review
Thank you! I have fixed the doctesting errors.
comment:15 follow-up: ↓ 16 Changed 10 years ago by
- 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: ↓ 17 Changed 10 years ago by
- 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 "$@" -iSome 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: ↓ 18 Changed 10 years ago by
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 10 years ago by
- 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 10 years ago by
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.
comment:20 follow-ups: ↓ 21 ↓ 22 Changed 10 years ago by
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 theMIP_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 10 years ago by
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!
comment:22 in reply to: ↑ 20 Changed 10 years ago by
comment:23 Changed 10 years ago by
- Status changed from needs_work to needs_review
comment:24 follow-ups: ↓ 26 ↓ 28 Changed 10 years ago by
- 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
comment:25 Changed 10 years ago by
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: ↓ 27 Changed 10 years ago by
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 10 years ago by
We only have
MixedIntegerLinearProgram
, but noLinearProgram
, 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: ↓ 39 ↓ 40 Changed 10 years ago by
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 10 years ago by
- Status changed from needs_work to needs_review
comment:30 Changed 10 years ago by
- Status changed from needs_review to needs_work
- Work issues set to rebase on 5.1.beta0
I'll rebase this later
comment:31 follow-up: ↓ 37 Changed 10 years ago by
- Status changed from needs_work to needs_review
patchbot: apply trac_12533-rebased.2.patch
comment:32 Changed 10 years ago by
(Does it fail to compile on beta1 or is it just me ? It applied fine though !)
comment:33 follow-up: ↓ 34 Changed 10 years ago by
- Status changed from needs_review to needs_info
comment:34 in reply to: ↑ 33 Changed 10 years ago by
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 10 years ago by
- Status changed from needs_info to needs_review
comment:36 follow-up: ↓ 38 Changed 10 years ago by
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 10 years ago by
comment:38 in reply to: ↑ 36 Changed 10 years ago by
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: ↓ 42 ↓ 44 Changed 10 years ago by
- 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 10 years ago by
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 10 years ago by
- Work issues changed from rebase on 5.1.beta0 to see the latest comments
comment:42 in reply to: ↑ 39 Changed 10 years ago by
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 10 years ago by
- Status changed from needs_work to needs_review
comment:44 in reply to: ↑ 39 Changed 10 years ago by
- 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 10 years ago by
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 10 years ago by
Never mind, I just looked up the PPL docs with respect to MIP_Problem
.
comment:47 follow-up: ↓ 52 Changed 10 years ago by
- 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 10 years ago by
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: ↓ 53 Changed 10 years ago by
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.
comment:50 Changed 10 years ago by
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).
comment:51 Changed 10 years ago by
- Description modified (diff)
comment:52 in reply to: ↑ 47 ; follow-ups: ↓ 55 ↓ 58 Changed 10 years ago by
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: ↓ 56 Changed 10 years ago by
Hi,
Replying to dimpase:
I do not understand a strange kludge with
get_exact_variable_value
vsget_variable_value
. Why don't you implementget_ariable_value
to return whatget_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 10 years ago by
- Status changed from needs_work to needs_review
comment:55 in reply to: ↑ 52 ; follow-up: ↓ 57 Changed 10 years ago by
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 10 years ago by
Replying to ptrrsn_1:
Hi,
Replying to dimpase:
I do not understand a strange kludge with
get_exact_variable_value
vsget_variable_value
. Why don't you implementget_ariable_value
to return whatget_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: ↓ 59 Changed 10 years ago by
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 10 years ago by
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 10 years ago by
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?
comment:60 Changed 10 years ago by
- Description modified (diff)
- Status changed from needs_review to positive_review
Still builds and works on Sage 5.2.rc0
.
comment:61 Changed 10 years ago by
- Description modified (diff)
comment:62 Changed 10 years ago by
- 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.
comment:63 Changed 10 years ago by
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()
andvariable_upper_bound()
preventing a possibility to set bounds toNone
.
Changed 10 years ago by
comment:64 follow-up: ↓ 65 Changed 10 years ago by
- Status changed from needs_work to needs_review
comment:65 in reply to: ↑ 64 Changed 10 years ago by
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 10 years ago by
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 10 years ago by
patchbot: apply trac_12533_arbitrary_precision_LP_solver_backend.patch
comment:68 Changed 10 years ago by
patchbot: apply only trac_12533_arbitrary_precision_LP_solver_backend.patch
comment:69 Changed 10 years ago by
- Description modified (diff)
comment:70 Changed 10 years ago by
- Description modified (diff)
comment:71 Changed 10 years ago by
- 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 10 years ago by
- Dependencies changed from 12553 to #12553
- Milestone changed from sage-5.4 to sage-5.5
comment:73 Changed 10 years ago by
- Milestone changed from sage-5.5 to sage-pending
comment:74 follow-up: ↓ 75 Changed 10 years ago by
- Dependencies changed from #12553 to #12553, #13646
Rebased on top of #13646. No real changes were necessary.
comment:75 in reply to: ↑ 74 Changed 10 years ago by
comment:76 follow-up: ↓ 77 Changed 10 years ago by
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 10 years ago by
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: ↓ 79 Changed 10 years ago by
- 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 10 years ago by
comment:80 Changed 10 years ago by
- Dependencies changed from #13646 to #13646, #13650
- Description modified (diff)
comment:81 Changed 10 years ago by
- Dependencies changed from #13646, #13650 to #13646
comment:82 Changed 10 years ago by
- Milestone changed from sage-pending to sage-5.5
comment:83 Changed 10 years ago by
- Description modified (diff)
comment:84 Changed 10 years ago by
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 10 years ago by
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 10 years ago by
- Merged in set to sage-5.5.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
comment:87 follow-up: ↓ 88 Changed 9 years ago by
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 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).