naginterfaces.library.opt.lp_​solve

naginterfaces.library.opt.lp_solve(bl, bu, x, comm, a=None, cvec=None, istate=None, io_manager=None)

lp_solve solves general linear programming problems. It is not intended for large sparse problems.

Note: this function uses optional algorithmic parameters, see also: lp_option_file(), lp_option_string(), nlp1_init().

For full information please refer to the NAG Library document for e04mf

https://support.nag.com/numeric/nl/nagdoc_30.3/flhtml/e04/e04mff.html

Parameters

blfloat, array-like, shape $(n+\text{nclin})$

$bl$ must contain the lower bounds for all the constraints

bufloat, array-like, shape $(n+\text{nclin})$

$bu$ must contain the upper bounds for all the constraints

xfloat, array-like, shape $\left(n\right)$

An initial estimate of the solution.

commdict, communication object, modified in place

Communication structure.

This argument must have been initialized by a prior call to nlp1_init().

aNone or float, array-like, shape $(\text{nclin},:)$, optional

Note: the required extent for this argument in dimension 2 is determined as follows: if $\text{nclin}>0$: $n$; if $\text{nclin}=0$: $1$; otherwise: $0$.

The $\text{i}$th row of $a$ must contain the coefficients of the $\text{i}$th general linear constraint, for $\text{i}=1,2,\dots ,m_L$.

cvecNone or float, array-like, shape $\left(n\right)$, optional

The coefficients of the objective function when the problem is of type LP.

If the problem is of type FP, $cvec$ is not referenced.

istateNone or int, array-like, shape $(n+\text{nclin})$, optional

Need not be set if the (default) option ‘Cold Start’ is used.

If the option ‘Warm Start’ has been chosen, $istate$ specifies the desired status of the constraints at the start of the feasibility phase.

More precisely, the first $n$ elements of $istate$ refer to the upper and lower bounds on the variables, and the next $m_L$ elements refer to the general linear constraints (if any).

Possible values for $istate[j-1]$ are as follows:

$istate[j-1]$	Meaning
0	The corresponding constraint should not be in the initial working set.
1	The constraint should be in the initial working set at its lower bound.
2	The constraint should be in the initial working set at its upper bound.
3	The constraint should be in the initial working set as an equality. This value must not be specified unless $bl[j-1]=bu[j-1]$.

The values $-2$, $-1$ and $4$ are also acceptable but will be reset to zero by the function.

If lp_solve has been called previously with the same values of $\text{n}$ and $\text{nclin}$, $istate$ already contains satisfactory information. (See also the description of the option ‘Warm Start’.) The function also adjusts (if necessary) the values supplied in $x$ to be consistent with $istate$.

io_managerFileObjManager, optional

Manager for I/O in this routine.

Returns

istateint, ndarray, shape $(n+\text{nclin})$

The status of the constraints in the working set at the point returned in $x$. The significance of each possible value of $istate[j-1]$ is as follows:

$istate[j-1]$	Meaning
$-2$	The constraint violates its lower bound by more than the feasibility tolerance.
$-1$	The constraint violates its upper bound by more than the feasibility tolerance.
$0$	The constraint is satisfied to within the feasibility tolerance, but is not in the working set.
$1$	This inequality constraint is included in the working set at its lower bound.
$2$	This inequality constraint is included in the working set at its upper bound.
$3$	This constraint is included in the working set as an equality. This value of $istate$ can occur only when $bl[j-1]=bu[j-1]$.
$4$	This corresponds to optimality being declared with $x[j-1]$ being temporarily fixed at its current value. This value of $istate$ can occur only when $errno$ = 1 on exit.

xfloat, ndarray, shape $\left(n\right)$

The point at which lp_solve terminated. If the function exits successfully or $errno$ = 1 or 4, $x$ contains an estimate of the solution.

iteraint

The total number of iterations performed.

objfloat

The value of the objective function at $x$ if $x$ is feasible, or the sum of infeasibiliites at $x$ otherwise. If the problem is of type FP and $x$ is feasible, $obj$ is set to zero.

axNone or float, ndarray, shape $(max(1,\text{nclin}))$

The final values of the linear constraints $Ax$.

clamdafloat, ndarray, shape $(n+\text{nclin})$

The values of the Lagrange multipliers for each constraint with respect to the current working set. The first $n$ elements contain the multipliers for the bound constraints on the variables, and the next $m_L$ elements contain the multipliers for the general linear constraints (if any). If $istate[j-1]=0$ (i.e., constraint $j$ is not in the working set), $clamda[j-1]$ is zero. If $x$ is optimal, $clamda[j-1]$ should be non-negative if $istate[j-1]=1$, non-positive if $istate[j-1]=2$ and zero if $istate[j-1]=4$.

Other Parameters

‘Check Frequency’int

Default $=50$

Every $i$th iteration, a numerical test is made to see if the current solution $x$ satisfies the constraints in the working set. If the largest residual of the constraints in the working set is judged to be too large, the current working set is refactorized and the variables are recomputed to satisfy the constraints more accurately. If $i\le 0$, the default value is used.

‘Cold Start’valueless

Default

This option specifies how the initial working set is chosen. With a ‘Cold Start’, lp_solve chooses the initial working set based on the values of the variables and constraints at the initial point. Broadly speaking, the initial working set will include equality constraints and bounds or inequality constraints that violate or ‘nearly’ satisfy their bounds (to within ‘Crash Tolerance’).

With a ‘Warm Start’, you must provide a valid definition of every element of the array $istate$. lp_solve will override your specification of $istate$ if necessary, so that a poor choice of the working set will not cause a fatal error. For instance, any elements of $istate$ which are set to $-2$, $-1$ or $4$ will be reset to zero, as will any elements which are set to $3$ when the corresponding elements of $bl$ and $bu$ are not equal. A warm start will be advantageous if a good estimate of the initial working set is available – for example, when lp_solve is called repeatedly to solve related problems.

‘Warm Start’valueless

This option specifies how the initial working set is chosen. With a ‘Cold Start’, lp_solve chooses the initial working set based on the values of the variables and constraints at the initial point. Broadly speaking, the initial working set will include equality constraints and bounds or inequality constraints that violate or ‘nearly’ satisfy their bounds (to within ‘Crash Tolerance’).

With a ‘Warm Start’, you must provide a valid definition of every element of the array $istate$. lp_solve will override your specification of $istate$ if necessary, so that a poor choice of the working set will not cause a fatal error. For instance, any elements of $istate$ which are set to $-2$, $-1$ or $4$ will be reset to zero, as will any elements which are set to $3$ when the corresponding elements of $bl$ and $bu$ are not equal. A warm start will be advantageous if a good estimate of the initial working set is available – for example, when lp_solve is called repeatedly to solve related problems.

‘Crash Tolerance’float

Default $=0.01$

This value is used in conjunction with the option ‘Cold Start’ (the default value) when lp_solve selects an initial working set. If $0\le r\le 1$, the initial working set will include (if possible) bounds or general inequality constraints that lie within $r$ of their bounds. In particular, a constraint of the form $a_j^{T}x\ge l$ will be included in the initial working set if $|a_j^{T}x-l|\le r(1+\left|l\right|)$. If $r<0$ or $r>1$, the default value is used.

‘Defaults’valueless

This special keyword may be used to reset all options to their default values.

‘Expand Frequency’int

Default $=5$

This option is part of an anti-cycling procedure designed to guarantee progress even on highly degenerate problems.

The strategy is to force a positive step at every iteration, at the expense of violating the constraints by a small amount. Suppose that the value of the option ‘Feasibility Tolerance’ is $\delta$. Over a period of $i$ iterations, the feasibility tolerance actually used by lp_solve (i.e., the working feasibility tolerance) increases from $0.5\delta$ to $\delta$ (in steps of $0.5\delta /i$).

At certain stages the following ‘resetting procedure’ is used to remove constraint infeasibilities. First, all variables whose upper or lower bounds are in the working set are moved exactly onto their bounds. A count is kept of the number of nontrivial adjustments made. If the count is positive, iterative refinement is used to give variables that satisfy the working set to (essentially) machine precision. Finally, the working feasibility tolerance is reinitialized to $0.5\delta$.

If a problem requires more than $i$ iterations, the resetting procedure is invoked and a new cycle of $i$ iterations is started with $i$ incremented by $10$. (The decision to resume the feasibility phase or optimality phase is based on comparing any constraint infeasibilities with $\delta$.)

The resetting procedure is also invoked when lp_solve reaches an apparently optimal, infeasible or unbounded solution, unless this situation has already occurred twice. If any nontrivial adjustments are made, iterations are continued.

If $i\le 0$, the default value is used. If $i\ge 9999999$, no anti-cycling procedure is invoked.

‘Feasibility Tolerance’float

Default $=\sqrt{ϵ}$

If $r\ge ϵ$, $r$ defines the maximum acceptable absolute violation in each constraint at a ‘feasible’ point. For example, if the variables and the coefficients in the general constraints are of order unity, and the latter are correct to about $6$ decimal digits, it would be appropriate to specify $r$ as ${10}^{-6}$. If $0\le r<ϵ$, the default value is used.

lp_solve attempts to find a feasible solution before optimizing the objective function. If the sum of infeasibilities cannot be reduced to zero, the option ‘Minimum Sum of Infeasibilities’ can be used to find the minimum value of the sum. Let Sinf be the corresponding sum of infeasibilities. If Sinf is quite small, it may be appropriate to raise $r$ by a factor of $10$ or $100$. Otherwise, some error in the data should be suspected.

Note that a ‘feasible solution’ is a solution that satisfies the current constraints to within the tolerance $r$.

‘Infinite Bound Size’float

Default $={10}^{20}$

If $r>0$, $r$ defines the ‘infinite’ bound $\text{bigbnd}$ in the definition of the problem constraints. Any upper bound greater than or equal to $\text{bigbnd}$ will be regarded as $+\infty$ (and similarly any lower bound less than or equal to $-\text{bigbnd}$ will be regarded as $-\infty$). If $r<0$, the default value is used.

‘Infinite Step Size’float

Default $=max(\text{bigbnd},{10}^{20})$

If $r>0$, $r$ specifies the magnitude of the change in variables that will be considered a step to an unbounded solution. (Note that an unbounded solution can occur only when the problem is of type LP.) If the change in $x$ during an iteration would exceed the value of $r$, the objective function is considered to be unbounded below in the feasible region. If $r\le 0$, the default value is used.

‘Iteration Limit’int

Default $=max(50,5(n+m_L))$

The value of $i$ specifies the maximum number of iterations allowed before termination. With $i=0$ and $\text{‘Print Level'}>0$, the workspace needed will be computed and printed, but no iterations will be performed. If $i<0$, the default value is used.

‘Iters’int

Default $=max(50,5(n+m_L))$

The value of $i$ specifies the maximum number of iterations allowed before termination. With $i=0$ and $\text{‘Print Level'}>0$, the workspace needed will be computed and printed, but no iterations will be performed. If $i<0$, the default value is used.

‘Itns’int

Default $=max(50,5(n+m_L))$

The value of $i$ specifies the maximum number of iterations allowed before termination. With $i=0$ and $\text{‘Print Level'}>0$, the workspace needed will be computed and printed, but no iterations will be performed. If $i<0$, the default value is used.

‘List’valueless

Option ‘List’ enables printing of each option specification as it is supplied. ‘Nolist’ suppresses this printing.

‘Nolist’valueless

Default $=\text{‘Nolist'}$

Option ‘List’ enables printing of each option specification as it is supplied. ‘Nolist’ suppresses this printing.

‘Minimum Sum of Infeasibilities’str

Default $=NO$

If no feasible point exists for the constraints, this option is used to control whether or not lp_solve will calculate a point that minimizes the constraint violations. If $\text{‘Minimum Sum of Infeasibilities'}=\text{'NO'}$, lp_solve will terminate as soon as it is evident that no feasible point exists for the constraints. The final point will generally not be the point at which the sum of infeasibilities is minimized. If $\text{‘Minimum Sum of Infeasibilities'}=\text{'YES'}$, lp_solve will continue until the sum of infeasibilities is minimized.

‘Monitoring File’int

Default $=-1$

If $i\ge 0$ and $\text{‘Print Level'}\ge 5$, monitoring information produced by lp_solve at every iteration is sent to a file with logical unit number $i$. If $i<0$ and/or $\text{‘Print Level'}<5$, no monitoring information is produced.

‘Optimality Tolerance’float

Default $={ϵ}^{0.8}$

If $r\ge ϵ$, $r$ defines the tolerance used to determine if the bounds and general constraints have the right ‘sign’ for the solution to be judged to be optimal.

If $0\le r<ϵ$, the default value is used.

‘Print Level’int

Default $=0$

The value of $i$ controls the amount of printout produced by lp_solve, as indicated below. A detailed description of the printed output is given in Further Comments (summary output at each iteration and the final solution) and Monitoring Information (monitoring information at each iteration).

The following printout is sent to the file object associated with the advisory I/O unit (see FileObjManager):

$i$	Output
$0$	No output.
$1$	The final solution only.
$5$	One line of summary output ($<80$ characters; see Further Comments) for each iteration (no printout of the final solution).
$\ge 10$	The final solution and one line of summary output for each iteration.

The following printout is sent to the unit number given by the option ‘Monitoring File’:

$i$	Output
$<5$	No output.
$\ge 5$	One long line of output ($>80$ characters; see Monitoring Information) for each iteration (no printout of the final solution).
$\ge 20$	At each iteration, the Lagrange multipliers, the variables $x$, the constraint values $Ax$ and the constraint status (see $istate$).
$\ge 30$	At each iteration, the diagonal elements of the upper triangular matrix $T$ associated with the $TQ$ factorization (3) (see Definition of Search Direction) of the working set.

If $\text{‘Print Level'}\ge 5$ and the unit number defined by the option ‘Monitoring File’ is the advisory unit number, the summary output for each major iteration is suppressed.

‘Problem Type’str

Default $=$ LP

This option specifies the type of objective function to be minimized during the optimality phase. The following is the optional keyword and the dimensions of the array that must be specified in order to define the objective function:

LP	length-$\text{n}$ $cvec$ required.
FP	the objective function is omitted and $cvec$ is not referenced.

For problems of type FP, the objective function is omitted and $cvec$ is not referenced. The following keywords are also acceptable.

$a$	Option
Linear	LP
Feasible	FP

Raises

NagValueError

(errno $4$)

Too many iterations.

(errno $6$)

On entry, $n=⟨value⟩$.

Constraint: $n>0$.

(errno $6$)

On entry, $\text{nclin}=⟨value⟩$.

Constraint: $\text{nclin}\ge 0$.

(errno $6$)

On entry, the equal bounds on $⟨value⟩$ are infinite, because $bl[⟨value⟩]=\text{beta}$ and $bu[⟨value⟩]=\text{beta}$, but $\left|\text{beta}\right|\ge \text{bigbnd}$: $\text{beta}=⟨value⟩$ and $\text{bigbnd}=⟨value⟩$.

(errno $6$)

On entry, the bounds on $⟨value⟩$ are inconsistent: $bl[⟨value⟩]=⟨value⟩$ and $bu[⟨value⟩]=⟨value⟩$.

(errno $6$)

On entry with a Warm Start, $istate[⟨value⟩]=⟨value⟩$.

(errno $6$)

On entry with a Cold Start, $istate[⟨value⟩]=⟨value⟩$.

(errno $6$)

On entry, the equal bounds on variable $⟨value⟩$ are infinite, because $bl[⟨value⟩]=\text{beta}$ and $bu[⟨value⟩]=\text{beta}$, but $\left|\text{beta}\right|\ge \text{bigbnd}$: $\text{beta}=⟨value⟩$ and $\text{bigbnd}=⟨value⟩$.

(errno $6$)

On entry, the equal bounds on linear constraint $⟨value⟩$ are infinite, because $bl[⟨value⟩]=\text{beta}$ and $bu[⟨value⟩]=\text{beta}$, but $\left|\text{beta}\right|\ge \text{bigbnd}$: $\text{beta}=⟨value⟩$ and $\text{bigbnd}=⟨value⟩$.

(errno $6$)

On entry, the equal bounds on nonlinear constraint $⟨value⟩$ are infinite, because $bl[⟨value⟩]=\text{beta}$ and $bu[⟨value⟩]=\text{beta}$, but $\left|\text{beta}\right|\ge \text{bigbnd}$: $\text{beta}=⟨value⟩$ and $\text{bigbnd}=⟨value⟩$.

(errno $6$)

On entry, the bounds on variable $⟨value⟩$ are inconsistent: $bl[⟨value⟩]=⟨value⟩$ and $bu[⟨value⟩]=⟨value⟩$.

(errno $6$)

On entry, the bounds on linear constraint $⟨value⟩$ are inconsistent: $bl[⟨value⟩]=⟨value⟩$ and $bu[⟨value⟩]=⟨value⟩$.

(errno $6$)

On entry, the bounds on nonlinear constraint $⟨value⟩$ are inconsistent: $bl[⟨value⟩]=⟨value⟩$ and $bu[⟨value⟩]=⟨value⟩$.

(errno $7$)

‘Problem Type’ not recognized. Problem abandoned.

Warns

NagAlgorithmicWarning

(errno $1$)

Weak $⟨value⟩$ solution.

(errno $2$)

$⟨value⟩$ solution is unbounded.

(errno $3$)

No feasible point for the linear constraints.

(errno $3$)

Cannot satisfy the working-set constraints to the accuracy requested.

Notes

In the NAG Library the traditional C interface for this routine uses a different algorithmic base. Please contact NAG if you have any questions about compatibility.

lp_solve is designed to solve Linear Programming (LP) problems of the form

$$\begin{array}{c}{minimize}_{x\in R^n}{c}^{T}x\text{, subject to}l\le \left\{\begin{array}{c}x\\ Ax\end{array}\right\}\le u\text{,}\end{array}$$

where $c$ is an $n$-element vector and $A$ is an $m_L\times n$ matrix.

This is the default type of problem, referred to as type LP. The option ‘Problem Type’ may be used to specify an alternative problem type FP, in which the objective function is omitted and the function attempts to find a feasible point for the set of constraints.

The constraints involving $A$ are called the general constraints. Note that upper and lower bounds are specified for all the variables and for all the general constraints. An equality constraint can be specified by setting $l_i=u_i$. If certain bounds are not present, the associated elements of $l$ or $u$ can be set to special values that will be treated as $-\infty$ or $+\infty$. (See the description of the option ‘Infinite Bound Size’.)

You must supply an initial estimate of the solution.

The method used by lp_solve is described in detail in Algorithmic Details.

References

Gill, P E, Hammarling, S, Murray, W, Saunders, M A and Wright, M H, 1986, Users’ guide for LSSOL (Version 1.0), Report SOL 86-1, Department of Operations Research, Stanford University

Gill, P E and Murray, W, 1978, Numerically stable methods for quadratic programming, Math. Programming (14), 349–372

Gill, P E, Murray, W, Saunders, M A and Wright, M H, 1984, Procedures for optimization problems with a mixture of bounds and general linear constraints, ACM Trans. Math. Software (10), 282–298

Gill, P E, Murray, W, Saunders, M A and Wright, M H, 1989, A practical anti-cycling procedure for linearly constrained optimization, Math. Programming (45), 437–474

Gill, P E, Murray, W, Saunders, M A and Wright, M H, 1991, Inertia-controlling methods for general quadratic programming, SIAM Rev. (33), 1–36

Gill, P E, Murray, W and Wright, M H, 1981, Practical Optimization, Academic Press