Using lpsolve from MATLAB

MATLAB?

MATLAB® is a high-performance language for technical computing. It integrates computation, visualization, and programming in an easy-to-use environment where problems and solutions are expressed in familiar mathematical notation. Typical uses include

MATLAB is an interactive system whose basic data element is an array that does not require dimensioning. This allows you to solve many technical computing problems, especially those with matrix and vector formulations, in a fraction of the time it would take to write a program in a scalar noninteractive language such as C or Fortran.

The name MATLAB stands for matrix laboratory. MATLAB was originally written to provide easy access to matrix software developed by the LINPACK and EISPACK projects. Today, MATLAB engines incorporate the LAPACK and BLAS libraries, embedding the state of the art in software for matrix computation.

MATLAB has evolved over a period of years with input from many users. In university environments, it is the standard instructional tool for introductory and advanced courses in mathematics, engineering, and science. In industry, MATLAB is the tool of choice for high-productivity research, development, and analysis.

MATLAB features a family of add-on application-specific solutions called toolboxes. Very important to most users of MATLAB, toolboxes allow you to learn and apply specialized technology. Toolboxes are comprehensive collections of MATLAB functions (M-files) that extend the MATLAB environment to solve particular classes of problems. Areas in which toolboxes are available include signal processing, control systems, neural networks, fuzzy logic, wavelets, simulation, and many others.

We will not discuss the specifics of MATLAB here but instead refer the reader to the MATLAB website and documentation.

MATLAB and lpsolve

lpsolve is callable from MATLAB via an external interface or MEX-function. As such, it looks like lpsolve is fully integrated with MATLAB. Matrices can directly be transferred between MATLAB and lpsolve in both directions. The complete interface is written in C so it has maximum performance. The whole lpsolve API is implemented with some extra's specific for MATLAB (especially for matrix support). So you have full control to the complete lpsolve functionality via the mxlpsolve MATLAB driver. If you find that this involves too much work to solve an lp model then you can also work via higher-level M-files that can make things a lot easier. See further in this article.

Installation

To make this possible, a driver program is needed: mxlpsolve (mxlpsolve.dll under Windows). This driver must be put in a directory known to MATLAB (specified via File, Set Path or via the MATLAB path command) and MATLAB can call the mxlpsolve solver.

This driver calls lpsolve via the lpsolve shared library (lpsolve51.dll under Windows and liblpsolve51.so under Unix/Linux). This has the advantage that the mxlpsolve driver doesn't have to be recompiled when an update of lpsolve is provided. The shared library must be somewhere in the Windows path.

So note the difference between the MATLAB lpsolve driver that is called mxlpsolve and the lpsolve library that implements the API that is called lpsolve51.

There are also some MATLAB script files (.m) as a quick start.

To test if everything is installed correctly, enter mxlpsolve in the MATLAB command window. If it gives the following, then everything is ok:

mxlpsolve MATLAB Interface version 5.1.0.0
using lpsolve version 5.1.1.2

Usage: [ret1, ret2, ...] = mxlpsolve('functionname', arg1, arg2, ...)

However, if you get the following:

mxlpsolve driver not found !!!
Check if mxlpsolve.dll is on your system and in a directory known to MATLAB.
Press enter to see the paths where MATLAB looks for the driver.

Then MATLAB can find the mxlpsolve.m file, but not the mxlpsolve.dll file. This dll should be in the same directory as the .m file.

If you get the following:

??? Undefined function or variable 'mxlpsolve'.

Then MATLAB cannot find the mxlpsolve.* files. Enter path in the command line to see the MATLAB search path for its files. You can modify this path via File, Set Path. Specify the path where the mxlpsolve.* files are located on your system.

If you get the following:

??? Failed to initialise lpsolve library.

Error in ==> ...\mxlpsolve.dll

Then MATLAB can find the mxlpsolve driver program, but the driver program cannot find the lpsolve library that contains the lpsolve implementation. This library is called lpsolve51.dll and should be on your system in a directory that in the PATH environment variable. This path can be shown via the following command in MATLAB: !PATH

The lpsolve51.dll files must be in one of these specified directories. It is common to place this in the WINDOWS\system32 folder.

Note that it may also be necessary to restart MATLAB after having put the files in the specified directory. It was noted that MATLAB sometimes doesn't see the newly added files in folders until it is restarted.

All this is developed and tested with MATLAB version 6.0.0.88 Release 12.

Solve an lp model from MATLAB via mxlpsolve

In the following text, >> before the MATLAB commands is the MATLAB prompt. Only the text after >> must be entered.

To call an lpsolve function, the following syntax must be used:

>> [ret1, ret2, ...] = mxlpsolve('functionname', arg1, arg2, ...)

The return values are optional and depend on the function called. functionname must always be enclosed between single quotes to make it alphanumerical and it is case sensitive. The number and type of arguments depend on the function called. Some functions even have a variable number of arguments and a different behaviour occurs depending on the type of the argument. functionname can be (almost) any of the lpsolve API routines (see lp_solve API reference) plus some extra MATLAB specific functions. Most of the lpsolve API routines use or return an lprec structure. To make things more robust in MATLAB, this structure is replaced by a handle. This is an incrementing number starting from 0 and the lprec structures are maintained internally by the mxlpsolve driver. However you will see not much (if any) difference in the use of it.

Almost all callable functions can be found in the lp_solve API reference. Some are exactly as described in the reference guide, others have a slightly different syntax to make maximum use of the MATLAB functionality. For example make_lp is used identical as described. But get_variables is slightly different. In the API reference, this function has two arguments. The first the lp handle and the second the resulting variables and this array must already be dimensioned. When lpsolve is used from MATLAB, nothing must be dimensioned in advance. The mxlpsolve driver takes care of dimensioning all return variables and they are always returned as return value of the call to mxlpsolve. Never as argument to the routine. This can be a single value as for get_objective (although MATLAB stores this in a 1x1 matrix) or a matrix or vector as in get_variables. In this case, get_variables returns a 4x1 matrix (vector) with the result of the 4 variables of the lp model.

Note that you can get an overview of the available functionnames and their arguments by entering the following in MATLAB:

>> help mxlpsolve

An example

(Note that you can execute this example by entering command per command as shown below or by just entering example1. This will execute example1.m. You can see its contents by entering type example1.m)

>> lp=mxlpsolve('make_lp', 0, 4);
>> mxlpsolve('set_verbose', lp, 3);
>> mxlpsolve('set_obj_fn', lp, [1, 3, 6.24, 0.1]);
>> mxlpsolve('add_constraint', lp, [0, 78.26, 0, 2.9], 2, 92.3);
>> mxlpsolve('add_constraint', lp, [0.24, 0, 11.31, 0], 1, 14.8);
>> mxlpsolve('add_constraint', lp, [12.68, 0, 0.08, 0.9], 2, 4);
>> mxlpsolve('set_lowbo', lp, 1, 28.6);
>> mxlpsolve('set_lowbo', lp, 4, 18);
>> mxlpsolve('set_upbo', lp, 4, 48.98);
>> mxlpsolve('set_col_name', lp, 1, 'COLONE');
>> mxlpsolve('set_col_name', lp, 2, 'COLTWO');
>> mxlpsolve('set_col_name', lp, 3, 'COLTHREE');
>> mxlpsolve('set_col_name', lp, 4, 'COLFOUR');
>> mxlpsolve('set_row_name', lp, 1, 'THISROW');
>> mxlpsolve('set_row_name', lp, 2, 'THATROW');
>> mxlpsolve('set_row_name', lp, 3, 'LASTROW');
>> mxlpsolve('write_lp', lp, 'a.lp');
>> mxlpsolve('get_mat', lp, 1, 2)

ans =

   78.2600

>> mxlpsolve('solve', lp)

ans =

     0

>> mxlpsolve('get_objective', lp)

ans =

   31.7828

>> mxlpsolve('get_variables', lp)

ans =

   28.6000
         0
         0
   31.8276

>> mxlpsolve('get_constraints', lp)

ans =

   92.3000
    6.8640
  391.2928

>> mxlpsolve('delete_lp', lp);

Note that there are some commands that return an answer. To see the answer, the command was not terminated with a semicolon (;). If the semicolon is put at the end of a command, the answer is not shown. However it is also possible to write the answer in a variable. For example: 

>> obj=mxlpsolve('get_objective', lp)

obj =

   31.7828

Or without echoing on screen:

>> obj=mxlpsolve('get_objective', lp);

The last command will only write the result in variable obj without showing anything on screen. get_variables and get_constraints return a vector with the result. This can also be put in a variable:

>> x=mxlpsolve('get_variables', lp);
>> b=mxlpsolve('get_constraints', lp);

It is always possible to show the contents of a variable by just giving it as command:

>> x

x =
  28.6000
        0
        0
  31.8276

Matrices

In MATLAB, all numerical data is stored in matrices; even a scalar variable. MATLAB also supports complex numbers (a + b * i with i=SQRT(-1)). mxlpsolve can only work with real numbers. MATLAB also supports sparse matrices. Sparse matrices are matrices where only the non-zero elements are provided and stored. This results in both less storage and faster calculation if there are a sufficient number of zero values in the matrix and there usually are. The mxlpsolve driver supports both dense and sparse matrices and their use is totally transparent to the user. Everywhere a matrix can be provided, it can be dense or sparse. In the above example all matrices were dense. For example: 
>> mxlpsolve('add_constraint', lp, [0.24, 0, 11.31, 0], 1, 14.8);

In sparse matrix notation, this can be written:

>> mxlpsolve('add_constraint', lp, sparse([0.24, 0, 11.31, 0]), 1, 14.8);

Most of the time, variables are used to provide the data:

>> mxlpsolve('add_constraint', lp, a1, 1, 14.8);

Where a1 is a matrix variable that can be dense or sparse.

The mxlpsolve driver sees all provided matrices as sparse matrices. mxlpsolve also uses sparse matrices internally and data can be provided sparse via the ex routines. For example add_constraintex. The mxlpsolve driver always uses the ex routines to provide the data to lpsolve. Even if you call from MATLAB the routine names that would require a dense matrix (for example add_constraint), the mxlpsolve driver will always call the sparse version of the routine (for example add_constraintex). This results in the most performing behaviour. Note that if a dense matrix is provided, the dimension must exactly match the dimension that is expected by mxlpsolve. Matrices with too few or too much elements gives an 'invalid vector.' error. Sparse matrices can off course provide less elements (the non provided elements are seen as zero). However if too many elements are provided or an element with a too large index, again an 'invalid vector.' error is raised.

Most of the time, mxlpsolve needs vectors (rows or columns). In all situations, it doesn't matter if the vectors are row or column vectors. The driver accepts them both. For example:

>> mxlpsolve('add_constraint', lp, [0.24; 0; 11.31; 0], 1, 14.8);

Which is a column vector, but it is also accepted.

An important final note. Several lp_solve API routines accept a vector where the first element (element 0) is not used. Other lp_solve API calls do use the first element. In the MATLAB interface, there is never an unused element in the matrices. So if the lp_solve API specifies that the first element is not used, then this element is not in the MATLAB matrix.

Sets

All numerical data is stored in matrices. Alphanumerical data, however, is more difficult to store in matrices. Matrices require that each element has the same size (length) and that is difficult and unpractical for alphanumerical data. In a limited number of lpsolve routines, alphanumerical data is required or returned and in some also multiple elements. An example is set_col_name. For this, MATLAB sets are used. To specify a set of alphanumerical elements, the following notation is used: { 'element1', 'element2', ... }. Note the { and } symbols instead of [ and ] that are used with matrices.

Maximum usage of matrices/sets with mxlpsolve

Because MATLAB is all about matrices, all lpsolve API routines that need a column or row number to get/set information for that column/row are extended in the mxlpsolve MATLAB driver to also work with matrices. For example set_int in the API can only set the integer status for one column. If the status for several integer variables must be set, then set_int must be called multiple times. The mxlpsolve MATLAB driver however also allows specifying a vector to set the integer status of all variables at once. The API call is: return = mxlpsolve('set_int', lp_handle, column, must_be_int). The matrix version of this call is: return = mxlpsolve('set_int', lp_handle, [must_be_int]). The API call to return the integer status of a variable is: return = mxlpsolve('is_int', lp_handle, column). The matrix version of this call is: [is_int] = mxlpsolve('is_int', lp_handle)
Also note the get_mat and set_mat routines. In MATLAB these are extended to return/set the complete constraint matrix. See following example.

Above example can thus also be done as follows:
(Note that you can execute this example by entering command per command as shown below or by just entering example2. This will execute example2.m. You can see its contents by entering type example2.m)

>> lp=mxlpsolve('make_lp', 0, 4);
>> mxlpsolve('set_verbose', lp, 3);
>> mxlpsolve('set_obj_fn', lp, [1, 3, 6.24, 0.1]);
>> mxlpsolve('add_constraint', lp, [0, 78.26, 0, 2.9], 2, 92.3);
>> mxlpsolve('add_constraint', lp, [0.24, 0, 11.31, 0], 1, 14.8);
>> mxlpsolve('add_constraint', lp, [12.68, 0, 0.08, 0.9], 2, 4);
>> mxlpsolve('set_lowbo', lp, [28.6, 0, 0, 18]);
>> mxlpsolve('set_upbo', lp, [Inf, Inf, Inf, 48.98]);
>> mxlpsolve('set_col_name', lp, {'COLONE', 'COLTWO', 'COLTHREE', 'COLFOUR'});
>> mxlpsolve('set_row_name', lp, {'THISROW', 'THATROW', 'LASTROW'});
>> mxlpsolve('write_lp', lp, 'a.lp');
>> mxlpsolve('get_mat', lp)

ans =

         0   78.2600         0    2.9000
    0.2400         0   11.3100         0
   12.6800         0    0.0800    0.9000

>> mxlpsolve('solve', lp)

ans =

     0

>> mxlpsolve('get_objective', lp)

ans =

   31.7828

>> mxlpsolve('get_variables', lp)

ans =

   28.6000
         0
         0
   31.8276

>> mxlpsolve('get_constraints', lp)

ans =

   92.3000
    6.8640
  391.2928

Note the usage of Inf in set_upbo. This stands for 'infinity'. Meaning an infinite upper bound. It is also possible to use -Inf to express minus infinity. This can for example be used to create a free variable.

To show the full power of the matrices, let's now do some matrix calculations to check the solution. It works further on above example:

>> A=mxlpsolve('get_mat', lp);
>> X=mxlpsolve('get_variables', lp);
>> B = A * X

B =
   92.3000
    6.8640
  391.2928

So what we have done here is calculate the values of the constraints (RHS) by multiplying the constraint matrix with the solution vector. Now take a look at the values of the constraints that lpsolve has found:

>> mxlpsolve('get_constraints', lp)

ans =

   92.3000
    6.8640
  391.2928

Exactly the same as the calculated B vector, as expected.

Also the value of the objective can be calculated in a same way:

>> C=mxlpsolve('get_obj_fn', lp);
>> X=mxlpsolve('get_variables', lp);
>> obj = C * X

obj =

   31.7828

So what we have done here is calculate the value of the objective by multiplying the objective vector with the solution vector. Now take a look at the value of the objective that lpsolve has found:

>> mxlpsolve('get_objective', lp)

ans =

   31.7828

Again exactly the same as the calculated obj value, as expected.

M-files

MATLAB can execute a sequence of statements stored in diskfiles. Such files are called "M-files" because they must have the file type of ".m" as the last part of their filename (extension). Much of your work with MATLAB will be in creating and refining M-files. M-files are usually created using your local editor.

M-files can be compared with batch files or scripts. You can put MATLAB commands in them and execute them at any time. The M-file is executed like any other command, by entering its name (without the .m extension).

The mxlpsolve MATLAB distribution contains some example M-files to demonstrate this.

To see the contents of such a file, enter the command 'type filename'. You can also edit these files with your favourite text editor (or notepad).

example1.m

Contains the commands as shown in the first example of this article.

example2.m

Contains the commands as shown in the second example of this article.

lp_solve.m

This script uses the API to create a higher-level function called lp_solve. This function accepts as arguments some matrices and options to create and solve an lp model. See the beginning of the file or type help lp_solve or just lp_solve to see its usage:

 LP_SOLVE  Solves mixed integer linear programming problems.

   SYNOPSIS: [obj,x,duals] = lp_solve(f,a,b,e,vlb,vub,xint,scalemode,keep)

      solves the MILP problem

              max v = f'*x
                a*x <> b
                  vlb <= x <= vub
                  x(int) are integer

   ARGUMENTS: The first four arguments are required:

            f: n vector of coefficients for a linear objective function.
            a: m by n matrix representing linear constraints.
            b: m vector of right sides for the inequality constraints.
            e: m vector that determines the sense of the inequalities:
                      e(i) = -1  ==> Less Than
                      e(i) =  0  ==> Equals
                      e(i) =  1  ==> Greater Than
          vlb: n vector of lower bounds. If empty or omitted,
               then the lower bounds are set to zero.
          vub: n vector of upper bounds. May be omitted or empty.
         xint: vector of integer variables. May be omitted or empty.
    scalemode: scale flag. Off when 0 or omitted.
         keep: Flag for keeping the lp problem after it's been solved.
               If omitted, the lp will be deleted when solved.

   OUTPUT: A nonempty output is returned if a solution is found:

          obj: Optimal value of the objective function.
            x: Optimal value of the decision variables.
        duals: solution of the dual problem.

Example of usage. To create and solve following lp-model:

max: -x1 + 2 x2;
C1: 2x1 + x2 < 5;
-4 x1 + 4 x2 <5;

int x2,x1;

The following command can be used:

>> [obj, x]=lp_solve([-1, 2], [2, 1; -4, 4], [5, 5], [-1, -1], [], [], [1, 2])

obj =

     3


x =

     1
     2

lp_maker.m

This script is analog to the lp_solve script and also uses the API to create a higher-level function called lp_maker. This function accepts as arguments some matrices and options to create an lp model. Note that this scripts only creates a model and returns a handle. See the beginning of the file or type help lp_maker or just lp_maker to see its usage:

>> help lp_maker

 LP_MAKER  Makes mixed integer linear programming problems.

   SYNOPSIS: lp_handle = lp_maker(f,a,b,e,vlb,vub,xint,scalemode,setminim)
      make the MILP problem
        max v = f'*x
          a*x <> b
            x >= vlb >= 0
            x <= vub
            x(int) are integer

   ARGUMENTS: The first four arguments are required:
            f: n vector of coefficients for a linear objective function.
            a: m by n sparse matrix representing linear constraints.
            b: m vector of right sides for the inequality constraints.
            e: m vector that determines the sense of the inequalities:
                      e(i) < 0  ==> Less Than
                      e(i) = 0  ==> Equals
                      e(i) > 0  ==> Greater Than
          vlb: n vector of non-negative lower bounds. If empty or omitted,
               then the lower bounds are set to zero.
          vub: n vector of upper bounds. May be omitted or empty.
         xint: vector of integer variables. May be omitted or empty.
    scalemode: scale flag. Off when 0 or omitted.
     setminim: Set maximum lp when this flag equals 0 or omitted.

   OUTPUT: lp_handle is an integer handle to the lp created.

Example of usage. To create following lp-model:

max: -x1 + 2 x2;
C1: 2x1 + x2 < 5;
-4 x1 + 4 x2 <5;

int x2,x1;

The following command can be used:

>> lp=lp_maker([-1, 2], [2, 1; -4, 4], [5, 5], [-1, -1], [], [], [1, 2])

lp =

     0

To solve the model and get the solution:

>> mxlpsolve('solve', lp)

ans =

     0

>> mxlpsolve('get_objective', lp)

ans =

     3

>> mxlpsolve('get_variables', lp)

ans =

     1
     2

Don't forget to free the handle and its associated memory when you are done:

>> mxlpsolve('delete_lp', lp);

lpdemo.m

Contains several examples to build and solve lp models.

ex.m

Contains several examples to build and solve lp models. Also solves the lp_examples from the lp_solve distribution.

Overview of API routines

Note again that the MATLAB command 'help mxlpsolve' gives an overview of all functions that can be called via mxlpsolve with their arguments and return values.

Extra MATLAB routines

These routines are not part of the lpsolve API, but are added for backwards compatibility. Most of them exist in the lpsolve API with another name.

Compile the mxlpsolve driver

Windows

Under Windows, the mxlpsolve MATLAB driver is a dll: mxlpsolve.dll
This dll is an interface to the lpsolve51.dll lpsolve dll that contains the implementation of lp_solve. lpsolve51.dll is distributed with the lp_solve package. The mxlpsolve MATLAB driver dll (mxlpsolve.dll) is just a wrapper between MATLAB and lp_solve to translate the input/output to/from MATLAB and the lp_solve library.

The mxlpsolve MATLAB driver is written in C. To compile this code, the MATLAB compiler is needed (mex). This compiler must be called from MATLAB. To make the compilation process easier, a makefile can be used: MakefileWin.m
Enter 'help MakefileWin' from the MATLAB command window to see a list of options.
It may be necessary to edit this file first to change the path where lp_solve is installed. Change at the beginning lpsolvepath.
To make for release, just enter MakefileWin and everything is build.
This compiles two source files: lpsolve.c and hash.c
Then these are linked with the library lp_explicit.lib to generate the mxlpsolve.dll file. The lp_explicit.lib file is a wrapper library between the lp_solve dll and the compiled application. This wrapper is needed because the lp_solve dll uses __stdcall calling convention. There seems to be a problem in MATLAB to call __stdcall functions directly (unexpected crashes). The lp_explicit library uses __cdecl calling convention and this then calls the lp_solve dll which uses __stdcall calling convention. Looks a bit complex, but it works without any problem.
The optional arguments to MakefileWin are used for development. The first argument allows specifying a filename so that only this file is build. For example hash.c should only be compiled once while developing. So specifying 'lpsolve.c' as first argument will only compile this file and then link everything. This makes the build process a bit faster. The second argument is by default 0. When set to 1, then extra argument checking is done and while executing, some debug information is printed. Should only be used for debugging purposes. When released, this parameter should be 0. The third argument is by default 1. When set to 0, the makefile will not ask to press enter to start building.

There appears to be another way to compile MATLAB mex files with gcc for Windows. This is not tested. See Compiling Matlab mex files with gcc for Windows.

Unix/Linux

Untested! Should be something like.

<MATLAB-DIR>/bin/mex -I../../.. -L../../../lpsolve51 -O3 lpsolve.c hash.c -llpsolve51 -lm

Note: A full path to mex has been given in case teTeX is installed and so there is another mex:

$ which mex
/usr/local/teTeX/bin/mex

If anyone has made this work, please let know to Peter Notebaert to update this document.

See also Using lpsolve from Scilab, Using lpsolve from O-Matrix