Re: [PPL-devel] [GIT] ppl/ppl(pip): Added a standalone PIP solver demo program.
Perhaps you could also add a demo program with an interface like piplib's "example". That would make it easier to compare your solver to other pip solvers such as barvinok's lexmin and isl's isl_pip. skimo
This should not be of a real problem. I should be able to do that soon. However, I got trouble finding documentation about these files, in particular what the first column of matrices is for. If you know, please tell me. Also, do you require output in piplib's parenthesed format ? The decision trees I generate are a bit different, and cannot strictly fit piplib's output format structure. The main difference is that a single decision node can embed several tests, resulting in a test like this: If test1 AND test2 AND ... testn Then solution else _|_ In such cases, the 'else' block always contain an empty solution. Best, François Sven Verdoolaege a écrit :
Perhaps you could also add a demo program with an interface like piplib's "example". That would make it easier to compare your solver to other pip solvers such as barvinok's lexmin and isl's isl_pip.
skimo
On Fri, Oct 23, 2009 at 07:15:01PM +0200, Francois Galea wrote:
This should not be of a real problem. I should be able to do that soon. However, I got trouble finding documentation about these files, in particular what the first column of matrices is for. If you know, please tell me.
Ah... this is the standard PolyLib format. The first column indicates whether the row describes an equality (0) or an inequality (1). The constant term is in the final column. In the second polytope, the coefficients of the parameters appear after those of the unknowns. You can assume that the "big parameter" is -1. That's what I do too.
Also, do you require output in piplib's parenthesed format ?
I don't do that in either of my solvers, so I certainly wouldn't insist you do that. skimo
Sven Verdoolaege a écrit :
On Fri, Oct 23, 2009 at 07:15:01PM +0200, Francois Galea wrote:
This should not be of a real problem. I should be able to do that soon. However, I got trouble finding documentation about these files, in particular what the first column of matrices is for. If you know, please tell me.
Ah... this is the standard PolyLib format. The first column indicates whether the row describes an equality (0) or an inequality (1). The constant term is in the final column. In the second polytope, the coefficients of the parameters appear after those of the unknowns.
You can assume that the "big parameter" is -1. That's what I do too.
Also, do you require output in piplib's parenthesed format ?
I don't do that in either of my solvers, so I certainly wouldn't insist you do that.
I just commited a new version of the standalone solver. It now reads Polylib-formatted files, and it can read PIPlib files when using the '-p' switch. Though, it seems the example problems in piplib are revealing a(nother) flaw in the solver. I am currently investigating about this. Best, François
On Wed, Oct 28, 2009 at 03:56:36PM +0100, François Galea wrote:
Though, it seems the example problems in piplib are revealing a(nother) flaw in the solver. I am currently investigating about this.
OK, please let me know when you have fixed this problem. skimo
Sven Verdoolaege a écrit :
On Wed, Oct 28, 2009 at 03:56:36PM +0100, François Galea wrote:
Though, it seems the example problems in piplib are revealing a(nother) flaw in the solver. I am currently investigating about this.
OK, please let me know when you have fixed this problem.
I just fixed a trivial bug in the parser, for files which do not have parameters but have one context matrix row. This helps reading (and solving) some of piplib's examples. I still find at least one problem file which causes trouble ( However, some results I found are different from those which are in the corresponding '.ll' solution files. For instance, in 'boulet.pip', I get the solution minimum {0 ; 0 ; 0}, since all constraints have a nonnegative constant term. PIPlib finds a solution with negative elements : "if (p>=-5) then {-3*p-15 ; -p-5 ; p+5}." This may be valid if variables and parameters are not supposed nonnegative, but my current implementation of the solver does not support negative variables and parameters. Hence the question: which result can be considered correct ? Best, François.
On Wed, Oct 28, 2009 at 04:47:39PM +0100, François Galea wrote:
However, some results I found are different from those which are in the corresponding '.ll' solution files. For instance, in 'boulet.pip', I get the solution minimum {0 ; 0 ; 0}, since all constraints have a nonnegative constant term. PIPlib finds a solution with negative elements : "if (p>=-5) then {-3*p-15 ; -p-5 ; p+5}."
This may be valid if variables and parameters are not supposed nonnegative, but my current implementation of the solver does not support negative variables and parameters.
That's what the options "Urs_parms" and "Urs_unknowns" in boulet.pip mean. That is, both the parameters and the unknowns have unrestricted sign. So, piplib's answer is correct (see the piplib manual, where this example originates from). A bit of history. The original version of pip would assume that all unknowns and parameters are non-negative, but allowed the user to specify a "big parameter" that is treated in a special way by piplib. By reformulating the problem a little bit and by applying yet another trick to deal with urs parameters, the user could trick piplib into handling urs unknowns and parameters. A couple of years ago, I made some changes to piplib that allow the user to simply _indicate_ that the unknowns and parameters have urs and then piplib will perform all these tricks internally. The default was not changed for reasons of backward compatibility. Now, I actually think it is wrong to expose this implementation detail to the user, so, in isl, I make no assumption about the sign of the unknowns or the parameters. In the demo application isl_pip, I then add the appropriate ">= 0" constraints if the user did _not_ specify the Urs_parms or Urs_unknowns options. skimo
On Wed, Oct 28, 2009 at 05:11:37PM +0100, Sven Verdoolaege wrote:
parameters. A couple of years ago, I made some changes to piplib that allow the user to simply _indicate_ that the unknowns and parameters have urs and then piplib will perform all these tricks internally. The default was not changed for reasons of backward compatibility.
My memory may have been failing on this part. I think I just helped making this feature a bit more usable, but Cedric probably did the initial implementation, which dates back from 2003 (before there was any git). skimo
On Thu, Oct 29, 2009 at 01:02:52PM +0100, Sven Verdoolaege wrote:
On Wed, Oct 28, 2009 at 05:11:37PM +0100, Sven Verdoolaege wrote:
parameters. A couple of years ago, I made some changes to piplib that allow the user to simply _indicate_ that the unknowns and parameters have urs and then piplib will perform all these tricks internally. The default was not changed for reasons of backward compatibility.
My memory may have been failing on this part. I think I just helped making this feature a bit more usable, but Cedric probably did the initial implementation, which dates back from 2003 (before there was any git).
Sorry again, but apparently I _did_ do it and the commits (late 2005, early 2006) are available in the git repo. (I got confused with the support for maximization problems, which uses basically the same technique.) skimo
Sven Verdoolaege a écrit :
On Thu, Oct 29, 2009 at 01:02:52PM +0100, Sven Verdoolaege wrote:
On Wed, Oct 28, 2009 at 05:11:37PM +0100, Sven Verdoolaege wrote:
parameters. A couple of years ago, I made some changes to piplib that allow the user to simply _indicate_ that the unknowns and parameters have urs and then piplib will perform all these tricks internally. The default was not changed for reasons of backward compatibility. My memory may have been failing on this part. I think I just helped making this feature a bit more usable, but Cedric probably did the initial implementation, which dates back from 2003 (before there was any git).
Sorry again, but apparently I _did_ do it and the commits (late 2005, early 2006) are available in the git repo. (I got confused with the support for maximization problems, which uses basically the same technique.)
Thanks, I will have a look at these commits once I have implemented the support for bignums in the PPL solver. Have you got any reference (article, book, ...) on which you based your implementation ? Thanks in advance. François
On Fri, Oct 30, 2009 at 01:31:14PM +0100, Francois Galea wrote:
Have you got any reference (article, book, ...) on which you based your implementation ?
Usually, I base my papers on my implementation. Anyway, which implementation are you talking about? I have two. The basic idea of barvinok's lexmin is described in this presentation: https://lirias.kuleuven.be/handle/123456789/182679 So this was in fact the only time I presented something that I hadn't implemented yet. The actual implementation was done later that year. I submitted a paper about it to the post-conference proceeding, but it was rejected. I can send it to you if you want. The implemenation in isl is pretty recent and I haven't had time to write a paper about it. I was actually thinking about writing a combined paper about the implementations in barvinok and isl. Many of the trick I applied in isl were inspired by my earlier work in barvinok. I did present the isl implementation today in an informal meeting today in Leiden. The slides should become available online next week. (The head of our group needs to approve everything that gets added to the publications database.) skimo
On Sat, Oct 31, 2009 at 12:40:41AM +0100, Sven Verdoolaege wrote:
The implemenation in isl is pretty recent and I haven't had time to write a paper about it. I was actually thinking about writing a combined paper about the implementations in barvinok and isl. Many of the trick I applied in isl were inspired by my earlier work in barvinok. I did present the isl implementation today in an informal meeting today in Leiden. The slides should become available online next week.
On Fri, Oct 30, 2009 at 01:31:14PM +0100, Francois Galea wrote:
Thanks, I will have a look at these commits once I have implemented the support for bignums in the PPL solver.
Do you mean "big parameter"? There's nothing really interesting to see in those commits. I just mentioned them to show I'm not hallucinating. In any case, in piplib, I just implemented the tricks described in the manual. You should probably look at that before you start implementing. Note that the manual proposes two different tricks to handle negative unknowns and negative parameters. I have no idea why. I mean, it's clear why you shouldn't use the other trick in the main tableau, but it's not clear why you shouldn't use a big parameter in the context tableau. But you are problaby not using the dual simplex + Gomory cuts technique in the context, so you shouldn't have a problem with negative parameters. skimo
Sven Verdoolaege a écrit :
On Fri, Oct 30, 2009 at 01:31:14PM +0100, Francois Galea wrote:
Thanks, I will have a look at these commits once I have implemented the support for bignums in the PPL solver.
Do you mean "big parameter"?
Indeed, this is what I meant.
There's nothing really interesting to see in those commits. I just mentioned them to show I'm not hallucinating. In any case, in piplib, I just implemented the tricks described in the manual. You should probably look at that before you start implementing. Note that the manual proposes two different tricks to handle negative unknowns and negative parameters. I have no idea why. I mean, it's clear why you shouldn't use the other trick in the main tableau, but it's not clear why you shouldn't use a big parameter in the context tableau. But you are problaby not using the dual simplex + Gomory cuts technique in the context, so you shouldn't have a problem with negative parameters.
I will have a further look at all of this soon. Meanwhile, I still have fixes to do on the solver core. Thank you for all your advice. Best, François.
participants (3)
-
Francois Galea -
François Galea
-
Sven Verdoolaege