The LPSolve command solves a linear program (LP), which involves computing the minimum (or maximum) of a linear objective function subject to linear constraints.

Continuous, integer, mixed-integer and binary (or zero-one) LPs can be solved. Throughout this page, the term integer programming is used to represent all forms of integer programs.  Integer programs are specified using the assume, integervariables or binaryvariables options.  See the following Integer Programming Options section for more information.

This help page describes the use of the LPSolve command when the LP is specified in algebraic form.  A summary of this form is given in the Optimization/AlgebraicForm help page. LPSolve also recognizes the problem in Matrix form (see the LPSolve (Matrix Form) help page). Matrix form leads to more efficient computation, but is more complex.

LPSolve uses either an active-set or interior point method. See the method= option described below.

The first parameter obj is the objective function, which must be a linear algebraic expression.

The second parameter constr is optional and is a set or list of relations (of type `<=` or `=`), linear in the problem variables.  The problem variables are the indeterminates of type name found in obj and constr. They can also be specified using the variables option.

Bounds on one or more of the variables are given as additional arguments, each of the form $\mathrm{varname}=\mathrm{varrange}$ where varname is a variable name and $\mathrm{varrange}$ is its range.  The range endpoints can in general include values of type infinity. For the interior point method, however, the lower bounds must be finite. Non-negativity of the problem variables is not assumed by default, but can be specified with the assume = nonnegative option.

Maple returns the solution as a list containing the final minimum (or maximum) value and a point (the extremum).  If the output = solutionmodule option is provided, then a module is returned.  See the Optimization/Solution help page for more information.

If you only need a feasible point for the problem, use 0 as the first argument to LPSolve followed by constraints and/or bounds.

The Optimization[ImportMPS] command can be used to import MPS(X) data files.  This command returns a combined Matrix and Vector representation of the LP that can be sent to the LPSolve command using the Matrix form of input.  For more information, see the LPSolve (Matrix Form) help page.

The opts argument can contain one or more of the following options. These options apply to all forms of LPs accepted by the LPSolve command and are described in more detail in the Optimization/Options help page.  See the following Integer Programming Options and Continuous Programming Options sections for additional options that only apply to either integer or continuous programs.

assume = nonnegative -- Assume all variables are non-negative.

feasibilitytolerance = realcons(positive) -- For the active-set method, set the maximum absolute allowable constraint violation. For the interior point method, set the tolerance for the sum of the relative constraint violation and relative duality gap.

infinitebound = realcons(positive) -- For the active-set method, set any value of a variable greater than the infinitebound value to be equivalent to infinity during the computation. This option is ignored when using the interior point method.

initialpoint = set(equation) or list(equation) -- Use the provided initial point, which is a set or list of equations $\mathrm{varname}=\mathrm{value}$.

iterationlimit = posint -- Set the maximum number of iterations performed by the active-set or interior point algorithm.

maximize or maximize = truefalse -- Maximize the objective function when equal to true and minimize when equal to false.  The option 'maximize' is equivalent to maximize = true. The default is maximize = false.

output = solutionmodule -- Return a module as described in the Optimization/Solution help page.

useunits = true or false or a list.  See Optimization/Units.

variables = list(name) or set(name) -- Specify the problem variables.

The opts argument can contain one or more of the following options. These options only apply to integer programs and are described in more detail in the Optimization/Options help page.

assume = binary, integer or nonnegint -- Assume all variables take on binary (0 or 1), integer or non-negative integer values.

binaryvariables = list(name) or set(name) -- Specify the problem variables that only take the values 0 or 1.

depthlimit = posint -- Set the maximum depth of the branch-and-bound tree.

integertolerance = realcons(positive) -- Specify the maximum acceptable absolute violation in a value for it to be considered an integer.

integervariables = list(name) or set(name) -- Specify the problem variables that only take integer values.

nodelimit = nonnegint -- Set the maximum number of nodes searched in the branch-and-bound tree.  A value of 0 means all nodes are investigated.

The opts argument can contain one or more of the following options. These options only apply to continuous programs and are described in more detail in the Optimization/Options help page.

method = activeset, interiorpoint -- Specify whether to use the active-set or interior point algorithms. If neither method is requested, a heuristic is used to choose the method. In general, the interior point method will be more efficient for large, sparse problems. See the notes below for further details on each algorithm. If the input is given in Matrix form and the constraint matrices have the storage=sparse option set, the interior point method will be used. Otherwise, the heuristic is based on the number of variables, constraints, and the density of the constraint coefficient matrices.

For continuous programs, the LPSolve command uses one of two methods. The first method is an iterative active-set method implemented in a built-in library provided by the Numerical Algorithms Group (NAG). The second method is a sparse iterative interior point method developed by Dr. H. Wolkowicz at the University of Waterloo and colleagues, based on the following paper:

M. Gonzalez-Lima, H. Wei, H. Wolkowicz. "A stable primal-dual approach for linear programming under nondegeneracy assumptions." Computational Optimization and Applications. Vol. 44. (2009): 213-247.

The interior point method requires that all variables be bounded either above or below.

For both methods, an initial point can be provided using the initialpoint option. Otherwise, a default point is used.

Integer programs are solved using a branch-and-bound strategy in which a tree of nodes is created.  Each node corresponds to a continuous LP subproblem which is solved using the active-set method.

The computation is performed in floating-point. Therefore, all data provided must have type realcons and all returned solutions are floating-point, even if the problem is specified with exact values.  For more information about numeric computation in the Optimization package, see the Optimization/Computation help page. The only situation in which the output is not floating-point is when integer variables are specified. In this case, and only with algebraic and operator input, the final values for the integer variables are rounded to the nearest integer.

Although parameters constr and bd are optional, LPSolve returns an error if it does not detect at least one constraint (in the form of a general constraint), a bound, or the assume = nonnegative option.

LPSolve returns an error if the problem is infeasible.  If the problem appears to be unbounded, LPSolve issues a warning and returns the last computed result. This result may be meaningless.

Although the assume option is accepted, general assumptions are not supported by commands in the Optimization package.

$\mathrm{with}\left(\mathrm{Optimization}\right)\&colon;$

$\mathrm{LPSolve}\left(-4x-5y\&comma;\left\{0\le x\&comma;0\le y\&comma;x+2y\le 6\&comma;5x+4y\le 20\right\}\right)$

$\left[\mathrm{-19.}\&comma;\left[x=2.66666666666667\&comma;y=1.66666666666667\right]\right]$

$\mathrm{LPSolve}\left(-x-y\&comma;\left\{y\le 3x+\frac{1}{2}\&comma;y\le -5x+2\right\}\&comma;\mathrm{assume}=\mathrm{nonnegative}\right)$

$\left[\mathrm{-1.25000000000000}\&comma;\left[x=0.187500000000000\&comma;y=1.06250000000000\right]\right]$

$\mathrm{LPSolve}\left(-6x+4y+z\&comma;\left\{-x+3y\le 3\&comma;5x-10y\le 20\&comma;2z-3y=6\right\}\&comma;x=1..20\&comma;y=0..\mathrm{\infty }\right)$

$\left[\mathrm{-66.5000000000000}\&comma;\left[x=18.0000000000000\&comma;y=7.00000000000000\&comma;z=13.5000000000000\right]\right]$

$\mathrm{LPSolve}\left(-7x+2y\&comma;\left\{-x+3y\le 3\&comma;4x-12y\le 20\right\}\&comma;x=-5..5\&comma;y=0..\mathrm{\infty }\&comma;\mathrm{maximize}\right)$

$\left[21.\&comma;\left[x=\mathrm{-3.}\&comma;y=0.\right]\right]$

$\mathrm{LPSolve}\left(-5x-7y\&comma;\left\{7x+y\le 35\&comma;-x+3y\le 6\right\}\&comma;\mathrm{assume}=\mathrm{integer}\right)$

$\left[\mathrm{-41}\&comma;\left[x=4\&comma;y=3\right]\right]$

$\mathrm{LPSolve}\left(2x+5y\&comma;\left\{x-y\le 5\&comma;3x-y=1\right\}\&comma;\mathrm{assume}=\left\{\mathrm{integer}\&comma;\mathrm{nonnegative}\right\}\right)$

$\left[12\&comma;\left[x=1\&comma;y=2\right]\right]$

The method option was introduced in Maple 15.

For more information on Maple 15 changes, see Updates in Maple 15.

The Optimization[LPSolve] command was updated in Maple 2018.

The useunits option was introduced in Maple 2018.

For more information on Maple 2018 changes, see Updates in Maple 2018.