Developed at INRIA, Scilab has been developed for system control and signal processing applications. It is freely distributed in source code format.
Scilab is made of three distinct parts: an interpreter, libraries of functions (Scilab procedures) and libraries of Fortran and C routines. These routines (which, strictly speaking, do not belong to Scilab but are interactively called by the interpreter) are of independent interest and most of them are available through Netlib. A few of them have been slightly modified for better compatibility with Scilab's interpreter. A key feature of the Scilab syntax is its ability to handle matrices: basic matrix manipulations such as concatenation, extraction or transpose are immediately performed as well as basic operations such as addition or multiplication. Scilab also aims at handling more complex objects than numerical matrices. For instance, control people may want to manipulate rational or polynomial transfer matrices. This is done in Scilab by manipulating lists and typed lists which allows a natural symbolic representation of complicated mathematical objects such as transfer functions, linear systems or graphs.
Polynomials, polynomials matrices and transfer matrices are also defined and the syntax used for manipulating these matrices is identical to that used for manipulating constant vectors and matrices.
Scilab provides a variety of powerful primitives for the analysis of non-linear systems. Integration of explicit and implicit dynamic systems can be accomplished numerically. The scicos toolbox allows the graphic definition and simulation of complex interconnected hybrid systems.
Scilab has an open programming environment where the creation of functions and libraries of functions is completely in the hands of the user. Functions are recognized as data objects in Scilab and, thus, can be manipulated or created as other data objects. For example, functions can be defined inside Scilab and passed as input or output arguments of other functions.
In addition Scilab supports a character string data type which, in particular, allows the on-line creation of functions. Matrices of character strings are also manipulated with the same syntax as ordinary matrices.
Finally, Scilab is easily interfaced with Fortran or C subprograms. This allows use of standardized packages and libraries in the interpreted environment of Scilab.
The general philosophy of Scilab is to provide the following sort of computing environment:
We will not discuss the specifics of Scilab here but instead refer the reader to the Scilab website and documentation.
lpsolve is callable from Scilab via an external interface. As such, it looks like lpsolve is fully integrated with Scilab. Matrices can directly be transferred between Scilab 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 Scilab (especially for matrix support). So you have full control to the complete lpsolve functionality via the sclpsolve Scilab driver. If you find that this involves too much work to solve an lp model then you can also work via higher-level scripts that can make things a lot easier. See further in this article.
Compile and build sclpsolve:
----------------------------
1. Under Windows, the Microsoft Visual C/C++ compiler must be installed
and the environment variables must be active do that when a command prompt
is opened, the cl and nmake commands can be executed.
Under Unix/Linux, the standard c compiler is used.
2. Edit the file Path.incl and change pathnames as needed.
3. Start Scilab
4. Check under Scilab that the current directory is the lpsolve directory.
Use the Scilab pwd command to show the current directory.
With the chdir command, you can change the current directory.
This current directory must be lp_solve_5.1/extra/scilab/lpsolve
example: chdir('/lp_solve/lp_solve_5.1/extra/scilab/lpsolve')
5. To compile and build sclpsolve, enter the following command in Scilab:
-->exec builder.sce
This should be done once to build the sclpsolve driver and to produce
the file loader.sce.
Load the sclpsolve driver in the Scilab memory space:
-----------------------------------------------------
1. Under Windows, make sure that the lpsolve51.dll file is somewhere in the path
Under Unix/Linux, make sure that the liblpsolve51.so shared library is in /usr/lib
or /lib so that Unix can find it.
2. A precompiled library is provided for Windows (sclpsolve.dll).
For Unix/Linux, it is required that the sclpsolve driver is first build.
That must be done only once. So if you haven't taken the steps yet
to build the sclpsolve driver, then do this first as described at
the beginning of this file.
3. Start Scilab
4. Check under Scilab that the current directory is the lpsolve directory.
Use the Scilab pwd command to show the current directory.
With the chdir command, you can change the current directory.
This current directory must be lp_solve_5.1/extra/scilab/lpsolve
example: chdir('/lp_solve/lp_solve_5.1/extra/scilab/lpsolve')
5. Enter the following command in Scilab:
-->exec loader.sce
To make this possible, a driver program is needed: sclpsolve (sclpsolve.dll under Windows, sclpsolve.a under Unix/Linux). This driver must be put in a directory known to Scilab and Scilab can call the sclpsolve 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 sclpsolve driver doesn't have to be recompiled when an update of lpsolve is provided. For Windows, the lpsolve51.dll file must be somewhere in the path. For Unix, the lpsolve shared library (liblpsolve51.so) must be in the /usr/lib or /lib directory.
So note the difference between the Scilab lpsolve driver that is called sclpsolve and the lpsolve library that implements the API that is called lpsolve51.
There are also some Scilab script files (*.sce, *.sci) as a quick start.
The first thing that must be done, each time Scilab is restarted and you want to use lpsolve is load the sclpsolve driver into the Scilab workspace. This can be done via the script loader.sce. The following command must be used to load the driver:
exec loader.sce
It is assumed here that the current directory is the Scilab lpsolve directory (lp_solve_5.1/extra/scilab/lpsolve), but this is not a requirement. You can also provide the full path to the script files. The current directory can be shown via the pwd command in Scilab:
pwd
That is basically all you need to do. From now on, you can use the library. This until Scilab is restarted. Then this command must be given again to reload the library.
To make things easier, you can edit the file scilab.star with your favourite editor (or notepad/vi) in the Scilab directory and add above line at the end of this file. That will automatically load the lpsolve driver in memory when Scilab is started. So it will appear as if the sclpsolve command is then always available.
If you get an error similar to below, then probably the lpsolve library can not be found:
link failed for dll c:\lp_solve\lp_solve_5.1\extra\scilab\lpsolve\libs\sclpsolve.dll
addinter(liblpmex,'lpmex_gateway','sclpsolve')
!--error 236
link: the shared archive was not loaded
Under Windows, the lpsolve51.dll file must be in one of the directories specified by the PATH environment variable. This path can be seen in Scilab via the command getenv("PATH"). It is common to place dlls in the WINDOWS\system32 folder.
Under Unix/Linux, the liblpsolve51.so file must be in the directory /usr/lib or /lib.
To test if everything is installed correctly, enter sclpsolve() in the Scilab command window. If it gives the following, then everything is ok:
sclpsolve scilab Interface version 5.1.0.1
using lpsolve version 5.1.1.3
Usage: [ret1, ret2, ...] = sclpsolve('functionname', arg1, arg2, ...)
All this is developed and tested with Scilab versions 2.7 and 3.0 both under Windows and Linux (RedHat).
In the following text, --> before the Scilab commands is the Scilab prompt. Only the text after --> must be entered.
To call an lpsolve function, the following syntax must be used:
-->[ret1, ret2, ...] = sclpsolve('functionname', arg1, arg2, ...)
The return values are optional and depend on the function called. functionname must always be enclosed between (single or double) 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 Scilab specific functions. Most of the lpsolve API routines use or return an lprec structure. To make things more robust in Scilab, this structure is replaced by a handle. This is an incrementing number starting from 0 and the lprec structures are maintained internally by the sclpsolve 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 Scilab 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 Scilab, nothing must be dimensioned in advance. The sclpsolve driver takes care of dimensioning all return variables and they are always returned as return value of the call to sclpsolve. Never as argument to the routine. This can be a single value as for get_objective (although Scilab 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 Scilab:
-->help sclpsolve
(Note that you can execute this example by entering command per command as shown below or by just entering exec example1.sce. This will execute example1.sce.)
-->lp=sclpsolve('make_lp', 0, 4);
-->sclpsolve('set_verbose', lp, 3);
-->sclpsolve('set_obj_fn', lp, [1, 3, 6.24, 0.1]);
-->sclpsolve('add_constraint', lp, [0, 78.26, 0, 2.9], 2, 92.3);
-->sclpsolve('add_constraint', lp, [0.24, 0, 11.31, 0], 1, 14.8);
-->sclpsolve('add_constraint', lp, [12.68, 0, 0.08, 0.9], 2, 4);
-->sclpsolve('set_lowbo', lp, 1, 28.6);
-->sclpsolve('set_lowbo', lp, 4, 18);
-->sclpsolve('set_upbo', lp, 4, 48.98);
-->sclpsolve('set_col_name', lp, 1, 'COLONE');
-->sclpsolve('set_col_name', lp, 2, 'COLTWO');
-->sclpsolve('set_col_name', lp, 3, 'COLTHREE');
-->sclpsolve('set_col_name', lp, 4, 'COLFOUR');
-->sclpsolve('set_row_name', lp, 1, 'THISROW');
-->sclpsolve('set_row_name', lp, 2, 'THATROW');
-->sclpsolve('set_row_name', lp, 3, 'LASTROW');
-->sclpsolve('write_lp', lp, 'a.lp');
-->sclpsolve('get_mat', lp, 1, 2)
ans =
78.26
-->sclpsolve('solve', lp)
ans =
0.
-->sclpsolve('get_objective', lp)
ans =
31.782759
-->sclpsolve('get_variables', lp)
ans =
! 28.6 !
! 0. !
! 0. !
! 31.827586 !
-->sclpsolve('get_constraints', lp)
ans =
! 92.3 !
! 6.864 !
! 391.29283 !
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=sclpsolve('get_objective', lp)
obj =
31.782759
Or without echoing on screen:
-->obj=sclpsolve('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=sclpsolve('get_variables', lp);
-->b=sclpsolve('get_constraints', lp);
It is always possible to show the contents of a variable by just giving it as command:
-->x x = ! 28.6 ! ! 0. ! ! 0. ! ! 31.827586 !
Don't forget to free the handle and its associated memory when you are done:
-->sclpsolve('delete_lp', lp);
-->sclpsolve('add_constraint', lp, [0.24, 0, 11.31, 0], 1, 14.8);
In sparse matrix notation, this can be written:
-->sclpsolve('add_constraint', lp, mtlb_sparse(sparse([0.24, 0, 11.31, 0])), 1, 14.8);
Most of the time, variables are used to provide the data:
-->sclpsolve('add_constraint', lp, a1, 1, 14.8);
Where a1 is a dense matrix variable. A sparse matrix is then provided as follows:
-->sclpsolve('add_constraint', lp, mtlb_sparse(a1), 1, 14.8);
The sclpsolve driver sees all provided matrices as sparse matrices. sclpsolve also uses sparse matrices internally and data can be provided sparse via the ex routines. For example add_constraintex. The sclpsolve driver always uses the ex routines to provide the data to lpsolve. Even if you call from Scilab the routine names that would require a dense matrix (for example add_constraint), the sclpsolve 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 sclpsolve. 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, sclpsolve 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:
-->sclpsolve('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 Scilab 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 Scilab matrix.
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, Scilab 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.
It is noted however that this doesn't seem to work very well in Scilab. Scilab allows to return string sets, but when a string set is provided to an interface program, the following error occurs:
!--error 9999
Invalid string matrix (at most one column!)
!--error 999
SIGSTP: aborting current computation
This is not an error generated by the sclpsolve driver, but from the Scilab parser. Hopefully, this problem will be corrected in the future.
Because Scilab 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 sclpsolve Scilab 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 sclpsolve Scilab driver however also allows specifying a vector to set the integer
status of all variables at once. The API call is: return = sclpsolve('set_int', lp_handle, column, must_be_int). The
matrix version of this call is: return = sclpsolve('set_int', lp_handle, [must_be_int]).
The API call to return the integer status of a variable is: return = sclpsolve('is_int', lp_handle, column). The
matrix version of this call is: [is_int] = sclpsolve('is_int', lp_handle)
Also note the get_mat and set_mat routines. In Scilab 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 exec example2.sce.
This will execute example2.sce.)
-->lp=sclpsolve('make_lp', 0, 4);
-->sclpsolve('set_verbose', lp, 3);
-->sclpsolve('set_obj_fn', lp, [1, 3, 6.24, 0.1]);
-->sclpsolve('add_constraint', lp, [0, 78.26, 0, 2.9], 2, 92.3);
-->sclpsolve('add_constraint', lp, [0.24, 0, 11.31, 0], 1, 14.8);
-->sclpsolve('add_constraint', lp, [12.68, 0, 0.08, 0.9], 2, 4);
-->sclpsolve('set_lowbo', lp, [28.6, 0, 0, 18]);
-->sclpsolve('set_upbo', lp, [%inf, %inf, %inf, 48.98]);
-->// sclpsolve('set_col_name', lp, {'COLONE', 'COLTWO', 'COLTHREE', 'COLFOUR'}); // gives a Scilab error with most releases :-(
-->// sclpsolve('set_row_name', lp, {'THISROW', 'THATROW', 'LASTROW'}); // gives a Scilab error with most releases :-(
-->sclpsolve('write_lp', lp, 'a.lp');
-->sclpsolve('get_mat', lp)
ans =
! 0. 78.26 0. 2.9 !
! .24 0. 11.31 0. !
! 12.68 0. .08 .9 !
-->sclpsolve('solve', lp)
ans =
0.
-->sclpsolve('get_objective', lp)
ans =
31.782759
-->sclpsolve('get_variables', lp)
ans =
! 28.6 !
! 0. !
! 0. !
! 31.827586 !
-->sclpsolve('get_constraints', lp)
ans =
! 92.3 !
! 6.864 !
! 391.29283 !
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=sclpsolve('get_mat', lp);
-->X=sclpsolve('get_variables', lp);
-->B = A * X
B =
! 92.3 !
! 6.864 !
! 391.29283 !
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:
-->sclpsolve('get_constraints', lp)
ans =
! 92.3 !
! 6.864 !
! 391.29283 !
Exactly the same as the calculated B vector, as expected.
Also the value of the objective can be calculated in a same way:
-->C=sclpsolve('get_obj_fn', lp);
-->X=sclpsolve('get_variables', lp);
obj =
31.782759
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:
-->sclpsolve('get_objective', lp)
ans =
31.7828
Again exactly the same as the calculated obj value, as expected.
Scilab can execute a sequence of statements stored in diskfiles. Scilab has two kinds of these. The first kinds are ASCII files where Scilab commands are written in the same way as in the command window. These files normally have the extension .sce. These script files must be executed via the exec command. For example:
exec example1.sce
The second kinds are binary files. However the user enters the commands first in an ASCII file (normally with extention .sci) and then these are translated to binary files via the Scilab genlib command. The .sci files also may only contain Scilab commands. There are two advantages of using these. The first is that you don't have to use the exec command or provide the extension to execute them. So it is as if you execute a regular Scilab command. The second advantage is that they are somewhat faster.
The lpsolve distribution contains some sample .sce files that must be executed via exec and also some .sci high-level routines that can be executed without exec. They are already precompiled.
Contains the commands as shown in the first example of this article. Execute via exec example1.sce
Contains the commands as shown in the second example of this article. Execute via exec example2.sce
Contains the commands of a practical example. See further in this article.
Contains the commands of a practical example. See further in this article.
Contains the commands of a practical example. See further in this article.
Contains the commands of a practical example. See further in this article.
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 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])
x =
! 1. !
! 2. !
obj =
3.
Note that you can also provide sparse matrices to this function without having to use mtlb_sparse. The script is taking care of this.
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 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:
-->sclpsolve('solve', lp)
ans =
0.
-->sclpsolve('get_objective', lp)
ans =
3.
-->sclpsolve('get_variables', lp)
ans =
! 1. !
! 2. !
Don't forget to free the handle and its associated memory when you are done:
-->sclpsolve('delete_lp', lp);
Note that you can also provide sparse matrices to this function without having to use mtlb_sparse. The script is taking care of this.
Contains several examples to build and solve lp models. Execute via exec lpdemo.sce
Contains several examples to build and solve lp models. Also solves the lp_examples from the lp_solve distribution. Execute via exec ex.sce
We shall illustrate the method of linear programming by means of a simple example, giving a combination graphical/numerical solution, and then solve both a slightly as well as a substantially more complicated problem.
Suppose a farmer has 75 acres on which to plant two crops: wheat and barley. To produce these crops, it costs the farmer (for seed, fertilizer, etc.) $120 per acre for the wheat and $210 per acre for the barley. The farmer has $15000 available for expenses. But after the harvest, the farmer must store the crops while awaiting favourable market conditions. The farmer has storage space for 4000 bushels. Each acre yields an average of 110 bushels of wheat or 30 bushels of barley. If the net profit per bushel of wheat (after all expenses have been subtracted) is $1.30 and for barley is $2.00, how should the farmer plant the 75 acres to maximize profit?
We begin by formulating the problem mathematically. First we express the objective, that is the profit, and the constraints algebraically, then we graph them, and lastly we arrive at the solution by graphical inspection and a minor arithmetic calculation.
Let x denote the number of acres allotted to wheat and y the number of acres allotted to barley. Then the expression to be maximized, that is the profit, is clearly
P = (110)(1.30)x + (30)(2.00)y = 143x + 60y.
There are three constraint inequalities, specified by the limits on expenses, storage and acreage. They are respectively:
120x + 210y <= 15000
110x + 30y <= 4000
x + y <= 75
Strictly speaking there are two more constraint inequalities forced by the fact that the farmer cannot plant a negative number of acres, namely:
x >= 0, y >= 0.
Next we graph the regions specified by the constraints. The last two say that we only need to consider the first quadrant in the x-y plane. Here's a graph delineating the triangular region in the first quadrant determined by the first inequality.
-->clear -->X = 0.1:0.1:125; -->Y1 = (15000. - 120*X)/210; -->plot2d3(X, Y1)
Now let's put in the other two constraint inequalities.
-->clear
-->X = 0.1:0.05:38;
-->Y1 = (15000. - 120*X)/210;
-->Y2 = max((4000 - 110.*X)./30, 0);
-->Y3 = max(75 - X, 0.);
-->Ytop = min(min(Y1, Y2), Y3);
-->plot2d3(X, Ytop)
-->xtitle("Solution space")
The black area is the solution space that holds valid solutions. This means that any point in this area fulfils the constraints.
Now let's superimpose on top of this picture the objective function P.
-->X = 15:20:35;
-->plot2d(X, (6315.63 - 143.0 * X) / 60.0)
-->xtitle("Solution space and objective")
The line gives a picture of the objective function. All solutions that intersect with the black area are valid solutions, meaning that this result also fulfils the set constraints. The more the line goes to the right, the higher the objective value is. The optimal solution or best objective is a line that is still in the black area, but with an as large as possible value (as shown here).
It seems apparent that the maximum value of P will occur on the level curve (that is, level
line) that passes through the vertex of the polygon that lies near (22,53).
It is the intersection of x + y = 75 and 110*x + 30*y = 4000
This is a corner point of the diagram. This is not a coincidence. The simplex algorithm, which is used
by lp_solve, starts from a theorem that the optimal solution is such a corner point.
In fact we can compute the result:
-->x = [1, 1; 110, 30] \ [75; 4000] x = ! 21.875 ! ! 53.125 !
The acreage that results in the maximum profit is 21.875 for wheat and 53.125 for barley. In that case the profit is:
-->P = [143, 60] * x
P =
6315.625
That is, $6315.625.
Note that these command are in script example3.sce
Now, lp_solve comes into the picture to solve this linear programming problem more generally. After that we will use it to solve two more complicated problems involving more variables and constraints.
For this example, we use the higher-level script lp_maker to build the model and then some lp_solve API calls to retrieve the solution. Here is again the usage of 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 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.
Now let's formulate this model with lp_solve:
-->f = [143, 60];
-->A = [120, 210; 110, 30; 1, 1];
-->b = [15000, 4000, 75];
-->lp = lp_maker(f, A, b, [-1, -1, -1], [], [], [], 1, 0);
-->solvestat = sclpsolve("solve", lp)
solvestat =
0.
-->sclpsolve("get_objective", lp)
ans =
6315.625
-->sclpsolve("get_variables", lp)
ans =
! 21.875 !
! 53.125 !
-->sclpsolve("delete_lp", lp);
Note that these command are in script example4.oms
With the higher-level script lp_maker, we provide all data to lp_solve. lp_solve returns a handle (lp) to the created model. Then the API call 'solve' is used to calculate the optimal solution of the model. The value of the objective function is retrieved via the API call 'get_objective' and the values of the variables are retrieved via the API call 'get_variables'. At last, the model is removed from memory via a call to 'delete_lp'. Don't forget this to free all memory allocated by lp_solve.
The solution is the same answer we obtained before. Note that the non-negativity constraints are accounted implicitly because variables are by default non-negative in lp_solve.
Well, we could have done this problem by hand (as shown in the introduction) because it is very small and it
can be graphically presented.
Now suppose that the farmer is dealing with a third crop, say corn, and that the corresponding data is:
cost per acre $150.75 yield per acre 125 bushels profit per bushel $1.56
With three variables it is already a lot more difficult to show this model graphically. Adding more variables makes it even impossible because we can't imagine anymore how to represent this. We only have a practical understanding of 3 dimentions, but beyound that it is all very theorethical.
If we denote the number of acres allotted to corn by z, then the objective function becomes:
P = (110)(1.30)x + (30)(2.00)y + (125)(1.56) = 143x + 60y + 195z
And the constraint inequalities are:
120x + 210y + 150.75z <= 15000
110x + 30y + 125z <= 4000
x + y + z <= 75
x >= 0, y >= 0, z >= 0
The problem is solved with lp_solve as follows:
-->f = [143, 60, 195];
-->A = [120, 210, 150.75; 110, 30, 125; 1, 1, 1];
-->b = [15000, 4000, 75];
-->lp = lp_maker(f, A, b, [-1, -1, -1], [], [], [], 1, 0);
-->solvestat = sclpsolve("solve", lp)
solvestat =
0.
-->sclpsolve("get_objective", lp)
ans =
6986.8421
-->sclpsolve("get_variables", lp)
ans =
! 0. !
! 56.578947 !
! 18.421053 !
-->sclpsolve("delete_lp", lp);
Note that these command are in script example5.oms
So the farmer should ditch the wheat and plant 56.5789 acres of barley and 18.4211 acres of corn.
There is no practical limit on the number of variables and constraints that Scilab can handle. Certainly none that the relatively unsophisticated user will encounter. Indeed, in many true applications of the technique of linear programming, one needs to deal with many variables and constraints. The solution of such a problem by hand is not feasible, and software like Scilab is crucial to success. For example, in the farming problem with which we have been working, one could have more crops than two or three. Think agribusiness instead of family farmer. And one could have constraints that arise from other things beside expenses, storage and acreage limitations. For example:
Below is a sequence of commands that solves exactly such a problem. You should be able to recognize the objective expression and the constraints from the data that is entered. But as an aid, you might answer the following questions:
-->f = [110*1.3, 30*2.0, 125*1.56, 75*1.8, 95*.95, 100*2.25, 50*1.35];
-->A = [120, 210, 150.75, 115, 186, 140, 85; 110, 30, 125, 75, 95, 100, 50; 1, 1, 1, 1, 1, 1, 1; 1, -1, 0, 0, 0, 0, 0; 0, 0, 1, 0, -2, 0, 0; 0, 0, 0, -1, 0, -1, 1];
-->b = [55000, 40000, 400, 0, 0, 0];
-->lp = lp_maker(f, A, b, [-1, -1, -1, -1, -1, -1], [10, 10, 10, 10, 20, 20, 20], [100, %inf, 50, %inf, %inf, 250, %inf], [], 1, 0);
-->solvestat = sclpsolve("solve", lp)
solvestat =
0.
-->sclpsolve("get_objective", lp)
ans =
75398.043
-->sclpsolve("get_variables", lp)
ans =
! 10. !
! 10. !
! 40. !
! 45.652174 !
! 20. !
! 250. !
! 20. !
-->sclpsolve("delete_lp", lp);
Note that these command are in script example6.oms
Note that we have used in this formulation the vlb and vub arguments of lp_maker. This to set lower and upper bounds on variables. This could have been done via extra constraints, but it is more performant to set bounds on variables. Also note that %inf is used for variables that have no upper limit. This stands for Infinity.
Note that despite the complexity of the problem, lp_solve solves it almost instantaneously. It seems the farmer should bet the farm on crop number 6. We strongly suggest you alter the expense and/or the storage limit in the problem and see what effect that has on the answer.
Suppose we want to solve the following linear program using Scilab:
max 4x1 + 2x2 + x3
s. t. 2x1 + x2 <= 1
x1 + 2x3 <= 2
x1 + x2 + x3 = 1
x1 >= 0
x1 <= 1
x2 >= 0
x2 <= 1
x3 >= 0
x3 <= 2
Convert the LP into Scilab format we get:
f = [4, 2, 1]
A = [2, 1, 0; 1, 0, 2; 1, 1, 1]
b = [1, 2, 1]
Note that constraints on single variables are not put in the constraint matrix. lp_solve can set bounds on individual variables and this is more performant than creating additional constraints. These bounds are:
l = [ 0, 0, 0]
u = [ 1, 1, 2]
Now lets enter this in Scilab:
-->f = [4, 2, 1]; -->A = [2, 1, 0; 1, 0, 2; 1, 1, 1]; -->b = [1, 2, 1]; -->l = [ 0, 0, 0]; -->u = [ 1, 1, 2];
Now solve the linear program using Scilab: Type the commands
-->lp = lp_maker(f, A, b, [-1, -1, -1], l, u, [], 1, 0);
-->solvestat = sclpsolve("solve", lp)
solvestat =
0.
-->sclpsolve("get_objective", lp)
ans =
2.5
-->sclpsolve("get_variables", lp)
ans =
! 0.5 !
! 0. !
! 0.5 !
-->sclpsolve("delete_lp", lp)
What to do when some of the variables are missing ?
For example, suppose there are no lower bounds on the variables. In this case define l to be the empty set using the Scilab command:
-->l = [];
This has the same effect as before, because lp_solve has as default lower bound for variables 0.
But what if you want that variables may also become negative?
Then you can use -%inf as lower bounds:
-->l = [-%inf, -%inf, -%inf];
Solve this and you get a different result:
-->lp = lp_maker(f, A, b, [-1, -1, -1], l, u, [], 1, 0);
-->solvestat = sclpsolve("solve", lp)
solvestat =
0.
-->sclpsolve("get_objective", lp)
ans =
2.6666667
-->sclpsolve("get_variables", lp)
ans =
! 0.6666667 !
! - 0.3333333 !
! 0.6666667 !
-->sclpsolve("delete_lp", lp)
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.
Under Windows, the sclpsolve Scilab driver is a dll: sclpsolve.dll
Under Unix/Linux, the sclpsolve Scilab driver is a static library sclpsolve.a
The library is an interface to the lpsolve51 library that contains the implementation of lp_solve.
Under windows this is a dll lpsolve51.dll and under Unix/Linux it is a shared library liblpsolve51.so
They are distributed with the lp_solve package. See at the beginning of this article where these files must be installed.
The sclpsolve Scilab driver is just
a wrapper between Scilab and lp_solve to translate the input/output to/from Scilab and the lp_solve library.
The sclpsolve Scilab driver is written in C. To compile this code, under Windows the Microsoft C compiler is needed and under
Unix the standard compiler is used.
This compiler must be called from Scilab. To make the compilation process easier, a script can be used:
builder.sce
Before the compilation is started, it may be necessary to edit the file Path.incl. In this file it is specified where scilab is installed
and were lp_solve is installed. Change the paths as needed.
To make everything, just enter exec builder.sce and everything is build.
This compiles the source files to the needed libraries, compiles the sci scripts and makes the manuals. It also
generates a new loader.sce file to load the driver into the Scilab workspace.
This build process is the same under Windows and Unix/Linux. Note that builder.sce generates Makefiles that are then used to build the code. Don't edit the Makefiles since your changes will be lost when build.sce is executed again.
See also Using lpsolve from MATLAB, Using lpsolve from O-Matrix, Using lpsolve from Octave