  Auxiliary variables are often used to model a convex piecewise linear
function in the framework of linear optimization. This work shows that such
variables yield a block diagonal plus low rank structure in the reduced KKT
system of the dual problem. We show how the structure can be detected
efficiently, and derive the linear algebra formulas for an interior point
method which exploit such structure. The structure is detected in 36% of the
cases in Netlib. Numerical results on the inverse planning problem in radiation
therapy show an order of magnitude speed-up compared to the state-of-the-art
interior point solver CPLEX, and considerable improvements in dose distribution
compared to current algorithms.
