glpk01.tex

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

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