What optimization problems do you want to have solved?

Question

I love to work on AI optimization software (Genetic Algorithms, Particle Swarm, Ant Colony, ...). Unfortunately I have run out of interesting problems to solve. What problem would you like to have solved?

Answer 1

This list of NP complete problems should keep you busy for a while...

Answer 2

How about the Hutter Prize?

From the entry on Wikipedia:

The Hutter Prize is a cash prize funded by Marcus Hutter which rewards data compression improvements on a specific 100 MB English text file. [...]

The goal of the Hutter Prize is to encourage research in artificial intelligence (AI). The organizers believe that text compression and AI are equivalent problems.

Basically the idea is that in order to make a compressor which is able to compress data most efficiently, the compressor must be, in Marcus Hutter's words, "smarter". For more information on the relation between artificial intelligence and compression, see the Motivation and FAQ sections of the Hutter Prize website.

Answer 3

Does the Netflix Prize count?

Answer 4

I would like my bank balance optimised so that there is as much money as possible left at the end of the month, instead of the other way round.

Answer 5

What about the Go Game ?

Answer 6

Here's an interesting practical problem I came up while tinkering with color quantization and image compression.

The basic idea is that I would like a program to which I give a picture and it reduces the amount of colors is it as much as possible without me noticing it. Since every person has a different sensitivity of the eye (and eyes have different sensitivity of red/green/blue intensities), it should be possible to specify this sensitivity threshold in some way.

In other words, in a truecolor picture, replace every pixel's color with another color so that:

• The total count of different colors in a picture would be the smallest possible; and
• Every new pixel would have it's color no further from the original color than some user-specified value D.

The D can be defined in different ways, pick your favorite. For example:

• Separate red, green and blue components for specifying the maximum possible deviation for each of them (for every pixel you get a rectangular cuboid of valid replacement values);
• A real number which would represent the maximum allowable distance in the RGB cube (for every pixel you get a sphere of valid replacement values);
• Something inbetween or completely different.

Answer 7

Most efficient solution to a given set of Sudoku puzzles. (excluding brute-force methods)