A specialized primal-dual interior point method for truss layout optimization problems

Technical Report ERGO-17-012

A. Weldeyesus and J. Gondzio

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

PDF ERGO-17-012.pdf.

Written: November 13, 2017.