1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/doc/glpk01.tex Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,348 @@
1.4 +%* glpk01.tex *%
1.5 +
1.6 +\chapter{Introduction}
1.7 +
1.8 +GLPK (\underline{G}NU \underline{L}inear \underline{P}rogramming
1.9 +\underline{K}it) is a set of routines written in the ANSI C programming
1.10 +language and organized in the form of a callable library. It is intended
1.11 +for solving linear programming (LP), mixed integer programming (MIP),
1.12 +and other related problems.
1.13 +
1.14 +\section{LP problem}
1.15 +\label{seclp}
1.16 +
1.17 +GLPK assumes the following formulation of {\it linear programming (LP)}
1.18 +problem:
1.19 +
1.20 +\medskip
1.21 +
1.22 +\noindent
1.23 +\hspace{.5in} minimize (or maximize)
1.24 +$$z = c_1x_{m+1} + c_2x_{m+2} + \dots + c_nx_{m+n} + c_0 \eqno (1.1)$$
1.25 +\hspace{.5in} subject to linear constraints
1.26 +$$
1.27 +\begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}
1.28 +x_1&=&a_{11}x_{m+1}&+&a_{12}x_{m+2}&+ \dots +&a_{1n}x_{m+n} \\
1.29 +x_2&=&a_{21}x_{m+1}&+&a_{22}x_{m+2}&+ \dots +&a_{2n}x_{m+n} \\
1.30 +\multicolumn{7}{c}
1.31 +{.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .} \\
1.32 +x_m&=&a_{m1}x_{m+1}&+&a_{m2}x_{m+2}&+ \dots +&a_{mn}x_{m+n} \\
1.33 +\end{array} \eqno (1.2)
1.34 +$$
1.35 +\hspace{.5in} and bounds of variables
1.36 +$$
1.37 +\begin{array}{r@{\:}c@{\:}c@{\:}c@{\:}l}
1.38 +l_1&\leq&x_1&\leq&u_1 \\
1.39 +l_2&\leq&x_2&\leq&u_2 \\
1.40 +\multicolumn{5}{c}{.\ \ .\ \ .\ \ .\ \ .}\\
1.41 +l_{m+n}&\leq&x_{m+n}&\leq&u_{m+n} \\
1.42 +\end{array} \eqno (1.3)
1.43 +$$
1.44 +where: $x_1, x_2, \dots, x_m$ are auxiliary variables;
1.45 +$x_{m+1}, x_{m+2}, \dots, x_{m+n}$ are\linebreak structural variables;
1.46 +$z$ is the objective function;
1.47 +$c_1, c_2, \dots, c_n$ are objective coefficients;
1.48 +$c_0$ is the constant term (``shift'') of the objective function;
1.49 +$a_{11}, a_{12}, \dots, a_{mn}$ are constraint coefficients;
1.50 +$l_1, l_2, \dots, l_{m+n}$ are lower bounds of variables;
1.51 +$u_1, u_2, \dots, u_{m+n}$ are upper bounds of variables.
1.52 +
1.53 +Auxiliary variables are also called {\it rows}, because they correspond
1.54 +to rows of the constraint matrix (i.e. a matrix built of the constraint
1.55 +coefficients). Similarly, structural variables are also called
1.56 +{\it columns}, because they correspond to columns of the constraint
1.57 +matrix.
1.58 +
1.59 +Bounds of variables can be finite as well as infinite. Besides, lower
1.60 +and upper bounds can be equal to each other. Thus, the following types
1.61 +of variables are possible:
1.62 +\begin{center}
1.63 +\begin{tabular}{r@{}c@{}ll}
1.64 +\multicolumn{3}{c}{Bounds of variable} & Type of variable \\
1.65 +\hline
1.66 +$-\infty <$ &$\ x_k\ $& $< +\infty$ & Free (unbounded) variable \\
1.67 +$l_k \leq$ &$\ x_k\ $& $< +\infty$ & Variable with lower bound \\
1.68 +$-\infty <$ &$\ x_k\ $& $\leq u_k$ & Variable with upper bound \\
1.69 +$l_k \leq$ &$\ x_k\ $& $\leq u_k$ & Double-bounded variable \\
1.70 +$l_k =$ &$\ x_k\ $& $= u_k$ & Fixed variable \\
1.71 +\end{tabular}
1.72 +\end{center}
1.73 +\noindent
1.74 +Note that the types of variables shown above are applicable to
1.75 +structural as well as to auxiliary variables.
1.76 +
1.77 +To solve the LP problem (1.1)---(1.3) is to find such values of all
1.78 +structural and auxiliary variables, which:
1.79 +
1.80 +$\bullet$ satisfy to all the linear constraints (1.2), and
1.81 +
1.82 +$\bullet$ are within their bounds (1.3), and
1.83 +
1.84 +$\bullet$ provide the smallest (in case of minimization) or the largest
1.85 +(in case of maximization) value of the objective function (1.1).
1.86 +
1.87 +\section{MIP problem}
1.88 +
1.89 +{\it Mixed integer linear programming (MIP)} problem is LP problem in
1.90 +which some variables are additionally required to be integer.
1.91 +
1.92 +GLPK assumes that MIP problem has the same formulation as ordinary
1.93 +(pure) LP problem (1.1)---(1.3), i.e. includes auxiliary and structural
1.94 +variables, which may have lower and/or upper bounds. However, in case of
1.95 +MIP problem some variables may be required to be integer. This
1.96 +additional constraint means that a value of each {\it integer variable}
1.97 +must be only integer number. (Should note that GLPK allows only
1.98 +structural variables to be of integer kind.)
1.99 +
1.100 +\section{Using the package}
1.101 +
1.102 +\subsection{Brief example}
1.103 +
1.104 +In order to understand what GLPK is from the user's standpoint,
1.105 +consider the following simple LP problem:
1.106 +
1.107 +\medskip
1.108 +
1.109 +\noindent
1.110 +\hspace{.5in} maximize
1.111 +$$z = 10 x_1 + 6 x_2 + 4 x_3$$
1.112 +\hspace{.5in} subject to
1.113 +$$
1.114 +\begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}
1.115 +x_1 &+&x_2 &+&x_3 &\leq 100 \\
1.116 +10 x_1 &+& 4 x_2 & +&5 x_3 & \leq 600 \\
1.117 +2 x_1 &+& 2 x_2 & +& 6 x_3 & \leq 300 \\
1.118 +\end{array}
1.119 +$$
1.120 +\hspace{.5in} where all variables are non-negative
1.121 +$$x_1 \geq 0, \ x_2 \geq 0, \ x_3 \geq 0$$
1.122 +
1.123 +At first this LP problem should be transformed to the standard form
1.124 +(1.1)---(1.3). This can be easily done by introducing auxiliary
1.125 +variables, by one for each original inequality constraint. Thus, the
1.126 +problem can be reformulated as follows:
1.127 +
1.128 +\medskip
1.129 +
1.130 +\noindent
1.131 +\hspace{.5in} maximize
1.132 +$$z = 10 x_1 + 6 x_2 + 4 x_3$$
1.133 +\hspace{.5in} subject to
1.134 +$$
1.135 +\begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}
1.136 +p& = &x_1 &+&x_2 &+&x_3 \\
1.137 +q& = &10 x_1 &+& 4 x_2 &+& 5 x_3 \\
1.138 +r& = &2 x_1 &+& 2 x_2 &+& 6 x_3 \\
1.139 +\end{array}
1.140 +$$
1.141 +\hspace{.5in} and bounds of variables
1.142 +$$
1.143 +\begin{array}{ccc}
1.144 +\nonumber -\infty < p \leq 100 && 0 \leq x_1 < +\infty \\
1.145 +\nonumber -\infty < q \leq 600 && 0 \leq x_2 < +\infty \\
1.146 +\nonumber -\infty < r \leq 300 && 0 \leq x_3 < +\infty \\
1.147 +\end{array}
1.148 +$$
1.149 +where $p, q, r$ are auxiliary variables (rows), and $x_1, x_2, x_3$ are
1.150 +structural variables (columns).
1.151 +
1.152 +The example C program shown below uses GLPK API routines in order to
1.153 +solve this LP problem.\footnote{If you just need to solve LP or MIP
1.154 +instance, you may write it in MPS or CPLEX LP format and then use the
1.155 +GLPK stand-alone solver to obtain a solution. This is much less
1.156 +time-consuming than programming in C with GLPK API routines.}
1.157 +
1.158 +\newpage
1.159 +
1.160 +\begin{verbatim}
1.161 +/* sample.c */
1.162 +
1.163 +#include <stdio.h>
1.164 +#include <stdlib.h>
1.165 +#include <glpk.h>
1.166 +
1.167 +int main(void)
1.168 +{ glp_prob *lp;
1.169 + int ia[1+1000], ja[1+1000];
1.170 + double ar[1+1000], z, x1, x2, x3;
1.171 +s1: lp = glp_create_prob();
1.172 +s2: glp_set_prob_name(lp, "sample");
1.173 +s3: glp_set_obj_dir(lp, GLP_MAX);
1.174 +s4: glp_add_rows(lp, 3);
1.175 +s5: glp_set_row_name(lp, 1, "p");
1.176 +s6: glp_set_row_bnds(lp, 1, GLP_UP, 0.0, 100.0);
1.177 +s7: glp_set_row_name(lp, 2, "q");
1.178 +s8: glp_set_row_bnds(lp, 2, GLP_UP, 0.0, 600.0);
1.179 +s9: glp_set_row_name(lp, 3, "r");
1.180 +s10: glp_set_row_bnds(lp, 3, GLP_UP, 0.0, 300.0);
1.181 +s11: glp_add_cols(lp, 3);
1.182 +s12: glp_set_col_name(lp, 1, "x1");
1.183 +s13: glp_set_col_bnds(lp, 1, GLP_LO, 0.0, 0.0);
1.184 +s14: glp_set_obj_coef(lp, 1, 10.0);
1.185 +s15: glp_set_col_name(lp, 2, "x2");
1.186 +s16: glp_set_col_bnds(lp, 2, GLP_LO, 0.0, 0.0);
1.187 +s17: glp_set_obj_coef(lp, 2, 6.0);
1.188 +s18: glp_set_col_name(lp, 3, "x3");
1.189 +s19: glp_set_col_bnds(lp, 3, GLP_LO, 0.0, 0.0);
1.190 +s20: glp_set_obj_coef(lp, 3, 4.0);
1.191 +s21: ia[1] = 1, ja[1] = 1, ar[1] = 1.0; /* a[1,1] = 1 */
1.192 +s22: ia[2] = 1, ja[2] = 2, ar[2] = 1.0; /* a[1,2] = 1 */
1.193 +s23: ia[3] = 1, ja[3] = 3, ar[3] = 1.0; /* a[1,3] = 1 */
1.194 +s24: ia[4] = 2, ja[4] = 1, ar[4] = 10.0; /* a[2,1] = 10 */
1.195 +s25: ia[5] = 3, ja[5] = 1, ar[5] = 2.0; /* a[3,1] = 2 */
1.196 +s26: ia[6] = 2, ja[6] = 2, ar[6] = 4.0; /* a[2,2] = 4 */
1.197 +s27: ia[7] = 3, ja[7] = 2, ar[7] = 2.0; /* a[3,2] = 2 */
1.198 +s28: ia[8] = 2, ja[8] = 3, ar[8] = 5.0; /* a[2,3] = 5 */
1.199 +s29: ia[9] = 3, ja[9] = 3, ar[9] = 6.0; /* a[3,3] = 6 */
1.200 +s30: glp_load_matrix(lp, 9, ia, ja, ar);
1.201 +s31: glp_simplex(lp, NULL);
1.202 +s32: z = glp_get_obj_val(lp);
1.203 +s33: x1 = glp_get_col_prim(lp, 1);
1.204 +s34: x2 = glp_get_col_prim(lp, 2);
1.205 +s35: x3 = glp_get_col_prim(lp, 3);
1.206 +s36: printf("\nz = %g; x1 = %g; x2 = %g; x3 = %g\n",
1.207 + z, x1, x2, x3);
1.208 +s37: glp_delete_prob(lp);
1.209 + return 0;
1.210 +}
1.211 +
1.212 +/* eof */
1.213 +\end{verbatim}
1.214 +
1.215 +The statement \verb|s1| creates a problem object. Being created the
1.216 +object is initially empty. The statement \verb|s2| assigns a symbolic
1.217 +name to the problem object.
1.218 +
1.219 +The statement \verb|s3| calls the routine \verb|glp_set_obj_dir| in
1.220 +order to set the optimization direction flag, where \verb|GLP_MAX| means
1.221 +maximization.
1.222 +
1.223 +The statement \verb|s4| adds three rows to the problem object.
1.224 +
1.225 +The statement \verb|s5| assigns the symbolic name `\verb|p|' to the
1.226 +first row, and the statement \verb|s6| sets the type and bounds of the
1.227 +first row, where \verb|GLP_UP| means that the row has an upper bound.
1.228 +The statements \verb|s7|, \verb|s8|, \verb|s9|, \verb|s10| are used in
1.229 +the same way in order to assign the symbolic names `\verb|q|' and
1.230 +`\verb|r|' to the second and third rows and set their types and bounds.
1.231 +
1.232 +The statement \verb|s11| adds three columns to the problem object.
1.233 +
1.234 +The statement \verb|s12| assigns the symbolic name `\verb|x1|' to the
1.235 +first column, the statement \verb|s13| sets the type and bounds of the
1.236 +first column, where \verb|GLP_LO| means that the column has an lower
1.237 +bound, and the statement \verb|s14| sets the objective coefficient for
1.238 +the first column. The statements \verb|s15|---\verb|s20| are used in the
1.239 +same way in order to assign the symbolic names `\verb|x2|' and
1.240 +`\verb|x3|' to the second and third columns and set their types, bounds,
1.241 +and objective coefficients.
1.242 +
1.243 +The statements \verb|s21|---\verb|s29| prepare non-zero elements of the
1.244 +constraint matrix (i.e. constraint coefficients). Row indices of each
1.245 +element are stored in the array \verb|ia|, column indices are stored in
1.246 +the array \verb|ja|, and numerical values of corresponding elements are
1.247 +stored in the array \verb|ar|. Then the statement \verb|s30| calls
1.248 +the routine \verb|glp_load_matrix|, which loads information from these
1.249 +three arrays into the problem object.
1.250 +
1.251 +Now all data have been entered into the problem object, and therefore
1.252 +the statement \verb|s31| calls the routine \verb|glp_simplex|, which is
1.253 +a driver to the simplex method, in order to solve the LP problem. This
1.254 +routine finds an optimal solution and stores all relevant information
1.255 +back into the problem object.
1.256 +
1.257 +The statement \verb|s32| obtains a computed value of the objective
1.258 +function, and the statements \verb|s33|---\verb|s35| obtain computed
1.259 +values of structural variables (columns), which correspond to the
1.260 +optimal basic solution found by the solver.
1.261 +
1.262 +The statement \verb|s36| writes the optimal solution to the standard
1.263 +output. The printout may look like follows:
1.264 +
1.265 +{\footnotesize
1.266 +\begin{verbatim}
1.267 +* 0: objval = 0.000000000e+00 infeas = 0.000000000e+00 (0)
1.268 +* 2: objval = 7.333333333e+02 infeas = 0.000000000e+00 (0)
1.269 +OPTIMAL SOLUTION FOUND
1.270 +
1.271 +z = 733.333; x1 = 33.3333; x2 = 66.6667; x3 = 0
1.272 +\end{verbatim}
1.273 +
1.274 +}
1.275 +
1.276 +Finally, the statement \verb|s37| calls the routine
1.277 +\verb|glp_delete_prob|, which frees all the memory allocated to the
1.278 +problem object.
1.279 +
1.280 +\subsection{Compiling}
1.281 +
1.282 +The GLPK package has the only header file \verb|glpk.h|, which should
1.283 +be available on compiling a C (or C++) program using GLPK API routines.
1.284 +
1.285 +If the header file is installed in the default location
1.286 +\verb|/usr/local/include|, the following typical command may be used to
1.287 +compile, say, the example C program described above with the GNU C
1.288 +compiler:
1.289 +
1.290 +\begin{verbatim}
1.291 + $ gcc -c sample.c
1.292 +\end{verbatim}
1.293 +
1.294 +If \verb|glpk.h| is not in the default location, the corresponding
1.295 +directory containing it should be made known to the C compiler through
1.296 +\verb|-I| option, for example:
1.297 +
1.298 +\begin{verbatim}
1.299 + $ gcc -I/foo/bar/glpk-4.15/include -c sample.c
1.300 +\end{verbatim}
1.301 +
1.302 +In any case the compilation results in an object file \verb|sample.o|.
1.303 +
1.304 +\subsection{Linking}
1.305 +
1.306 +The GLPK library is a single file \verb|libglpk.a|. (On systems which
1.307 +support shared libraries there may be also a shared version of the
1.308 +library \verb|libglpk.so|.)
1.309 +
1.310 +If the library is installed in the default
1.311 +location \verb|/usr/local/lib|, the following typical command may be
1.312 +used to link, say, the example C program described above against with
1.313 +the library:
1.314 +
1.315 +\begin{verbatim}
1.316 + $ gcc sample.o -lglpk -lm
1.317 +\end{verbatim}
1.318 +
1.319 +If the GLPK library is not in the default location, the corresponding
1.320 +directory containing it should be made known to the linker through
1.321 +\verb|-L| option, for example:
1.322 +
1.323 +\begin{verbatim}
1.324 + $ gcc -L/foo/bar/glpk-4.15 sample.o -lglpk -lm
1.325 +\end{verbatim}
1.326 +
1.327 +Depending on configuration of the package linking against with the GLPK
1.328 +library may require the following optional libraries:
1.329 +
1.330 +\bigskip
1.331 +
1.332 +\begin{tabular}{@{}ll}
1.333 +\verb|-lgmp| & the GNU MP bignum library; \\
1.334 +\verb|-lz| & the zlib data compression library; \\
1.335 +\verb|-lltdl| & the GNU ltdl shared support library. \\
1.336 +\end{tabular}
1.337 +
1.338 +\bigskip
1.339 +
1.340 +\noindent
1.341 +in which case corresponding libraries should be also made known to the
1.342 +linker, for example:
1.343 +
1.344 +\begin{verbatim}
1.345 + $ gcc sample.o -lglpk -lz -lltdl -lm
1.346 +\end{verbatim}
1.347 +
1.348 +For more details about configuration options of the GLPK package see
1.349 +Appendix \ref{install}, page \pageref{install}.
1.350 +
1.351 +%* eof *%