1 | %* glpk01.tex *% |
---|
2 | |
---|
3 | \chapter{Introduction} |
---|
4 | |
---|
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. |
---|
10 | |
---|
11 | \section{LP problem} |
---|
12 | \label{seclp} |
---|
13 | |
---|
14 | GLPK assumes the following formulation of {\it linear programming (LP)} |
---|
15 | problem: |
---|
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} |
---|
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. |
---|
49 | |
---|
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. |
---|
55 | |
---|
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. |
---|
73 | |
---|
74 | To solve the LP problem (1.1)---(1.3) is to find such values of all |
---|
75 | structural 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 |
---|
87 | which some variables are additionally required to be integer. |
---|
88 | |
---|
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.) |
---|
96 | |
---|
97 | \section{Using the package} |
---|
98 | |
---|
99 | \subsection{Brief example} |
---|
100 | |
---|
101 | In order to understand what GLPK is from the user's standpoint, |
---|
102 | consider 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} |
---|
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$$ |
---|
119 | |
---|
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: |
---|
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} |
---|
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). |
---|
148 | |
---|
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.} |
---|
154 | |
---|
155 | \newpage |
---|
156 | |
---|
157 | \begin{verbatim} |
---|
158 | /* sample.c */ |
---|
159 | |
---|
160 | #include <stdio.h> |
---|
161 | #include <stdlib.h> |
---|
162 | #include <glpk.h> |
---|
163 | |
---|
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 | } |
---|
208 | |
---|
209 | /* eof */ |
---|
210 | \end{verbatim} |
---|
211 | |
---|
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. |
---|
215 | |
---|
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. |
---|
219 | |
---|
220 | The statement \verb|s4| adds three rows to the problem object. |
---|
221 | |
---|
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. |
---|
228 | |
---|
229 | The statement \verb|s11| adds three columns to the problem object. |
---|
230 | |
---|
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. |
---|
239 | |
---|
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. |
---|
247 | |
---|
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. |
---|
253 | |
---|
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. |
---|
258 | |
---|
259 | The statement \verb|s36| writes the optimal solution to the standard |
---|
260 | output. 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) |
---|
266 | OPTIMAL SOLUTION FOUND |
---|
267 | |
---|
268 | z = 733.333; x1 = 33.3333; x2 = 66.6667; x3 = 0 |
---|
269 | \end{verbatim} |
---|
270 | |
---|
271 | } |
---|
272 | |
---|
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. |
---|
276 | |
---|
277 | \subsection{Compiling} |
---|
278 | |
---|
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. |
---|
281 | |
---|
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: |
---|
286 | |
---|
287 | \begin{verbatim} |
---|
288 | $ gcc -c sample.c |
---|
289 | \end{verbatim} |
---|
290 | |
---|
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: |
---|
294 | |
---|
295 | \begin{verbatim} |
---|
296 | $ gcc -I/foo/bar/glpk-4.15/include -c sample.c |
---|
297 | \end{verbatim} |
---|
298 | |
---|
299 | In any case the compilation results in an object file \verb|sample.o|. |
---|
300 | |
---|
301 | \subsection{Linking} |
---|
302 | |
---|
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|.) |
---|
306 | |
---|
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: |
---|
311 | |
---|
312 | \begin{verbatim} |
---|
313 | $ gcc sample.o -lglpk -lm |
---|
314 | \end{verbatim} |
---|
315 | |
---|
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: |
---|
319 | |
---|
320 | \begin{verbatim} |
---|
321 | $ gcc -L/foo/bar/glpk-4.15 sample.o -lglpk -lm |
---|
322 | \end{verbatim} |
---|
323 | |
---|
324 | Depending on configuration of the package linking against with the GLPK |
---|
325 | library 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 |
---|
338 | in which case corresponding libraries should be also made known to the |
---|
339 | linker, for example: |
---|
340 | |
---|
341 | \begin{verbatim} |
---|
342 | $ gcc sample.o -lglpk -lz -lltdl -lm |
---|
343 | \end{verbatim} |
---|
344 | |
---|
345 | For more details about configuration options of the GLPK package see |
---|
346 | Appendix \ref{install}, page \pageref{install}. |
---|
347 | |
---|
348 | %* eof *% |
---|