CONTENTS:

This package contains the ANSI C sources for a very efficient (mixed integer)
linear problem solver. To compile without warnings, you need ANSI include
files as well. Its base is a sparse matrix dual simplex LP solver.  MILP
problems are solved with a branch-and-bound iteration over LP solutions.

It uses a lex and yacc parser to read a human-friendly algebraic input format.

MPS format

If you insist on using the old MPS format, you can obtain a converter from MPS
to lp_solve format from ftp.es.ele.tue.nl as pub/lp_solve/mps2eq_0.2.tar.Z.

PROCEDURAL INTERFACE

One of the questions that pop up regularly is: can't I just call lp_solve as a
procedure instead of writing and reading files? The answer is: no interface is
provided. I suggest using a pipe to lp_solve if you want to run it more than
once.

If you really want to try to create such an interface, here are some hints:

lp_solve uses a sparse matrix stored in a single array (Orig_mat). This matrix
contains the objective function and all constraints with more than 2
variables. Constraints with just one variable are called (upper or lower)
bounds, and are kept in special array's, Orig_upbo and Orig_lowbo. In
Orig_mat, the matrix is stored column after column, where the start indexes of
the columns are kept in the array Cend. The right-hand-side values of the
constraints are kept in the array Orig_rh. What the type of the constraint was
(<, >, =) in the original problem description is recorded in array Relat. The
names of the variables are stored in array Names. The total number of
constraints with more than 1 variable (rows in the matrix) is stored in Rows.
Variable Columns contains the total number of columns, Nonnuls the total
number of non-nul elements in Mat, and Sum is equal to Rows + Columns.

Filling of these variables is done by the call

  readinput(Cend, Orig_rh, Relat, Orig_lowbo, Orig_upbo, Orig_mat, Names);

in main.

By the way, all of this is documented in main.c, where all global variables
are declared.

Read read.c to see how I fill the datastructures.

See write.c to understand where the result is after solving.

Because of the relatively complex sparse matrix structure, I do not plan to
add a procedural interface to lp_solve myself. If anybody comes up with a
very general solution, please let me know.


KNOWN BUGS / PROBLEMS

The program does not store simple bounds on variables in the main matrix.
Therefore, simple problems like:

x + y;
x < 1;
y < 1;

define an empty matrix. This sometimes causes the program to crash. All
real-life problems do not have this property, fortunately.

FUTURE ENHANCEMENTS:

The program lacks at least the following two things:

- matrix optimization as preprocessing
- matrix normalization to increase numerical stability

Contributions are welcome.


AUTHOR:

For any comment on the sources, contact: michel@es.ele.tue.nl


INSTALL:

Look into file INSTALL for installation hints.


TESTING:

After a succesful build, run:

make test


