1
$\begingroup$

I want to compute the min-cost joint assignment to a set of variables. I have 50 variables, and each can take on 5 different values. So, there are 550 (a huge number) possible joint assignments. Finding a good one can be hard!

Now, the problem is that computing the cost of any assignment takes about 15-20 minutes. Finding an approximation to the min-cost assignment is also okay, doesn't have to be the global solution. But with this large computational load, what is a logical approach to finding a low-cost joint assignment?

  • 0
    @IlmariKaronen: True.2012-07-18

1 Answers 1

2

In general, if the costs of different assignments are completely arbitrary, there may be no better solution than a brute force search through the assignment space. Any improvements on that will have to come from exploiting some statistical structure in the costs that gives us a better-than-random chance of picking low-cost assignments to try.

Assuming that the costs of similar assignments are at least somewhat correlated, I'd give some variant of shotgun hill climbing a try. Alternatively, depending on the shape of the cost landscape, simulated annealing or genetic algorithms might work better, but I'd try hill climbing first just to get a baseline to compare against.

Of course, this all depends on what the cost landscape looks like. Without more detail on how the costs are calculated, you're unlikely to get very specific answers. If you don't even know what the cost landscape looks like yourself, well, then you'll just have to experiment with different search heuristics and see what works best.

  • 0
    Thanks for the thorough response. I implemented a pretty basic GA and I'm going to let that search for a couple of days, and hopefully get a good instantiation.2012-07-18