Optimization/Graph problems wishlist....

[Nathann Cohen]

Hello everybody !!!

Now that the basics of Linear Programming are written, I am looking
for ways to make it useful in Sage : I have been looking for
Optimization/Graph algorithms which could be implemented this way and
came up with the following ones :

Bin packing
http://en.wikipedia.org/wiki/Bin_packing_problem

Independent set of Representatives
( generalizes, for example, graph coloring )

Knapsack ( it seems Sage only solves some special cases for the
moment )
http://en.wikipedia.org/wiki/Knapsack_problem

Gomory-Hu Tree ( Polynomial )
http://www.cs.bgu.ac.il/~visproj/eransagi/flow.html

I will begin to write them as soon as LP will be merged into Sage, but
I thought you may want plenty of other ones, and I sent this message
just for that : if you can think about any Polynomial/NP-complete
function you think would be useful in Sage, say its name ! ;-)

Nathann

[William Stein]

Cool. This really increases my desire to have the LP code merged into Sage!
When you write some of the above, it would be good to add a 1-page
section to the standard "Sage tutorial" illustrating some of it, so
many first time Sage users will encounter this capability of Sage.

William

>
> Nathann
>
> >
>



--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org

[Minh Nguyen]

Hi Nathann,

On Sat, Aug 15, 2009 at 1:54 AM, Nathann Cohen<nathan...@gmail.com> wrote:

<SNIP>

> Knapsack ( it seems Sage only solves some special cases for the
> moment )
> http://en.wikipedia.org/wiki/Knapsack_problem

This is on my todo list. See this sage-devel thread:

http://groups.google.com/group/sage-devel/browse_thread/thread/ac4b9c0f7f7a1513

--
Regards
Minh Van Nguyen

[Nathann Cohen]

Hmmm.... And how does one writes into the Sage Tutorial ? I have been
willing to write a bit about graphs for a while, and it would be a
good idea to document LP there...

[William Stein]

Modify the files in here:

SAGE_ROOT/sage/devel/sage/doc/en/tutorial

This is just part of the standard Sage library repository.

William

[Nathann Cohen]

Excellent.

I will try to do that quickly ! ;-)
By the way, were you writing about tutorials for the functions I
mentionned or for the use of linear programming in Sage ?

I sent a patch yesterday for Knapsack, and ISR/Bin Packing are written
already. I will send a patch for them as soon as I will have tested
them and added examples in the docstrings. For the Gomory-Hu tree, I
will wait for #6680 to be merged as it would be a shame not to use
Graph.min_edge_cut() for that ;-)

Nathann

On Aug 14, 8:28 pm, William Stein <wst...@gmail.com> wrote:

[William Stein]

On Sat, Aug 15, 2009 at 4:43 AM, Nathann Cohen<nathan...@gmail.com> wrote:
>
> Excellent.
>
> I will try to do that quickly ! ;-)
> By the way, were you writing about tutorials for the functions I
> mentionned or for the use of linear programming in Sage ?

The use of linear programming in Sage. The tutorial is supposed to be
very general and broadly accessible.

> I sent a patch yesterday for Knapsack, and ISR/Bin Packing are written
> already. I will send a patch for them as soon as I will have tested
> them and added examples in the docstrings. For the Gomory-Hu tree, I
> will wait for #6680 to be merged as it would be a shame not to use
> Graph.min_edge_cut() for that ;-)
>
> Nathann
>
> On Aug 14, 8:28 pm, William Stein <wst...@gmail.com> wrote:
>> On Fri, Aug 14, 2009 at 9:28 AM, Nathann Cohen<nathann.co...@gmail.com> wrote:
>>
>> > Hmmm.... And how does one writes into the Sage Tutorial ? I have been
>> > willing to write a bit about graphs for a while, and it would be a
>> > good idea to document LP there...
>>
>> Modify the files in here:
>>
>>      SAGE_ROOT/sage/devel/sage/doc/en/tutorial
>>
>> This is just part of the standard Sage library repository.
>>
>> William
> >
>