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 implemented a small knapsack problem solver module in sage/numerical/knapsack.py 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? -- 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 -~----------~----~----~----~------~----~------~--~---
