[Solved]: Are there some real-world optimization problems with very cheap objective functions?

Problem Detail: 

Many real world optimization tasks (especially black box optimization) have objective functions, which are quite expensive to evaluate. For example to find the optimal shape of an airplane wing, a computer model of the wing needs to be constructed and then a large physical simulation needs to be executed, usually taking many hours.

Are there some real-world optimization tasks that have optimization functions which are extremely cheap (on the order of milliseconds) to evaluate? The only thing that comes to my mind are some classical functions, such as the travelling salesman problem with up to a few hundred nodes. The evaluation of a solution consists just of adding a few hundred numbers, which is easily accomplished on the desired time scale. Unfortunately, I am not convinced that the TSP is a real-world problem, since it is so simple.

Asked By : Martin Drozdik

Answered By : mhum

If you don't consider the Traveling Salesman Problem to be "real-world" enough, maybe take a look at its close cousin the Vehicle Routing Problem (VRP). In particular, consider all the variations of VRP, many of which clearly have their origins in real-world situations (e.g.: time windows, backhauls, etc...). This survey (pdf) by Eksioglu et al. details many of these variations. And, as far as I can tell, VRP objective functions are not much more difficult to evaluate than those of TSPs.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37028

3.2K people like this

 Download Related Notes/Documents