Knapsack algorithm

[nathanncohen]

A general knapsack algorithm using Linear programming ( check you have #6502 installed ! ) to patiently wait for more efficient versions :-)

Component: numerical

Author: Nathann Cohen

Reviewer: David Joyner

Merged: Sage 4.1.2.alpha2

Issue created by migration from https://trac.sagemath.org/ticket/6749

[wdjoyner]

comment:1

This needs a really detailed example, worked out so that a non-expert (like myself) can understand it. This of the first example you would try to teach an undergraduate. That would be perfect.

[wdjoyner]

comment:2

Replying to @wdjoyner:

This needs a really detailed example, worked out so that a non-expert (like myself) can understand it. Think of the first example you would try to teach an undergraduate. That would be perfect.

For example, there seems to be a simple knapsack problems solved here: http://sites.google.com/site/mikescoderama/Home/0-1-knapsack-problem-in-p
There is a more complicated one here: http://rosettacode.org/wiki/Knapsack_Problem#Simple_Solution
Also, http://webspace.ship.edu/thbrig/DynamicProgramming/Knapsack%20Program/index.html, and the xkcd example
http://www.itl.nist.gov/div897/sqg/dads/HTML/knapsackProblem.html :-)

[nathanncohen]

comment:3

I just added documentation and the example you required. I guess the docstrings took me 10 times what the function requires, but I learned a lot about sage's documentation, the Reference manual, Sphinx, and the fact that you should NEVER, for ANY REASON, delete a branch of Sage.

It gets angry if you do.

And I uploaded a new knapsack.patch replacing the old one ;-)

Nathann

[nathanncohen]

comment:4

A small mistake when uploading the patch... Well, now the two of them are good ;-)

[wdjoyner]

comment:5

This patch (after the dependencies are applied) applies fine to 4.1.1.rc2 on an intel macbook running 10.4.11. It passes sage -testall except for (apparently unrelated) errors with

The following tests failed:


        sage -t  "devel/sage/sage/interfaces/maxima.py"
        sage -t  "devel/sage/sage/symbolic/expression.pyx"

However, I will ask someone at work (an expert in OR) to check the code before posting a positive review.

[wdjoyner]

comment:6

I've had a talk with my OR colleague. I don't think "A list of pairs (weight,value) where each pair is repeated the number of times it is taken into the solution. " is the proper English grammar for what is meant. I think "A list of pairs (w_i, u_i), for each object i occurring in the solution. " is better. Do you agree?

Also, he suggested that the "objective value" (or maximal useful value, in your terminology) be included in the solution. Perhaps you could include this as an optional keyword, leaving the current behaviour as the default? If you also agree to this, please add a corresponding example to the docstring.

[nathanncohen]

comment:8

Excellent suggestion ! So :

• I fixed the grammar error ( sorry, I'm still learning english every day ;-) )
• I Included the objective value in the output

But :
Actually, this objective value requires no computation at all as it is automatically computed by the LP solver.. So as it can be useful anyway, the function now returns a pair [value, list] ( where list is the value the function returned previously ), and value=maximum useful value.
Besides, I added the flag value_only in case the use only needs the optimal value and does not care about the assignment. This, because the LP solvers can be forced not to return the assignment of the variables and only the objective value, avoiding this way some computations.

Besides, this syntax makes knapsack consistant with the other optimization functions I wrote for graphs, and I hope will all the LP functions we will write in the future ;-)

To avoid mistakes, I updated both patches ( they were identical ), and the new version obviously contains the old one, plus the update I just wrote !

Thank you for your review !

Nathann

[wdjoyner]

comment:9

There was this failure:

sage -t  "devel/sage/sage/numerical/knapsack.py"            
**********************************************************************
File "/Users/davidjoyner/sagefiles/sage-4.1.1.rc2/devel/sage/sage/numerical/knapsack.py", line 608:
    sage: knapsack([1,1.5,0.5], max=2)
Expected:
    [2.0, [1, 0.500000000000000]]
Got:
    [2.0, [1.50000000000000, 0.500000000000000]]
**********************************************************************

[nathanncohen]

comment:11

I always forget the LP solvers are non-deterministic algorithms, and because of this the values they return sometimes change, which causes trouble with docstrings ;-)

Sorry !

( Fixed, as usual the two patches are updated )

[wdjoyner]

comment:13

This last patch (and its dependency) installed fine as before (same system, and version) with the following failures:

The following tests failed:


        sage -t  "devel/sage/doc/en/bordeaux_2008/birds_other.rst"
        sage -t  "devel/sage/sage/interfaces/maxima.py"
        sage -t  "devel/sage/sage/symbolic/expression.pyx"

I think these are unrelated, so this gets a positive review from me. Thanks for implementing it!

[sagetrac-mvngu]

comment:14

This will have to wait until #6502 is resolved. Which patch is to be merged? Most likely, I think some if not all doctests would have to be flagged with "# optional" if they require the optional GLPK spkg.

[nathanncohen]

Attachment: knapsack.patch.gz

[nathanncohen]

comment:15

Attachment: knapsack.2.patch.gz

Updated. And you can apply any one of them, they're both the same ( I uploaded two by mistake the first time, then updated both )

[wdjoyner]

comment:16

This patch (on top of the updated 6502) did not apply for me (4.1.1.rc2, intel macbook 10.4.11).

[nathanncohen]

comment:17

I am using 4.1.1, perhaps it explains ?

I just tried it again with only 6502 and this one, and noticed nothing wrong O_o

[nathanncohen]

comment:18

Could you please try it again on a 4.1.1 ?

[wdjoyner]

comment:19

Replying to @nathanncohen:

Could you please try it again on a 4.1.1 ?

I created a new clone and re-tried this. This time it worked! Passed tests as before (same Sage version, same machine ....).

[nathanncohen]

comment:20

As the functions dealing with LP have not been reviewed, I prefer to rewrite the MIP class for Sage to make it easier to use. I will post a new version of the MIP patch as soon as possible, along with all the patches for functions using it.

Sorry for the trouble, I'll try to make it quick !

Nathann

[nathanncohen]

comment:21

Here is the new version, slightly modified to use the symbolics from #6869 ( the new version of MIP you need to try this code ! )

[nathanncohen]

Attachment: knapsack-symbolics.patch.gz

[wdjoyner]

comment:23

This applies fine to 4.1.2.a0 and passes testall without any other packages installed (no glpk, etc).

Running more tests...

[wdjoyner]

comment:24

This applies fine to 4.1.2.a0 and passes testall with glpk package installed.

[sagetrac-mvngu]

comment:25

Merged knapsack-symbolics.patch.

With knapsack-symbolics.patch, I got a warning when building the reference manual:

WARNING: /scratch/mvngu/release/sage-4.1.2.alpha1/local/lib/python2.6/site-packages/sage/numerical/knapsack.py:docstring of sage.numerical.knapsack.knapsack:69: (WARNING/2) Block quote ends without a blank line; unexpected unindent.

See #6916 for a follow-up to this ticket.

[sagetrac-mvngu]

Author: Nathann Cohen

[sagetrac-mvngu]

Reviewer: David Joyner

[sagetrac-mvngu]

Merged: Sage 4.1.2.alpha2