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