%* 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 *%