Linear programming problems (where a multivariate linear function needs to be maximized or minimized subject to linear (in)equality constraints), as well as (mixed) integer programming problems, can be solved by using the function lpsolve. Problems can be entered directly (in symbolic or matrix form) or loaded from a file in LP or (gzipped) MPS format.
lpsolve accepts four arguments :
The return value is in the form [optimum,soln] where optimum is the minimum/maximum value of the objective function and soln is the list of coordinates corresponding to the point at which the optimal value is attained, i.e. the optimal solution. If there is no feasible solution, an empty list is returned. When the objective function is unbounded, optimum is returned as +infinity (for maximization problems) or infinity (for minimization problems). If an error is experienced while solving (terminating the process), undef is returned.
The given objective function is minimized by default. To maximize it, include the option lp_maximize=true or lp_maximize or simply maximize. Also note that all variables are, unless specified otherwise, assumed to be continuous and unrestricted in sign.
By default, lpsolve uses primal simplex method implementation to solve LP problems. For example, to solve the problem specified in (1), input :
Output :
Therefore, the minimum value of f(x,y,z)=2 x+y−z+4 is equal to −4 under the given constraints. The optimal value is attained at point (x,y,z)=(0,5,13) .
Constraints may also take the form expr=a..b for bounded linear expressions.
Input :
Output :
Use the assume=lp_nonnegative option to specify that all variables are nonnegative. It is easier than entering the nonnegativity constraints explicitly.
Input:
Output:
Bounds can be added separately for some variables. They should be entered after constraints.
Input :
Output :
Number of iterations can be limited by setting lp_iterationlimit to some positive integer. If maximum number of iterations is reached, the current feasible solution (not necessarily an optimal one) is returned.
lpsolve supports entering linear programming problems in matrix form, where obj is a vector of coefficients c and constr is a list [A,b,A_{eq},b_{eq}] such that objective function c^{T} x is to be minimized/maximized subject to constraints A x≤b and A_{eq} x=b_{eq} . If a problem does not contain equality constraints, parameters A_{eq} and b_{eq} may be omitted. For a problem that does not contain inequality constraints, empty lists must be entered in place of A and in place of b .
The parameter bd is entered as a list of two vectors b_{l} and b_{u} of the same length as the vector c such that b_{l}≤x≤b_{u} . These vectors may contain +infinity or infinity.
Input :
Output :
Input :
Output :
Input :
Output :
lpsolve allows restricting (some) variables to integer values. Such problems, called (mixed) integer programming problems, are solved by applying branch&bound method.
To solve pure integer programming problems, in which all variables are integers, use option assume=integer or assume=lp_integer.
Input :
Output :
Use option assume=lp_binary to specify that all variables are binary, i.e. the only allowed values are 0 and 1. These usually represent false and true, respectively, giving the variable a certain meaning in logical context.
Input :
Output :
To solve mixed integer problems, where some variables are integers and some are continuous, use option keywords lp_integervariables to specify integer variables and/or lp_binaryvariables to specify binary variables.
Input :
Output :
Use the assume=lp_nonnegint or assume=nonnegint option to get nonnegative integer values.
Input :
Output :
When specifying MIP problems in matrix form, lists corresponding to options lp_integervariables and lp_binaryvariables are populated with variable indices, like in the following example.
Input :
Output :
One can also specify a range of indices instead of a list when there is too much variables. Example : lp_binaryvariables=0..99 means that all variables x_{i} such that 0≤ i≤ 99 are binary.
Branch&bound algorithm by definition generates a binary tree of subproblems by branching on integer variables with fractional values. lpsolve features an implementation which stores only active nodes of branch&bound tree in a list, thus saving a lot of space. Also, since variable bounds are the only parameters that change during branch&bound algorithm, number of constraints does not rise with depth, which is the benefit of the upperbounding technique built in the simplex algorithm. Therefore a steady speed and minimal resource usage is always maintained, no matter how long the execution time is. This allows for solving problems that require tens or hundreds of thousands of nodes to be generated before finding an optimal solution.
There are several ways to force the branch&bound algorithm to stop prematurely when the execution takes too much time. One can set lp_timelimit to integer number which defines the maximum number of milliseconds allowed to find an optimal solution. Other ways are to set lp_nodelimit or lp_depthlimit to limit the number of nodes generated in branch&bound tree or its depth, respectively. Finally, one can set lp_gaptolerance to some positive value, say t>0 , which terminates the algorithm after finding an incumbent solution and proving that the corresponding objective value differs from optimum value for less than t· 100 % . It is done by monitoring the size of integrality gap, i.e. the difference between current incumbent objective value and the best objective value bound among active nodes.
If branch&bound algorithm terminates prematurely, a warning message indicating the cause is displayed. Incumbent solution, if any, is returned as the result, else the problem is declared to be infeasible.
At every iteration of branch&bound algorithm, a node must be selected for branching on some variable that has a fractional optimal value for the corresponding relaxed subproblem. There exist different methods for making such decisions, called branching strategies. Two types of branching strategies exist: node selection and variable selection strategy.
Node selection strategy can be set by using the lp_nodeselect option. Possible values are :
By default, lp_bestprojection strategy is used. Another sophisticated strategy is lp_hybrid : before an incumbent solution is found, solver uses lp_depthfirst strategy, “diving” into the tree as an incumbent solution is more likely to be located deeply. When an incumbent is found, solver switches to lp_breadthfirst strategy trying to close the integrality gap as quickly as possible.
Variable selection strategy can be set by using the lp_varselect option. Possible values are :
By default, lp_pseudocost strategy is used. However, since pseudocostbased choice cannot be made before all integer variables have been branched upon at least one time in each direction, lp_mostfractional strategy is used until that condition is fulfilled.
Using the right combination of branching strategies may significantly reduce the number of subproblems needed to be examined when solving a particular MIP problem. However, what is “right” varies from problem to problem. Default strategies are the most sophisticated (as they use the available data most extensively) and usually the most effective ones. But that is not always the case, as illustrated by the following example :
A= 
 , b= 
 , c= 
 . 
When using the default settings, about 24000 subproblems need to be examined before an optimal solution is found. When lp_nodeselect is set to lp_breadthfirst the solver needs to examine only about 20000 subproblems, but when set to lp_hybrid (a strategy which in general performs better) it examines about 111000 nodes in total.
Strong Gomory mixed integer cuts are generated at every node of the branch&bound tree and used to improve the objective value bound. After solving the relaxed subproblem with simplex method, at most one strong cut is generated and added to the subproblem which is subsequently reoptimized. Simplex reoptimizations are fast because they start with the last feasible basis, but applying cuts makes the simplex tableau larger, hence applying many of them may actually slow the computation down. To limit the number of cuts that can be applied to a subproblem, one can use lp_maxcuts option, setting it either to zero (which disables cut generation altogether) or to some positive integer. Also, one may set it to +infinity, which means that any number of cuts may be applied to any node. By default, lp_maxcuts equals to 5.
By typing lp_verbose=true or simply lp_verbose when specifying options for lpsolve, detailed messages are printed during and after solving a MIP problem. During branch&bound algorithm a status report in form
<n>: <m> nodes active, lower bound: <lb>[, integrality gap: <g>]
is displayed every 5 seconds, where n is the number of already examined subproblems. Also, a report is printed every time incumbent solution is found or updated, as well as when the solver switches to pseudocostbased branching. After the algorithm is finished, i.e. when an optimal solution is found, summary is displayed containing the total number of examined subproblems, the number of most nodes being active at the same time and the number of applied Gomory mixed integer cuts.
In the following example, two nonnegative integers x_{1} and x_{2} are found such that 1867 x_{1}+1913 x_{2}=3618894 and x_{1}+x_{2} is minimal. The solver shows all progress and summary messages.
Input :
Output :
Optimizing... Applying branch&bound method to find integer feasible solutions... 3937: Incumbent solution found Summary: * 3938 subproblem(s) examined * max. tree size: 1 nodes * 0 Gomory cut(s) applied
lpsolve provides, in addition to its own exact solver implementing primal simplex method with upperbounding technique, an interface to GLPK (GNU Linear Programming Kit) library which contains sophisticated LP/MIP solvers in floatingpoint arithmetic, designed to be very fast and to handle large problems. Choosing between the available solvers is done by setting lp_method option.
By default, lp_method is set to lp_simplex, which solves the problem using primal simplex method, but performing exact computation only when all problem coefficients are exact. If at least one of them is approximative (a floatingpoint number), GLPK solver is used instead (see below).
Setting lp_method to exact forces the solver to perform exact computation even when some coefficients are inexact (they are converted to rational equivalents before applying simplex method).
Specifying lp_method=float forces lpsolve to use floatingpoint solver. If a MIP problem is given, it is combined with branch&cut algorithm. GLPK simplex solver parameters can be controlled by setting lp_timelimit, lp_gaptolerance and lp_varselect options. If the latter is not set, Driebeek–Tomlin heuristic is used by default (see GLPK manual for details). If lp_maxcuts is greater than zero, GMI and MIR cut generation is enabled, else it is disabled. If the problem contains binary variables, cover and clique cut generation is enabled, else it is disabled. Finally, lp_verbose=true enables detailed messages.
Setting lp_method to lp_interiorpoint uses primaldual interiorpoint algorithm which is part of GLPK. The only parameter that can be controlled via options is the verbosity level.
For example, try to solve the following LP problem using the default settings.
subject to

Input :
Output :
If assume=nonnegint is used for the same problem, i.e. when x_{k}∈ℤ_{+} for k=1,2,3 , the following result is obtained by GLPK MIP solver :
The solution of the original problem can also be obtained with interiorpoint solver by including lp_method=lp_interiorpoint after assume=lp_nonnegative :
Linear (integer) programming problems can be loaded from MPS or CPLEX LP format files (these formats are described in GLPK manual, Appendices B and C). The file name string needs to be passed as obj parameter. If the file name has extension “lp”, CPLEX LP format is assumed, and if the extension is “mps” or “gz”, MPS or gzipped MPS format is assumed.
For example, assume that somefile.lp file is stored in directory /path/to/file contains the following lines of text :
Maximize obj: x1 + 2 x2 + 3 x3 + x4 Subject To c1:  x1 + x2 + x3 + 10 x4 <= 20 c2: x1  3 x2 + x3 <= 30 c3: x2  3.5 x4 = 0 Bounds 0 <= x1 <= 40 2 <= x4 <= 3 End
To find an optimal solution to linear program specified in the file, one just needs to input :
Output :
Reading problem data from '/path/to/file/somefile.lp'... 3 rows, 4 columns, 9 nonzeros 10 lines were read
Additional variable bounds and options may be provided alongside the file name. Note that the original constraints (those which are read from file) cannot be removed.
Input :
Output :
It is advisable to use only (capital) letters, digits and underscore when naming variables in a LP file, although the corresponding format allows many more characters. That is because these names are converted to Giac identifiers during the loading process.
Warning! Too large problems won’t be loaded. More precisely, if n_{v}· n_{c}>10^{5} , where n_{v} is the number of variables and n_{c} is the number of constraints, loading is aborted. Many MPS files available, for example, in the Netlib repository (http://www.netlib.org/), contain very large problems with thousands of variables and constraints. Trying to load them to Xcas without a safety limit could easily eat up huge amounts of available memory, probably freezing up the whole system. If a large LP problem needs to be solved, one may consider using GLPK standalone solver^{1}.