# How to compute the min-cost joint assignment to a variable set when checking the cost of a single joint assignment is high?

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?

-
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