mgcv (version 1.9-3)

lp: Basic linear programming

Description

Solves, for $\mathbf{x}$, linear programming problems in the standard form $$min{\mathbf{c}}^T\mathbf{x}\text{ s.t. }\mathbf{A}\mathbf{x}=\mathbf{b},\mathbf{b}\ge \mathbf{0}$$ or in the form $$min{\mathbf{c}}^T\mathbf{x}\text{ s.t. }\mathbf{A}\mathbf{x}\ge \mathbf{b},\mathbf{C}\mathbf{x}=\mathbf{d}$$ A lightweight implementation of the simplex method, designed for problems of modest size, not large scale problems requiring sparse methods.

feasible finds starting values meeting the constraints, which is also useful for finding feasible initial values for quadratic programming.

Usage

lp(c,A,b,C=NULL,d=NULL,Bi=NULL,maxit=max(1000, nrow(A) * 10), phase1 = FALSE)
feasible(A,b,C=NULL,d=NULL,maxit = max(1000, nrow(A) * 10))

Value

A vector. Either the solution of the problem (lp), or a feaible initial vector (feasible). Produces an error if there is no solution or maxit is exceeded.

Arguments

c

The vector defining the linear program objective function ${\mathbf{c}}^T\mathbf{x}$.

A

The constraint matrix.

b

The vector defining the r.h.s. of the constraint involving A.

C

NULL to signal a problem in standard form. Otherwise the matrix defining the equality constraints.

d

NULL to signal a problem in standard form. Otherwise the vector defining the r.h.s. of the equality constraint.

Bi

For a problem in standard form, index of the elements of $\mathbf{x}$ initially non-zero. $\mathbf{A}[,Bi]{\mathbf{x}}^{\ast }=\mathbf{b}$ must have a unique solution with ${\mathbf{x}}^{\ast }\ge \mathbf{0}$. NULL to have this set found automatically by solution of a phase 1 linear program.

maxit

Maximum number of iterations of the simplex method to allow.

phase1

signals that function is being called to solve a phase 1 problem.

Author

Simon N. Wood

WARNINGS

Not designed for large scale problems requiring sparse methods, nor for problems where significant degeneracy is expected.

Details

This code was written to provide a lightweight method for finding feasible initial coefficients for shape constrained splines, but is suitable for solving general linear programming problems of modest size. Given that it uses dense matrix computations, it is not suitable for large scale problems where it is important to exploit sparcity. Neither is it suitable for the sort of linear programming problems arising from integer programs, where degeneracy may be a substantial problem.

The function uses the simplex method (see e.g. Chapter 13 of Nocedal and Wright, 2006). Computational efficiency is ensured by QR decomposing $\mathbf{A}[,Bi]$ and then efficiently updating the decomposition, every time the active set Bi changes, using Givens based updating schemes broadly similar to those given in Golub and van Loan (2013) 5.1.3 p240 and 6.5.3 p337. Given the QR factorization solution of systems involving $\mathbf{A}[,Bi]$ is efficient.

References

Golub G.H. and C.F. van Loan (2013) Matrix Computations (4th edition) Johns Hopkins

Nocedal J. and S. Wright (2006) Numerical Optimization (2nd edition) Springer

See Also

pcls

Examples

library(mgcv)
## very simple linear program...
c <- c(-4,-2,0,0)
A <- matrix(c(1,2,1,.5,1,0,0,1),2,4)
b <- c(5,8)
x <- lp(c,A,b,c(3,4));sum(c*x);x ## Bi given

x <- lp(c,A,b);sum(c*x);x ## Bi found automatically

## equivalent formulation Ax>b
A <- -matrix(c(1,2,1,.5),2,2)
b <- -c(5,8)
C <- matrix(0,0,2); d <- numeric(0)
c <- c(-4,-2)
x <- lp(c,A,b,C=C,d=d);sum(c*x);x

## equivalent formulation Ax>b, Cx=d
c <- c(-4,-2,0)
A <- matrix(c(0,-2,0,-.5,1,0),2,3)
C <- matrix(c(1,1,1),1,3); d <- 5
b <- c(0,-8)
x <- lp(c,A,b,C=C,d=d);sum(c*x);x