# Are there some real-world optimization problems with very cheap objective functions?

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.

• "Unfortunately, I am not convinced that the TSP is a real-world problem" - routing a drill during a PCB manufacturing process, routing the thingie that places components into those holes, routing the solder arm (this one probably takes the same route as the drill), routing literal salesmen across multiple destinations, routing delivery trucks while avoiding left turns... Jan 7, 2015 at 6:04
• "A few hundred nodes" and "on the order of milliseconds" seems to be a vast underestimation of how fast such an objective function can be evaluated. We're talking about tens of thousands of nodes, not a few hundred. Some other examples (other than TSP) are cutting stock (cutting up glass/paper sheets to meet customer's specifications as efficiently as possible) and assignment problems (such as assigning classes to time slots so there are no conflicts). Jan 7, 2015 at 12:24
• In genetics we are often forced to use the Expectation Maximization algorithm to estimate parameters for our models since there typically exist no analytical solutions. Each iteration requires evaluating the likelihood function (or posterior if you're doing MAP estimation) which is usually polynomial with respect to the parameters and input. Technically you could skip directly evaluating the function and have stopping criterion based on the parameters not changing much, but that could result is bad final estimates Jan 8, 2015 at 22:35