Trusses, NP-completeness, and genetic algorithms

The optimization of large trusses often leads to a nearly optimal solution, rather than a truly optimal design. In fact, the problem space for truss optimization grows exponentially with the size of the truss. Using the method of problem reduction, this paper demonstrates that truss optimization is in the set of NP-complete problems. Hence, the only practical techniques for solving the truss problem are heuristic in nature. Genetic algorithms provide a viable solution for large trusses. Copyright ASCE 2006.