I once had a financial bin packing problem at a previous company. Rather than going down a dynamic programming route which was highly exponential, we decided to use a combination of monte-carlo simulation and a very basic genetic algorithm to try and find a solution. This made use of the fact that we could try solutions extremely quickly, and also timebound the overall time taken (something that was important as we had a limited time window). We'd still be able to run 1-2e6 different approaches in under a second.
Although we couldn't guarentee the "best" approach possible we generally came up with something good enough, often in many orders of magnitude less time.
A good example of the performance improvements you can make when you move from thinking of what the best solution is to what a "good enough" one is.
Although we couldn't guarentee the "best" approach possible we generally came up with something good enough, often in many orders of magnitude less time.
A good example of the performance improvements you can make when you move from thinking of what the best solution is to what a "good enough" one is.