The paper considers the classical problem of finding a truss design
with minimal compliance subject to a given external force and a volume
bound. Feasible structures are defined through the ground structure
approach. While this problem is well-studied for continuous bar areas,
we treat here the case of discrete areas. This problem is of big
practical relevance if the truss must be built from pre-produced bars
with given areas. As a special case, we treat the design problem for a
single bar area, i.e., a 0/1-problem.

In contrast to heuristic methods considered in other approaches,
this paper together with Part II presents an algorithmic framework
for the calculation of a global optimizer of the underlying large-scaled
mixed integer design problem. This framework is given by a convergent
branch-and-bound algorithm which is based on straightforward continuous
relaxations of the bar areas. The main issue of the paper and of the
approach lies in the fact that the relaxed nonlinear optimization problem
can be formulated as a quadratic programming problem QP. Here the paper
generalizes, extends, and makes corrections to an older paper dealing
with this theory. Although the Hessian of this QP is indefinite, it is
possible to circumvent non-convexity and to calculate global
optimizers. Moreover, the QPs to be solved in the branch-and-bound
search tree differ from each other just in the objective
function. Therefore, very good starting points are available.
This makes the resulting branch-and-bound methodology very efficient.

In Part I we give an introduction to the problem and collect all
theory and related proofs for the treatment of the original
problem formulation and some relaxed problems. For implementation
details of the methodology and for numerical examples the reader
is referred to Part II.