|
From: | Meketon, Marc |
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 think it would be fun to turn cspsol into an easy to use web app. I plan to do this at the #hack4good hackday in Dublin on Tuesday http://blog.geekli.st/post/64940486207/geeklist-hack4good-goes-to-the-web-summit-in-dublin Thanks for the help David 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] |