knapsack problem in OpenEdge - Forum - OpenEdge Development - Progress Community
 Forum

knapsack problem in OpenEdge

This question is not answered

There are some algorithms to address this problem (using weight and size limitations to calculate the optimal boxes for a given shipment). Has anybody solved this using ABL yet? 

All Replies
  • Which part of the algorithm are you having trouble with?

  • I was just wondering if anybody has done it yet in ABL. I found some references to the Shotput algorithm etc ..

  • Yes, I have but it has been literally twenty years ago.  We were looking how to saw different sized pieces from metal bars to reduce waste.  So someone with manufacturing experience might be able to relate.

    Scott Augé
    President
    Amduus Information Works, Inc.
    Technical Services for Business and Government
    http://www.amduus.com/cms

  • Yes (though we're replacing it with a 3rd party solution), but our solution is proprietary and can't be shared externally.  I expect that a lot of similar algorithms that are being used commercially would be similarly protected.

  • At my previous client we had a similar situation, albeit that we had to come up with production work orders that could rely up to 30 parameters. What we did was to construct a dataset of parameters and hand it over to a .net program that - in parallel - brute forced a good solution. Not "the best" per-se, because there could be trillions of combinations of parameters that needed to be checked. The .Net solution was able to process ~2 million combinations per second per thread. Do it on a 28 cpu machine and you end up with ~55 million combination checks per second. In our case we cut off the calculation after 3 seconds and picked the one that was the best till then.

    As a comparison: the previous solution was 100% progress based and was able to calculate around 30 combinations per second. It was allowed to run for max 30 minutes to come up with a work order, thus having checked at max 50.000 combinations. Our .Net solution handles those in 0.025 seconds....