1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ "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... $\endgroup$
    – John Dvorak
    Jan 7, 2015 at 6:04
  • 2
    $\begingroup$ "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). $\endgroup$
    – Tom van der Zanden
    Jan 7, 2015 at 12:24
  • 1
    $\begingroup$ 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 $\endgroup$
    – Nicholas Mancuso
    Jan 8, 2015 at 22:35

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.