Linear programming docs and problem

[Ryan Hinton]

First, I'm hoping someone (e.g. Nathann Cohen) will notice trac #9801
which makes a few corrections to the linear programming part of the
Sage Constructions document. I've fixed one problem, but I'm left
with two more.

1. The maximal matching example code does not like my fix.

sage: g = graphs.PetersenGraph()
sage: p = MixedIntegerLinearProgram()
sage: b = p.new_variable(dim=2)
sage: for u in g.vertices():
... p.add_constraint(sum([b[u][v] for v in g.neighbors(u)]),
max=1)
sage: for u, v in g.edges(labels=None):
... p.add_constraint(b[u][v] + b[v][u], min=1, max=1)
sage: # I added the objective function as follows
sage: p.set_objective(sum(b[u][v] + b[v][u] for u,v in
g.edges(labels=None)))
sage: p.solve()
...
MIPSolverException: 'GLPK : Solution is undefined'

I probably just messed up the objective function. Anyone see the fix?

2. I tried to install GLPK on one machine following the instructions
in this same document, but it failed.

sage: p.solve()
...
ValueError: There does not seem to be any (Mixed) Integer Linear
Program solver installed. Please visit
http://www.sagemath.org/doc/constructions/linear_programming.html to
learn more about the solvers available.

I followed the same process on another machine and it worked fine.
How do I debug this?

Thanks!

- Ryan

[David Kirkby]

On 25 August 2010 17:23, Ryan Hinton <iob...@email.com> wrote:
> First, I'm hoping someone (e.g. Nathann Cohen) will notice trac #9801
> which makes a few corrections to the linear programming part of the
> Sage Constructions document.  I've fixed one problem, but I'm left
> with two more.

http://www.sagemath.org/doc/constructions/linear_programming.html

looks wrong/outdated to me. GLPK is a standard Sage package, so I
don't think there is any need for the:

sage: install_package("glpk") # not tested

but Nathann will know more than me.

Dave

[Nathann Cohen]

Hello !!!

Well, I'm sorry to say it like that, but as David mentionned this
document is really outdated now, which mean I have been thinking about
rewriting all of it. Actually, I already wrote an introduction to
graphs and LP using Sage, which should soon be available as a part of
the (french) Sagebook, but I intended o translate it next week.

I am really sorry I was not able to review patches or answer messages
these last days as efficiently as usual : I have been backpacking for
2 weeks, which is extremely nice for the mind but does not get coding
done. I will be unavailable for something like a week and a half
again, which I will spend unable to reach internet. I hope to be able
to post patches for a real graph tutorial, along with a real LP
tutorial (and not these "constructions" things -- they were moved to
the "construction" document because they relied on an (formerly)
optional package -> GLPK), up to date and (I hope) interesting.

> 1.  The maximal matching example code does not like my fix.

> ...

> I probably just messed up the objective function.  Anyone see the fix?

Your objective function is fine. The problem is the unsatisfiable
constraint that for any edge b[u][v] + b[v][u] == 1. It means that
exactly one of these two edges has to be "taken". As the Petersen
graph is 3-regular, it means that the sum of the weights of the edges
adjacent to each vertex is at least 1.5, which is not a matching. It
should be nicer if you remove the min = 1 in this constraint.

Of course, if this mistake was mine, please receive my humblest
apologies... ^^;

(Oh, and you probably want the variables to be binary)

> 2.  I tried to install GLPK on one machine following the instructions
> in this same document, but it failed.

GLPK is now installed by default, and its behaviour has been changed
recently. Would I be right in guessing you are using an old version of
Sage ?

> I followed the same process on another machine and it worked fine.
> How do I debug this?

Same running version of Sage ? Anyway, GLPK is now installed by
default.

Nathann

[Ryan Hinton]

You are both right! The "working" install is in Sage 4.5.1, and the
"broken" install is Sage 4.4.3. I tried to rebuild glpk on the
failing machine and noticed that it requested a "sage -b" in order to
complete the installation. I haven't done that, so I assume it will
work. (I have to wait for some long simulations to finish before I
can try it.)

I'm happy to wait for your LP/graphs rewrite. I plan to use LP for an
engineering optimization problem soon (not graph related), so it
seemed like a good idea to try it out. I probably won't get to it for
a few weeks, so your schedule sounds perfect. If the interface hasn't
changed too much, the current documentation is probably enough to get
me started. But a nice, shiny, new (accurate!) reference is always
nice.

Thanks!

- Ryan