Opened 11 years ago
Closed 10 years ago
#6749 closed enhancement (fixed)
[with patch, positive review] Knapsack algorithm
Reported by: | ncohen | Owned by: | jkantor |
---|---|---|---|
Priority: | major | Milestone: | sage-4.1.2 |
Component: | numerical | Keywords: | |
Cc: | Merged in: | Sage 4.1.2.alpha2 | |
Authors: | Nathann Cohen | Reviewers: | David Joyner |
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
A general knapsack algorithm using Linear programming ( check you have #6502 installed ! ) to patiently wait for more efficient versions :-)
Attachments (3)
Change History (28)
comment:1 follow-up: ↓ 2 Changed 11 years ago by
- Summary changed from [with patch, needs review] Knapsack algorithm to [with patch, needs work] Knapsack algorithm
comment:2 in reply to: ↑ 1 Changed 11 years ago by
Replying to wdj:
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 :-)
comment:3 Changed 11 years ago by
- Summary changed from [with patch, needs work] Knapsack algorithm to [with patch, needs review] Knapsack algorithm
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
comment:4 Changed 11 years ago by
A small mistake when uploading the patch... Well, now the two of them are good ;-)
comment:5 Changed 11 years ago by
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.
comment:6 Changed 11 years ago by
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.
comment:7 Changed 11 years ago by
- Summary changed from [with patch, needs review] Knapsack algorithm to [with patch, needs work] Knapsack algorithm
comment:8 Changed 11 years ago by
- Summary changed from [with patch, needs work] Knapsack algorithm to [with patch, needs review] Knapsack algorithm
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
comment:9 Changed 11 years ago by
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]] **********************************************************************
comment:10 Changed 11 years ago by
- Summary changed from [with patch, needs review] Knapsack algorithm to [with patch, needs work] Knapsack algorithm
comment:11 Changed 11 years ago by
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 )
comment:12 Changed 11 years ago by
- Summary changed from [with patch, needs work] Knapsack algorithm to [with patch, needs review] Knapsack algorithm
comment:13 Changed 11 years ago by
- Summary changed from [with patch, needs review] Knapsack algorithm to [with patch, positive review] Knapsack algorithm
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!
comment:14 Changed 11 years ago by
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.
Changed 11 years ago by
Changed 11 years ago by
comment:15 Changed 11 years ago by
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 )
comment:16 Changed 11 years ago by
- Summary changed from [with patch, positive review] Knapsack algorithm to [with patch, needs work] Knapsack algorithm
This patch (on top of the updated 6502) did not apply for me (4.1.1.rc2, intel macbook 10.4.11).
comment:17 Changed 11 years ago by
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
comment:18 follow-up: ↓ 19 Changed 11 years ago by
- Summary changed from [with patch, needs work] Knapsack algorithm to [with patch, needs review] Knapsack algorithm
Could you please try it again on a 4.1.1 ?
comment:19 in reply to: ↑ 18 Changed 11 years ago by
- Summary changed from [with patch, needs review] Knapsack algorithm to [with patch, positive review] Knapsack algorithm
Replying to ncohen:
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 ....).
comment:20 Changed 10 years ago by
- Summary changed from [with patch, positive review] Knapsack algorithm to [with patch, needs work] Knapsack algorithm
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
comment:21 Changed 10 years ago by
Here is the new version, slightly modified to use the symbolics from #6869 ( the new version of MIP you need to try this code ! )
Changed 10 years ago by
comment:22 Changed 10 years ago by
- Summary changed from [with patch, needs work] Knapsack algorithm to [with patch, needs review] Knapsack algorithm
comment:23 Changed 10 years ago by
This applies fine to 4.1.2.a0 and passes testall without any other packages installed (no glpk, etc).
Running more tests...
comment:24 Changed 10 years ago by
- Summary changed from [with patch, needs review] Knapsack algorithm to [with patch, positive review] Knapsack algorithm
This applies fine to 4.1.2.a0 and passes testall with glpk package installed.
comment:25 Changed 10 years ago by
- Merged in set to Sage 4.1.2.alpha2
- Resolution set to fixed
- Reviewers set to David Joyner
- Status changed from new to closed
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.
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.