The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Linear programming docs and problem
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 4 messages

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Aug 25 2010, 12:23 pm
From: Ryan Hinton <iob...@email.com>
Date: Wed, 25 Aug 2010 09:23:34 -0700 (PDT)
Local: Wed, Aug 25 2010 12:23 pm
Subject: Linear programming docs and problem
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
http://www.sagemath.org/doc/constructions/linear_programming.html to

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

Thanks!

- Ryan

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 25 2010, 7:54 pm
From: David Kirkby <david.kir...@onetel.net>
Date: Thu, 26 Aug 2010 00:54:18 +0100
Local: Wed, Aug 25 2010 7:54 pm
Subject: Re: [sage-devel] Linear programming docs and problem
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

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 26 2010, 2:09 am
From: Nathann Cohen <nathann.co...@gmail.com>
Date: Wed, 25 Aug 2010 23:09:39 -0700 (PDT)
Local: Thurs, Aug 26 2010 2:09 am
Subject: Re: Linear programming docs and problem
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.

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 26 2010, 1:26 pm
From: Ryan Hinton <iob...@email.com>
Date: Thu, 26 Aug 2010 10:26:14 -0700 (PDT)
Local: Thurs, Aug 26 2010 1:26 pm
Subject: Re: Linear programming docs and problem
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

On Aug 26, 12:09 am, Nathann Cohen <nathann.co...@gmail.com> wrote: