Complex Combinatorial Algorithms

Question

So Wendy's advertises their sandwich as having 256 combinations - meaning there are 8 ingredients you can either have to not have (although I wonder why they would count the combination where you include nothing as valid, but I digress).

A generalized approach allows you to multiply the various states of each selection together, which allows more complex combinations. In this case Wendy's items can only be included or excluded. But some sandwiches might have the option of two kinds of mustard (but not both, to save costs).

These are fairly straightforward. You multiply the number of options together, so For Wendy's it's:

2*2*2*2*2*2*2*2 = 256

If they diversified their mustard selection as above it would be:

2*2*3*2*2*2*2*2 = 384

Going further appears to be harder.

If you make sesame seeds a separate item, then they require the bun item. You can have the sesame seed only if you include the bun, and you can have the bun without sesame seeds, but you cannot have sesame seeds without the bun. This can be simplified to a single bun item with three states (none, bun with seeds, bun without) but there are situations where that cannot be done.

Dell's computer configurator, for instance, disallows certain combinations (maybe the slots are all full, items are incompatible when put into same system, etc).

• What are the appropriate combinatorial approaches when dealing with significantly more complex systems where items can conflict?
• What are good, generalized, approaches to storing such information without having to code for each product/combination/item to catch conflicts?
• Is there a simple way to say, "there are X ways to configure your system/sandwich" when the system has to deal with complex conflicting combinations?

Answer 1

HP's high-end server manufacturing facility in California used a custom rule-based system for many years to do just this.

The factory shopfloor build-cycle process included up-front checks to ensure the order was buildable prior to releasing it to the builders and testers.

One of these checks determined whether the order's bill of materials (BOM) conformed to a list of rules specified by the process engineers. For example, if the customer orders processors, ensure they have also ordered sufficient dc-converter parts; or, if they have ordered a certain quantity of memory DIMMs, ensure they have also ordered a daughter-board to accommodate the additional capacity.

A computer science student with a background in compilers would have recognized the code. The code parsed the BOM, internally generating a threaded tree of parts grouped by type. It then applied the rules to the internal tree to make the determination of whether the order conformed.

As a side-effect, the system also generated build documentation for each order which workers pulled up as they built each system. It also generated expected test results for the post-build burn-in process so the testing bays could reference them and determine whether everything was built correctly.