lemon-project-template-glpk: deps/glpk/doc/glpk01.tex comparison

lemon-project-template-glpk

comparison deps/glpk/doc/glpk01.tex @ 9:33de93886c88

Import GLPK 4.47

author	Alpar Juttner <alpar@cs.elte.hu>
date	Sun, 06 Nov 2011 20:59:10 +0100
parents
children

comparison

equal deleted inserted replaced

--1:000000000000
+:0315aeb3b8d6
+%* 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 *%