On Tue, Jul 7, 2009 at 12:48 AM, Minh Nguyen<nguyenmi...@gmail.com> wrote: > > Hi David, > > On Mon, Jul 6, 2009 at 10:34 PM, David Joyner<wdjoy...@gmail.com> wrote: > > <SNIP> > >> I'm not an expert but did find this ((essentially vacuous) page: >> http://www.coin-or.org/SYMPHONY/branchandcut/MCKP/ >> and the knapsack problem is listed among the applications of Symphony: >> http://www.coin-or.org/SYMPHONY/branchandcut/applications.htm >> I could find no examples. > > Thank you for the pointer. > > <SNIP> > >>> So my question is: Do folks agree or disagree with me Cythonizing >>> >>> sage/numerical/knapsack.py >>> >>> and implement further algorithms in Cython? >> >> >> Well, I can't see an argument against making it faster:-) >> However, it would be nice if you could add some brute force code to >> actually solve an instance of the knapsack problem, for example >> the burgler problem at >> http://webspace.ship.edu/thbrig/DynamicProgramming/Knapsack%20Program/index.html > > At the moment, my priority is to implement as many algorithms as I > can/understand. On that list are certainly a greedy algorithm and a > dynamic programming algorithm. Somewhere down the list are more > efficient algorithms for other types of knapsack problems. My main > references are >
You might also want to implement a LLL-based knapsack solving algorithm, since Sage includes fplll which is an extremely fast LLL implementation. I don't know if this page is any good but it is about LLL knapsack algorithms: http://www.math.ucsd.edu/~crypto/Projects/JenniferBakker/Math187/index.html I bet COIN-OR doesn't have anything like that, so it could be a unique advantage of Sage in one case, maybe. William > [1] S. Martello and P. Toth. Knapsack Problems. > http://www.or.deis.unibo.it/knapsack.html > > [2] H. Kellerer, U. Pferschy and D. Pisinger. Knapsack problems. > > >> I probably would not use your code for teaching nut I know people >> who probably would if thee were enough examples to help them with the syntax. > > -- > Regards > Minh Van Nguyen > > > > -- William Stein Associate Professor of Mathematics University of Washington http://wstein.org --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
