COIN-OR::LEMON - Graph Library

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

subpack-glpk
Last change on this file was 9:33de93886c88, checked in by Alpar Juttner <alpar@…>, 13 years ago

Import GLPK 4.47

File size: 12.1 KB
Line 
1%* glpk01.tex *%
2
3\chapter{Introduction}
4
5GLPK (\underline{G}NU \underline{L}inear \underline{P}rogramming
6\underline{K}it) is a set of routines written in the ANSI C programming
7language and organized in the form of a callable library. It is intended
8for solving linear programming (LP), mixed integer programming (MIP),
9and other related problems.
10
11\section{LP problem}
12\label{seclp}
13
14GLPK assumes the following formulation of {\it linear programming (LP)}
15problem:
16
17\medskip
18
19\noindent
20\hspace{.5in} minimize (or maximize)
21$$z = c_1x_{m+1} + c_2x_{m+2} + \dots + c_nx_{m+n} + c_0 \eqno (1.1)$$
22\hspace{.5in} subject to linear constraints
23$$
24\begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}
25x_1&=&a_{11}x_{m+1}&+&a_{12}x_{m+2}&+ \dots +&a_{1n}x_{m+n} \\
26x_2&=&a_{21}x_{m+1}&+&a_{22}x_{m+2}&+ \dots +&a_{2n}x_{m+n} \\
27\multicolumn{7}{c}
28{.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .} \\
29x_m&=&a_{m1}x_{m+1}&+&a_{m2}x_{m+2}&+ \dots +&a_{mn}x_{m+n} \\
30\end{array} \eqno (1.2)
31$$
32\hspace{.5in} and bounds of variables
33$$
34\begin{array}{r@{\:}c@{\:}c@{\:}c@{\:}l}
35l_1&\leq&x_1&\leq&u_1 \\
36l_2&\leq&x_2&\leq&u_2 \\
37\multicolumn{5}{c}{.\ \ .\ \ .\ \ .\ \ .}\\
38l_{m+n}&\leq&x_{m+n}&\leq&u_{m+n} \\
39\end{array} \eqno (1.3)
40$$
41where: $x_1, x_2, \dots, x_m$ are auxiliary variables;
42$x_{m+1}, x_{m+2}, \dots, x_{m+n}$ are\linebreak structural variables;
43$z$ is the objective function;
44$c_1, c_2, \dots, c_n$ are objective coefficients;
45$c_0$ is the constant term (``shift'') of the objective function;
46$a_{11}, a_{12}, \dots, a_{mn}$ are constraint coefficients;
47$l_1, l_2, \dots, l_{m+n}$ are lower bounds of variables;
48$u_1, u_2, \dots, u_{m+n}$ are upper bounds of variables.
49
50Auxiliary variables are also called {\it rows}, because they correspond
51to rows of the constraint matrix (i.e. a matrix built of the constraint
52coefficients). Similarly, structural variables are also called
53{\it columns}, because they correspond to columns of the constraint
54matrix.
55
56Bounds of variables can be finite as well as infinite. Besides, lower
57and upper bounds can be equal to each other. Thus, the following types
58of variables are possible:
59\begin{center}
60\begin{tabular}{r@{}c@{}ll}
61\multicolumn{3}{c}{Bounds of variable} & Type of variable \\
62\hline
63$-\infty <$ &$\ x_k\ $& $< +\infty$ & Free (unbounded) variable \\
64$l_k \leq$ &$\ x_k\ $& $< +\infty$  & Variable with lower bound \\
65$-\infty <$ &$\ x_k\ $& $\leq u_k$  & Variable with upper bound \\
66$l_k \leq$ &$\ x_k\ $& $\leq u_k$   & Double-bounded variable \\
67$l_k =$ &$\ x_k\ $& $= u_k$         & Fixed variable \\
68\end{tabular}
69\end{center}
70\noindent
71Note that the types of variables shown above are applicable to
72structural as well as to auxiliary variables.
73
74To solve the LP problem (1.1)---(1.3) is to find such values of all
75structural and auxiliary variables, which:
76
77$\bullet$ satisfy to all the linear constraints (1.2), and
78
79$\bullet$ are within their bounds (1.3), and
80
81$\bullet$ provide the smallest (in case of minimization) or the largest
82(in case of maximization) value of the objective function (1.1).
83
84\section{MIP problem}
85
86{\it Mixed integer linear programming (MIP)} problem is LP problem in
87which some variables are additionally required to be integer.
88
89GLPK assumes that MIP problem has the same formulation as ordinary
90(pure) LP problem (1.1)---(1.3), i.e. includes auxiliary and structural
91variables, which may have lower and/or upper bounds. However, in case of
92MIP problem some variables may be required to be integer. This
93additional constraint means that a value of each {\it integer variable}
94must be only integer number. (Should note that GLPK allows only
95structural variables to be of integer kind.)
96
97\section{Using the package}
98
99\subsection{Brief example}
100
101In order to understand what GLPK is from the user's standpoint,
102consider the following simple LP problem:
103
104\medskip
105
106\noindent
107\hspace{.5in} maximize
108$$z = 10 x_1 + 6 x_2 + 4 x_3$$
109\hspace{.5in} subject to
110$$
111\begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}
112x_1 &+&x_2 &+&x_3 &\leq 100 \\
11310 x_1 &+& 4 x_2 & +&5 x_3 & \leq 600 \\
1142 x_1 &+& 2 x_2 & +& 6 x_3 & \leq 300 \\
115\end{array}
116$$
117\hspace{.5in} where all variables are non-negative
118$$x_1 \geq 0, \ x_2 \geq 0, \ x_3 \geq 0$$
119
120At first this LP problem should be transformed to the standard form
121(1.1)---(1.3). This can be easily done by introducing auxiliary
122variables, by one for each original inequality constraint. Thus, the
123problem can be reformulated as follows:
124
125\medskip
126
127\noindent
128\hspace{.5in} maximize
129$$z = 10 x_1 + 6 x_2 + 4 x_3$$
130\hspace{.5in} subject to
131$$
132\begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}
133p& = &x_1 &+&x_2 &+&x_3 \\
134q& = &10 x_1 &+& 4 x_2 &+& 5 x_3 \\
135r& = &2  x_1 &+& 2 x_2 &+& 6 x_3 \\
136\end{array}
137$$
138\hspace{.5in} and bounds of variables
139$$
140\begin{array}{ccc}
141\nonumber -\infty < p \leq 100 && 0 \leq x_1 < +\infty \\
142\nonumber -\infty < q \leq 600 && 0 \leq x_2 < +\infty \\
143\nonumber -\infty < r \leq 300 && 0 \leq x_3 < +\infty \\
144\end{array}
145$$
146where $p, q, r$ are auxiliary variables (rows), and $x_1, x_2, x_3$ are
147structural variables (columns).
148
149The example C program shown below uses GLPK API routines in order to
150solve this LP problem.\footnote{If you just need to solve LP or MIP
151instance, you may write it in MPS or CPLEX LP format and then use the
152GLPK stand-alone solver to obtain a solution. This is much less
153time-consuming than programming in C with GLPK API routines.}
154
155\newpage
156
157\begin{verbatim}
158/* sample.c */
159
160#include <stdio.h>
161#include <stdlib.h>
162#include <glpk.h>
163
164int main(void)
165{     glp_prob *lp;
166      int ia[1+1000], ja[1+1000];
167      double ar[1+1000], z, x1, x2, x3;
168s1:   lp = glp_create_prob();
169s2:   glp_set_prob_name(lp, "sample");
170s3:   glp_set_obj_dir(lp, GLP_MAX);
171s4:   glp_add_rows(lp, 3);
172s5:   glp_set_row_name(lp, 1, "p");
173s6:   glp_set_row_bnds(lp, 1, GLP_UP, 0.0, 100.0);
174s7:   glp_set_row_name(lp, 2, "q");
175s8:   glp_set_row_bnds(lp, 2, GLP_UP, 0.0, 600.0);
176s9:   glp_set_row_name(lp, 3, "r");
177s10:  glp_set_row_bnds(lp, 3, GLP_UP, 0.0, 300.0);
178s11:  glp_add_cols(lp, 3);
179s12:  glp_set_col_name(lp, 1, "x1");
180s13:  glp_set_col_bnds(lp, 1, GLP_LO, 0.0, 0.0);
181s14:  glp_set_obj_coef(lp, 1, 10.0);
182s15:  glp_set_col_name(lp, 2, "x2");
183s16:  glp_set_col_bnds(lp, 2, GLP_LO, 0.0, 0.0);
184s17:  glp_set_obj_coef(lp, 2, 6.0);
185s18:  glp_set_col_name(lp, 3, "x3");
186s19:  glp_set_col_bnds(lp, 3, GLP_LO, 0.0, 0.0);
187s20:  glp_set_obj_coef(lp, 3, 4.0);
188s21:  ia[1] = 1, ja[1] = 1, ar[1] =  1.0; /* a[1,1] =  1 */
189s22:  ia[2] = 1, ja[2] = 2, ar[2] =  1.0; /* a[1,2] =  1 */
190s23:  ia[3] = 1, ja[3] = 3, ar[3] =  1.0; /* a[1,3] =  1 */
191s24:  ia[4] = 2, ja[4] = 1, ar[4] = 10.0; /* a[2,1] = 10 */
192s25:  ia[5] = 3, ja[5] = 1, ar[5] =  2.0; /* a[3,1] =  2 */
193s26:  ia[6] = 2, ja[6] = 2, ar[6] =  4.0; /* a[2,2] =  4 */
194s27:  ia[7] = 3, ja[7] = 2, ar[7] =  2.0; /* a[3,2] =  2 */
195s28:  ia[8] = 2, ja[8] = 3, ar[8] =  5.0; /* a[2,3] =  5 */
196s29:  ia[9] = 3, ja[9] = 3, ar[9] =  6.0; /* a[3,3] =  6 */
197s30:  glp_load_matrix(lp, 9, ia, ja, ar);
198s31:  glp_simplex(lp, NULL);
199s32:  z = glp_get_obj_val(lp);
200s33:  x1 = glp_get_col_prim(lp, 1);
201s34:  x2 = glp_get_col_prim(lp, 2);
202s35:  x3 = glp_get_col_prim(lp, 3);
203s36:  printf("\nz = %g; x1 = %g; x2 = %g; x3 = %g\n",
204         z, x1, x2, x3);
205s37:  glp_delete_prob(lp);
206      return 0;
207}
208
209/* eof */
210\end{verbatim}
211
212The statement \verb|s1| creates a problem object. Being created the
213object is initially empty. The statement \verb|s2| assigns a symbolic
214name to the problem object.
215
216The statement \verb|s3| calls the routine \verb|glp_set_obj_dir| in
217order to set the optimization direction flag, where \verb|GLP_MAX| means
218maximization.
219
220The statement \verb|s4| adds three rows to the problem object.
221
222The statement \verb|s5| assigns the symbolic name `\verb|p|' to the
223first row, and the statement \verb|s6| sets the type and bounds of the
224first row, where \verb|GLP_UP| means that the row has an upper bound.
225The statements \verb|s7|, \verb|s8|, \verb|s9|, \verb|s10| are used in
226the same way in order to assign the symbolic names `\verb|q|' and
227`\verb|r|' to the second and third rows and set their types and bounds.
228
229The statement \verb|s11| adds three columns to the problem object.
230
231The statement \verb|s12| assigns the symbolic name `\verb|x1|' to the
232first column, the statement \verb|s13| sets the type and bounds of the
233first column, where \verb|GLP_LO| means that the column has an lower
234bound, and the statement \verb|s14| sets the objective coefficient for
235the first column. The statements \verb|s15|---\verb|s20| are used in the
236same way in order to assign the symbolic names `\verb|x2|' and
237`\verb|x3|' to the second and third columns and set their types, bounds,
238and objective coefficients.
239
240The statements \verb|s21|---\verb|s29| prepare non-zero elements of the
241constraint matrix (i.e. constraint coefficients). Row indices of each
242element are stored in the array \verb|ia|, column indices are stored in
243the array \verb|ja|, and numerical values of corresponding elements are
244stored in the array \verb|ar|. Then the statement \verb|s30| calls
245the routine \verb|glp_load_matrix|, which loads information from these
246three arrays into the problem object.
247
248Now all data have been entered into the problem object, and therefore
249the statement \verb|s31| calls the routine \verb|glp_simplex|, which is
250a driver to the simplex method, in order to solve the LP problem. This
251routine finds an optimal solution and stores all relevant information
252back into the problem object.
253
254The statement \verb|s32| obtains a computed value of the objective
255function, and the statements \verb|s33|---\verb|s35| obtain computed
256values of structural variables (columns), which correspond to the
257optimal basic solution found by the solver.
258
259The statement \verb|s36| writes the optimal solution to the standard
260output. The printout may look like follows:
261
262{\footnotesize
263\begin{verbatim}
264*     0:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (0)
265*     2:   objval =   7.333333333e+02   infeas =   0.000000000e+00 (0)
266OPTIMAL SOLUTION FOUND
267
268z = 733.333; x1 = 33.3333; x2 = 66.6667; x3 = 0
269\end{verbatim}
270
271}
272
273Finally, the statement \verb|s37| calls the routine
274\verb|glp_delete_prob|, which frees all the memory allocated to the
275problem object.
276
277\subsection{Compiling}
278
279The GLPK package has the only header file \verb|glpk.h|, which should
280be available on compiling a C (or C++) program using GLPK API routines.
281
282If the header file is installed in the default location
283\verb|/usr/local/include|, the following typical command may be used to
284compile, say, the example C program described above with the GNU C
285compiler:
286
287\begin{verbatim}
288   $ gcc -c sample.c
289\end{verbatim}
290
291If \verb|glpk.h| is not in the default location, the corresponding
292directory containing it should be made known to the C compiler through
293\verb|-I| option, for example:
294
295\begin{verbatim}
296   $ gcc -I/foo/bar/glpk-4.15/include -c sample.c
297\end{verbatim}
298
299In any case the compilation results in an object file \verb|sample.o|.
300
301\subsection{Linking}
302
303The GLPK library is a single file \verb|libglpk.a|. (On systems which
304support shared libraries there may be also a shared version of the
305library \verb|libglpk.so|.)
306
307If the library is installed in the default
308location \verb|/usr/local/lib|, the following typical command may be
309used to link, say, the example C program described above against with
310the library:
311
312\begin{verbatim}
313   $ gcc sample.o -lglpk -lm
314\end{verbatim}
315
316If the GLPK library is not in the default location, the corresponding
317directory containing it should be made known to the linker through
318\verb|-L| option, for example:
319
320\begin{verbatim}
321   $ gcc -L/foo/bar/glpk-4.15 sample.o -lglpk -lm
322\end{verbatim}
323
324Depending on configuration of the package linking against with the GLPK
325library may require the following optional libraries:
326
327\bigskip
328
329\begin{tabular}{@{}ll}
330\verb|-lgmp|  & the GNU MP bignum library; \\
331\verb|-lz|    & the zlib data compression library; \\
332\verb|-lltdl| & the GNU ltdl shared support library. \\
333\end{tabular}
334
335\bigskip
336
337\noindent
338in which case corresponding libraries should be also made known to the
339linker, for example:
340
341\begin{verbatim}
342   $ gcc sample.o -lglpk -lz -lltdl -lm
343\end{verbatim}
344
345For more details about configuration options of the GLPK package see
346Appendix \ref{install}, page \pageref{install}.
347
348%* eof *%
Note: See TracBrowser for help on using the repository browser.