Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
There are $50^5$ joint assignments, not 550. –  Ross Millikan Jul 13 '12 at 19:41
    
@RossMillikan Sorry, poor copy and paste. But wouldn't it be $5^{50}$, not $50^5$? –  yoda Jul 17 '12 at 13:37
    
No, one variable can take $5$ values, two can take $2^5=25$, and $50$ can take $50^5$. This is actually not so many ($3.125E8$)-I have run through that many cases, but they didn't take 15 minutes to run. –  Ross Millikan Jul 17 '12 at 13:43
    
@Ross: $2^5 = 32 \ne 25 = 5^2$. Brain fart? –  Ilmari Karonen Jul 18 '12 at 15:04
    
@IlmariKaronen: True. –  Ross Millikan Jul 18 '12 at 15:10

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks for the answer (and sorry for the delayed response). The costs definitely aren't completely arbitrary, but I don't have a clear picture of the optimization space. My assumption is that there are a large number of local minima, and I don't necessarily want the global min (that would be nice), but just something better than an arbitrary selection (as good as possible in a small time constraint, clearly) –  yoda Jul 17 '12 at 13:38
    
Well, in that case, some simple hill climbing algorithm sounds reasonable. For example, you could start with a random assignment, try changing each of the variables to each alternative value and switch to the new assignment if it gives a lower cost. When you end up in a local minimum (i.e. an assignment that can't be improved by any single-variable change), save it and restart from another random assignment. Once you've got that working, you can try to refine it into something like simulated annealing or tabu search and see if those work any better. –  Ilmari Karonen Jul 18 '12 at 15:13
    
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. –  yoda Jul 18 '12 at 15:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.