%* glpk01.tex *%

\chapter{Introduction}

GLPK (\underline{G}NU \underline{L}inear \underline{P}rogramming

\underline{K}it) is a set of routines written in the ANSI C programming

language and organized in the form of a callable library. It is intended

for solving linear programming (LP), mixed integer programming (MIP),

and other related problems.

\section{LP problem}

\label{seclp}

GLPK assumes the following formulation of {\it linear programming (LP)}

problem:

\medskip

\noindent

\hspace{.5in} minimize (or maximize)

$$z = c_1x_{m+1} + c_2x_{m+2} + \dots + c_nx_{m+n} + c_0 \eqno (1.1)$$

\hspace{.5in} subject to linear constraints

$$

\begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}

x_1&=&a_{11}x_{m+1}&+&a_{12}x_{m+2}&+ \dots +&a_{1n}x_{m+n} \\

x_2&=&a_{21}x_{m+1}&+&a_{22}x_{m+2}&+ \dots +&a_{2n}x_{m+n} \\

\multicolumn{7}{c}

{.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .} \\

x_m&=&a_{m1}x_{m+1}&+&a_{m2}x_{m+2}&+ \dots +&a_{mn}x_{m+n} \\

\end{array} \eqno (1.2)

$$

\hspace{.5in} and bounds of variables

$$

\begin{array}{r@{\:}c@{\:}c@{\:}c@{\:}l}

l_1&\leq&x_1&\leq&u_1 \\

l_2&\leq&x_2&\leq&u_2 \\

\multicolumn{5}{c}{.\ \ .\ \ .\ \ .\ \ .}\\

l_{m+n}&\leq&x_{m+n}&\leq&u_{m+n} \\

\end{array} \eqno (1.3)

$$

where: $x_1, x_2, \dots, x_m$ are auxiliary variables;

$x_{m+1}, x_{m+2}, \dots, x_{m+n}$ are\linebreak structural variables;

$z$ is the objective function;

$c_1, c_2, \dots, c_n$ are objective coefficients;

$c_0$ is the constant term (``shift'') of the objective function;

$a_{11}, a_{12}, \dots, a_{mn}$ are constraint coefficients;

$l_1, l_2, \dots, l_{m+n}$ are lower bounds of variables;

$u_1, u_2, \dots, u_{m+n}$ are upper bounds of variables.

Auxiliary variables are also called {\it rows}, because they correspond

to rows of the constraint matrix (i.e. a matrix built of the constraint

coefficients). Similarly, structural variables are also called

{\it columns}, because they correspond to columns of the constraint

matrix.

Bounds of variables can be finite as well as infinite. Besides, lower

and upper bounds can be equal to each other. Thus, the following types

of variables are possible:

\begin{center}

\begin{tabular}{r@{}c@{}ll}

\multicolumn{3}{c}{Bounds of variable} & Type of variable \\

\hline

$-\infty <$ &$\ x_k\ $& $< +\infty$ & Free (unbounded) variable \\

$l_k \leq$ &$\ x_k\ $& $< +\infty$  & Variable with lower bound \\

$-\infty <$ &$\ x_k\ $& $\leq u_k$  & Variable with upper bound \\

$l_k \leq$ &$\ x_k\ $& $\leq u_k$   & Double-bounded variable \\

$l_k =$ &$\ x_k\ $& $= u_k$         & Fixed variable \\

\end{tabular}

\end{center}

\noindent

Note that the types of variables shown above are applicable to

structural as well as to auxiliary variables.

To solve the LP problem (1.1)---(1.3) is to find such values of all

structural and auxiliary variables, which:

$\bullet$ satisfy to all the linear constraints (1.2), and

$\bullet$ are within their bounds (1.3), and

$\bullet$ provide the smallest (in case of minimization) or the largest

(in case of maximization) value of the objective function (1.1).

\section{MIP problem}

{\it Mixed integer linear programming (MIP)} problem is LP problem in

which some variables are additionally required to be integer.

GLPK assumes that MIP problem has the same formulation as ordinary

(pure) LP problem (1.1)---(1.3), i.e. includes auxiliary and structural

variables, which may have lower and/or upper bounds. However, in case of

MIP problem some variables may be required to be integer. This

additional constraint means that a value of each {\it integer variable}

must be only integer number. (Should note that GLPK allows only

structural variables to be of integer kind.)

\section{Using the package}

\subsection{Brief example}

In order to understand what GLPK is from the user's standpoint,

consider the following simple LP problem:

\medskip

\noindent

\hspace{.5in} maximize

$$z = 10 x_1 + 6 x_2 + 4 x_3$$

\hspace{.5in} subject to

$$

\begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}

x_1 &+&x_2 &+&x_3 &\leq 100 \\

10 x_1 &+& 4 x_2 & +&5 x_3 & \leq 600 \\

2 x_1 &+& 2 x_2 & +& 6 x_3 & \leq 300 \\

\end{array}

$$

\hspace{.5in} where all variables are non-negative

$$x_1 \geq 0, \ x_2 \geq 0, \ x_3 \geq 0$$

At first this LP problem should be transformed to the standard form

(1.1)---(1.3). This can be easily done by introducing auxiliary

variables, by one for each original inequality constraint. Thus, the

problem can be reformulated as follows:

\medskip

\noindent

\hspace{.5in} maximize

$$z = 10 x_1 + 6 x_2 + 4 x_3$$

\hspace{.5in} subject to

$$

\begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}

p& = &x_1 &+&x_2 &+&x_3 \\

q& = &10 x_1 &+& 4 x_2 &+& 5 x_3 \\

r& = &2  x_1 &+& 2 x_2 &+& 6 x_3 \\

\end{array}

$$

\hspace{.5in} and bounds of variables

$$

\begin{array}{ccc}

\nonumber -\infty < p \leq 100 && 0 \leq x_1 < +\infty \\

\nonumber -\infty < q \leq 600 && 0 \leq x_2 < +\infty \\

\nonumber -\infty < r \leq 300 && 0 \leq x_3 < +\infty \\

\end{array}

$$

where $p, q, r$ are auxiliary variables (rows), and $x_1, x_2, x_3$ are

structural variables (columns).

The example C program shown below uses GLPK API routines in order to

solve this LP problem.\footnote{If you just need to solve LP or MIP

instance, you may write it in MPS or CPLEX LP format and then use the

GLPK stand-alone solver to obtain a solution. This is much less

time-consuming than programming in C with GLPK API routines.}

\newpage

\begin{verbatim}

/* sample.c */

#include <stdio.h>

#include <stdlib.h>

#include <glpk.h>

int main(void)

{     glp_prob *lp;

      int ia[1+1000], ja[1+1000];

      double ar[1+1000], z, x1, x2, x3;

s1:   lp = glp_create_prob();

s2:   glp_set_prob_name(lp, "sample");

s3:   glp_set_obj_dir(lp, GLP_MAX);

s4:   glp_add_rows(lp, 3);

s5:   glp_set_row_name(lp, 1, "p");

s6:   glp_set_row_bnds(lp, 1, GLP_UP, 0.0, 100.0);

s7:   glp_set_row_name(lp, 2, "q");

s8:   glp_set_row_bnds(lp, 2, GLP_UP, 0.0, 600.0);

s9:   glp_set_row_name(lp, 3, "r");

s10:  glp_set_row_bnds(lp, 3, GLP_UP, 0.0, 300.0);

s11:  glp_add_cols(lp, 3);

s12:  glp_set_col_name(lp, 1, "x1");

s13:  glp_set_col_bnds(lp, 1, GLP_LO, 0.0, 0.0);

s14:  glp_set_obj_coef(lp, 1, 10.0);

s15:  glp_set_col_name(lp, 2, "x2");

s16:  glp_set_col_bnds(lp, 2, GLP_LO, 0.0, 0.0);

s17:  glp_set_obj_coef(lp, 2, 6.0);

s18:  glp_set_col_name(lp, 3, "x3");

s19:  glp_set_col_bnds(lp, 3, GLP_LO, 0.0, 0.0);

s20:  glp_set_obj_coef(lp, 3, 4.0);

s21:  ia[1] = 1, ja[1] = 1, ar[1] =  1.0; /* a[1,1] =  1 */

s22:  ia[2] = 1, ja[2] = 2, ar[2] =  1.0; /* a[1,2] =  1 */

s23:  ia[3] = 1, ja[3] = 3, ar[3] =  1.0; /* a[1,3] =  1 */

s24:  ia[4] = 2, ja[4] = 1, ar[4] = 10.0; /* a[2,1] = 10 */

s25:  ia[5] = 3, ja[5] = 1, ar[5] =  2.0; /* a[3,1] =  2 */

s26:  ia[6] = 2, ja[6] = 2, ar[6] =  4.0; /* a[2,2] =  4 */

s27:  ia[7] = 3, ja[7] = 2, ar[7] =  2.0; /* a[3,2] =  2 */

s28:  ia[8] = 2, ja[8] = 3, ar[8] =  5.0; /* a[2,3] =  5 */

s29:  ia[9] = 3, ja[9] = 3, ar[9] =  6.0; /* a[3,3] =  6 */

s30:  glp_load_matrix(lp, 9, ia, ja, ar);

s31:  glp_simplex(lp, NULL);

s32:  z = glp_get_obj_val(lp);

s33:  x1 = glp_get_col_prim(lp, 1);

s34:  x2 = glp_get_col_prim(lp, 2);

s35:  x3 = glp_get_col_prim(lp, 3);

s36:  printf("\nz = %g; x1 = %g; x2 = %g; x3 = %g\n",

         z, x1, x2, x3);

s37:  glp_delete_prob(lp);

      return 0;

}

/* eof */

\end{verbatim}

The statement \verb|s1| creates a problem object. Being created the

object is initially empty. The statement \verb|s2| assigns a symbolic

name to the problem object.

The statement \verb|s3| calls the routine \verb|glp_set_obj_dir| in

order to set the optimization direction flag, where \verb|GLP_MAX| means

maximization.

The statement \verb|s4| adds three rows to the problem object.

The statement \verb|s5| assigns the symbolic name `\verb|p|' to the

first row, and the statement \verb|s6| sets the type and bounds of the

first row, where \verb|GLP_UP| means that the row has an upper bound.

The statements \verb|s7|, \verb|s8|, \verb|s9|, \verb|s10| are used in

the same way in order to assign the symbolic names `\verb|q|' and

`\verb|r|' to the second and third rows and set their types and bounds.

The statement \verb|s11| adds three columns to the problem object.

The statement \verb|s12| assigns the symbolic name `\verb|x1|' to the

first column, the statement \verb|s13| sets the type and bounds of the

first column, where \verb|GLP_LO| means that the column has an lower

bound, and the statement \verb|s14| sets the objective coefficient for

the first column. The statements \verb|s15|---\verb|s20| are used in the

same way in order to assign the symbolic names `\verb|x2|' and

`\verb|x3|' to the second and third columns and set their types, bounds,

and objective coefficients.

The statements \verb|s21|---\verb|s29| prepare non-zero elements of the

constraint matrix (i.e. constraint coefficients). Row indices of each

element are stored in the array \verb|ia|, column indices are stored in

the array \verb|ja|, and numerical values of corresponding elements are

stored in the array \verb|ar|. Then the statement \verb|s30| calls

the routine \verb|glp_load_matrix|, which loads information from these

three arrays into the problem object.

Now all data have been entered into the problem object, and therefore

the statement \verb|s31| calls the routine \verb|glp_simplex|, which is

a driver to the simplex method, in order to solve the LP problem. This

routine finds an optimal solution and stores all relevant information

back into the problem object.

The statement \verb|s32| obtains a computed value of the objective

function, and the statements \verb|s33|---\verb|s35| obtain computed

values of structural variables (columns), which correspond to the

optimal basic solution found by the solver.

The statement \verb|s36| writes the optimal solution to the standard

output. The printout may look like follows:

{\footnotesize

\begin{verbatim}

*     0:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (0)

*     2:   objval =   7.333333333e+02   infeas =   0.000000000e+00 (0)

OPTIMAL SOLUTION FOUND

z = 733.333; x1 = 33.3333; x2 = 66.6667; x3 = 0

\end{verbatim}

}

Finally, the statement \verb|s37| calls the routine

\verb|glp_delete_prob|, which frees all the memory allocated to the

problem object.

\subsection{Compiling}

The GLPK package has the only header file \verb|glpk.h|, which should

be available on compiling a C (or C++) program using GLPK API routines.

If the header file is installed in the default location

\verb|/usr/local/include|, the following typical command may be used to

compile, say, the example C program described above with the GNU C

compiler:

\begin{verbatim}

   $ gcc -c sample.c

\end{verbatim}

If \verb|glpk.h| is not in the default location, the corresponding

directory containing it should be made known to the C compiler through

\verb|-I| option, for example:

\begin{verbatim}

   $ gcc -I/foo/bar/glpk-4.15/include -c sample.c

\end{verbatim}

In any case the compilation results in an object file \verb|sample.o|.

\subsection{Linking}

The GLPK library is a single file \verb|libglpk.a|. (On systems which

support shared libraries there may be also a shared version of the

library \verb|libglpk.so|.)

If the library is installed in the default

location \verb|/usr/local/lib|, the following typical command may be

used to link, say, the example C program described above against with

the library:

\begin{verbatim}

   $ gcc sample.o -lglpk -lm

\end{verbatim}

If the GLPK library is not in the default location, the corresponding

directory containing it should be made known to the linker through

\verb|-L| option, for example:

\begin{verbatim}

   $ gcc -L/foo/bar/glpk-4.15 sample.o -lglpk -lm

\end{verbatim}

Depending on configuration of the package linking against with the GLPK

library may require the following optional libraries:

\bigskip

\begin{tabular}{@{}ll}

\verb|-lgmp|  & the GNU MP bignum library; \\

\verb|-lz|    & the zlib data compression library; \\

\verb|-lltdl| & the GNU ltdl shared support library. \\

\end{tabular}

\bigskip

\noindent

in which case corresponding libraries should be also made known to the

linker, for example:

\begin{verbatim}

   $ gcc sample.o -lglpk -lz -lltdl -lm

\end{verbatim}

For more details about configuration options of the GLPK package see

Appendix \ref{install}, page \pageref{install}.

%* eof *%