Re: [sage-devel] implement knapsack problems solvers in Cython or Python?

[David Joyner]

On Mon, Jul 6, 2009 at 4:57 AM, Minh Nguyen<nguye...@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
>
> >
>

[Minh Nguyen]

Hi David,

On Mon, Jul 6, 2009 at 10:34 PM, David Joyner<wdjo...@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

[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.

[William Stein]

On Tue, Jul 7, 2009 at 12:48 AM, Minh Nguyen<nguye...@gmail.com> wrote:
>
> Hi David,
>
> On Mon, Jul 6, 2009 at 10:34 PM, David Joyner<wdjo...@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

[Minh Nguyen]

Hi William,

On Mon, Jul 6, 2009 at 11:44 PM, William Stein<wst...@gmail.com> wrote:

<SNIP>

> 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

Thank you for the link.

> I bet COIN-OR doesn't have anything like that, so it could be a unique
> advantage of Sage in one case, maybe.

--
Regards
Minh Van Nguyen

[Minh Nguyen]

On Mon, Jul 6, 2009 at 6:57 PM, Minh Nguyen<nguye...@gmail.com> wrote:

<SNIP>

> So my question is: Do folks agree or disagree with me Cythonizing
>
> sage/numerical/knapsack.py
>
> and implement further algorithms in Cython?

Cythonizing the module

sage/numerical/knapsack.py

is now ticket #6513:

http://trac.sagemath.org/sage_trac/ticket/6513