The Euler Mathematical Toolbox is a powerful, versatile, and open source software for numerical and symbolic computations written and maintained by R. Grothmann from the University of Eichstätt. Euler is similar to MATLAB, but uses an own style and an own syntax. Euler supports symbolic mathematics using the open algebra system Maxima.
The most recent version of Euler runs in Windows (98/XP/Vista), or under Linux in Wine. The native Linux version is currently outdated.
We will not discuss the specifics of Euler here but instead refer the reader to the Euler website.
lpsolve is callable from Euler via a dynamic linked DLL function. As such, it looks like lpsolve is fully integrated with Euler. Matrices can directly be transferred between Euler 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 Euler (especially for matrix support). So you have full control to the complete lpsolve functionality via the eulpsolve Euler driver. If you find that this involves too much work to solve an lp model then you can also work via higher-level Euler files that can make things a lot easier. See further in this article.
Compile and build eulpsolve:
----------------------------
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.
2. Go to directory lp_solve_5.5\extra\Euler
3. Edit cvc.bat and change the path of the Eulerpath environment variable to your path.
4. To compile and build eulpsolve, enter the following command:
cvc
Load the eulpsolve driver in the Euler memory space:
-------------------------------------------------------
1. Under Windows, make sure that the lpsolve55.dll file is somewhere in the path
(archive lp_solve_5.5.2.5_dev.zip)
2. A precompiled library is provided for Windows (eulpsolve.dll).
3. Start Euler
4. Enter the following command in Euler:
>dll("<path>/eulpsolve.dll", "eulpsolve", -1)
Or if this fails (because you use version an Euler version 7.0 or older):
>dll("<path>/eulpsolve.dll", "eulpsolve", 0)
>dll("<path>/eulpsolve.dll", "eulpsolve", 1);
>dll("<path>/eulpsolve.dll", "eulpsolve", 2);
>dll("<path>/eulpsolve.dll", "eulpsolve", 3);
>dll("<path>/eulpsolve.dll", "eulpsolve", 4);
>dll("<path>/eulpsolve.dll", "eulpsolve", 5);
>dll("<path>/eulpsolve.dll", "eulpsolve", 6);
>dll("<path>/eulpsolve.dll", "eulpsolve", 7);
For <path> use the path where the eulpsolve.dll is located.
These commands can be put in a file, for example loadlpsolve.en, with a regular editor like notepad.
They can then be opened as a notebook in Euler and executed.
Euler is ideally suited to handle linear programming problems. These are problems in which you have a quantity, depending linearly on several variables, that you want to maximize or minimize subject to several constraints that are expressed as linear inequalities in the same variables. If the number of variables and the number of constraints are small, then there are numerous mathematical techniques for solving a linear programming problem. Indeed these techniques are often taught in high school or university level courses in finite mathematics. But sometimes these numbers are high, or even if low, the constants in the linear inequalities or the object expression for the quantity to be optimized may be numerically complicated in which case a software package like Euler is required to effect a solution.
To make this possible, a driver program is needed: eulpsolve (eulpsolve.dll under Windows). This driver must be loaded in Euler and Euler can call the eulpsolve solver.
This driver calls lpsolve via the lpsolve shared library (lpsolve55.dll under Windows). This has the advantage that the eulpsolve 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 Euler lpsolve driver that is called eulpsolve and the lpsolve library that implements the API that is called lpsolve55.
There are also some Euler notebooks (.en) as a quick start.
The first thing that must be done, each time Euler is restarted and you want to use lpsolve is load the eulpsolve driver into the Euler workspace. This is done via the dll command. Suppose that eulpsolve.dll is installed in c:\Program Files\Euler\dll, then the following command must be used to load the driver:
>dll("c:/Program Files/Euler/dll/eulpsolve.dll", "eulpsolve", -1)
Note that this command is only accepted from Euler version 7.1 or newer. On older Euler versions, -1 is not accepted on the third argument. There is however a work-around for this. You can then use the following commands (all together):
>dll("c:/Program Files/Euler/dll/eulpsolve.dll", "eulpsolve", 0)
>dll("c:/Program Files/Euler/dll/eulpsolve.dll", "eulpsolve", 1);
>dll("c:/Program Files/Euler/dll/eulpsolve.dll", "eulpsolve", 2);
>dll("c:/Program Files/Euler/dll/eulpsolve.dll", "eulpsolve", 3);
>dll("c:/Program Files/Euler/dll/eulpsolve.dll", "eulpsolve", 4);
>dll("c:/Program Files/Euler/dll/eulpsolve.dll", "eulpsolve", 5);
>dll("c:/Program Files/Euler/dll/eulpsolve.dll", "eulpsolve", 6);
>dll("c:/Program Files/Euler/dll/eulpsolve.dll", "eulpsolve", 7);
These commands can be put in a file, for example loadlpsolve.en or loadlpsolve.e, with a regular editor like notepad. The .en file can then be opened as a notebook in Euler and executed. The .e file can be loaded and executed via the load statement.
That is basically all you need to do. From now on, you can use the library. This until Euler is restarted. Then this command must be given again to reload the library.
To test if everything is installed correctly, enter eulpsolve(); in the Euler command prompt. If it gives the following, then everything is ok:
>eulpsolve();
eulpsolve Euler Interface version 5.5.0.7
using lpsolve version 5.5.2.5
Usage: [ret1, ret2, ...] = eulpsolve("functionname", arg1, arg2, ...)
However, if you get a message box with the following:
eulpsolve no function or variable, or wrong argument number!
Then either the dll command that was previous given was unsuccessful (or not given at all) or something was misspelled after the ,
Check the dll command again. If it gives a message box with the following message:
--------------------------- euler.exe - Unable To Locate Component --------------------------- This application has failed to start because lpsolve55.dll was not found. Re-installing the application may fix this problem. --------------------------- OK ---------------------------
And then in Euler:
Could not open the DLL library!
Could not find the function!
error in :
dll("<path>/eulpsolve.dll", "eulpsolve", 0)
Then Euler can find the eulpsolve driver program, but the driver program cannot find the lpsolve library that contains the lpsolve implementation. This library is called lpsolve55.dll and should be on your system in a directory that in the PATH environment variable. This path can be shown via the command line command PATH.
The lpsolve55.dll files must be in one of these specified directories. It is common to place this in the WINDOWS\system32 folder.
If the message in Euler is shown without a message box of a missing lpsolve55.dll file then eulpsolve.dll cannot be found.
All this is developed and tested with Euler versions 7.0 and 7.1 beta. This is the minimum supported release. Older releases are unsupported. Only from version 7.1 on, it is possible to print something in the Euler window from the external library. So on older versions, when something must be printed, it will be shown in a messagebox. If you are working with a lower version than 7.1 it is best that the verbose level of the set_verbose API call is less than or equal to 3. Otherwise too much messageboxes will be given and it is unpractical to work with this. If you need this verbose level, then use at least version 7.1
In the following text, > before the Euler commands is the Euler command line. Only the text after > must be entered.
To call an lpsolve function, the following syntax must be used:
>{ret1, ret2, ...} = eulpsolve("functionname", arg1, arg2, ...)
The return values are optional and depend on the function called. functionname must always be enclosed between 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 Euler specific functions. Most of the lpsolve API routines use or return an lprec structure. To make things more robust in Euler, this structure is replaced by a handle or the model name. The lprec structures are maintained internally by the lpsolve driver. The handle is an incrementing number starting from 0. Starting from driver version 5.5.0.2, it is also possible to use the model name instead of the handle. This can of course only be done if a name is given to the model. This is done via lpsolve routine set_lp_name or by specifying the model name in routine read_lp. See Using model name instead of handle.
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 Euler 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 Euler, nothing must be dimensioned in advance. The eulpsolve driver takes care of dimensioning all return variables and they are always returned as return value of the call to eulpsolve. Never as argument to the routine. This can be a single value as for get_objective (although Euler 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 execute this example by entering command per command as shown below or by opening and executing notebook example1.en)
>lp=eulpsolve("make_lp", 0, 4);
>eulpsolve("set_verbose", lp, 3);
>eulpsolve("set_obj_fn", lp, [1, 3, 6.24, 0.1]);
>eulpsolve("add_constraint", lp, [0, 78.26, 0, 2.9], 2, 92.3);
>eulpsolve("add_constraint", lp, [0.24, 0, 11.31, 0], 1, 14.8);
>eulpsolve("add_constraint", lp, [12.68, 0, 0.08, 0.9], 2, 4);
>eulpsolve("set_lowbo", lp, 1, 28.6);
>eulpsolve("set_lowbo", lp, 4, 18);
>eulpsolve("set_upbo", lp, 4, 48.98);
>eulpsolve("set_col_name", lp, 1, "COLONE");
>eulpsolve("set_col_name", lp, 2, "COLTWO");
>eulpsolve("set_col_name", lp, 3, "COLTHREE");
>eulpsolve("set_col_name", lp, 4, "COLFOUR");
>eulpsolve("set_row_name", lp, 1, "THISROW");
>eulpsolve("set_row_name", lp, 2, "THATROW");
>eulpsolve("set_row_name", lp, 3, "LASTROW");
>eulpsolve("write_lp", lp, "a.lp");
>eulpsolve("get_mat", lp, 1, 2)
78.26
>eulpsolve("solve", lp)
0
>eulpsolve("get_objective", lp)
31.78275862069
>eulpsolve("get_variables", lp)
28.6
0
0
31.8275862069
>eulpsolve("get_constraints", lp)
92.3
6.864
391.2928275862
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=eulpsolve("get_objective", lp)
31.78275862069
Or:
>obj=eulpsolve("get_objective", lp);
Both will write the result in variable obj. Without the semicolon, the result is also shown on screen. get_variables and get_constraints return a vector with the result. This can also be put in a variable:
>x=eulpsolve("get_variables", lp);
>b=eulpsolve("get_constraints", lp);
It is always possible to show the contents of a variable by just giving it as command:
>x
28.6
0
0
31.8275862069
Don't forget to free the handle and its associated memory when you are done:
>eulpsolve("delete_lp", lp);
Note that for larger and/or complex models, solving time can be long. If this must be interrupt then the ESC key can be pressed. Euler shows this also in the status bar. lp_solve checks regularly if this key is pressed and if so, solve is interrupted. If verbose level is set then this is also shown on screen. Anyway, the return status will indicate that solve was aborted.
>lp=eulpsolve("make_lp", 0, 4);
>eulpsolve("set_lp_name", lp, "mymodel");
>eulpsolve("set_verbose", "mymodel", 3);
>eulpsolve("set_obj_fn", "mymodel", [1, 3, 6.24, 0.1]);
>eulpsolve("add_constraint", "mymodel", [0, 78.26, 0, 2.9], 2, 92.3);
>eulpsolve("add_constraint", "mymodel", [0.24, 0, 11.31, 0], 1, 14.8);
>eulpsolve("add_constraint", "mymodel", [12.68, 0, 0.08, 0.9], 2, 4);
>eulpsolve("set_lowbo", "mymodel", 1, 28.6);
>eulpsolve("set_lowbo", "mymodel", 4, 18);
>eulpsolve("set_upbo", "mymodel", 4, 48.98);
>eulpsolve("set_col_name", "mymodel", 1, "COLONE");
>eulpsolve("set_col_name", "mymodel", 2, "COLTWO");
>eulpsolve("set_col_name", "mymodel", 3, "COLTHREE");
>eulpsolve("set_col_name", "mymodel", 4, "COLFOUR");
>eulpsolve("set_row_name", "mymodel", 1, "THISROW");
>eulpsolve("set_row_name", "mymodel", 2, "THATROW");
>eulpsolve("set_row_name", "mymodel", 3, "LASTROW");
>eulpsolve("write_lp", "mymodel", "a.lp");
>eulpsolve("get_mat", "mymodel", 1, 2)
78.26
>eulpsolve("solve", "mymodel")
0
>eulpsolve("get_objective", "mymodel")
31.78275862069
>eulpsolve("get_variables", "mymodel")
28.6
0
0
31.8275862069
>eulpsolve("get_constraints", "mymodel")
92.3
6.864
391.2928275862
So everywhere a handle is needed, you can also use the model name. You can even mix the two methods.
There is also a specific Euler routine to get the handle from the model name: get_handle.
For example:
>eulpsolve("get_handle", "mymodel")
0
Don't forget to free the handle and its associated memory when you are done:
>eulpsolve("delete_lp", "mymodel");
In the next part of this documentation, the handle is used. But if you name the model, the name could thus also be used.
>eulpsolve("add_constraint", lp, [0.24, 0, 11.31, 0], 1, 14.8);
Most of the time, variables are used to provide the data:
>eulpsolve("add_constraint", lp, a1, 1, 14.8);
Where a1 is a matrix variable.
Matrices with too few or too much elements gives an 'invalid vector.' error.
Most of the time, eulpsolve 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:
>eulpsolve("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 Euler 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 Euler matrix.
Because Euler 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 eulpsolve Euler 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 eulpsolve Euler driver however also allows specifying a vector to set the integer
status of all variables at once. The API call is: return = eulpsolve("set_int", lp, column, must_be_int). The
matrix version of this call is: return = eulpsolve("set_int", lp, [must_be_int]).
The API call to return the integer status of a variable is: return = eulpsolve("is_int", lp, column). The
matrix version of this call is: [is_int] = eulpsolve("is_int", lp)
Also note the get_mat and set_mat routines. In Euler 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 opening and executing notebook example2.en)
>lp=eulpsolve("make_lp", 0, 4);
>eulpsolve("set_verbose", lp, 3);
>eulpsolve("set_obj_fn", lp, [1, 3, 6.24, 0.1]);
>eulpsolve("add_constraint", lp, [0, 78.26, 0, 2.9], 2, 92.3);
>eulpsolve("add_constraint", lp, [0.24, 0, 11.31, 0], 1, 14.8);
>eulpsolve("add_constraint", lp, [12.68, 0, 0.08, 0.9], 2, 4);
>eulpsolve("set_lowbo", lp, [28.6, 0, 0, 18]);
>eulpsolve("set_upbo", lp, [1.0e30, 1.0e30, 1.0e30, 48.98]);
>eulpsolve("set_col_name", lp, 1, "COLONE");
>eulpsolve("set_col_name", lp, 2, "COLTWO");
>eulpsolve("set_col_name", lp, 3, "COLTHREE");
>eulpsolve("set_col_name", lp, 4, "COLFOUR");
>eulpsolve("set_row_name", lp, 1, "THISROW");
>eulpsolve("set_row_name", lp, 2, "THATROW");
>eulpsolve("set_row_name", lp, 3, "LASTROW");
>eulpsolve("write_lp", lp, "a.lp");
>eulpsolve("get_mat", lp)
0 78.26 0 2.9
0.24 0 11.31 0
12.68 0 0.08 0.9
>eulpsolve("solve", lp)
0
>eulpsolve("get_objective", lp)
31.78275862069
>eulpsolve("get_variables", lp)
28.6
0
0
31.8275862069
>eulpsolve("get_constraints", lp)
92.3
6.864
391.2928275862
Note the usage of 1.0e30 in set_upbo. This stands for "infinity". Meaning an infinite upper bound. It is also possible to use -1.0e30 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=eulpsolve("get_mat", lp);
>X=eulpsolve("get_variables", lp);
>B = A . X
92.3
6.864
391.2928275862
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:
>eulpsolve("get_constraints", lp)
92.3
6.864
391.2928275862
Exactly the same as the calculated B vector, as expected.
Also the value of the objective can be calculated in a same way:
>C=eulpsolve("get_obj_fn", lp);
>X=eulpsolve("get_variables", lp);
>obj = C . X
31.78275862069
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:
>eulpsolve("get_objective", lp)
31.78275862069
Again exactly the same as the calculated obj value, as expected.
>lp=eulpsolve("make_lp", 0, 4);
>eulpsolve("set_verbose", lp, 3);
>eulpsolve("add_constraint", lp, [0, 78.26, 0, 2.9], 2, 92.3);
>eulpsolve("add_constraint", lp, [0.24, 0, 11.31, 0], 1, 14.8);
>eulpsolve("add_constraint", lp, [12.68, 0, 0.08, 0.9], 2, 4);
Note the 3rd parameter on set_verbose and the 4th on add_constraint. These are lp_solve constants. One could define all the possible constants in Euler and then use them in the calls, but that has several disadvantages. First there stays the possibility to provide a constant that is not intended for that particular call. Another issue is that calls that return a constant are still returning it numerical.
Both issues can now be handled by string constants. The above code can be done as following with string constants:
>lp=eulpsolve("make_lp", 0, 4);
>eulpsolve("set_verbose", lp, "IMPORTANT");
>eulpsolve("add_constraint", lp, [0, 78.26, 0, 2.9], "GE", 92.3);
>eulpsolve("add_constraint", lp, [0.24, 0, 11.31, 0], "LE", 14.8);
>eulpsolve("add_constraint", lp, [12.68, 0, 0.08, 0.9], "GE", 4);
This is not only more readable, there is much lesser chance that mistakes are being made. The calling routine knows which constants are possible and only allows these. So unknown constants or constants that are intended for other calls are not accepted. For example:
>eulpsolve("set_verbose", lp, "blabla");
eulpsolve returned an error:
BLABLA: Unknown.
>eulpsolve("set_verbose", lp, "GE");
eulpsolve returned an error:
GE: Not allowed here.
Note the difference between the two error messages. The first says that the constant is not known, the second that the constant cannot be used at that place.
Constants are case insensitive. Internally they are always translated to upper case. Also when returned they will always be in upper case.
The constant names are the ones as specified in the documentation of each API routine. There are only 3 exceptions, extensions actually. "LE", "GE" and "EQ" in add_constraint and is_constr_type can also be "<", "<=", ">", ">=", "=". When returned however, "GE", "LE", "EQ" will be used.
Some constants can be a combination of multiple constants. For example set_scaling:
>eulpsolve("set_scaling", lp, 3+128);
With the string version of constants this can be done as following:
>eulpsolve("set_scaling", lp, "SCALE_MEAN|SCALE_INTEGERS");
| is the OR operator used to combine multiple constants. There may optinally be spaces before and after the |.
Not all OR combinations are legal. For example in set_scaling, a choice must be made between SCALE_EXTREME, SCALE_RANGE, SCALE_MEAN, SCALE_GEOMETRIC or SCALE_CURTISREID. They may not be combined with each other. This is also tested:
>eulpsolve("set_scaling", lp, "SCALE_MEAN|SCALE_RANGE");
eulpsolve returned an error:
SCALE_RANGE cannot be combined with SCALE_MEAN
Everywhere constants must be provided, numeric or string values may be provided. The routine automatically interpretes them.
Returning constants is a different story. The user must let lp_solve know how to return it. Numerical or as string. The default is numerical:
>eulpsolve("get_scaling", lp)
131
To let lp_solve return a constant as string, a call to a new function must be made: return_constants
>eulpsolve("return_constants", 1);
From now on, all returned constants are returned as string:
>eulpsolve("get_scaling", lp)
SCALE_MEAN|SCALE_INTEGERS
This for all routines until return_constants is again called with 0:
>eulpsolve("return_constants", 0);
The (new) current setting of return_constants is always returned by the call. Even when set:
>eulpsolve("return_constants", 1)
1
To get the value without setting it, don't provide the second argument:
>eulpsolve("return_constants")
1
In the next part of this documentation, return_constants is the default, 0, so all constants are returned numerical and provided constants are also numerical. This to keep the documentation as compatible as possible with older versions. But don't let you hold that back to use string constants in your code.
Euler can execute a sequence of statements stored in files. There are two types. Notebooks and Euler files.
Notebooks contains a number of Euler statements that are stored in a file. They should have the extension *.en and are first loaded in the text window of Euler and then executed. There are some notebook examples with the distribution of lpsolve.
Euler files. If you want to develop longer and more complicated programs, it becomes useful to put all function definitions and all commands into external Euler files. These files should have the extension *.e, and can be loaded into Euler with the load command. Files in the current directory will be found using the name alone. The current directory is the directory, where the current notebook is loaded from or saved to. Otherwise, use the full path the file, or include the directory of the file into the Euler path. Euler files often contain support functions (subroutines) that can be used in your code.
You can also edit these files with your favourite text editor (or notepad).
Loads the eulpsolve driver in Euler. Also loads Euler files lpsolve.e and lpmaker.e. See further for their usage.
To execute and also see which commands are executed in the debug window, use following commands:
File, Open notebook... Open loadlpsolve.en File, Run all Commands in this Notebook
Contains the commands as shown in the first example of this article.
Contains the commands as shown in the second example of 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.
Contains the commands of a practical example. See further in this article.
This Euler file uses the API to create a higher-level function called lpsolve. This function accepts as arguments some matrices and options to create and solve an lp model. See the beginning of the file or enter help lpsolve to see its usage:
>load "lpsolve" >help lpsolve
LPSOLVE Solves mixed integer linear programming problems.
SYNOPSIS: {obj,x,duals} = lpsolve(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:
>load "lpsolve"
>{obj, x}=lpsolve([-1, 2], [2, 1; -4, 4], [5, 5], [-1, -1], [], [], [1, 2]);
>obj
3
>x
1
2
This Euler file is analog to the lpsolve Euler file and also uses the API to create a higher-level function called lpmaker. This function accepts as arguments some matrices and options to create an lp model. Note that this Euler file only creates a model and returns a handle. See the beginning of the file or enter help lpmaker to see its usage:
>load "lpmaker" >help lpmaker
LPMAKER Makes mixed integer linear programming problems.
SYNOPSIS: lp_handle = lpmaker(f,a,b,e,vlb,vub,xint,scalemode,setminim)
make 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) < 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:
>load "lpmaker"
>lp=lpmaker([-1, 2], [2, 1; -4, 4], [5, 5], [-1, -1], [], [], [1, 2])
0
To solve the model and get the solution:
>eulpsolve("solve", lp)
0
>eulpsolve("get_objective", lp)
3
>eulpsolve("get_variables", lp)
1
2
Don't forget to free the handle and its associated memory when you are done:
>eulpsolve("delete_lp", lp);
Contains several examples to build and solve lp models.
Contains several examples to build and solve lp models. Also solves the lp_examples from the lp_solve distribution.
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.
>X = 0.1:0.05:125; >Y1 = (15000. - 120*X)/210; >plot2d(X,Y1,bar=1); >insimg;
Now let's put in the other two constraint inequalities.
>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); >plot2d(X,Ytop,bar=1); >insimg;
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 a contour plot of the objective function P.
>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);
>plot2d(X,Ytop,bar=1);
>n=(1000:1000:9000)';
>plot2d("(n-143*x)/60", add=1, color=2);
>insimg;
The red lines give 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 lines go 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.
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]
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
6315.625
That is, $6315.625.
Note that these command are in notebook example3.en
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 Euler file lpmaker to build the model and then some lp_solve API calls to retrieve the solution. Here is again the usage of lpmaker:
LPMAKER Makes mixed integer linear programming problems.
SYNOPSIS: lp_handle = lpmaker(f,a,b,e,vlb,vub,xint,scalemode,setminim)
make 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) < 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 = lpmaker(f, A, b, [-1, -1, -1], [], [], [], 1, 0);
>solvestat = eulpsolve("solve", lp);
>eulpsolve("get_objective", lp)
6315.625
>eulpsolve("get_variables", lp)
21.875
53.125
>eulpsolve("delete_lp", lp);
Note that these command are in notebook example4.en
With the higher-level Euler file lpmaker, 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 = lpmaker(f, A, b, [-1, -1, -1], [], [], [], 1, 0);
>solvestat = eulpsolve("solve", lp);
>eulpsolve("get_objective", lp)
6986.842105263
>eulpsolve("get_variables", lp)
0
56.57894736842
18.42105263158
>eulpsolve("delete_lp", lp);
Note that these command are in notebook example5.en
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 Euler 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 Euler 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 = lpmaker(f, A, b, [-1,-1,-1,-1,-1,-1],[10,10,10,10,20,20,20],[100,1.0e30,50,1.0e30,1.0e30,250,1.0e30],[],1,0);
>solvestat = eulpsolve("solve", lp);
>eulpsolve("get_objective", lp)
75398.04347826
>eulpsolve("get_variables", lp)
10
10
40
45.65217391304
20
250
20
>eulpsolve("delete_lp", lp);
Note that these command are in notebook example6.en
Note that we have used in this formulation the vlb and vub arguments of lpmaker. 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 Euler:
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 Euler 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 Euler:
>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 Euler: Type the commands
>lp = lpmaker(f, A, b, [-1, -1, -1], l, u, [], 1, 0);
>solvestat = eulpsolve("solve", lp);
>eulpsolve("get_objective", lp)
2.5
>eulpsolve("get_variables", lp)
0.5
0
0.5
>eulpsolve("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 Euler 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 -1.0e30 as lower bounds:
>l = [-1.0e30, -1.0e30, -1.0e30];
Solve this and you get a different result:
>lp = lpmaker(f, A, b, [-1, -1, -1], l, u, [], 1, 0);
>solvestat = eulpsolve("solve", lp);
>eulpsolve("get_objective", lp)
2.666666666667
>eulpsolve("get_variables", lp)
0.6666666666667
-0.3333333333333
0.6666666666667
>eulpsolve("delete_lp", lp);
Note that everwhere where lp is used as argument that this can be a handle (lp_handle) or the models name.
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 eulpsolve Euler driver is a dll: eulpsolve.dll
Under Unix/Linux, the eulpsolve Euler driver is a shared library.: eulpsolve.so
This driver is an interface to the lpsolve library lpsolve55.dll/liblpsolve55.so that contains the implementation of lp_solve.
lpsolve55.dll/liblpsolve55.so is distributed with the lp_solve package (archive lp_solve_5.5.2.5_dev.zip/lp_solve_5.5.2.5_dev.tar.gz).
The eulpsolve Euler driver is just a wrapper between Euler and lp_solve to translate the input/output to/from Euler and the lp_solve library.
The eulpsolve Euler driver is written in C. To compile this code, under Windows the Microsoft visual C compiler is needed and under Unix/Linux the standard cc compiler.
The needed commands are in a batch file/script.
Under Windows it is called cvc.bat, under Unix/Linux ccc.
In a command prompt/shell, go to the lpsolve Euler directory and enter cvc.bat/sh ccc
and the compilation is done. The result is eulpsolve.dll/eulpsolve.so.
See also Using lpsolve from MATLAB, Using lpsolve from O-Matrix, Using lpsolve from Sysquake, Using lpsolve from Scilab, Using lpsolve from Octave, Using lpsolve from FreeMat, Using lpsolve from Python, Using lpsolve from Sage, Using lpsolve from PHP, Using lpsolve from R, Using lpsolve from Microsoft Solver Foundation