#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: see the latest
comments
Report Upstream: N/A | Reviewers: David Coudert
Authors: | Merged in:
Dependencies: | Stopgaps:
-------------------------------------------+--------------------------------
Comment (by ptrrsn_1):
Replying to [comment:39 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
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12533#comment:42>
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.
