Greedy Solver

Our initial approach for solving NTP problems was a greedy algorithm: Forces are analyzed one at a time. The push-relabel algorithm PRF by Cherkassky and Goldberg [21] is used to find a valid flow. Once a flow has been found it is fixed, and a remaining capacity for each joint (eq. 2.3) is computed that will produce a reduced network that must support the next force. A maximum flow is found for the second force with respect to the reduced network and so on for all forces.

$$K_{j}'=K_{j}-\phi _{F}(j)\delta (j,F)\vert\vert F\vert\vert$$ (2.3)

This simple algorithm misses solutions, yet is quick, and thus we preferred it for time reasons to the more sophisticated solvers. With the greedy model, some solutions might be missed; but the ones found are good -- so the structures evolve within the space of provable solutions, that is, those for which a greedy solution is found. This algorithm was particularly useful in the crane cases (sections 2.4, 2.6.3), where there is one special force, several orders of magnitude larger than the others. All experiments detailed here use this approach, except for the tree experiment (section 2.8) and EvoCAD (2.9), which employ the ``embedded solver'' explained below.