System Architecture: Strategy and Product Development for Complex Systems, First Edition

Appendix D: Classical Combinatorial Optimization Problems

We explained in Chapter 16 that system architecture problems can be framed as combinatorial optimization problems. When we identified the six patterns of architecture problems, we mentioned that some of them look superficially like classical combinatorial optimization problems. For example, we argued that down-selecting problems look like 0/1 knapsack problems, with the difference that the value of elements is not additive—there are synergies, interferences, and redundancies.

In this appendix, we provide a list of some of the most typical combinatorial optimization problems. The list is partially adapted from Gandibleux’s classification of combinatorial optimization problems according ...