Opened 11 years ago

Closed 11 years ago

# [with patch, positive review] Knapsack algorithm

Reported by: Owned by: ncohen jkantor major sage-4.1.2 numerical Sage 4.1.2.alpha2 Nathann Cohen David Joyner

### Description

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

### comment:1 follow-up: ↓ 2 Changed 11 years ago by wdj

• Summary changed from [with patch, needs review] Knapsack algorithm to [with patch, needs work] Knapsack algorithm

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.

### comment:2 in reply to: ↑ 1 Changed 11 years ago by 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 ncohen

• 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 ncohen

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

### comment:5 Changed 11 years ago by wdj

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 wdj

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 wdj

• Summary changed from [with patch, needs review] Knapsack algorithm to [with patch, needs work] Knapsack algorithm

### comment:8 Changed 11 years ago by ncohen

• 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 wdj

```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 wdj

• Summary changed from [with patch, needs review] Knapsack algorithm to [with patch, needs work] Knapsack algorithm

### comment:11 Changed 11 years ago by ncohen

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 ncohen

• Summary changed from [with patch, needs work] Knapsack algorithm to [with patch, needs review] Knapsack algorithm

### comment:13 Changed 11 years ago by wdj

• 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 mvngu

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.

### comment:15 Changed 11 years ago by ncohen

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 wdj

• 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 ncohen

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 ncohen

• 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 wdj

• Summary changed from [with patch, needs review] Knapsack algorithm to [with patch, positive review] Knapsack algorithm

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 11 years ago by ncohen

• 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 11 years ago by ncohen

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

### comment:22 Changed 11 years ago by ncohen

• Summary changed from [with patch, needs work] Knapsack algorithm to [with patch, needs review] Knapsack algorithm

### comment:23 Changed 11 years ago by wdj

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 11 years ago by wdj

• 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 11 years ago by mvngu

• Authors set to Nathann Cohen
• 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.

Note: See TracTickets for help on using tickets.