NP-completeness seems to me like one of those things that's mostly just theoretical and not really something you'd run into in a normal work environment.
So I'm kind of curious if anyone's ever run into a problem at their job that turned out to be NP-complete, and that the design needed to be changed to accommodate for it?
The travelling salesman problem is a perfect example. The same kind of logistical problems apply to airlines, post offices, and all kinds of industries.
Any kind of mapping tool where you need to find optimal traveling points between more than two locations can without any changes become a NP-Complete problem
The problem of optimizing wave picking from a warehouse is equivalent to the Travelling Salesman problem.
That is, you have N-orders waiting to be picked, and you want to find the n best orders to minimize distance travelled and different pick locations visited by a picker.
I recently came across this problem. We punted and used an approximation that will work well for the average case, but may sometimes provide sub-optimal results.
Also, the knapsack problem (which is NP-hard) shows up fairly frequently. It's a seductive trap for attempting to optimize things.
As the others have stated, the knapsack (for packing cargo) and traveling salesmen problem are probably the most common "real world" NP-complete problems.
I tend to run into problems at work that can't be proven to be NP complete or incomplete because they're not very well defined.
I agreed to write software for a friend's father when I was a first-year college student. It was for scheduling resources. I didn't realize it at the time, but it turned out to be an NP complete problem.
Thankfully just finding a solution was acceptable - didn't need to find the optimal solution. It was fun writing heuristics - actually a set of them - that could be changed while the program was running and trying to solve the problem.
I had a solution done in a summer, but then worked on new versions each successive year. My big plans to sell it fell flat. I was a better developer than marketer.
It was a lot of fun and taught me early on a lot about the real-world of development - (end users, requirements gathering, testing, etc - a lot of the things that you DON'T get in undergrad CS)
To address your question - it was for a teacher who had to schedule students for special instruction. He was a speech therapist and audiologist - but it could be applied to any similar field. He had existing teacher, classroom and student activities to work around and had to meet some specific number of times per week with students. It is the knapsack problem or any number of other similar/equivalent scheduling problems.
Again, it turned out that just getting a solution was fine - we didn't have to maximize or minimize anything - we just had to accommodate all the students.
I can only recall not being able to solve test cases that I used to run scenarios - all the problems he provided over the years we solved.
I was never able to market it - mostly because I had no idea what I was doing and I was not sure how to reach my market/buyers.
It's worth noting that there are heuristic approximation techniques for obtaining "good enough" answers for NP-complete problems, such as simulated annealing and compressed annealing. If you can reduce your NP-complete problem to the Traveling Salesman problem, you can use these approaches. (Any NP-complete problem can be reduced to any other NP-complete problem, but actually doing that is sometimes a pain in the ass.)
Anyway, there are simulated-annealing and compressed-annealing implementations out there; one such is Djinni, which is written in C++ and has Python bindings.
Another example is that companies with regional distribution centers, especially those that deliver directly to the customer (e.g. Netflix), need to worry about the family of NP-Complete problems known as facility location.
In fact, the idea that NP-Complete problems are relevant in the real world is evidenced by the fact that approximation algorithms for them so frequently show up in journals of operational research.
I was working on a mapping program a few years back, like a native Google Maps. I put little markers on the map for locations, but a lot of markers were clustered closely at certain locations. My boss said "let me make it so I can just drag the markers away a little" (and it'd have a line or speech-bubble-pointer-thingy going from the marker to the actual location).
I thought it was silly to make the user do this, especially since he'd spend 5 minutes making it perfect, and then change the zoom level, and then everything would be wrong.
I decided to try writing a function to find a way to lay out labels such that the total screen distance from each label to its location was minimized. I believe I convinced myself at the time that this was NP-complete, but that the number of points might be small enough for it to still be feasible, at least in many cases. (I remember thinking we spent way too much time in class on NP-completeness proofs, and not enough on alternative solutions: if your boss wants something done, you can't just say "NP hard, won't do" -- you still have to come up with something.)
Then Google Maps came along and just splatted all the labels on top of each other, which totally sucks (and I curse it every day), but I can't compete with their other features so I gave up. :-(