NP complete or NP hard problems in real life

Question

Does anybody have real life examples where they regularly solve NP complete or NP hard problems (by heuristics, or chasing a suboptimal solution or whatever) in their job? I know they occur in scheduling, planning, VLSI design, etc., but I am trying to get an idea of the major industries employing programmers or engineers today that regularly do this. If one were to develop expertise or a library, in say, combinatorial optimization where could one use that as part of a programming job?

Any personal accounts?

Answer 1

Some of the things I can think of (most of these I've been involved in more or less):

• Development environments for languages and compilers. Questions such as: does this grammar generate an ambiguous language? (This problem is actually undecidable!)
• Data recovery. Reassembly of partially lost data packets or recovering fragmented files. (Factorial complexity)
• Software security. Assessment of all the possible execution paths through a piece of software to determine whether some observed behaviour can be attributed to it. (Halting problem?)
• Logistics. Optimizing the use of transports based on packets to transport, their size and where they have to go. (At least exponential)

There are lots of standard examples such as finding the shortest route, nurse scheduling, etc. but if you're into combinatorial optimization, you know all about those :)

Answer 2

I have used time constrained simulated annealing to solve a travelling saleman like problem in touch panel manufacturing. Every millisecond we could shave from the cycle time of the laser etching of each panel would increase the throughput, utilisation and thus profitability of the machine, so I put a lot of effort into minimising dead time (non scribing paths) between scribing paths (which obviously couldn't be optimised away).

I used a time-bounded algorithm to get around the NP hardness of the problem, as we couldn't afford the risk that optimisation calculation might take longer than the time saved by the more optimum path. While the machine was moving the panel from the loading position to the position where the laser head was over the closest corner I had the time to run some simulations. The algorithm almost never ran to completion within the few hundred milliseconds of the move, but almost always returned a better scribe path than any of the simple, non adaptive models we had always used before (such as a spiral or snake paths).

Answer 3

I'm working (right now, actually) on the bioinformatics problem of multiple local DNA sequence alignment. The point of this is that if a lot of sequences from genes with some common property (similar expression profile or same transcription factor binding in a ChIP-chip experiment) align strongly at some point, then you've probably found the reason for their common property. Then again, I'm more interested in the statistical aspects of the problem. Even though it's NP-hard, you don't lose much by using heuristics in practice. The interesting part of the problem, IMHO, is a signal to noise ratio issue.

Answer 4

I don't really know, what NP complete/hard means, but I think, supply autoplanning is a kind of that.

You have demand plan 90 days forwards for 100 product SKUs: beer! The 100 product SKU comes from:

• there're 10-15 kind of level-1 base raw brewed stuff, they're brewed in thousdnd litre big cans, and it takes a day;
• after brewing, some materials must be added (leaven?), and it must be rest for 10-15 day, then you got 15-20 kind of level-2 stuff;
• finally, when it's ready, some materials should be added, it's the level-3 stuff, called drinkable beer, there're cc. 30 kind of beers;
• the beer can be bottled as 3 dl, 5 dl, sometimes it gets special necklacigng (level 4), then it can be packed as 5x4 box, 6-pack (level 5).

There're machine "lines" for each operation: from brewing to packaging. The machines can perform more operations, say, some packing machines can make 6-pack and 3-pack, but others can do only 6-pack. There're constraints, e.g. speed, or the big brewing kettle is for brewing min. 6000, max, 8000 l of beer, (but if the beer type is light, then the min. is 5000 l and the max. is 7000 l). And so on, on every level.

The task: as I mentioned, there's a demand plan, for the 100 kind of level-5 (the bottled, packaged stuff). Make an optimal manufactoring plan for all the 5 levels, all machines. Minimize machine switches (e.g. bottling .5, .5, .5, .3, .3, .3 is better than .3, .5, .3, .5, .3, .5, there're less swithc, less dead time for bottling machines). Priorize by customer: some customers requires to ship the beer only with more than 50% of expiration time remains. Etc, etc.

Discover bottlenecks (eh), make alternate plans with adding non-existent machines to these points, then the best virtual scenario can be used to suggest to buy a new machines.

Is it hard enough, or should I tell ya how a textile factory works?

(Personal remark: the web, the bank and the logistics are challenging areas, but they're baby toys compared to manufactoring problems.)

Disclaimer: numbers are distorted for security reason, order of magnitude is real.