Simulated annealing for optimization

Hello everyone,

i have a question to simulated annealing. I want to use it to solve a quadratic asignment problem (QAP) because it is very large and it takes to long to solve it with an exact algorithm. Is it possible to solve a QAP with simulated annealing ?

And how can I solve it with constraints like or . I can just give the algorithm a start value and a lower bound / upper bound.

Can please someone help me ?

Best regards !

Answer 1

[Walter Roberson]

Generally speaking, simulated annealing can be used to solve QAP, but it would likely be much much slower than a routine designed for solving QAP.

simulannealbnd supports bounds constraints, but no other kinds of constraints, and it does not support anything like event functions that might provide constraints. You would therefore need to code the constraints as a penalty, which is always risky because the routines do not know to avoid penalty areas.

Simulated Annealing is a slow process. You would probably be better off with patternsearch()

[Kernel7364]

Thank you very much for your quick and detailed answer. It helped me a lot.

I will study the two algorithm patternsearch() and simulannealbnd,

But why is it slow for a quadratic problem ? I have a QAP in the following form: I have a trainstation with around 30 platforms and there are more than 500 trains per day and I have to assign every train to exactly one platform. It is not possible to solve it with an exact algorithm like Branch and Bound because there are way to many variables.

Thats why I read that Simulated annealing is one of the fastest options to solve a problem of that type. I will try something out and hope that I can get a quick solution to that problem. It doesnt matter if its with patternsearch or simulated annealing. :)

Thank you very much again for your help !

I hope that you can tell me a good algorithm for my trainstation problem and for a problem of this size.

Best regards !

[Walter Roberson]

simmulannealbnd might not be bad for finding an approximate solution, but it is likely to take a long time to find the global minima.

The theory of simmulated annealing says that it is the only minimizer that can find the global minima of arbitrarily hard problems, provided it is given enough time and a slow enough temperature schedule. I have my doubts though: I suspect it might be more like the situation with random walks, which in 3 or more dimensions are not certain to reach any given point (indeed, random walk theory says that the probability that any given point will be reached in infinite time decreases rapidly as the number of dimensions increases.)

WIth the problem as described, it is not clear why you do not simply use Round Robin scheduling -- or if the trains have variable dwell time, then LRU (Least Recently Used).

[Kernel7364]

Thank you so much for your quick response again.

Your advices are really helpful for me. I will try different heuristic algorithm to find a good solution. After that I will compare the results and the times what they needed to find a solution.

Since I read in so many papers that Simmulated annealing is the best to find an approximate solution to my problem, I focused my study on that algorithm but I will definately try out the other ones too.

But I have one more question to the function simmulannealbnd.

how is it possible to set constraints like in that algorithm ?

In the link you gave me are just constraints for the upper bound and lower bound but since I have a QAP I also have constraints that for example .

That basicly means that every train has to be assigned to exactly one platform. And furthermore I have to give that algorithm the arrival and departure time that Matlab knows when a platform is available again after one train left the trainstation.

How is it possible to set this constraints. I could not find it in the link you gave me.

Sorry if some of my questions are silly, I am just a beginner with Matlab.

Thanks for your help !

[Walter Roberson]

I already told you that it is not possible to set constraints with simmulannealbnd . All you can do is add a penalty when the constraint is violated. However when you use penalties, you have to plan them carefully. For example if you return 1000000 when the constraint is violated, then SA would be happy to try to search for a location that returned only 999999.99999 instead of understanding that the area is to be denied.