.. function:: linprog(c, A, sense, b, l, u, solver)
Solves the linear programming problem:
\min_{x}\, &c^Tx\\ s.t. &a_i^Tx \text{ sense}_i \, b_i \forall\,\, i\\ &l \leq x \leq u\\
where:
c
is the objective vector, always in the sense of minimizationA
is the constraint matrix, with rows a_i (viewed as column-oriented vectors)sense
is a vector of constraint sense characters'<'
,'='
, and'>'
b
is the right-hand side vectorl
is the vector of lower bounds on the variablesu
is the vector of upper bounds on the variables, andsolver
is an optional parameter specifying the desired solver, see :ref:`choosing solvers <choosing-solvers>`. If this parameter is not provided, the default solver is used.
A scalar is accepted for the b
, sense
, l
, and u
arguments, in which case its value is replicated. The values -Inf
and Inf
are interpreted to mean that there is no corresponding lower or upper bound.
Note
Linear programming solvers extensively exploit the sparsity of the constraint matrix A
. While both dense and sparse matrices are accepted, for large-scale problems sparse matrices should be provided if permitted by the problem structure.
A shortened version is defined as:
linprog(c, A, sense, b, solver) = linprog(c, A, sense, b, 0, Inf, solver)
The linprog
function returns an instance of the type:
type LinprogSolution status objval sol attrs end
where status
is a termination status symbol, one of :Optimal
, :Infeasible
, :Unbounded
, :UserLimit
(iteration limit or timeout), :Error
(and maybe others).
If status
is :Optimal
, the other members have the following values:
objval
-- optimal objective valuesol
-- primal solution vectorattrs
-- a dictionary that may contain other relevant attributes such as:redcost
-- dual multipliers for active variable bounds (zero if inactive)lambda
-- dual multipliers for active linear constraints (equalities are always active)
If status
is :Infeasible
, the attrs
member will contain an infeasibilityray
if available; similarly for :Unbounded
problems, attrs
will contain an unboundedray
if available.
For example, we can solve the two-dimensional problem (see test/linprog.jl
):
\min_{x,y}\, &-x\\ s.t. &2x + y \leq 1.5\\ & x \geq 0, y \geq 0
by:
using MathProgBase sol = linprog([-1,0],[2 1],'<',1.5) if sol.status == :Optimal println("Optimal objective value is $(sol.objval)") println("Optimal solution vector is: [$(sol.sol[1]), $(sol.sol[2])]") else println("Error: solution status $(sol.status)") end
.. function:: linprog(c, A, lb, ub, l, u, solver)
This variant allows one to specify two-sided linear constraints (also known as range constraints) to solve the linear programming problem:
\min_{x}\, &c^Tx\\ s.t. &lb \leq Ax \leq ub\\ &l \leq x \leq u\\
where:
c
is the objective vector, always in the sense of minimizationA
is the constraint matrixlb
is the vector of row lower boundsub
is the vector of row upper boundsl
is the vector of lower bounds on the variablesu
is the vector of upper bounds on the variables, andsolver
is an optional parameter specifying the desired solver, see :ref:`choosing solvers <choosing-solvers>`. If this parameter is not provided, the default solver is used.
A scalar is accepted for the l
, u
, lb
, and ub
arguments, in which case its value is replicated. The values -Inf
and Inf
are interpreted to mean that there is no corresponding lower or upper bound. Equality constraints are specified by setting the row lower and upper bounds to the same value.
A shortened version is defined as:
linprog(c, A, lb, ub, solver) = linprog(c, A, lb, ub, 0, Inf, solver)