Abstract
Truss layout optimization problems are commonly modeled as linear
programming problems and are known to challenge the existing
optimization solvers because of their large dimension and numerical
difficulties. A technique called member adding that has correspondence
to column generation is used to produce a sequence of smaller sub-problems
that ultimately approximate the original problem. Although each
of these sub-problems is signifficantly smaller than the full
formulation of the problem, they still remain large and require
computationally efficient solution techniques. Moreover, the level
of difficulty in such problems increases signifficantly for multiple-load
case problems. In this article, we present a special purpose primal-dual
interior point method tuned to such problems. The method exploits
the algebraic structure of the problems to reduce the normal equations
originating from the algorithm to much smaller linear equation systems.
Additionally, these systems are solved using iterative methods rather
than using more expensive direct methods. Finally, due to high degree
of similarity among the subsequent sub-problems after performing few
member adding iterations, the proposed method uses a warm-start
strategy to define a starting point and achieve convergence within
fewer interior point iterations. The efficiency and robustness
of the method are demonstrated with several numerical experiments
on single- and multiple-load case problems.
Key words: Truss layout optimization, Linear programming, Interior point methods, Iterative methods for linear systems