alpar@9: %* glpk01.tex *%
alpar@9: 
alpar@9: \chapter{Introduction}
alpar@9: 
alpar@9: GLPK (\underline{G}NU \underline{L}inear \underline{P}rogramming
alpar@9: \underline{K}it) is a set of routines written in the ANSI C programming
alpar@9: language and organized in the form of a callable library. It is intended
alpar@9: for solving linear programming (LP), mixed integer programming (MIP),
alpar@9: and other related problems.
alpar@9: 
alpar@9: \section{LP problem}
alpar@9: \label{seclp}
alpar@9: 
alpar@9: GLPK assumes the following formulation of {\it linear programming (LP)}
alpar@9: problem:
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \hspace{.5in} minimize (or maximize)
alpar@9: $$z = c_1x_{m+1} + c_2x_{m+2} + \dots + c_nx_{m+n} + c_0 \eqno (1.1)$$
alpar@9: \hspace{.5in} subject to linear constraints
alpar@9: $$
alpar@9: \begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}
alpar@9: x_1&=&a_{11}x_{m+1}&+&a_{12}x_{m+2}&+ \dots +&a_{1n}x_{m+n} \\
alpar@9: x_2&=&a_{21}x_{m+1}&+&a_{22}x_{m+2}&+ \dots +&a_{2n}x_{m+n} \\
alpar@9: \multicolumn{7}{c}
alpar@9: {.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .} \\
alpar@9: x_m&=&a_{m1}x_{m+1}&+&a_{m2}x_{m+2}&+ \dots +&a_{mn}x_{m+n} \\
alpar@9: \end{array} \eqno (1.2)
alpar@9: $$
alpar@9: \hspace{.5in} and bounds of variables
alpar@9: $$
alpar@9: \begin{array}{r@{\:}c@{\:}c@{\:}c@{\:}l}
alpar@9: l_1&\leq&x_1&\leq&u_1 \\
alpar@9: l_2&\leq&x_2&\leq&u_2 \\
alpar@9: \multicolumn{5}{c}{.\ \ .\ \ .\ \ .\ \ .}\\
alpar@9: l_{m+n}&\leq&x_{m+n}&\leq&u_{m+n} \\
alpar@9: \end{array} \eqno (1.3)
alpar@9: $$
alpar@9: where: $x_1, x_2, \dots, x_m$ are auxiliary variables;
alpar@9: $x_{m+1}, x_{m+2}, \dots, x_{m+n}$ are\linebreak structural variables;
alpar@9: $z$ is the objective function;
alpar@9: $c_1, c_2, \dots, c_n$ are objective coefficients;
alpar@9: $c_0$ is the constant term (``shift'') of the objective function;
alpar@9: $a_{11}, a_{12}, \dots, a_{mn}$ are constraint coefficients;
alpar@9: $l_1, l_2, \dots, l_{m+n}$ are lower bounds of variables;
alpar@9: $u_1, u_2, \dots, u_{m+n}$ are upper bounds of variables.
alpar@9: 
alpar@9: Auxiliary variables are also called {\it rows}, because they correspond
alpar@9: to rows of the constraint matrix (i.e. a matrix built of the constraint
alpar@9: coefficients). Similarly, structural variables are also called
alpar@9: {\it columns}, because they correspond to columns of the constraint
alpar@9: matrix.
alpar@9: 
alpar@9: Bounds of variables can be finite as well as infinite. Besides, lower
alpar@9: and upper bounds can be equal to each other. Thus, the following types
alpar@9: of variables are possible:
alpar@9: \begin{center}
alpar@9: \begin{tabular}{r@{}c@{}ll}
alpar@9: \multicolumn{3}{c}{Bounds of variable} & Type of variable \\
alpar@9: \hline
alpar@9: $-\infty <$ &$\ x_k\ $& $< +\infty$ & Free (unbounded) variable \\
alpar@9: $l_k \leq$ &$\ x_k\ $& $< +\infty$  & Variable with lower bound \\
alpar@9: $-\infty <$ &$\ x_k\ $& $\leq u_k$  & Variable with upper bound \\
alpar@9: $l_k \leq$ &$\ x_k\ $& $\leq u_k$   & Double-bounded variable \\
alpar@9: $l_k =$ &$\ x_k\ $& $= u_k$         & Fixed variable \\
alpar@9: \end{tabular}
alpar@9: \end{center}
alpar@9: \noindent
alpar@9: Note that the types of variables shown above are applicable to
alpar@9: structural as well as to auxiliary variables.
alpar@9: 
alpar@9: To solve the LP problem (1.1)---(1.3) is to find such values of all
alpar@9: structural and auxiliary variables, which:
alpar@9: 
alpar@9: $\bullet$ satisfy to all the linear constraints (1.2), and
alpar@9: 
alpar@9: $\bullet$ are within their bounds (1.3), and
alpar@9: 
alpar@9: $\bullet$ provide the smallest (in case of minimization) or the largest
alpar@9: (in case of maximization) value of the objective function (1.1).
alpar@9: 
alpar@9: \section{MIP problem}
alpar@9: 
alpar@9: {\it Mixed integer linear programming (MIP)} problem is LP problem in
alpar@9: which some variables are additionally required to be integer.
alpar@9: 
alpar@9: GLPK assumes that MIP problem has the same formulation as ordinary
alpar@9: (pure) LP problem (1.1)---(1.3), i.e. includes auxiliary and structural
alpar@9: variables, which may have lower and/or upper bounds. However, in case of
alpar@9: MIP problem some variables may be required to be integer. This
alpar@9: additional constraint means that a value of each {\it integer variable}
alpar@9: must be only integer number. (Should note that GLPK allows only
alpar@9: structural variables to be of integer kind.)
alpar@9: 
alpar@9: \section{Using the package}
alpar@9: 
alpar@9: \subsection{Brief example}
alpar@9: 
alpar@9: In order to understand what GLPK is from the user's standpoint,
alpar@9: consider the following simple LP problem:
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \hspace{.5in} maximize
alpar@9: $$z = 10 x_1 + 6 x_2 + 4 x_3$$
alpar@9: \hspace{.5in} subject to
alpar@9: $$
alpar@9: \begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}
alpar@9: x_1 &+&x_2 &+&x_3 &\leq 100 \\
alpar@9: 10 x_1 &+& 4 x_2 & +&5 x_3 & \leq 600 \\
alpar@9: 2 x_1 &+& 2 x_2 & +& 6 x_3 & \leq 300 \\
alpar@9: \end{array}
alpar@9: $$
alpar@9: \hspace{.5in} where all variables are non-negative
alpar@9: $$x_1 \geq 0, \ x_2 \geq 0, \ x_3 \geq 0$$
alpar@9: 
alpar@9: At first this LP problem should be transformed to the standard form
alpar@9: (1.1)---(1.3). This can be easily done by introducing auxiliary
alpar@9: variables, by one for each original inequality constraint. Thus, the
alpar@9: problem can be reformulated as follows:
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \hspace{.5in} maximize
alpar@9: $$z = 10 x_1 + 6 x_2 + 4 x_3$$
alpar@9: \hspace{.5in} subject to
alpar@9: $$
alpar@9: \begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}
alpar@9: p& = &x_1 &+&x_2 &+&x_3 \\
alpar@9: q& = &10 x_1 &+& 4 x_2 &+& 5 x_3 \\
alpar@9: r& = &2  x_1 &+& 2 x_2 &+& 6 x_3 \\
alpar@9: \end{array}
alpar@9: $$
alpar@9: \hspace{.5in} and bounds of variables
alpar@9: $$
alpar@9: \begin{array}{ccc}
alpar@9: \nonumber -\infty < p \leq 100 && 0 \leq x_1 < +\infty \\
alpar@9: \nonumber -\infty < q \leq 600 && 0 \leq x_2 < +\infty \\
alpar@9: \nonumber -\infty < r \leq 300 && 0 \leq x_3 < +\infty \\
alpar@9: \end{array}
alpar@9: $$
alpar@9: where $p, q, r$ are auxiliary variables (rows), and $x_1, x_2, x_3$ are
alpar@9: structural variables (columns).
alpar@9: 
alpar@9: The example C program shown below uses GLPK API routines in order to
alpar@9: solve this LP problem.\footnote{If you just need to solve LP or MIP
alpar@9: instance, you may write it in MPS or CPLEX LP format and then use the
alpar@9: GLPK stand-alone solver to obtain a solution. This is much less
alpar@9: time-consuming than programming in C with GLPK API routines.}
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: /* sample.c */
alpar@9: 
alpar@9: #include <stdio.h>
alpar@9: #include <stdlib.h>
alpar@9: #include <glpk.h>
alpar@9: 
alpar@9: int main(void)
alpar@9: {     glp_prob *lp;
alpar@9:       int ia[1+1000], ja[1+1000];
alpar@9:       double ar[1+1000], z, x1, x2, x3;
alpar@9: s1:   lp = glp_create_prob();
alpar@9: s2:   glp_set_prob_name(lp, "sample");
alpar@9: s3:   glp_set_obj_dir(lp, GLP_MAX);
alpar@9: s4:   glp_add_rows(lp, 3);
alpar@9: s5:   glp_set_row_name(lp, 1, "p");
alpar@9: s6:   glp_set_row_bnds(lp, 1, GLP_UP, 0.0, 100.0);
alpar@9: s7:   glp_set_row_name(lp, 2, "q");
alpar@9: s8:   glp_set_row_bnds(lp, 2, GLP_UP, 0.0, 600.0);
alpar@9: s9:   glp_set_row_name(lp, 3, "r");
alpar@9: s10:  glp_set_row_bnds(lp, 3, GLP_UP, 0.0, 300.0);
alpar@9: s11:  glp_add_cols(lp, 3);
alpar@9: s12:  glp_set_col_name(lp, 1, "x1");
alpar@9: s13:  glp_set_col_bnds(lp, 1, GLP_LO, 0.0, 0.0);
alpar@9: s14:  glp_set_obj_coef(lp, 1, 10.0);
alpar@9: s15:  glp_set_col_name(lp, 2, "x2");
alpar@9: s16:  glp_set_col_bnds(lp, 2, GLP_LO, 0.0, 0.0);
alpar@9: s17:  glp_set_obj_coef(lp, 2, 6.0);
alpar@9: s18:  glp_set_col_name(lp, 3, "x3");
alpar@9: s19:  glp_set_col_bnds(lp, 3, GLP_LO, 0.0, 0.0);
alpar@9: s20:  glp_set_obj_coef(lp, 3, 4.0);
alpar@9: s21:  ia[1] = 1, ja[1] = 1, ar[1] =  1.0; /* a[1,1] =  1 */
alpar@9: s22:  ia[2] = 1, ja[2] = 2, ar[2] =  1.0; /* a[1,2] =  1 */
alpar@9: s23:  ia[3] = 1, ja[3] = 3, ar[3] =  1.0; /* a[1,3] =  1 */
alpar@9: s24:  ia[4] = 2, ja[4] = 1, ar[4] = 10.0; /* a[2,1] = 10 */
alpar@9: s25:  ia[5] = 3, ja[5] = 1, ar[5] =  2.0; /* a[3,1] =  2 */
alpar@9: s26:  ia[6] = 2, ja[6] = 2, ar[6] =  4.0; /* a[2,2] =  4 */
alpar@9: s27:  ia[7] = 3, ja[7] = 2, ar[7] =  2.0; /* a[3,2] =  2 */
alpar@9: s28:  ia[8] = 2, ja[8] = 3, ar[8] =  5.0; /* a[2,3] =  5 */
alpar@9: s29:  ia[9] = 3, ja[9] = 3, ar[9] =  6.0; /* a[3,3] =  6 */
alpar@9: s30:  glp_load_matrix(lp, 9, ia, ja, ar);
alpar@9: s31:  glp_simplex(lp, NULL);
alpar@9: s32:  z = glp_get_obj_val(lp);
alpar@9: s33:  x1 = glp_get_col_prim(lp, 1);
alpar@9: s34:  x2 = glp_get_col_prim(lp, 2);
alpar@9: s35:  x3 = glp_get_col_prim(lp, 3);
alpar@9: s36:  printf("\nz = %g; x1 = %g; x2 = %g; x3 = %g\n",
alpar@9:          z, x1, x2, x3);
alpar@9: s37:  glp_delete_prob(lp);
alpar@9:       return 0;
alpar@9: }
alpar@9: 
alpar@9: /* eof */
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: The statement \verb|s1| creates a problem object. Being created the
alpar@9: object is initially empty. The statement \verb|s2| assigns a symbolic
alpar@9: name to the problem object.
alpar@9: 
alpar@9: The statement \verb|s3| calls the routine \verb|glp_set_obj_dir| in
alpar@9: order to set the optimization direction flag, where \verb|GLP_MAX| means
alpar@9: maximization.
alpar@9: 
alpar@9: The statement \verb|s4| adds three rows to the problem object.
alpar@9: 
alpar@9: The statement \verb|s5| assigns the symbolic name `\verb|p|' to the
alpar@9: first row, and the statement \verb|s6| sets the type and bounds of the
alpar@9: first row, where \verb|GLP_UP| means that the row has an upper bound.
alpar@9: The statements \verb|s7|, \verb|s8|, \verb|s9|, \verb|s10| are used in
alpar@9: the same way in order to assign the symbolic names `\verb|q|' and
alpar@9: `\verb|r|' to the second and third rows and set their types and bounds.
alpar@9: 
alpar@9: The statement \verb|s11| adds three columns to the problem object.
alpar@9: 
alpar@9: The statement \verb|s12| assigns the symbolic name `\verb|x1|' to the
alpar@9: first column, the statement \verb|s13| sets the type and bounds of the
alpar@9: first column, where \verb|GLP_LO| means that the column has an lower
alpar@9: bound, and the statement \verb|s14| sets the objective coefficient for
alpar@9: the first column. The statements \verb|s15|---\verb|s20| are used in the
alpar@9: same way in order to assign the symbolic names `\verb|x2|' and
alpar@9: `\verb|x3|' to the second and third columns and set their types, bounds,
alpar@9: and objective coefficients.
alpar@9: 
alpar@9: The statements \verb|s21|---\verb|s29| prepare non-zero elements of the
alpar@9: constraint matrix (i.e. constraint coefficients). Row indices of each
alpar@9: element are stored in the array \verb|ia|, column indices are stored in
alpar@9: the array \verb|ja|, and numerical values of corresponding elements are
alpar@9: stored in the array \verb|ar|. Then the statement \verb|s30| calls
alpar@9: the routine \verb|glp_load_matrix|, which loads information from these
alpar@9: three arrays into the problem object.
alpar@9: 
alpar@9: Now all data have been entered into the problem object, and therefore
alpar@9: the statement \verb|s31| calls the routine \verb|glp_simplex|, which is
alpar@9: a driver to the simplex method, in order to solve the LP problem. This
alpar@9: routine finds an optimal solution and stores all relevant information
alpar@9: back into the problem object.
alpar@9: 
alpar@9: The statement \verb|s32| obtains a computed value of the objective
alpar@9: function, and the statements \verb|s33|---\verb|s35| obtain computed
alpar@9: values of structural variables (columns), which correspond to the
alpar@9: optimal basic solution found by the solver.
alpar@9: 
alpar@9: The statement \verb|s36| writes the optimal solution to the standard
alpar@9: output. The printout may look like follows:
alpar@9: 
alpar@9: {\footnotesize
alpar@9: \begin{verbatim}
alpar@9: *     0:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (0)
alpar@9: *     2:   objval =   7.333333333e+02   infeas =   0.000000000e+00 (0)
alpar@9: OPTIMAL SOLUTION FOUND
alpar@9: 
alpar@9: z = 733.333; x1 = 33.3333; x2 = 66.6667; x3 = 0
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: }
alpar@9: 
alpar@9: Finally, the statement \verb|s37| calls the routine
alpar@9: \verb|glp_delete_prob|, which frees all the memory allocated to the
alpar@9: problem object.
alpar@9: 
alpar@9: \subsection{Compiling}
alpar@9: 
alpar@9: The GLPK package has the only header file \verb|glpk.h|, which should
alpar@9: be available on compiling a C (or C++) program using GLPK API routines.
alpar@9: 
alpar@9: If the header file is installed in the default location
alpar@9: \verb|/usr/local/include|, the following typical command may be used to
alpar@9: compile, say, the example C program described above with the GNU C
alpar@9: compiler:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    $ gcc -c sample.c
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: If \verb|glpk.h| is not in the default location, the corresponding
alpar@9: directory containing it should be made known to the C compiler through
alpar@9: \verb|-I| option, for example:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    $ gcc -I/foo/bar/glpk-4.15/include -c sample.c
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: In any case the compilation results in an object file \verb|sample.o|.
alpar@9: 
alpar@9: \subsection{Linking}
alpar@9: 
alpar@9: The GLPK library is a single file \verb|libglpk.a|. (On systems which
alpar@9: support shared libraries there may be also a shared version of the
alpar@9: library \verb|libglpk.so|.)
alpar@9: 
alpar@9: If the library is installed in the default
alpar@9: location \verb|/usr/local/lib|, the following typical command may be
alpar@9: used to link, say, the example C program described above against with
alpar@9: the library:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    $ gcc sample.o -lglpk -lm
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: If the GLPK library is not in the default location, the corresponding
alpar@9: directory containing it should be made known to the linker through
alpar@9: \verb|-L| option, for example:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    $ gcc -L/foo/bar/glpk-4.15 sample.o -lglpk -lm
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: Depending on configuration of the package linking against with the GLPK
alpar@9: library may require the following optional libraries:
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: \begin{tabular}{@{}ll}
alpar@9: \verb|-lgmp|  & the GNU MP bignum library; \\
alpar@9: \verb|-lz|    & the zlib data compression library; \\
alpar@9: \verb|-lltdl| & the GNU ltdl shared support library. \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: \noindent
alpar@9: in which case corresponding libraries should be also made known to the
alpar@9: linker, for example:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    $ gcc sample.o -lglpk -lz -lltdl -lm
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: For more details about configuration options of the GLPK package see
alpar@9: Appendix \ref{install}, page \pageref{install}.
alpar@9: 
alpar@9: %* eof *%