Sunday, June 24, 2012

Roadef 2012 first results for B datasets with Planner

The Google ROADEF research competition ended 2 weeks ago and I had too little time to submit an entry with Drools Planner.
However, I 've done a few quick tries on the B instances the last 2 weekends to test the just-in-time selectors:
  • 300 seconds single-threaded on JDK 6 on my 2 year old computer
  • Entity tabu search with size 7, minimalAcceptedSelection 2000
  • With the new just-in-time selectors enabled.
Update: I 've updated the results on 1-JUL-2012 to include the memory footprint fix.

Here are Planner's results on the B instances, which are notorious for their large problem scale:

Instance Hard Score Soft score Better than original
B10 - 3 747 407 470  51 %
B20 - 1 059 414 398  80 %
B30   - 163 774 53697 %
B40 - 4 677 922 31649 %
B50   - 923 842 56893 %
B60 - 9 525 882 69125 %
B70- 15 313 722 82260 %
B80 - 1 214 588 65491 %
B90- 15 885 640 05632 %
B100- 18 814 086 53155 %
Average63 %

Note that the original solution is not some random solution, but already a feasible solution. This means the machine resource utilization would be 63% better on average by using Drools Planner.

All instances were solved in their entirety: I didn't need to result to partitioning like some of the other contestants to be able to solve them.
All instances require 1 GB memory or less, but the results above are done with 2 GB memory, because the biggest instance (B10) gives better results with a heap slightly bigger then 1 GB.

Note that the solver configuration hasn't been thoroughly tweaked. Now, with the end of the competition, that the other contestants are also opening their ideas (and hopefully their code), it will be interesting to see what we can learn from each other. I 've already had some conversations with the excellent Kaho team last week and I 'll be experimenting with some of their suggestions.


  1. Are you using a 32bit JDK?

    How is it that you are limited to 4GB (or 2.6 as you say)?

  2. @Sean not sure, but I want to get it under 1GB, so it doesn't matter why it crashes.

    I founds why its using so much memory: because of the class MrMachineMoveCost.

  3. I can now load and run even B10 in 1GB memory. I 'll update this blog with the new results once the benchmarker has rerun them on all instances.
    Here's the commit that made all the difference.