A Linear Program (LP) is a problem that can be expressed as follows (the Standard Form):
minimize cx
subject to Ax = b, x >= 0
where x is the vector of variables to be solved for, A is a matrix of known coefficients, and c and b are vectors of known coefficients. The expression c’x is the objective function, and the equation Ax = b and the inequality x >= 0 are called the constraints. All these entities must have consistent dimensions. The matrix A is generally not square; hence you don’t solve an LP by just inverting A. Usually A has more columns than rows, and Ax = b is therefore quite likely underdetermined, leaving great latitude in the choice of x with which to minimize c’x.
Although all linear programs can be put into the Standard Form, in practice it may not be necessary to do so. For example, although the Standard Form requires all variables to be non-negative, most good LP software allow arbitrary bounds on the variables. The web page Linear Programming Frequently Asked Questions, maintained by Robert Fourer, provides further information on linear programming and related software, while Hans Mittelmann evaluates the performance of various codes at his site.
Download a problem in one of the following formats:
1. MPS Format : MPS format is a standard ASCII medium used by most of the commercial LP codes. Essentially all commercial LP codes accept this format. MPS format is column oriented (as opposed to entering the model as equations), and everything (variables, rows, etc.) receive a name. Descriptions of MPS format can be found in Bixby’s miplib or at Fourer’s site. The MPS form of the LPs were obtained from David Gay’s netlib/lp directory. You can download the entire netlib directory as a single g-zipped tar file. You can also download individual problems. We have presolved all the netlib problems using the presolver of CPLEX Version 9.1.3. You can download the entire presolved netlib directory as a single g-zipped tar file (presolved problems). You can also download individual presolved problems
2. LP Format : This downloads the coefficients A, b, c, l, and u of an LP problem in the following form:
minimize c‘x subject to Ax = b, l <= x <= u
The coefficients for the LP Format are generated using a program of Mauricio Rescende that converts MPS Format to LP Format. The Fortran-based file format is described here. You can download the entire netlib directory as a single g-zipped tar file (LP Format), or you can download individual problems. The CPLEX presolved problems are available in a C-based file format. You can download the entire presolved netlib directory as a single g-zipped tar file (C-based, presolved), or you can download individual presolved problems.
3. MATLAB Mat Format : This downloads the MATLAB version of the Linear Programming problem. The MATLAB version of the LPs were generated by Tim Davis. You can download the entire directory of MATLAB Mat files as a single g-zipped tar file. You can also download individual MATLAB Mat files.
4. AMPL Format : AMPL should be run with one of these data files and an AMPL model. AMPL is a language for formulating, solving, and understanding mathematical programming problems. The language is described in the book AMPL: A Modeling Language for Mathematical Programming by Robert Fourer (Dept. of Industrial Engineering, Northwestern University), David M. Gay, Brian W. Kernighan (Bell Laboratories). You can download the entire directory of AMPL data files as a single g-zipped tar file. You can also download individual AMPL data files.
5. LP Solve Format : The test problems are downloaded in the format used by LP_Solve (Michel Berkelaar). The code used to generate this problem format was extracted by Hans Mittelmann from LP_Solve. Mittelmann provides codes to convert MPS format to and from LP_Solve format. You can download the entire directory of netlib test problems in LP Solve Format as a single g-zipped tar file. You can also download individual LP Solve files.