I know that exponential time algorithms should generally be avoided but are sometimes necessary. A case being the Traveling Salesman. How common are such algorithms in production software? Are these cases typically necessary or a result of rush jobs? I understand that many can be solved with a good heuristic. What is typically done with those that cannot?
Something that not in production software but done on production software is formal verification. It is probably not adopted for most customer software but gains track for embedded systems and drivers, that is for hard- and software whose correctness is important (and tractable).
Those verficiation problems that are actually computable (barrier #1) are often EXPTIME-hard, in the more lucky cases you get PSPACE-complete problems (barrier #2). Both classes are (suspected to be) harder than NP-complete problems, which are easy in comparison. Doubly-exponential problems are also easily obtained.
In these cases, heuristics (in the sense of end result) don't cut it as you need definite results; therefore you need big machines and time. There are heuristics (in the sense of alternative selection) that often lead to shorter runtime (i.e. clever search space exploration when error states are searched) but in the worst case, waiting is all you can do. Or you can do a pen-and-paper proof and have it checked by machines, which is computationally simpler.
Programming language interpreters are worse than exponential time (in the length of their input, i.e. in the length of the program they're interpreting), and they are quite common. Another example is automatic theorem proving / constraint solving / sat solving / integer linear programming. And yet another example is symbolic differentiation as implemented in e.g. Maple/Mathematica (although it is possible to do symbolic differentiation in linear time if you're allowed to share subexpressions between nodes).
Let me take the example of travelling salesman problem. I have worked on it a few times.
There are a few times when I have been in a team that wrote solution for travelling salesman problem but with some more parameters. For example, it could be a store with a fleet of technicians and engineers each with a unique skill set. The destinations come up every day in the form of service requests. All the programs are in production though they have undergone modifications and maintenance since originally writing them.
This is how they worked. Each engineer would receive a list of things to service on a hand held device everyday. As they finish each service task, they should close the case. The cases that are left out join the cases to be scheduled for the following day with slightly higher priority as by then the customer would have expressed some dissatisfaction. There was a large set of reasons why an engineer would not attend a case. Traffic problems were most common.
How common are they? At least as common as number of after sale service requests coming from customers. Without after sale service, for example, retaining customers is going to be hard and gaining new ones is going to be harder.
With many web based shops such as Amazon and other book stores and other such shops doing well in business, I would think travelling salesman is more common than it used to be. Also, there could be many variations of the travelling salesman problem that are taught in text books.