Assuming that P ≠ NP (see the article Does P equal NP?), there are unfortunately no efficient algorithms for solving some optimization problems. Yet, as is often the case in mathematics, these problems can be so simply stated that their underlying difficulty is hard to imagine. Take the famous traveling salesman problem: given a set of cities, what is the shortest route that visits every city and returns to its starting point? Despite this simple formulation, no algorithm can solve the problem efficiently: even the best takes an amount of time that grows exponentially with the number of cities. What can we do when we want to solve a "large-scale" problem (of the kind encountered in practice) within an "acceptable" time (a few minutes or so)?
Heuristics… -----------------
One approach is to use heuristics (from the Greek heuriskein, meaning "to find"). A heuristic aims to find a solution that satisfies the problem's constraints and is of "good quality" according to the chosen optimization criterion. The solution will not necessarily be optimal, but an effective heuristic attempts to find a good-quality solution within the allotted time.
For example, a simple approach to the traveling salesman problem is the nearest-neighbor heuristic: at each step, we choose the next city so that its distance from the current city is as small as possible, continuing until every city has been visited. We then return to the first city visited to obtain a route (or tour). This heuristic is fast, but in practice it gives rather poor results: there is no guarantee that the last city visited will be "close" to the first, which can leave us with a long and costly final route.