On the use of the simplex algorithm for the absolute deviation curve fitting problem

Linear curve-fitting problems are commonly solved using a criterion which minimises the sum of the squares of deviations of observations from the line. The legitimacy of this operation relies on a number of assumptions which in practice are often left untested. Alternatively the curve-fitting exercise is justified by its computational tractibility. An alternative procedure which fits lines using a criterion of minimising the sum of the absolute deviations of observations from the line is acknowledged to have attractive properties, but is often avoided because of computational difficulties in solution. In fact this problem has long been known to be amenable to solution by linear programming, and in this paper we present some results, commentary and advice based on the use of three LP codes to solve the problem. Two of these codes are conventional implementations of the simplex method while the third is a special purpose code written for just this problem. Live data from a problem of batch manufacture was used, and the influence of data is part of the investigation. At least some of the advice is contrary to that offered by earlier authors.