Algorithm Animation: Affine Scaling


Since most people benefit greatly from geometric intuition, it is natural to try to represent a algorithms graphically. The obvious/textbook graphical representation of algorithms for linear programming involve restricting ones attention to situations with at most 3 variables. However, real-world linear programming problems involve thousands of variables and constraints. It would be nice to have graphical representations for these problems too. If one is willing to restrict ones attention to a specific application area, then it is often easy to come up with a nice representation of the problem.

Minimum-Weight Structural Design

Here we consider the minimum-weight structural design problem. A simple version of this problem is defined as follows. One starts with a graph (i.e., list of nodes and connecting arcs) that represents places in 2 or 3 dimensional space where structural beams could be placed. The problem is to design a structure that is anchored at certain specified nodes and that can support a specified load (i.e., force vector) at certain other specific nodes. We assume that each beam must have a cross sectional area that is proportional to the tension/compression that that beam must carry in order to have force balance at every node in the structure. Of course, the objective is to minimize weight, which is assumed to be proportional to the sum of the volumes of the beams. Without going into the details (see Chapter 15 of Linear Programming: Foundations and Extensions), the problem can be easily formulated as a linear programming problem.

Affine-Scaling Algorithm

The applet below animates the affine-scaling algorithm for solving linear programming problems. There are several data sets one can choose from. After selecting a problem and clicking on the Solve button, you will see a graphical animation of the affine-scaling algorithm. Nodes are shown in blue except for anchor nodes which are magenta and load nodes which are yellow. The load vectors themselves aren't shown; they are in all cases vectors pointing vertically downward.

Details of the affine-scaling algorithm can be found in many places for example Chapter 20 of Linear Programming: Foundations and Extensions).

Running the Animation

In the optimal structure, beams with zero cross-sectional area are, of course, simply not built. Of the beams that remain, some are under compression and others are under tension. The compressed beams are shown in red while the beams under tension are shown in green.

There are a few parameters that you can play with. The step length parameter should be a number between 0 and 1. In commercial implementations of these sorts of algorithms, the step length is taken to be very close to 1 (typically, 0.995) and the algorithm runs in very few iterations. One can obtain a more interesting animation by setting this parameter close to 0 (say 0.1). In this case, assuming the computer you are using is fast enough, the animation should flow like a movie going from the initial inaccurate guess to the optimal solution.

The second parameter is the strength of the beam material. A larger value gives smaller cross sections. You should simply adjust this parameter as appropriate to get a nice visual representation for each specific problem.