|Subject:||Re: [Help-glpk] cspsol webapp|
|Date:||Sun, 27 Oct 2013 10:38:35 -0500|
Solving the knapsack subproblem of the CSP is typically best done using dynamic programming and not using MIP. You may wish to consider that.
The best dynamic programming algorithm I have found is in the book by Kellerer, Pferschy and Pisinger [2004, Springer-Verlag, ISBN 3-540-40286-1].
I had implemented a related knapsack problem using that book. In this case the cost and the weight of the objects were the same (some folks call this the subset-sum problem), and later on I posted it as an answer in stack overflow (http://stackoverflow.com/questions/18066624/maximum-sum-of-a-subset-of-size-k-with-sum-less-than-m/18535311#18535311). While that isn’t the exact algorithm you would need, it might give you a clue on how the DP algorithm works.
From: help-glpk-bounces+address@hidden [mailto:help-glpk-bounces+address@hidden
On Behalf Of David Curran
I plan to do this at the #hack4good hackday in Dublin on Tuesday
Thanks for the help
This e-mail and any attachments may be confidential or legally privileged. If you received this message in error or are not the intended recipient, you should destroy the e-mail message and any attachments or copies, and you are prohibited from retaining, distributing, disclosing or using any information contained herein. Please inform us of the erroneous delivery by return e-mail. Thank you for your cooperation.
|[Prev in Thread]||Current Thread||[Next in Thread]|