[tsumnia]

I talk briefly about this in my video on Heuristic Functions (I won't link just to stop shameless plugging), but its a combination of funding, knowledge, and team.

Scheduling problems are a specific type of Optimization problem and many of those problems are NP-hard to exponential in complexity. For example a 25x25 Linear Assignment Problem has 25! potentially configurations, which would take longer than the heat death of the universe to find the global maxima. It doesn't matter what algorithm you use, finding the absolute best solution and proving it is impossible.

I'm not super familiar with Hungarian/Munkres but a quick GPT conversation points out that its O(n^3) isn't really good for those types of large problem sizes. Even if 25! isn't bad, I can always increase my N.

Again, how do you decide if Hungarian is better than Simulated? You find a bunch of problems that both can do and test the algorithms against them. If you get decent enough results, I'm sure there's a science journal out there that would also publish the results.

[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.