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

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

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

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