The Design of the XMP Linear Programming Library; MIS Technical Report No. 80-2

[2], 27, [8] pages. Figure. References. Staplebound. Illustrated covers. Pencil notes on front cover. Cover has tape repairs. The author may have later joined the National Bureau of Economic Research (NBER). XMP is a hierarchically structured library of FORTRAN subroutines for linear programming. Its purpose is to facilitate algorithmic research and model development in operations research and related disciplines. The intended audience for XMP, the design goals that were identified as essential for serving that audience, and the way in which those goals were embodied in a working system, are described. Experience with XMP shows that an LP system can be designed primarily for flexibility and ease of modification without too great a sacrifice in computational efficiency. This paper was written to advance a particular viewpoint toward the development of mathematical software and to influence the designed of future systems of mathematical programming. This document appears to have been subsequently published in ACM Transactions on Mathematical Software 7(4):481-497 December 1981. Linear programming is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization). More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Its feasible region is a convex polytope, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a real-valued affine (linear) function defined on this polyhedron. A linear programming algorithm finds a point in the polyhedron where this function has the smallest (or largest) value if such a point exists.…