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?