intpoint (version 1.0)

interior_point: Solves a linear programming problem using the interior point method

Description

This function solves a linear programming problem using a modification of Karmarkar's linear programming algorithm, developed by Vanderbei, Meketon and Freedman (1986). This algorithm uses a recentered projected gradient approach without a priori knowledge of the optimal objective function value.

Usage

interior_point(t, c, bA = NULL, A = NULL, bm = NULL, m = NULL, 
bM = NULL, M = NULL, e = 1e-04, a1 = 1, a2 = 0.97)

Arguments

t

Type of problem. Put 1 if it is a maximization problem, and -1 if it is a minimization one.

c

The vector corresponding to the coefficients of the objective function

bA

The vector corresponding to the right hand side constants (with =)

A

The coefficients of the problem constraints matrix A (with =)

bm

The vector corresponding to the right hand side constants (with

m

The coefficients of the problem constraints matrix A (with

bM

The vector corresponding to the right hand side constants (with >=)

M

The coefficients of the problem constraints matrix A (with >=)

e

The value of $\epsilon$. Default is 1e-04

a1

The value of $\alpha_1$. Default is 1

a2

The value of $\alpha_2$. Default is 0.97

Value

• a list with the values
• Z
  The optimum value of the objective function
• xf
  The solution vector
• n
  The number of iterations to solve the problem

Details

The function is defined in the form that we only need to put the values used in the problem. For example, for a linear programming problem in the form: l{ Maximize $Z=c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}$ subject to $a_{11}x_{1}+a_{12}x_{2}+...a_{1n}x_{n}\leq b_{1}$ $a_{21}x_{1}+a_{22}x_{2}+...a_{2n}x_{n}\leq b_{2}$ $...$ $a_{m1}x_{1}+a_{m2}x_{2}+...a_{mn}x_{n}\leq b_{m}$ } that is, all the restrictions are inequality in the form $\leq$, we need only to specify the vector bm and the vector(s) corresponding to the row(s) of A.

References

Gill, P.E., Murray, W. and Wright, M.H. (1991) Numerical Linear Algebra and Optimization vol. 1, Addison-Wesley. Karmarkar, N. (1984) A new polynomial-time algorithm for linear programming. Combinatorica 4, pp. 373-395. Vanderbei, R.J., Meketon, M.S. and Freedman, B.A. (1986) A modification of Karmarkar's linear programming algorithm. Algorithmica 1, pp. 395-407.

Examples

##
c<-c(1,3,-2)
bA<-c(25,30)
A<-array(4,c(2,3))
A[1,2]<-8;A[1,3]<-6;A[2,1]<-7;A[2,2]<-5;A[2,3]<-9
interior_point(-1,c,bA,A)

##
c<-c(1,2)
bm<-c(4)
bM<-c(1)
m<-array(1,c(1,2))
m[1,1]<-0
M<-array(1,c(1,2))
interior_point(1,c,bm=bm,m=m,bM=bM,M=M)

##
#  This example is taken from Exercise 7.5 of Gill, Murray,
#  and Wright (1991).

enj <- c(200, 6000, 3000, -200)
fat <- c(800, 6000, 1000, 400)
vitx <- c(50, 3, 150, 100)
vity <- c(10, 10, 75, 100)
vitz <- c(150, 35, 75, 5)
interior_point(1,c=enj, m=fat, bm=13800, M=rbind(vitx, vity, vitz),
bM = c(600, 300, 550))