[te]

> which would take longer than the heat death of the universe to find the global maxima

Sure, if you're using brute force, instead of a polynomial time algorithm.

> It doesn't matter what algorithm you use, finding the absolute best solution and proving it is impossible.

Hard disagree: https://en.wikipedia.org/wiki/Hungarian_algorithm

Linear Assignment seems a very strange choice to illustrate the utility of meta-heuristics, when that particular problem has a polynomial-time solution algorithm that has been known for 70 years.

[tsumnia]

I mostly use Linear Assignment because it was a simple problem that I could present to my students to serve as a foundation for learning about these algorithms and how they operate within a problem space. One aspect I believe helps in the learning process is to see an algorithm in action and to work through it at the base level.

The course is meant to serve as an intro to AI for students just coming out of a data structures course. Hungarian may be better for producing the optimal answer, I don't know I'd have to try it out. But I know that for my section on meta-heuristics Linear Assignment works as a great vehicle for demonstrating those algorithms.