#12533: arbitrary precision LP solver backend
-------------------------------------------+--------------------------------
Reporter: dimpase | Owner: ncohen
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-5.1
Component: linear programming | Resolution:
Keywords: arbitrary precision, LP | Work issues:
Report Upstream: N/A | Reviewers: David Coudert
Authors: | Merged in:
Dependencies: | Stopgaps:
-------------------------------------------+--------------------------------
Comment (by ptrrsn_1):
Replying to [comment:24 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
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12533#comment:28>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
