algorithm - Al Zimmermann's Son of Darts

Question

There's about 2 months left in Al Zimmermann's Son of Darts programming contest, and I'd like to improve my standing (currently in the 60s) to something more respectable. I'd like to get some ideas from the great community of stackoverflow on how best to approach this problem.

The contest problem is known as the Global Postage Stamp Problem in literatures. I don't have much experience with optimization algorithms (I know of hillclimbing and simulated annealing in concept only from college), and in fact the program that I have right now is basically sheer brute force, which of course isn't feasible for the larger search spaces.

Here are some papers on the subject:

• A Postage Stamp Problem (Alter & Barnett, 1980)
• Algorithms for Computing the h-Range of the Postage Stamp Problem (Mossige, 1981)
• A Postage Stamp Problem (Lunnon, 1986)
• Two New Techniques for Computing Extremal h-bases Ak (Challis, 1992)

Any hints and suggestions are welcome. Also, feel free to direct me to the proper site if stackoverflow isn't it.

Answer 1

I am not familiar with the problem. But maybe you could do things like branch & bound to get rid of the brute force aspect.

http://en.wikipedia.org/wiki/Branch_and_bound