lemon-project-template-glpk
view 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 |
line source
1 %* glpk01.tex *%
3 \chapter{Introduction}
5 GLPK (\underline{G}NU \underline{L}inear \underline{P}rogramming
6 \underline{K}it) is a set of routines written in the ANSI C programming
7 language and organized in the form of a callable library. It is intended
8 for solving linear programming (LP), mixed integer programming (MIP),
9 and other related problems.
11 \section{LP problem}
12 \label{seclp}
14 GLPK assumes the following formulation of {\it linear programming (LP)}
15 problem:
17 \medskip
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}
25 x_1&=&a_{11}x_{m+1}&+&a_{12}x_{m+2}&+ \dots +&a_{1n}x_{m+n} \\
26 x_2&=&a_{21}x_{m+1}&+&a_{22}x_{m+2}&+ \dots +&a_{2n}x_{m+n} \\
27 \multicolumn{7}{c}
28 {.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .} \\
29 x_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}
35 l_1&\leq&x_1&\leq&u_1 \\
36 l_2&\leq&x_2&\leq&u_2 \\
37 \multicolumn{5}{c}{.\ \ .\ \ .\ \ .\ \ .}\\
38 l_{m+n}&\leq&x_{m+n}&\leq&u_{m+n} \\
39 \end{array} \eqno (1.3)
40 $$
41 where: $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.
50 Auxiliary variables are also called {\it rows}, because they correspond
51 to rows of the constraint matrix (i.e. a matrix built of the constraint
52 coefficients). Similarly, structural variables are also called
53 {\it columns}, because they correspond to columns of the constraint
54 matrix.
56 Bounds of variables can be finite as well as infinite. Besides, lower
57 and upper bounds can be equal to each other. Thus, the following types
58 of 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
71 Note that the types of variables shown above are applicable to
72 structural as well as to auxiliary variables.
74 To solve the LP problem (1.1)---(1.3) is to find such values of all
75 structural and auxiliary variables, which:
77 $\bullet$ satisfy to all the linear constraints (1.2), and
79 $\bullet$ are within their bounds (1.3), and
81 $\bullet$ provide the smallest (in case of minimization) or the largest
82 (in case of maximization) value of the objective function (1.1).
84 \section{MIP problem}
86 {\it Mixed integer linear programming (MIP)} problem is LP problem in
87 which some variables are additionally required to be integer.
89 GLPK assumes that MIP problem has the same formulation as ordinary
90 (pure) LP problem (1.1)---(1.3), i.e. includes auxiliary and structural
91 variables, which may have lower and/or upper bounds. However, in case of
92 MIP problem some variables may be required to be integer. This
93 additional constraint means that a value of each {\it integer variable}
94 must be only integer number. (Should note that GLPK allows only
95 structural variables to be of integer kind.)
97 \section{Using the package}
99 \subsection{Brief example}
101 In order to understand what GLPK is from the user's standpoint,
102 consider the following simple LP problem:
104 \medskip
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}
112 x_1 &+&x_2 &+&x_3 &\leq 100 \\
113 10 x_1 &+& 4 x_2 & +&5 x_3 & \leq 600 \\
114 2 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$$
120 At first this LP problem should be transformed to the standard form
121 (1.1)---(1.3). This can be easily done by introducing auxiliary
122 variables, by one for each original inequality constraint. Thus, the
123 problem can be reformulated as follows:
125 \medskip
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}
133 p& = &x_1 &+&x_2 &+&x_3 \\
134 q& = &10 x_1 &+& 4 x_2 &+& 5 x_3 \\
135 r& = &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 $$
146 where $p, q, r$ are auxiliary variables (rows), and $x_1, x_2, x_3$ are
147 structural variables (columns).
149 The example C program shown below uses GLPK API routines in order to
150 solve this LP problem.\footnote{If you just need to solve LP or MIP
151 instance, you may write it in MPS or CPLEX LP format and then use the
152 GLPK stand-alone solver to obtain a solution. This is much less
153 time-consuming than programming in C with GLPK API routines.}
155 \newpage
157 \begin{verbatim}
158 /* sample.c */
160 #include <stdio.h>
161 #include <stdlib.h>
162 #include <glpk.h>
164 int main(void)
165 { glp_prob *lp;
166 int ia[1+1000], ja[1+1000];
167 double ar[1+1000], z, x1, x2, x3;
168 s1: lp = glp_create_prob();
169 s2: glp_set_prob_name(lp, "sample");
170 s3: glp_set_obj_dir(lp, GLP_MAX);
171 s4: glp_add_rows(lp, 3);
172 s5: glp_set_row_name(lp, 1, "p");
173 s6: glp_set_row_bnds(lp, 1, GLP_UP, 0.0, 100.0);
174 s7: glp_set_row_name(lp, 2, "q");
175 s8: glp_set_row_bnds(lp, 2, GLP_UP, 0.0, 600.0);
176 s9: glp_set_row_name(lp, 3, "r");
177 s10: glp_set_row_bnds(lp, 3, GLP_UP, 0.0, 300.0);
178 s11: glp_add_cols(lp, 3);
179 s12: glp_set_col_name(lp, 1, "x1");
180 s13: glp_set_col_bnds(lp, 1, GLP_LO, 0.0, 0.0);
181 s14: glp_set_obj_coef(lp, 1, 10.0);
182 s15: glp_set_col_name(lp, 2, "x2");
183 s16: glp_set_col_bnds(lp, 2, GLP_LO, 0.0, 0.0);
184 s17: glp_set_obj_coef(lp, 2, 6.0);
185 s18: glp_set_col_name(lp, 3, "x3");
186 s19: glp_set_col_bnds(lp, 3, GLP_LO, 0.0, 0.0);
187 s20: glp_set_obj_coef(lp, 3, 4.0);
188 s21: ia[1] = 1, ja[1] = 1, ar[1] = 1.0; /* a[1,1] = 1 */
189 s22: ia[2] = 1, ja[2] = 2, ar[2] = 1.0; /* a[1,2] = 1 */
190 s23: ia[3] = 1, ja[3] = 3, ar[3] = 1.0; /* a[1,3] = 1 */
191 s24: ia[4] = 2, ja[4] = 1, ar[4] = 10.0; /* a[2,1] = 10 */
192 s25: ia[5] = 3, ja[5] = 1, ar[5] = 2.0; /* a[3,1] = 2 */
193 s26: ia[6] = 2, ja[6] = 2, ar[6] = 4.0; /* a[2,2] = 4 */
194 s27: ia[7] = 3, ja[7] = 2, ar[7] = 2.0; /* a[3,2] = 2 */
195 s28: ia[8] = 2, ja[8] = 3, ar[8] = 5.0; /* a[2,3] = 5 */
196 s29: ia[9] = 3, ja[9] = 3, ar[9] = 6.0; /* a[3,3] = 6 */
197 s30: glp_load_matrix(lp, 9, ia, ja, ar);
198 s31: glp_simplex(lp, NULL);
199 s32: z = glp_get_obj_val(lp);
200 s33: x1 = glp_get_col_prim(lp, 1);
201 s34: x2 = glp_get_col_prim(lp, 2);
202 s35: x3 = glp_get_col_prim(lp, 3);
203 s36: printf("\nz = %g; x1 = %g; x2 = %g; x3 = %g\n",
204 z, x1, x2, x3);
205 s37: glp_delete_prob(lp);
206 return 0;
207 }
209 /* eof */
210 \end{verbatim}
212 The statement \verb|s1| creates a problem object. Being created the
213 object is initially empty. The statement \verb|s2| assigns a symbolic
214 name to the problem object.
216 The statement \verb|s3| calls the routine \verb|glp_set_obj_dir| in
217 order to set the optimization direction flag, where \verb|GLP_MAX| means
218 maximization.
220 The statement \verb|s4| adds three rows to the problem object.
222 The statement \verb|s5| assigns the symbolic name `\verb|p|' to the
223 first row, and the statement \verb|s6| sets the type and bounds of the
224 first row, where \verb|GLP_UP| means that the row has an upper bound.
225 The statements \verb|s7|, \verb|s8|, \verb|s9|, \verb|s10| are used in
226 the 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.
229 The statement \verb|s11| adds three columns to the problem object.
231 The statement \verb|s12| assigns the symbolic name `\verb|x1|' to the
232 first column, the statement \verb|s13| sets the type and bounds of the
233 first column, where \verb|GLP_LO| means that the column has an lower
234 bound, and the statement \verb|s14| sets the objective coefficient for
235 the first column. The statements \verb|s15|---\verb|s20| are used in the
236 same 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,
238 and objective coefficients.
240 The statements \verb|s21|---\verb|s29| prepare non-zero elements of the
241 constraint matrix (i.e. constraint coefficients). Row indices of each
242 element are stored in the array \verb|ia|, column indices are stored in
243 the array \verb|ja|, and numerical values of corresponding elements are
244 stored in the array \verb|ar|. Then the statement \verb|s30| calls
245 the routine \verb|glp_load_matrix|, which loads information from these
246 three arrays into the problem object.
248 Now all data have been entered into the problem object, and therefore
249 the statement \verb|s31| calls the routine \verb|glp_simplex|, which is
250 a driver to the simplex method, in order to solve the LP problem. This
251 routine finds an optimal solution and stores all relevant information
252 back into the problem object.
254 The statement \verb|s32| obtains a computed value of the objective
255 function, and the statements \verb|s33|---\verb|s35| obtain computed
256 values of structural variables (columns), which correspond to the
257 optimal basic solution found by the solver.
259 The statement \verb|s36| writes the optimal solution to the standard
260 output. The printout may look like follows:
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)
266 OPTIMAL SOLUTION FOUND
268 z = 733.333; x1 = 33.3333; x2 = 66.6667; x3 = 0
269 \end{verbatim}
271 }
273 Finally, the statement \verb|s37| calls the routine
274 \verb|glp_delete_prob|, which frees all the memory allocated to the
275 problem object.
277 \subsection{Compiling}
279 The GLPK package has the only header file \verb|glpk.h|, which should
280 be available on compiling a C (or C++) program using GLPK API routines.
282 If the header file is installed in the default location
283 \verb|/usr/local/include|, the following typical command may be used to
284 compile, say, the example C program described above with the GNU C
285 compiler:
287 \begin{verbatim}
288 $ gcc -c sample.c
289 \end{verbatim}
291 If \verb|glpk.h| is not in the default location, the corresponding
292 directory containing it should be made known to the C compiler through
293 \verb|-I| option, for example:
295 \begin{verbatim}
296 $ gcc -I/foo/bar/glpk-4.15/include -c sample.c
297 \end{verbatim}
299 In any case the compilation results in an object file \verb|sample.o|.
301 \subsection{Linking}
303 The GLPK library is a single file \verb|libglpk.a|. (On systems which
304 support shared libraries there may be also a shared version of the
305 library \verb|libglpk.so|.)
307 If the library is installed in the default
308 location \verb|/usr/local/lib|, the following typical command may be
309 used to link, say, the example C program described above against with
310 the library:
312 \begin{verbatim}
313 $ gcc sample.o -lglpk -lm
314 \end{verbatim}
316 If the GLPK library is not in the default location, the corresponding
317 directory containing it should be made known to the linker through
318 \verb|-L| option, for example:
320 \begin{verbatim}
321 $ gcc -L/foo/bar/glpk-4.15 sample.o -lglpk -lm
322 \end{verbatim}
324 Depending on configuration of the package linking against with the GLPK
325 library may require the following optional libraries:
327 \bigskip
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}
335 \bigskip
337 \noindent
338 in which case corresponding libraries should be also made known to the
339 linker, for example:
341 \begin{verbatim}
342 $ gcc sample.o -lglpk -lz -lltdl -lm
343 \end{verbatim}
345 For more details about configuration options of the GLPK package see
346 Appendix \ref{install}, page \pageref{install}.
348 %* eof *%