% \VignetteIndexEntry{R package for using the GNU Linear Programming Toolkit (GLPK) using MathProg or the API}
% \VignetteDepends{glpkAPI}
% \VignetteKeyword{Linear Progamming}
\documentclass[letterpaper]{article}
\usepackage{fancyvrb}
\title{Introduction to glpkAPI}
\author{Louis Luangkesorn \footnote{lugerpitt@gmail.com.  Thanks to Leo Lopes for his comments and suggestions.}}
\begin{document}
\SweaveOpts{concordance=TRUE}

\maketitle

\section{Introduction}

This document introduces the use of the glpkAPI package\footnote{Package glpkAPI maintained by Gabriel Gelius-Dietrich} for R.  The GNU Linear Programming Package (GLPK) is intended for solving linear programming (LP) and mixed integer programming (MIP) and other related problems. In addition, it includes facilities for converting problem information between the GNU MathProg language (a subset of the AMPL mathematical programming language), free and fixed MPS, and the CPLEX LP formats.\footnote{GNU Linear Programming Kit:  Reference Manual, Version 4.54 Draft, March 2014.}  The GLPK package is an interface into the C Application Programming Interface (API) to the GLPK solver.

This document will introduce the use of the GLPK package through the use of the  cannery problem from Dantzig\footnote{The demand data here is from the GLPK documentation, which differs slightly from Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, NJ, 1963.  The documentation demand values are used here for consistancy.} which is used in the GNU MathProg documentation.\footnote{GNU Linear Programming Kit:  Modeling Language GNU MathProg, Version 4.50 Draft, May 2013.}  The model file describing the cannery problem can be found in Appendix \ref{app:model}.

\section{Entering the model}

To use {\tt glpk}, first load the package.

<<>>=
library(glpkAPI)
@

Next read in the model and data.

There are several ways of entering the model.  {\tt glpk} can read the model and data in a GNU MathProg Language (GMPL) model file.  Alternatively, the model and data can be entered using the GLPK API.


\subsection{Reading a GNU MathProg Language model}

To use a GNU MathProg model requires several steps.

\begin{enumerate}
\item Allocating the workspace using {\tt initProbGLPK()}. The problem can then be given an name using {\tt setProbNameGLPK()}.
\item Reading model section using {\tt mplAllocWkspGLPK()} and 
{\tt mplReadModelGLPK()}. 
\item Reading data section(s) using {\tt mplReadDataGLPK()}.
\item Generating the model using {\tt mplGenerateGLPK()}.
\item Building the problem object using {\tt result <- mplBuildProbGLPK()}. 
\item Solving the problem using {\tt solveSimplexGLPK()}.
\item Postsolving the model using {\tt mplPostsolveGLPK()}.
\item Freeing the workspace using {\tt mplFreeWkspGLPK()} and {\tt delProbGLPK()}
\end{enumerate}


<<>>=
mip <- initProbGLPK()
setProbNameGLPK(mip, "transport")
trans <- mplAllocWkspGLPK()
result <- mplReadModelGLPK(trans,
	system.file("extdata", "transport.mod", package = "glpkAPI"), skip=0)
result <- mplGenerateGLPK(trans)
result <- mplBuildProbGLPK(trans, mip)
@

If the data was in a separate file, it would need to be read in using

\begin{verbatim}
mplReadDataGLPK(trans, "transport.mod")
\end{verbatim}

Then examine the problem size within R.

The rows represent the objective function as well as the supply and demand constraints.

<<>>=
numrows <- getNumRowsGLPK(mip)
numrows


for (i in 1:numrows){
	print(getRowNameGLPK(mip, i))
}
@

The columns represent the decision variables, which are the units sent over the cannary-market links.

<<>>=
numcols <- getNumColsGLPK(mip)
numcols

for (j in 1:numcols){
	print(getColNameGLPK(mip, j))
}
print(getNumNnzGLPK(mip))
@

After the model and data are entered, the model can then be solved using any one of many algorithms and the output would go to the specified output file.  For the Simplex method, the {\tt solveSimplexGLPK()} takes the problem name and solves it using the Simplex method.

<<>>=
return <- solveSimplexGLPK(mip)
return <- mplPostsolveGLPK(trans, mip, GLP_MIP);
@

We can then look at the solution in terms of the objective and constraints

<<>>=
for (i in 1:numrows){
print(getRowNameGLPK(mip, i))
print(getRowPrimGLPK(mip, i))
}
@

as well as the decision variables.

<<>>=
for (j in 1:numcols){
print(getColNameGLPK(mip, j))
print(getColPrimGLPK(mip, j))
}
@

Finally, clean up the workspace.

<<>>=
mplFreeWkspGLPK(trans)
delProbGLPK(mip)
@
\subsection{Using the API}

If the problem data already in {\em R}, such as pulled from a database or the result of previous analysis, the model and the data can be specified using the API.

First create R data objects to hold the various model parameters.

<<>>=
print ("USING API")
canneries <- c("Seattle", "San-Diego")
capacity <- c(350, 600)
markets <- c("New-York", "Chicago", "Topeka")
demand <- c(325, 300, 275)
distance <- c(2.5, 2.5, 1.7, 1.8, 1.8, 1.4)
dim(distance) <- c(2, 3)
freight <- 90
@

To use the API, define a problem instance and indicate that the objective is to minimize cost.

<<>>=
lpi <- initProbGLPK()
setProbNameGLPK(lpi, "cannery API")
setObjNameGLPK(lpi, "Total Cost")
setObjDirGLPK(lpi, GLP_MIN)
@

There are 6 columns, corresponding to the six potential cannery-market pairs whose transport the model solving for, each of which has a lower bound of zero.

<<>>=
numlinks <- length(distance)
nummarkets <- length(markets)
numcanneries <- length(canneries)
addColsGLPK(lpi, numlinks)
for (i in 1:numcanneries){
	cannerystartrow <- (i-1) * nummarkets
	for (j in 1:nummarkets){
		colname <-toString(c(canneries[i], markets[j]))
		transcost <- distance[i, j]*freight/1000
		setColNameGLPK(lpi, cannerystartrow+j, colname)
		setColBndGLPK(lpi, cannerystartrow+j, GLP_LO, 0.0, 0.0)
		setObjCoefsGLPK(lpi, cannerystartrow+j, transcost)
	}
}
@

Next, we will add constraints.  There are 5 constraints, two supply constraints relating to the canneries and three demand constraints relating to the markets. In addition, we will make the first row correspond to the objective function.  The objective row will be free, and does not have upper or lower bounds.

<<>>=
numcanneries <- length(canneries)
nummarkets <- length(markets)
addRowsGLPK(lpi, numcanneries+nummarkets+1)
setRowsNamesGLPK(lpi, 1, getObjNameGLPK(lpi))
for (i in 1:numcanneries){
	setRowsNamesGLPK(lpi, i+1, toString(c("Supply", canneries[i])))
	setRowBndGLPK(lpi, i+1, GLP_UP, 0, capacity[i])
}
for (j in 1:nummarkets){
	setRowsNamesGLPK(lpi, numcanneries+j+1, toString(c("Demand", markets[j])))
	setRowBndGLPK(lpi, numcanneries+j+1, GLP_LO, demand[j], 0)
}
@
Now, load the constraint matrix which represents the objective function and the constraints.  The non-zero values of the matrix are entered as three vectors, each with one element for each non-zero value.  A vector to indicate the row, a vector to indicate the column, and a vector which contains the matrix element value.  Last, we call {\tt loadMatrixGLPK(lpi)} to finish. 

<<>>=
# create variables to hold the constraint information
ia <- numeric()
ja <- numeric()
ar <- numeric()

# add in objective coefficients

for (i in 1:numcols){
	ia[i] <- 1
	ja[i] <- i
	ar[i] <- getObjCoefGLPK(lpi, i)
}

for (i in 1:numcanneries){
	#supply constraints
	cannerysupplyrow = numcols + (i-1)*nummarkets
	for (j in 1:nummarkets){
		ia[cannerysupplyrow+j] <- (i+1)
		ja[cannerysupplyrow+j] <- (i-1)+numcanneries *(j-1)+1
		ar[cannerysupplyrow+j] <- 1
	}
	#demand constraints
	marketdemandrow = numcols+numcanneries * nummarkets
	for (j in 1:nummarkets){
		colnum <- (i-1)*nummarkets+j
		ia[marketdemandrow + colnum] <- numcanneries+j+1
		ja[marketdemandrow + colnum] <- colnum
		ar[marketdemandrow + colnum] <- 1
	}
}
loadMatrixGLPK(lpi, length(ia), ia, ja, ar)
@

Then, examine the problem entered in the API.

<<>>=
numrows <- getNumRowsGLPK(lpi)
numrows
numcols <- getNumColsGLPK(lpi)
numcols
for (i in 1:numrows){
	print(getRowNameGLPK(lpi, i))
}
for (j in 1:numcols){
	print(getColNameGLPK(lpi, j))
}
print(getNumNnzGLPK(lpi))
@

Finally solve using the simplex method and look at the solution.

<<>>=
solveSimplexGLPK(lpi)

for (i in 1:numrows){
print(getRowNameGLPK(lpi, i))
print(getRowPrimGLPK(lpi, i))
}
for (j in 1:numcols){
print(getColNameGLPK(lpi, j))
print(getColPrimGLPK(lpi, j))  
}
@

And save the results to a file.

<<>>=
printSolGLPK(lpi, "transout.api")
@

\subsection{Using API to modify the model}

Now, we will solve the version of the problem that is found in Dantzig.  The demand at New York and Topeka are both 300 instead of 325 and 275.  This next section will use the API to modify the problem as read through the MathProg file.

In order to examine an individual row, we need to index the rows and columns.  This is done through the use of {\tt createIndexGLPK()}.  Then we can use the {\tt findRowGLPK()} and {\tt findColGLPK()}

<<>>=
cindex <- createIndexGLPK(lpi)
new_york_row = findRowGLPK(lpi, "Demand, New-York") 
topeka_row = findRowGLPK(lpi, "Demand, Topeka")
new_york_row
topeka_row
setRowBndGLPK(lpi, new_york_row, GLP_LO, 300, 0)
setRowBndGLPK(lpi, topeka_row, GLP_LO, 300, 0)
@

We can solve this modified problem and look at the results.

<<>>=
solveSimplexGLPK(lpi)

for (i in 1:numrows){
print(getRowNameGLPK(lpi, i))
print(getRowPrimGLPK(lpi, i))
print(getRowDualGLPK(lpi, i))
}
for (j in 1:numcols){
print(getColNameGLPK(lpi, j))
print(getColPrimGLPK(lpi, j))
print(getColDualGLPK(lpi,j))
print(getObjCoefGLPK(lpi, j))
}
@

Finally, clean up the workspace.

<<>>=
delProbGLPK(lpi)
@

\appendix
\section{Model file \label{app:model}}
{\bf {\it TRANSPORT.MOD}}

\VerbatimInput{"../inst/extdata/transport.mod"}

\section{Output \label{app:output}}

The following is the output of the command:
{\tt printSolGLPK(lpi, "transout.api")}

\VerbatimInput{transout.api}

\end{document}