On Mon, Jul 6, 2009 at 4:57 AM, Minh Nguyen<nguyenmi...@gmail.com> wrote: > > Hi folks, > > Knapsack problems and their algorithmic solutions have many > applications in industry, with operation research and cryptography to > name two. As many, if not all, of the operation research software of > COIN-OR are covered by licenses that are incompatible with GPLv2+, I > have thought about writing a Sage interface to a COIN-OR software > package for solving knapsack problems. However, let me admit that I'm > not an expert in combinatorial optimization, my knowledge of knapsack > problems is what one would get from undergraduate courses in discrete > mathematics and linear optimization, and I'm a COIN-OR beginner. So > please correct me if I make wrong or misleading statements about > COIN-OR. > > OK, now to the fun bits. As far as I look, I haven't been able to find > such a COIN-OR software package for solving knapsack problems. (If you > know of such a package, please provide me with a pointer to it.) So I
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. > implemented a small knapsack problem solver module in > > sage/numerical/knapsack.py This is cool. Thanks for doing that! > > In case you're wondering, yes, it's in Sage already since version > 4.0.2. As algorithmic solutions to knapsack problems are of great > importance to industry, I would like to rewrite that knapsack module > in Cython. From that Cythonized module, I plan to implement more > efficient algorithms in Cython for solving various types of knapsack > problems. This is in contrast to continue using the above Python > module and implement more algorithms on top of it. I thought I should > put this proposal through sage-devel first, so there wouldn't be any > surprises when I show up with a Cythonized version of a module in the > Sage library. > > 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 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 > > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
