1 | %* graphs.tex *% |
---|
2 | |
---|
3 | %*********************************************************************** |
---|
4 | % This code is part of GLPK (GNU Linear Programming Kit). |
---|
5 | % |
---|
6 | % Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, |
---|
7 | % 2009, 2010 Andrew Makhorin, Department for Applied Informatics, |
---|
8 | % Moscow Aviation Institute, Moscow, Russia. All rights reserved. |
---|
9 | % E-mail: <mao@gnu.org>. |
---|
10 | % |
---|
11 | % GLPK is free software: you can redistribute it and/or modify it |
---|
12 | % under the terms of the GNU General Public License as published by |
---|
13 | % the Free Software Foundation, either version 3 of the License, or |
---|
14 | % (at your option) any later version. |
---|
15 | % |
---|
16 | % GLPK is distributed in the hope that it will be useful, but WITHOUT |
---|
17 | % ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
---|
18 | % or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public |
---|
19 | % License for more details. |
---|
20 | % |
---|
21 | % You should have received a copy of the GNU General Public License |
---|
22 | % along with GLPK. If not, see <http://www.gnu.org/licenses/>. |
---|
23 | %*********************************************************************** |
---|
24 | |
---|
25 | \documentclass[11pt]{report} |
---|
26 | \usepackage{amssymb} |
---|
27 | \usepackage[dvipdfm,linktocpage,colorlinks,linkcolor=blue, |
---|
28 | urlcolor=blue]{hyperref} |
---|
29 | \usepackage[all]{xy} |
---|
30 | |
---|
31 | \renewcommand\contentsname{\sf\bfseries Contents} |
---|
32 | \renewcommand\chaptername{\sf\bfseries Chapter} |
---|
33 | \renewcommand\appendixname{\sf\bfseries Appendix} |
---|
34 | |
---|
35 | \begin{document} |
---|
36 | |
---|
37 | \thispagestyle{empty} |
---|
38 | |
---|
39 | \begin{center} |
---|
40 | |
---|
41 | \vspace*{1in} |
---|
42 | |
---|
43 | \begin{huge} |
---|
44 | \sf\bfseries GNU Linear Programming Kit |
---|
45 | \end{huge} |
---|
46 | |
---|
47 | \vspace{0.5in} |
---|
48 | |
---|
49 | \begin{LARGE} |
---|
50 | \sf Graph and Network Routines |
---|
51 | \end{LARGE} |
---|
52 | |
---|
53 | \vspace{0.5in} |
---|
54 | |
---|
55 | \begin{LARGE} |
---|
56 | \sf for GLPK Version 4.45 |
---|
57 | \end{LARGE} |
---|
58 | |
---|
59 | \vspace{0.5in} |
---|
60 | \begin{Large} |
---|
61 | \sf (DRAFT, December 2010) |
---|
62 | \end{Large} |
---|
63 | \end{center} |
---|
64 | |
---|
65 | \newpage |
---|
66 | |
---|
67 | \vspace*{1in} |
---|
68 | |
---|
69 | \vfill |
---|
70 | |
---|
71 | \noindent |
---|
72 | The GLPK package is part of the GNU Project released under the aegis of |
---|
73 | GNU. |
---|
74 | |
---|
75 | \medskip \noindent |
---|
76 | Copyright \copyright{} 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, |
---|
77 | 2008, 2009, 2010 Andrew Makhorin, Department for Applied Informatics, |
---|
78 | Moscow Aviation Institute, Moscow, Russia. All rights reserved. |
---|
79 | |
---|
80 | \medskip \noindent |
---|
81 | Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA |
---|
82 | 02110-1301, USA. |
---|
83 | |
---|
84 | \medskip \noindent |
---|
85 | Permission is granted to make and distribute verbatim copies of this |
---|
86 | manual provided the copyright notice and this permission notice are |
---|
87 | preserved on all copies. |
---|
88 | |
---|
89 | \medskip \noindent |
---|
90 | Permission is granted to copy and distribute modified versions of this |
---|
91 | manual under the conditions for verbatim copying, provided also that the |
---|
92 | entire resulting derived work is distributed under the terms of |
---|
93 | a permission notice identical to this one. |
---|
94 | |
---|
95 | \medskip \noindent |
---|
96 | Permission is granted to copy and distribute translations of this manual |
---|
97 | into another language, under the above conditions for modified versions. |
---|
98 | |
---|
99 | \tableofcontents |
---|
100 | |
---|
101 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
102 | |
---|
103 | \chapter{Basic Graph API Routines} |
---|
104 | |
---|
105 | \section{Graph program object} |
---|
106 | |
---|
107 | In GLPK the base program object used to represent graphs and networks |
---|
108 | is a directed graph (digraph). |
---|
109 | |
---|
110 | Formally, {\it digraph} (or simply, {\it graph}) is a pair $G=(V,A)$, |
---|
111 | where $V$ is a set of {\it vertices}, and $A$ is a set |
---|
112 | {\it arcs}.\footnote{$A$ may be a multiset.} Each arc $a\in A$ is an |
---|
113 | ordered pair of vertices $a=(x,y)$, where $x\in V$ is called {\it tail |
---|
114 | vertex} of arc $a$, and $y\in V$ is called its {\it head vertex}. |
---|
115 | |
---|
116 | Representation of a graph in the program includes three structs defined |
---|
117 | by typedef in the header \verb|glpk.h|: |
---|
118 | |
---|
119 | \medskip |
---|
120 | |
---|
121 | $\bullet$ \verb|glp_graph|, which represents the graph in a whole, |
---|
122 | |
---|
123 | $\bullet$ \verb|glp_vertex|, which represents a vertex of the graph, and |
---|
124 | |
---|
125 | $\bullet$ \verb|glp_arc|, which represents an arc of the graph. |
---|
126 | |
---|
127 | \medskip |
---|
128 | |
---|
129 | All these three structs are ``semi-opaque'', i.e. the application |
---|
130 | program can directly access their fields through pointers, however, |
---|
131 | changing the fields directly is not allowed---all changes should be |
---|
132 | performed only with appropriate GLPK API routines. |
---|
133 | |
---|
134 | \newpage |
---|
135 | |
---|
136 | \newenvironment{comment} |
---|
137 | {\addtolength{\leftskip}{17pt}\noindent} |
---|
138 | {\par\addtolength{\leftskip}{-17pt}} |
---|
139 | |
---|
140 | \noindent |
---|
141 | {\bf glp\_graph.} The struct \verb|glp_graph| has the following |
---|
142 | fields available to the application program: |
---|
143 | |
---|
144 | \medskip |
---|
145 | |
---|
146 | \noindent |
---|
147 | \verb|char *name;| |
---|
148 | |
---|
149 | \begin{comment}Symbolic name assigned to the graph. It is a pointer to |
---|
150 | a null terminated character string of length from 1 to 255 characters. |
---|
151 | If no name is assigned to the graph, this field contains \verb|NULL|. |
---|
152 | \end{comment} |
---|
153 | |
---|
154 | \medskip |
---|
155 | |
---|
156 | \noindent |
---|
157 | \verb|int nv;| |
---|
158 | |
---|
159 | \begin{comment}The number of vertices in the graph, $nv\geq 0$. |
---|
160 | \end{comment} |
---|
161 | |
---|
162 | \medskip |
---|
163 | |
---|
164 | \noindent |
---|
165 | \verb|int na;| |
---|
166 | |
---|
167 | \begin{comment}The number of arcs in the graph, $na\geq 0$. |
---|
168 | \end{comment} |
---|
169 | |
---|
170 | \medskip |
---|
171 | |
---|
172 | \noindent |
---|
173 | \verb|glp_vertex **v;| |
---|
174 | |
---|
175 | \begin{comment}Pointer to an array containing the list of vertices. |
---|
176 | Element $v[0]$ is not used. Element $v[i]$, $1\leq i\leq nv$, is a |
---|
177 | pointer to $i$-th vertex of the graph. Note that on adding new vertices |
---|
178 | to the graph the field $v$ may be altered due to reallocation. However, |
---|
179 | pointers $v[i]$ are not changed while corresponding vertices exist in |
---|
180 | the graph. |
---|
181 | \end{comment} |
---|
182 | |
---|
183 | \medskip |
---|
184 | |
---|
185 | \noindent |
---|
186 | \verb|int v_size;| |
---|
187 | |
---|
188 | \begin{comment}Size of vertex data blocks, in bytes, |
---|
189 | $0\leq v\_size\leq 256$. (See also the field \verb|data| in the struct |
---|
190 | \verb|glp_vertex|.) |
---|
191 | \end{comment} |
---|
192 | |
---|
193 | \medskip |
---|
194 | |
---|
195 | \noindent |
---|
196 | \verb|int a_size;| |
---|
197 | |
---|
198 | \begin{comment}Size of arc data blocks, in bytes, |
---|
199 | $0\leq v\_size\leq 256$. (See also the field \verb|data| in the struct |
---|
200 | \verb|glp_arc|.) |
---|
201 | \end{comment} |
---|
202 | |
---|
203 | \bigskip |
---|
204 | |
---|
205 | \noindent |
---|
206 | {\bf glp\_vertex.} The struct \verb|glp_vertex| has the following |
---|
207 | fields available to the application program: |
---|
208 | |
---|
209 | \medskip |
---|
210 | |
---|
211 | \noindent |
---|
212 | \verb|int i;| |
---|
213 | |
---|
214 | \begin{comment}Ordinal number of the vertex, $1\leq i\leq nv$. Note |
---|
215 | that element $v[i]$ in the struct \verb|glp_graph| points to the vertex, |
---|
216 | whose ordinal number is $i$. |
---|
217 | \end{comment} |
---|
218 | |
---|
219 | \medskip |
---|
220 | |
---|
221 | \noindent |
---|
222 | \verb|char *name;| |
---|
223 | |
---|
224 | \begin{comment}Symbolic name assigned to the vertex. It is a pointer to |
---|
225 | a null terminated character string of length from 1 to 255 characters. |
---|
226 | If no name is assigned to the vertex, this field contains \verb|NULL|. |
---|
227 | \end{comment} |
---|
228 | |
---|
229 | \medskip |
---|
230 | |
---|
231 | \noindent |
---|
232 | \verb|void *data;| |
---|
233 | |
---|
234 | \begin{comment}Pointer to a data block associated with the vertex. This |
---|
235 | data block is automatically allocated on creating a new vertex and freed |
---|
236 | on deleting the vertex. If $v\_size=0$, the block is not allocated, and |
---|
237 | this field contains \verb|NULL|. |
---|
238 | \end{comment} |
---|
239 | |
---|
240 | \medskip |
---|
241 | |
---|
242 | \noindent |
---|
243 | \verb|void *temp;| |
---|
244 | |
---|
245 | \begin{comment}Working pointer, which may be used freely for any |
---|
246 | purposes. The application program can change this field directly. |
---|
247 | \end{comment} |
---|
248 | |
---|
249 | \medskip |
---|
250 | |
---|
251 | \noindent |
---|
252 | \verb|glp_arc *in;| |
---|
253 | |
---|
254 | \begin{comment}Pointer to the (unordered) list of incoming arcs. If the |
---|
255 | vertex has no incoming arcs, this field contains \verb|NULL|. |
---|
256 | \end{comment} |
---|
257 | |
---|
258 | \medskip |
---|
259 | |
---|
260 | \noindent |
---|
261 | \verb|glp_arc *out;| |
---|
262 | |
---|
263 | \begin{comment}Pointer to the (unordered) list of outgoing arcs. If the |
---|
264 | vertex has no outgoing arcs, this field contains \verb|NULL|. |
---|
265 | \end{comment} |
---|
266 | |
---|
267 | \bigskip |
---|
268 | |
---|
269 | \noindent |
---|
270 | {\bf glp\_arc.} The struct \verb|glp_arc| has the following fields |
---|
271 | available to the application program: |
---|
272 | |
---|
273 | \medskip |
---|
274 | |
---|
275 | \noindent |
---|
276 | \verb|glp_vertex *tail;| |
---|
277 | |
---|
278 | \begin{comment}Pointer to a vertex, which is tail endpoint of the arc. |
---|
279 | \end{comment} |
---|
280 | |
---|
281 | \medskip |
---|
282 | |
---|
283 | \noindent |
---|
284 | \verb|glp_vertex *head;| |
---|
285 | |
---|
286 | \begin{comment}Pointer to a vertex, which is head endpoint of the arc. |
---|
287 | \end{comment} |
---|
288 | |
---|
289 | \medskip |
---|
290 | |
---|
291 | \noindent |
---|
292 | \verb|void *data;| |
---|
293 | |
---|
294 | \begin{comment}Pointer to a data block associated with the arc. This |
---|
295 | data block is automatically allocated on creating a new arc and freed on |
---|
296 | deleting the arc. If $v\_size=0$, the block is not allocated, and this |
---|
297 | field contains \verb|NULL|. |
---|
298 | \end{comment} |
---|
299 | |
---|
300 | \medskip |
---|
301 | |
---|
302 | \noindent |
---|
303 | \verb|void *temp;| |
---|
304 | |
---|
305 | \begin{comment}Working pointer, which may be used freely for any |
---|
306 | purposes. The application program can change this field directly. |
---|
307 | \end{comment} |
---|
308 | |
---|
309 | \medskip |
---|
310 | |
---|
311 | \noindent |
---|
312 | \verb|glp_arc *t_next;| |
---|
313 | |
---|
314 | \begin{comment}Pointer to another arc, which has the same tail endpoint |
---|
315 | as this one. \verb|NULL| in this field indicates the end of the list of |
---|
316 | outgoing arcs. |
---|
317 | \end{comment} |
---|
318 | |
---|
319 | \medskip |
---|
320 | |
---|
321 | \noindent |
---|
322 | \verb|glp_arc *h_next;| |
---|
323 | |
---|
324 | \begin{comment}Pointer to another arc, which has the same head endpoint |
---|
325 | as this one. \verb|NULL| in this field indicates the end of the list of |
---|
326 | incoming arcs. |
---|
327 | \end{comment} |
---|
328 | |
---|
329 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
330 | |
---|
331 | \newpage |
---|
332 | |
---|
333 | \section{Graph creating and modifying routines} |
---|
334 | |
---|
335 | \subsection{glp\_create\_graph---create graph} |
---|
336 | |
---|
337 | \subsubsection*{Synopsis} |
---|
338 | |
---|
339 | \begin{verbatim} |
---|
340 | glp_graph *glp_create_graph(int v_size, int a_size); |
---|
341 | \end{verbatim} |
---|
342 | |
---|
343 | \subsubsection*{Description} |
---|
344 | |
---|
345 | The routine \verb|glp_create_graph| creates a new graph, which |
---|
346 | initially is\linebreak empty, i.e. has no vertices and arcs. |
---|
347 | |
---|
348 | The parameter \verb|v_size| specifies the size of vertex data blocks, |
---|
349 | in bytes, $0\leq v\_size\leq 256$. |
---|
350 | |
---|
351 | The parameter \verb|a_size| specifies the size of arc data blocks, in |
---|
352 | bytes, $0\leq a\_size\leq 256$. |
---|
353 | |
---|
354 | \subsubsection*{Returns} |
---|
355 | |
---|
356 | The routine returns a pointer to the graph created. |
---|
357 | |
---|
358 | \subsection{glp\_set\_graph\_name---assign (change) graph name} |
---|
359 | |
---|
360 | \subsubsection*{Synopsis} |
---|
361 | |
---|
362 | \begin{verbatim} |
---|
363 | void glp_set_graph_name(glp_graph *G, const char *name); |
---|
364 | \end{verbatim} |
---|
365 | |
---|
366 | \subsubsection*{Description} |
---|
367 | |
---|
368 | The routine \verb|glp_set_graph_name| assigns a symbolic name specified |
---|
369 | by the character string \verb|name| (1 to 255 chars) to the graph. |
---|
370 | |
---|
371 | If the parameter \verb|name| is \verb|NULL| or an empty string, the |
---|
372 | routine erases the existing symbolic name of the graph. |
---|
373 | |
---|
374 | \newpage |
---|
375 | |
---|
376 | \subsection{glp\_add\_vertices---add new vertices to graph} |
---|
377 | |
---|
378 | \subsubsection*{Synopsis} |
---|
379 | |
---|
380 | \begin{verbatim} |
---|
381 | int glp_add_vertices(glp_graph *G, int nadd); |
---|
382 | \end{verbatim} |
---|
383 | |
---|
384 | \subsubsection*{Description} |
---|
385 | |
---|
386 | The routine \verb|glp_add_vertices| adds \verb|nadd| vertices to the |
---|
387 | specified graph. New vertices are always added to the end of the vertex |
---|
388 | list, so ordinal numbers of existing vertices remain unchanged. Note |
---|
389 | that this operation may change the field \verb|v| in the struct |
---|
390 | \verb|glp_graph| (pointer to the vertex array) due to reallocation. |
---|
391 | |
---|
392 | Being added each new vertex is isolated, i.e. has no incident arcs. |
---|
393 | |
---|
394 | If the size of vertex data blocks specified on creating the graph is |
---|
395 | non-zero, the routine also allocates a memory block of that size for |
---|
396 | each new vertex added, fills it by binary zeros, and stores a pointer to |
---|
397 | it in the field \verb|data| of the struct \verb|glp_vertex|. Otherwise, |
---|
398 | if the block size is zero, the field \verb|data| is set to \verb|NULL|. |
---|
399 | |
---|
400 | \subsubsection*{Returns} |
---|
401 | |
---|
402 | The routine \verb|glp_add_vertices| returns the ordinal number of the |
---|
403 | first new vertex added to the graph. |
---|
404 | |
---|
405 | \subsection{glp\_set\_vertex\_name---assign (change) vertex name} |
---|
406 | |
---|
407 | \subsubsection*{Synopsis} |
---|
408 | |
---|
409 | \begin{verbatim} |
---|
410 | void glp_set_vertex_name(glp_graph *G, int i, const char *name); |
---|
411 | \end{verbatim} |
---|
412 | |
---|
413 | \subsubsection*{Description} |
---|
414 | |
---|
415 | The routine \verb|glp_set_vertex_name| assigns a given symbolic name |
---|
416 | (1 up to 255 characters) to \verb|i|-th vertex of the specified graph. |
---|
417 | |
---|
418 | If the parameter \verb|name| is \verb|NULL| or empty string, the |
---|
419 | routine erases an existing name of \verb|i|-th vertex. |
---|
420 | |
---|
421 | \newpage |
---|
422 | |
---|
423 | \subsection{glp\_add\_arc---add new arc to graph} |
---|
424 | |
---|
425 | \subsubsection*{Synopsis} |
---|
426 | |
---|
427 | \begin{verbatim} |
---|
428 | glp_arc *glp_add_arc(glp_graph *G, int i, int j); |
---|
429 | \end{verbatim} |
---|
430 | |
---|
431 | \subsubsection*{Description} |
---|
432 | |
---|
433 | The routine \verb|glp_add_arc| adds one new arc to the specified graph. |
---|
434 | |
---|
435 | The parameters \verb|i| and \verb|j| specify the ordinal numbers of, |
---|
436 | resp., tail and head endpoints (vertices) of the arc. Note that |
---|
437 | self-loops and multiple arcs are allowed. |
---|
438 | |
---|
439 | If the size of arc data blocks specified on creating the graph is |
---|
440 | non-zero, the routine also allocates a memory block of that size, fills |
---|
441 | it by binary zeros, and stores a pointer to it in the field \verb|data| |
---|
442 | of the struct \verb|glp_arc|. Otherwise, if the block size is zero, the |
---|
443 | field \verb|data| is set to \verb|NULL|. |
---|
444 | |
---|
445 | \subsection{glp\_del\_vertices---delete vertices from graph} |
---|
446 | |
---|
447 | \subsubsection*{Synopsis} |
---|
448 | |
---|
449 | \begin{verbatim} |
---|
450 | void glp_del_vertices(glp_graph *G, int ndel, const int num[]); |
---|
451 | \end{verbatim} |
---|
452 | |
---|
453 | \subsubsection*{Description} |
---|
454 | |
---|
455 | The routine \verb|glp_del_vertices| deletes vertices along with all |
---|
456 | incident arcs from the specified graph. Ordinal numbers of vertices to |
---|
457 | be deleted should be placed in locations \verb|num[1]|, \dots, |
---|
458 | \verb|num[ndel]|, \verb|ndel| $>0$. |
---|
459 | |
---|
460 | Note that deleting vertices involves changing ordinal numbers of other |
---|
461 | vertices remaining in the graph. New ordinal numbers of the remaining |
---|
462 | vertices are assigned under the assumption that the original order of |
---|
463 | vertices is not changed. |
---|
464 | |
---|
465 | \subsection{glp\_del\_arc---delete arc from graph} |
---|
466 | |
---|
467 | \subsubsection*{Synopsis} |
---|
468 | |
---|
469 | \begin{verbatim} |
---|
470 | void glp_del_arc(glp_graph *G, glp_arc *a); |
---|
471 | \end{verbatim} |
---|
472 | |
---|
473 | \subsubsection*{Description} |
---|
474 | |
---|
475 | The routine \verb|glp_del_arc| deletes an arc from the specified graph. |
---|
476 | The arc to be deleted must exist. |
---|
477 | |
---|
478 | \subsection{glp\_erase\_graph---erase graph content} |
---|
479 | |
---|
480 | \subsubsection*{Synopsis} |
---|
481 | |
---|
482 | \begin{verbatim} |
---|
483 | void glp_erase_graph(glp_graph *G, int v_size, int a_size); |
---|
484 | \end{verbatim} |
---|
485 | |
---|
486 | \subsubsection*{Description} |
---|
487 | |
---|
488 | The routine \verb|glp_erase_graph| erases the content of the specified |
---|
489 | graph. The effect of this operation is the same as if the graph would be |
---|
490 | deleted with the routine \verb|glp_delete_graph| and then created anew |
---|
491 | with the routine \verb|glp_create_graph|, with exception that the handle |
---|
492 | (pointer) to the graph remains valid. |
---|
493 | |
---|
494 | The parameters \verb|v_size| and \verb|a_size| have the same meaning as |
---|
495 | for the routine \verb|glp_create_graph|. |
---|
496 | |
---|
497 | \subsection{glp\_delete\_graph---delete graph} |
---|
498 | |
---|
499 | \subsubsection*{Synopsis} |
---|
500 | |
---|
501 | \begin{verbatim} |
---|
502 | void glp_delete_graph(glp_graph *G); |
---|
503 | \end{verbatim} |
---|
504 | |
---|
505 | \subsubsection*{Description} |
---|
506 | |
---|
507 | The routine \verb|glp_delete_graph| deletes the specified graph and |
---|
508 | frees all the memory allocated to this program object. |
---|
509 | |
---|
510 | \newpage |
---|
511 | |
---|
512 | \section{Graph searching routines} |
---|
513 | |
---|
514 | \subsection{glp\_create\_v\_index---create vertex name index} |
---|
515 | |
---|
516 | \subsubsection*{Synopsis} |
---|
517 | |
---|
518 | \begin{verbatim} |
---|
519 | void glp_create_v_index(glp_graph *G); |
---|
520 | \end{verbatim} |
---|
521 | |
---|
522 | \subsubsection*{Description} |
---|
523 | |
---|
524 | The routine \verb|glp_create_v_index| creates the name index for the |
---|
525 | specified graph. The name index is an auxiliary data structure, which |
---|
526 | is intended to quickly (i.e. for logarithmic time) find vertices by |
---|
527 | their names. |
---|
528 | |
---|
529 | This routine can be called at any time. If the name index already |
---|
530 | exists, the routine does nothing. |
---|
531 | |
---|
532 | \subsection{glp\_find\_vertex---find vertex by its name} |
---|
533 | |
---|
534 | \subsubsection*{Synopsis} |
---|
535 | |
---|
536 | \begin{verbatim} |
---|
537 | int glp_find_vertex(glp_graph *G, const char *name); |
---|
538 | \end{verbatim} |
---|
539 | |
---|
540 | \subsubsection*{Returns} |
---|
541 | |
---|
542 | The routine \verb|glp_find_vertex| returns the ordinal number of |
---|
543 | a vertex, which is assigned (by the routine \verb|glp_set_vertex_name|) |
---|
544 | the specified symbolic \verb|name|. If no such vertex exists, the |
---|
545 | routine returns 0. |
---|
546 | |
---|
547 | \subsection{glp\_delete\_v\_index---delete vertex name index} |
---|
548 | |
---|
549 | \subsubsection*{Synopsis} |
---|
550 | |
---|
551 | \begin{verbatim} |
---|
552 | void glp_delete_v_index(glp_graph *G); |
---|
553 | \end{verbatim} |
---|
554 | |
---|
555 | \subsubsection*{Description} |
---|
556 | |
---|
557 | The routine \verb|glp_delete_v_index| deletes the name index previously |
---|
558 | created by the routine \verb|glp_create_v_index| and frees the memory |
---|
559 | allocated to this auxiliary data structure. |
---|
560 | |
---|
561 | This routine can be called at any time. If the name index does not |
---|
562 | exist, the routine does nothing. |
---|
563 | |
---|
564 | \newpage |
---|
565 | |
---|
566 | \section{Graph reading/writing routines} |
---|
567 | |
---|
568 | \subsection{glp\_read\_graph---read graph from plain text file} |
---|
569 | |
---|
570 | \subsubsection*{Synopsis} |
---|
571 | |
---|
572 | \begin{verbatim} |
---|
573 | int glp_read_graph(glp_graph *G, const char *fname); |
---|
574 | \end{verbatim} |
---|
575 | |
---|
576 | \subsubsection*{Description} |
---|
577 | |
---|
578 | The routine \verb|glp_read_graph| reads a graph from a plain text file, |
---|
579 | whose name is specified by the parameter \verb|fname|. Note that before |
---|
580 | reading data the current content of the graph object is completely |
---|
581 | erased with the routine \verb|glp_erase_graph|. |
---|
582 | |
---|
583 | For the file format see description of the routine |
---|
584 | \verb|glp_write_graph|. |
---|
585 | |
---|
586 | \subsubsection*{Returns} |
---|
587 | |
---|
588 | If the operation was successful, the routine returns zero. Otherwise |
---|
589 | it prints an error message and returns non-zero. |
---|
590 | |
---|
591 | \subsection{glp\_write\_graph---write graph to plain text file} |
---|
592 | |
---|
593 | \subsubsection*{Synopsis} |
---|
594 | |
---|
595 | \begin{verbatim} |
---|
596 | int glp_write_graph(glp_graph *G, const char *fname); |
---|
597 | \end{verbatim} |
---|
598 | |
---|
599 | \subsubsection*{Description} |
---|
600 | |
---|
601 | The routine \verb|glp_write_graph| writes the graph to a plain text |
---|
602 | file, whose name is specified by the parameter \verb|fname|. |
---|
603 | |
---|
604 | \subsubsection*{Returns} |
---|
605 | |
---|
606 | If the operation was successful, the routine returns zero. Otherwise |
---|
607 | it prints an error message and returns non-zero. |
---|
608 | |
---|
609 | \subsubsection*{File format} |
---|
610 | |
---|
611 | The file created by the routine \verb|glp_write_graph| is a plain text |
---|
612 | file, which contains the following information: |
---|
613 | |
---|
614 | \begin{verbatim} |
---|
615 | nv na |
---|
616 | i[1] j[1] |
---|
617 | i[2] j[2] |
---|
618 | . . . |
---|
619 | i[na] j[na] |
---|
620 | \end{verbatim} |
---|
621 | |
---|
622 | \noindent |
---|
623 | where: |
---|
624 | |
---|
625 | \noindent |
---|
626 | \verb|nv| is the number of vertices (nodes); |
---|
627 | |
---|
628 | \noindent |
---|
629 | \verb|na| is the number of arcs; |
---|
630 | |
---|
631 | \noindent |
---|
632 | \verb|i[k]|, $k=1,\dots,na$, is the index of tail vertex of arc $k$; |
---|
633 | |
---|
634 | \noindent |
---|
635 | \verb|j[k]|, $k=1,\dots,na$, is the index of head vertex of arc $k$. |
---|
636 | |
---|
637 | \subsection{glp\_read\_ccdata---read graph from text file in DIMACS |
---|
638 | clique/coloring format} |
---|
639 | |
---|
640 | \subsubsection*{Synopsis} |
---|
641 | |
---|
642 | \begin{verbatim} |
---|
643 | int glp_read_ccdata(glp_graph *G, int v_wgt, |
---|
644 | const char *fname); |
---|
645 | \end{verbatim} |
---|
646 | |
---|
647 | \subsubsection*{Description} |
---|
648 | |
---|
649 | The routine {\it glp\_read\_ccdata} reads a graph from a text file in |
---|
650 | DIMACS clique/coloring format. (Though this format is originally |
---|
651 | designed to represent data for the minimal vertex coloring and maximal |
---|
652 | clique problems, it may be used to represent general undirected and |
---|
653 | directed graphs, because the routine allows reading self-loops and |
---|
654 | multiple edges/arcs keeping the order of vertices specified for each |
---|
655 | edge/arc of the graph.) |
---|
656 | |
---|
657 | The parameter $G$ specifies the graph object to be read in. Note that |
---|
658 | before reading data the current content of the graph object is |
---|
659 | completely erased with the routine {\it glp\_erase\_graph}. |
---|
660 | |
---|
661 | The parameter {\it v\_wgt} specifies an offset of the field of type |
---|
662 | {\bf double} in the vertex data block, to which the routine stores the |
---|
663 | vertex weight. If {\it v\_wgt} $<0$, the vertex weights are not stored. |
---|
664 | |
---|
665 | The character string {\it fname} specifies the name of a text file to |
---|
666 | be read in. (If the file name ends with the suffix `\verb|.gz|', the |
---|
667 | file is assumed to be compressed, in which case the routine decompresses |
---|
668 | it ``on the fly''.) |
---|
669 | |
---|
670 | \subsubsection*{Returns} |
---|
671 | |
---|
672 | If the operation was successful, the routine returns zero. Otherwise, |
---|
673 | it prints an error message and returns non-zero. |
---|
674 | |
---|
675 | \subsubsection*{DIMACS clique/coloring format\footnote{This material is |
---|
676 | based on the paper ``Clique and Coloring Problems Graph Format'', which |
---|
677 | is publically available at |
---|
678 | {\tt http://dimacs.rutgers.edu/Challenges/}.}} |
---|
679 | |
---|
680 | The DIMACS input file is a plain ASCII text file. It contains |
---|
681 | {\it lines} of several types described below. A line is terminated with |
---|
682 | an end-of-line character. Fields in each line are separated by at least |
---|
683 | one blank space. Each line begins with a one-character designator to |
---|
684 | identify the line type. |
---|
685 | |
---|
686 | Note that DIMACS requires all numerical quantities to be integers in |
---|
687 | the range $[-2^{31},2^{31}-1]$ while GLPK allows the quantities to be |
---|
688 | floating-point numbers. |
---|
689 | |
---|
690 | \paragraph{Comment lines.} Comment lines give human-readable information |
---|
691 | about the file and are ignored by programs. Comment lines can appear |
---|
692 | anywhere in the file. Each comment line begins with a lower-case |
---|
693 | character \verb|c|. |
---|
694 | |
---|
695 | \begin{verbatim} |
---|
696 | c This is a comment line |
---|
697 | \end{verbatim} |
---|
698 | |
---|
699 | \paragraph{Problem line.} There is one problem line per data file. The |
---|
700 | problem line must appear before any node or edge descriptor lines. It |
---|
701 | has the following format: |
---|
702 | |
---|
703 | \begin{verbatim} |
---|
704 | p edge NODES EDGES |
---|
705 | \end{verbatim} |
---|
706 | |
---|
707 | \noindent |
---|
708 | The lower-case letter \verb|p| signifies that this is a problem line. |
---|
709 | The four-character problem designator \verb|edge| identifies the file |
---|
710 | as containing data for the minimal vertex coloring or maximal clique |
---|
711 | problem. The \verb|NODES| field contains an integer value specifying |
---|
712 | the number of vertices in the graph. The \verb|EDGES| field contains an |
---|
713 | integer value specifying the number of edges (arcs) in the graph. |
---|
714 | |
---|
715 | \paragraph{Vertex descriptors.} These lines give the weight assigned to |
---|
716 | a vertex of the graph. There is one vertex descriptor line for each |
---|
717 | vertex, with the following format. Vertices without a descriptor take on |
---|
718 | a default value of 1. |
---|
719 | |
---|
720 | \begin{verbatim} |
---|
721 | n ID VALUE |
---|
722 | \end{verbatim} |
---|
723 | |
---|
724 | \noindent |
---|
725 | The lower-case character \verb|n| signifies that this is a vertex |
---|
726 | descriptor line. The \verb|ID| field gives a vertex identification |
---|
727 | number, an integer between 1 and $n$, where $n$ is the number of |
---|
728 | vertices in the graph. The \verb|VALUE| field gives a vertex weight, |
---|
729 | which can either positive or negative (or zero). |
---|
730 | |
---|
731 | \paragraph{Edge descriptors.} There is one edge descriptor line for |
---|
732 | each edge (arc) of the graph, each with the following format: |
---|
733 | |
---|
734 | \begin{verbatim} |
---|
735 | e I J |
---|
736 | \end{verbatim} |
---|
737 | |
---|
738 | \noindent |
---|
739 | The lower-case character \verb|e| signifies that this is an edge |
---|
740 | descriptor line. For an edge (arc) $(i,j)$ the fields \verb|I| and |
---|
741 | \verb|J| specify its endpoints. |
---|
742 | |
---|
743 | \paragraph{Example.} The following example of an undirected graph: |
---|
744 | |
---|
745 | \bigskip |
---|
746 | |
---|
747 | \noindent\hfil |
---|
748 | \xymatrix %@C=32pt |
---|
749 | {&{v_1}\ar@{-}[ldd]\ar@{-}[dd]\ar@{-}[rd]\ar@{-}[rr]&&{v_2}\ar@{-}[ld] |
---|
750 | \ar@{-}[dd]\ar@{-}[rdd]&\\ |
---|
751 | &&{v_7}\ar@{-}[ld]\ar@{-}[rd]&&\\ |
---|
752 | {v_6}\ar@{-}[r]\ar@{-}[rdd]&{v_{10}}\ar@{-}[rr]\ar@{-}[rd]\ar@{-}[dd]&& |
---|
753 | {v_8}\ar@{-}[ld]\ar@{-}[dd]\ar@{-}[r]&{v_3}\ar@{-}[ldd]\\ |
---|
754 | &&{v_9}\ar@{-}[ld]\ar@{-}[rd]&&\\ |
---|
755 | &{v_5}\ar@{-}[rr]&&{v_4}&\\ |
---|
756 | } |
---|
757 | |
---|
758 | \bigskip |
---|
759 | |
---|
760 | \noindent |
---|
761 | might be coded in DIMACS clique/coloring format as follows: |
---|
762 | |
---|
763 | \begin{footnotesize} |
---|
764 | \begin{verbatim} |
---|
765 | c sample.col |
---|
766 | c |
---|
767 | c This is an example of the vertex coloring problem data |
---|
768 | c in DIMACS format. |
---|
769 | c |
---|
770 | p edge 10 21 |
---|
771 | c |
---|
772 | e 1 2 |
---|
773 | e 1 6 |
---|
774 | e 1 7 |
---|
775 | e 1 10 |
---|
776 | e 2 3 |
---|
777 | e 2 7 |
---|
778 | e 2 8 |
---|
779 | e 3 4 |
---|
780 | e 3 8 |
---|
781 | e 4 5 |
---|
782 | e 4 8 |
---|
783 | e 4 9 |
---|
784 | e 5 6 |
---|
785 | e 5 9 |
---|
786 | e 5 10 |
---|
787 | e 6 10 |
---|
788 | e 7 8 |
---|
789 | e 7 10 |
---|
790 | e 8 9 |
---|
791 | e 8 10 |
---|
792 | e 9 10 |
---|
793 | c |
---|
794 | c eof |
---|
795 | \end{verbatim} |
---|
796 | \end{footnotesize} |
---|
797 | |
---|
798 | \subsection{glp\_write\_ccdata---write graph to text file in DIMACS |
---|
799 | clique/coloring format} |
---|
800 | |
---|
801 | \subsubsection*{Synopsis} |
---|
802 | |
---|
803 | \begin{verbatim} |
---|
804 | int glp_write_ccdata(glp_graph *G, int v_wgt, |
---|
805 | const char *fname); |
---|
806 | \end{verbatim} |
---|
807 | |
---|
808 | \subsection*{Description} |
---|
809 | |
---|
810 | The routine {\it glp\_write\_ccdata} writes the graph object specified |
---|
811 | by the parameter $G$ to a text file in DIMACS clique/coloring format. |
---|
812 | (Though this format is originally designed to represent data for the |
---|
813 | minimal vertex coloring and maximal clique problems, it may be used to |
---|
814 | represent general undirected and directed graphs, because the routine |
---|
815 | allows writing self-loops and multiple edges/arcs keeping the order of |
---|
816 | vertices specified for each edge/arc of the graph.) |
---|
817 | |
---|
818 | The parameter {\it v\_wgt} specifies an offset of the field of type |
---|
819 | {\bf double} in the vertex data block, which contains the vertex weight. |
---|
820 | If {\it v\_wgt} $<0$, it is assumed that the weight of each vertex is 1. |
---|
821 | |
---|
822 | The character string {\it fname} specifies a name of the text file to be |
---|
823 | written out. (If the file name ends with suffix `\verb|.gz|', the file |
---|
824 | is assumed to be compressed, in which case the routine performs |
---|
825 | automatic compression on writing it.) |
---|
826 | |
---|
827 | \subsubsection*{Returns} |
---|
828 | |
---|
829 | If the operation was successful, the routine returns zero. Otherwise, |
---|
830 | it prints an error message and returns non-zero. |
---|
831 | |
---|
832 | \newpage |
---|
833 | |
---|
834 | \section{Graph analysis routines} |
---|
835 | |
---|
836 | \subsection{glp\_weak\_comp---find all weakly connected components of |
---|
837 | graph} |
---|
838 | |
---|
839 | \subsubsection*{Synopsis} |
---|
840 | |
---|
841 | \begin{verbatim} |
---|
842 | int glp_weak_comp(glp_graph *G, int v_num); |
---|
843 | \end{verbatim} |
---|
844 | |
---|
845 | \subsubsection*{Description} |
---|
846 | |
---|
847 | The routine \verb|glp_weak_comp| finds all weakly connected components |
---|
848 | of the specified graph. |
---|
849 | |
---|
850 | The parameter \verb|v_num| specifies an offset of the field of type |
---|
851 | \verb|int| in the vertex data block, to which the routine stores the |
---|
852 | number of a weakly connected component containing that vertex. If |
---|
853 | \verb|v_num| $<0$, no component numbers are stored. |
---|
854 | |
---|
855 | The components are numbered in arbitrary order from 1 to \verb|nc|, |
---|
856 | where \verb|nc| is the total number of components found, |
---|
857 | $0\leq$ \verb|nc| $\leq|V|$. |
---|
858 | |
---|
859 | \subsubsection*{Returns} |
---|
860 | |
---|
861 | The routine returns \verb|nc|, the total number of components found. |
---|
862 | |
---|
863 | \subsection{glp\_strong\_comp---find all strongly connected components |
---|
864 | of graph} |
---|
865 | |
---|
866 | \subsubsection*{Synopsis} |
---|
867 | |
---|
868 | \begin{verbatim} |
---|
869 | int glp_strong_comp(glp_graph *G, int v_num); |
---|
870 | \end{verbatim} |
---|
871 | |
---|
872 | \subsubsection*{Description} |
---|
873 | |
---|
874 | The routine \verb|glp_strong_comp| finds all strongly connected |
---|
875 | components of the specified graph. |
---|
876 | |
---|
877 | The parameter \verb|v_num| specifies an offset of the field of type |
---|
878 | \verb|int| in the vertex data block, to which the routine stores the |
---|
879 | number of a strongly connected component containing that vertex. If |
---|
880 | \verb|v_num| $<0$, no component numbers are stored. |
---|
881 | |
---|
882 | The components are numbered in arbitrary order from 1 to \verb|nc|, |
---|
883 | where \verb|nc| is the total number of components found, |
---|
884 | $0\leq$ \verb|nc| $\leq|V|$. However, the component numbering has the |
---|
885 | property that for every arc $(i\rightarrow j)$ in the graph the |
---|
886 | condition $num(i)\geq num(j)$ holds. |
---|
887 | |
---|
888 | \subsubsection*{Returns} |
---|
889 | |
---|
890 | The routine returns \verb|nc|, the total number of components found. |
---|
891 | |
---|
892 | \subsubsection*{References} |
---|
893 | |
---|
894 | I.~S.~Duff, J.~K.~Reid, Algorithm 529: Permutations to block triangular |
---|
895 | form, ACM Trans. on Math. Softw. 4 (1978), 189-92. |
---|
896 | |
---|
897 | \subsubsection*{Example} |
---|
898 | |
---|
899 | The following program reads a graph from a plain text file |
---|
900 | `\verb|graph.txt|' and finds all its strongly connected components. |
---|
901 | |
---|
902 | \begin{footnotesize} |
---|
903 | \begin{verbatim} |
---|
904 | #include <stddef.h> |
---|
905 | #include <stdio.h> |
---|
906 | #include <stdlib.h> |
---|
907 | #include <glpk.h> |
---|
908 | |
---|
909 | typedef struct { int num; } v_data; |
---|
910 | |
---|
911 | #define vertex(v) ((v_data *)((v)->data)) |
---|
912 | |
---|
913 | int main(void) |
---|
914 | { glp_graph *G; |
---|
915 | int i, nc; |
---|
916 | G = glp_create_graph(sizeof(v_data), 0); |
---|
917 | glp_read_graph(G, "graph.txt"); |
---|
918 | nc = glp_strong_comp(G, offsetof(v_data, num)); |
---|
919 | printf("nc = %d\n", nc); |
---|
920 | for (i = 1; i <= G->nv; i++) |
---|
921 | printf("num[%d] = %d\n", i, vertex(G->v[i])->num); |
---|
922 | glp_delete_graph(G); |
---|
923 | return 0; |
---|
924 | } |
---|
925 | \end{verbatim} |
---|
926 | \end{footnotesize} |
---|
927 | |
---|
928 | \noindent |
---|
929 | If the file `\verb|graph.txt|' contains the graph shown below: |
---|
930 | |
---|
931 | \bigskip |
---|
932 | |
---|
933 | \noindent\hfil |
---|
934 | \xymatrix |
---|
935 | {1\ar[r]&2\ar[r]&3\ar[r]\ar[dd]&4\ar[dd]\\ |
---|
936 | 5\ar[u]&6\ar[l]\\ |
---|
937 | 7\ar[u]&&8\ar[lu]\ar[ll]\ar[r]&9\ar[r]&10\ar[r]\ar[d]&11\ar[d]\\ |
---|
938 | 12\ar[u]\ar[rru]\ar@/_/[rr]&&13\ar[ll]\ar[u]\ar[rr]&&14\ar[lu]&15\ar[l] |
---|
939 | \\ |
---|
940 | } |
---|
941 | |
---|
942 | \bigskip\bigskip |
---|
943 | |
---|
944 | \noindent |
---|
945 | the program output may look like follows: |
---|
946 | |
---|
947 | \begin{footnotesize} |
---|
948 | \begin{verbatim} |
---|
949 | Reading graph from `graph.txt'... |
---|
950 | Graph has 15 vertices and 30 arcs |
---|
951 | 31 lines were read |
---|
952 | nc = 4 |
---|
953 | num[1] = 3 |
---|
954 | num[2] = 3 |
---|
955 | num[3] = 3 |
---|
956 | num[4] = 2 |
---|
957 | num[5] = 3 |
---|
958 | num[6] = 3 |
---|
959 | num[7] = 3 |
---|
960 | num[8] = 3 |
---|
961 | num[9] = 1 |
---|
962 | num[10] = 1 |
---|
963 | num[11] = 1 |
---|
964 | num[12] = 4 |
---|
965 | num[13] = 4 |
---|
966 | num[14] = 1 |
---|
967 | num[15] = 1 |
---|
968 | \end{verbatim} |
---|
969 | \end{footnotesize} |
---|
970 | |
---|
971 | \subsection{glp\_top\_sort---topological sorting of acyclic digraph} |
---|
972 | |
---|
973 | \subsubsection*{Synopsis} |
---|
974 | |
---|
975 | \begin{verbatim} |
---|
976 | int glp_top_sort(glp_graph *G, int v_num); |
---|
977 | \end{verbatim} |
---|
978 | |
---|
979 | \subsubsection*{Description} |
---|
980 | |
---|
981 | The routine \verb|glp_top_sort| performs topological sorting of |
---|
982 | vertices of the specified acyclic digraph. |
---|
983 | |
---|
984 | The parameter \verb|v_num| specifies an offset of the field of type |
---|
985 | \verb|int| in the vertex data block, to which the routine stores the |
---|
986 | vertex number assigned. If \verb|v_num| $<0$, vertex numbers are not |
---|
987 | stored. |
---|
988 | |
---|
989 | The vertices are numbered from 1 to $n$, where $n$ is the total number |
---|
990 | of vertices in the graph. The vertex numbering has the property that |
---|
991 | for every arc $(i\rightarrow j)$ in the graph the condition |
---|
992 | $num(i)<num(j)$ holds. Special case $num(i)=0$ means that vertex $i$ is |
---|
993 | not assigned a number, because the graph is {\it not} acyclic. |
---|
994 | |
---|
995 | \subsubsection*{Returns} |
---|
996 | |
---|
997 | If the graph is acyclic and therefore all the vertices have been |
---|
998 | assigned numbers, the routine \verb|glp_top_sort| returns zero. |
---|
999 | Otherwise, if the graph is not acyclic, the routine returns the number |
---|
1000 | of vertices which have not been numbered, i.e. for which $num(i)=0$. |
---|
1001 | |
---|
1002 | \subsubsection*{Example} |
---|
1003 | |
---|
1004 | The following program reads a digraph from a plain text file |
---|
1005 | `\verb|graph.txt|' and performs topological sorting of its vertices. |
---|
1006 | |
---|
1007 | \begin{footnotesize} |
---|
1008 | \begin{verbatim} |
---|
1009 | #include <stddef.h> |
---|
1010 | #include <stdio.h> |
---|
1011 | #include <stdlib.h> |
---|
1012 | #include <glpk.h> |
---|
1013 | |
---|
1014 | typedef struct { int num; } v_data; |
---|
1015 | |
---|
1016 | #define vertex(v) ((v_data *)((v)->data)) |
---|
1017 | |
---|
1018 | int main(void) |
---|
1019 | { glp_graph *G; |
---|
1020 | int i, cnt; |
---|
1021 | G = glp_create_graph(sizeof(v_data), 0); |
---|
1022 | glp_read_graph(G, "graph.txt"); |
---|
1023 | cnt = glp_top_sort(G, offsetof(v_data, num)); |
---|
1024 | printf("cnt = %d\n", cnt); |
---|
1025 | for (i = 1; i <= G->nv; i++) |
---|
1026 | printf("num[%d] = %d\n", i, vertex(G->v[i])->num); |
---|
1027 | glp_delete_graph(G); |
---|
1028 | return 0; |
---|
1029 | } |
---|
1030 | \end{verbatim} |
---|
1031 | \end{footnotesize} |
---|
1032 | |
---|
1033 | \noindent |
---|
1034 | If the file `\verb|graph.txt|' contains the graph shown below: |
---|
1035 | |
---|
1036 | \bigskip |
---|
1037 | |
---|
1038 | \noindent\hfil |
---|
1039 | \xymatrix @=20pt |
---|
1040 | { |
---|
1041 | 1\ar[rrr]&&&2\ar[r]\ar[rddd]&3\ar[rd]&&&&\\ |
---|
1042 | &&&4\ar[ru]&&5\ar[r]&6\ar[rd]\ar[dd]&&\\ |
---|
1043 | 7\ar[r]&8\ar[r]&9\ar[ruu]\ar[ru]\ar[r]\ar[rd]&10\ar[rr]\ar[rru]&& |
---|
1044 | 11\ar[ru]&&12\ar[r]&13\\ |
---|
1045 | &&&14\ar[r]&15\ar[rrru]\ar[rr]&&16\ar[rru]\ar[rr]&&17\\ |
---|
1046 | } |
---|
1047 | |
---|
1048 | \bigskip\bigskip |
---|
1049 | |
---|
1050 | \noindent |
---|
1051 | the program output may look like follows: |
---|
1052 | |
---|
1053 | \begin{footnotesize} |
---|
1054 | \begin{verbatim} |
---|
1055 | Reading graph from `graph.txt'... |
---|
1056 | Graph has 17 vertices and 23 arcs |
---|
1057 | 24 lines were read |
---|
1058 | cnt = 0 |
---|
1059 | num[1] = 8 |
---|
1060 | num[2] = 9 |
---|
1061 | num[3] = 10 |
---|
1062 | num[4] = 4 |
---|
1063 | num[5] = 11 |
---|
1064 | num[6] = 12 |
---|
1065 | num[7] = 1 |
---|
1066 | num[8] = 2 |
---|
1067 | num[9] = 3 |
---|
1068 | num[10] = 5 |
---|
1069 | num[11] = 6 |
---|
1070 | num[12] = 14 |
---|
1071 | num[13] = 16 |
---|
1072 | num[14] = 7 |
---|
1073 | num[15] = 13 |
---|
1074 | num[16] = 15 |
---|
1075 | num[17] = 17 |
---|
1076 | \end{verbatim} |
---|
1077 | \end{footnotesize} |
---|
1078 | |
---|
1079 | \noindent |
---|
1080 | The output corresponds to the following vertex numbering: |
---|
1081 | |
---|
1082 | \bigskip |
---|
1083 | |
---|
1084 | \noindent\hfil |
---|
1085 | \xymatrix @=20pt |
---|
1086 | { |
---|
1087 | 8\ar[rrr]&&&9\ar[r]\ar[rddd]&10\ar[rd]&&&&\\ |
---|
1088 | &&&4\ar[ru]&&11\ar[r]&12\ar[rd]\ar[dd]&&\\ |
---|
1089 | 1\ar[r]&2\ar[r]&3\ar[ruu]\ar[ru]\ar[r]\ar[rd]&5\ar[rr]\ar[rru]&& |
---|
1090 | 6\ar[ru]&&14\ar[r]&16\\ |
---|
1091 | &&&7\ar[r]&13\ar[rrru]\ar[rr]&&15\ar[rru]\ar[rr]&&17\\ |
---|
1092 | } |
---|
1093 | |
---|
1094 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
1095 | |
---|
1096 | \chapter{Network optimization API routines} |
---|
1097 | |
---|
1098 | \section{Minimum cost flow problem} |
---|
1099 | |
---|
1100 | \subsection{Background} |
---|
1101 | |
---|
1102 | The {\it minimum cost flow problem} (MCFP) is stated as follows. Let |
---|
1103 | there be given a directed graph (flow network) $G=(V,A)$, where $V$ is |
---|
1104 | a set of vertices (nodes), and $A\subseteq V\times V$ is a set of arcs. |
---|
1105 | Let for each node $i\in V$ there be given a quantity $b_i$ having the |
---|
1106 | following meaning: |
---|
1107 | |
---|
1108 | if $b_i>0$, then $|b_i|$ is a {\it supply} at node $i$, which shows |
---|
1109 | how many flow units are {\it generated} at node $i$ (or, equivalently, |
---|
1110 | entering the network through node $i$ from the outside); |
---|
1111 | |
---|
1112 | if $b_i<0$, then $|b_i|$ is a {\it demand} at node $i$, which shows how |
---|
1113 | many flow units are {\it lost} at node $i$ (or, equivalently, leaving |
---|
1114 | the network through node $i$ to the outside); |
---|
1115 | |
---|
1116 | if $b_i=0$, then $i$ is a {\it transshipment} node, at which the flow |
---|
1117 | is conserved, i.e. neither generated nor lost. |
---|
1118 | |
---|
1119 | Let also for each arc $a=(i,j)\in A$ there be given the following three |
---|
1120 | quantities: |
---|
1121 | |
---|
1122 | $l_{ij}$, a (non-negative) lower bound to the flow through arc $(i,j)$; |
---|
1123 | |
---|
1124 | $u_{ij}$, an upper bound to the flow through arc $(i,j)$, which is the |
---|
1125 | {\it arc capacity}; |
---|
1126 | |
---|
1127 | $c_{ij}$, a per-unit cost of the flow through arc $(i,j)$. |
---|
1128 | |
---|
1129 | The problem is to find flows $x_{ij}$ through every arc of the network, |
---|
1130 | which satisfy the specified bounds and the conservation constraints at |
---|
1131 | all nodes, and minimize the total flow cost. Here the conservation |
---|
1132 | constraint at a node means that the total flow entering this node |
---|
1133 | through its incoming arcs plus the supply at this node must be equal to |
---|
1134 | the total flow leaving this node through its outgoing arcs plus the |
---|
1135 | demand at this node. |
---|
1136 | |
---|
1137 | An example of the minimum cost flow problem is shown on Fig.~1. |
---|
1138 | |
---|
1139 | \bigskip |
---|
1140 | |
---|
1141 | \noindent\hfil |
---|
1142 | \xymatrix @C=48pt |
---|
1143 | {_{20}\ar@{~>}[d]& |
---|
1144 | v_2\ar[r]|{_{0,10,\$2}}\ar[dd]|{_{0,9,\$3}}& |
---|
1145 | v_3\ar[dd]|{_{2,12,\$1}}\ar[r]|{_{0,18,\$0}}& |
---|
1146 | v_8\ar[rd]|{_{0,20,\$9}}&\\ |
---|
1147 | v_1\ar[ru]|{_{0,14,\$0}}\ar[rd]|{_{0,23,\$0}}&&& |
---|
1148 | v_6\ar[d]|{_{0,7,\$0}}\ar[u]|{_{4,8,\$0}}& |
---|
1149 | v_9\ar@{~>}[d]\\ |
---|
1150 | &v_4\ar[r]|{_{0,26,\$0}}& |
---|
1151 | v_5\ar[luu]|{_{0,11,\$1}}\ar[ru]|{_{0,25,\$5}}\ar[r]|{_{0,4,\$7}}& |
---|
1152 | v_7\ar[ru]|{_{0,15,\$3}}&_{20}\\ |
---|
1153 | } |
---|
1154 | |
---|
1155 | \medskip |
---|
1156 | |
---|
1157 | \noindent\hfil |
---|
1158 | \begin{tabular}{ccc} |
---|
1159 | \xymatrix @C=48pt{v_i\ar[r]|{\ l,u,\$c\ }&v_j\\}& |
---|
1160 | \xymatrix{\hbox{\footnotesize supply}\ar@{~>}[r]&v_i\\}& |
---|
1161 | \xymatrix{v_i\ar@{~>}[r]&\hbox{\footnotesize demand}\\}\\ |
---|
1162 | \end{tabular} |
---|
1163 | |
---|
1164 | \bigskip |
---|
1165 | |
---|
1166 | \noindent\hfil |
---|
1167 | Fig.~1. An example of the minimum cost flow problem. |
---|
1168 | |
---|
1169 | \bigskip |
---|
1170 | |
---|
1171 | The minimum cost flow problem can be naturally formulated as the |
---|
1172 | following LP problem: |
---|
1173 | |
---|
1174 | \medskip |
---|
1175 | |
---|
1176 | \noindent |
---|
1177 | \hspace{.5in}minimize |
---|
1178 | $$z=\sum_{(i,j)\in A}c_{ij}x_{ij}\eqno(1)$$ |
---|
1179 | \hspace{.5in}subject to |
---|
1180 | $$\sum_{(i,j)\in A}x_{ij}-\sum_{(j,i)\in A}x_{ji}=b_i\ \ \ \hbox |
---|
1181 | {for all}\ i\in V\eqno(2)$$ |
---|
1182 | $$l_{ij}\leq x_{ij}\leq u_{ij}\ \ \ \hbox{for all}\ (i,j)\in A |
---|
1183 | \eqno(3)$$ |
---|
1184 | |
---|
1185 | \newpage |
---|
1186 | |
---|
1187 | \subsection{glp\_read\_mincost---read minimum cost flow problem\\data |
---|
1188 | in DIMACS format} |
---|
1189 | |
---|
1190 | \subsubsection*{Synopsis} |
---|
1191 | |
---|
1192 | \begin{verbatim} |
---|
1193 | int glp_read_mincost(glp_graph *G, int v_rhs, int a_low, |
---|
1194 | int a_cap, int a_cost, const char *fname); |
---|
1195 | \end{verbatim} |
---|
1196 | |
---|
1197 | \subsubsection*{Description} |
---|
1198 | |
---|
1199 | The routine \verb|glp_read_mincost| reads the minimum cost flow problem |
---|
1200 | data from a text file in DIMACS format. |
---|
1201 | |
---|
1202 | The parameter \verb|G| specifies the graph object, to which the problem |
---|
1203 | data have to be stored. Note that before reading data the current |
---|
1204 | content of the graph object is completely erased with the routine |
---|
1205 | \verb|glp_erase_graph|. |
---|
1206 | |
---|
1207 | The parameter \verb|v_rhs| specifies an offset of the field of type |
---|
1208 | \verb|double| in the vertex data block, to which the routine stores |
---|
1209 | $b_i$, the supply/demand value. If \verb|v_rhs| $<0$, the value is not |
---|
1210 | stored. |
---|
1211 | |
---|
1212 | The parameter \verb|a_low| specifies an offset of the field of type |
---|
1213 | \verb|double| in the arc data block, to which the routine stores |
---|
1214 | $l_{ij}$, the lower bound to the arc flow. If \verb|a_low| $<0$, the |
---|
1215 | lower bound is not stored. |
---|
1216 | |
---|
1217 | The parameter \verb|a_cap| specifies an offset of the field of type |
---|
1218 | \verb|double| in the arc data block, to which the routine stores |
---|
1219 | $u_{ij}$, the upper bound to the arc flow (the arc capacity). If |
---|
1220 | \verb|a_cap| $<0$, the upper bound is not stored. |
---|
1221 | |
---|
1222 | The parameter \verb|a_cost| specifies an offset of the field of type |
---|
1223 | \verb|double| in the arc data block, to which the routine stores |
---|
1224 | $c_{ij}$, the per-unit cost of the arc flow. If \verb|a_cost| $<0$, the |
---|
1225 | cost is not stored. |
---|
1226 | |
---|
1227 | The character string \verb|fname| specifies the name of a text file to |
---|
1228 | be read in. (If the file name name ends with the suffix `\verb|.gz|', |
---|
1229 | the file is assumed to be compressed, in which case the routine |
---|
1230 | decompresses it ``on the fly''.) |
---|
1231 | |
---|
1232 | \subsubsection*{Returns} |
---|
1233 | |
---|
1234 | If the operation was successful, the routine returns zero. Otherwise, |
---|
1235 | it prints an error message and returns non-zero. |
---|
1236 | |
---|
1237 | \newpage |
---|
1238 | |
---|
1239 | \subsubsection*{Example} |
---|
1240 | |
---|
1241 | \begin{footnotesize} |
---|
1242 | \begin{verbatim} |
---|
1243 | typedef struct |
---|
1244 | { /* vertex data block */ |
---|
1245 | ... |
---|
1246 | double rhs; |
---|
1247 | ... |
---|
1248 | } v_data; |
---|
1249 | |
---|
1250 | typedef struct |
---|
1251 | { /* arc data block */ |
---|
1252 | ... |
---|
1253 | double low, cap, cost; |
---|
1254 | ... |
---|
1255 | } a_data; |
---|
1256 | |
---|
1257 | int main(void) |
---|
1258 | { glp_graph *G; |
---|
1259 | int ret; |
---|
1260 | G = glp_create_graph(sizeof(v_data), sizeof(a_data)); |
---|
1261 | ret = glp_read_mincost(G, offsetof(v_data, rhs), |
---|
1262 | offsetof(a_data, low), offsetof(a_data, cap), |
---|
1263 | offsetof(a_data, cost), "sample.min"); |
---|
1264 | if (ret != 0) goto ... |
---|
1265 | ... |
---|
1266 | } |
---|
1267 | \end{verbatim} |
---|
1268 | \end{footnotesize} |
---|
1269 | |
---|
1270 | \subsubsection*{DIMACS minimum cost flow problem format\footnote{This |
---|
1271 | material is based on the paper ``The First DIMACS International |
---|
1272 | Algorithm Implementation Challenge: Problem Definitions and |
---|
1273 | Specifications'', which is publically available at |
---|
1274 | {\tt http://dimacs.rutgers.edu/Challenges/}.}} |
---|
1275 | \label{subsecmincost} |
---|
1276 | |
---|
1277 | The DIMACS input file is a plain ASCII text file. It contains |
---|
1278 | {\it lines} of several types described below. A line is terminated with |
---|
1279 | an end-of-line character. Fields in each line are separated by at least |
---|
1280 | one blank space. Each line begins with a one-character designator to |
---|
1281 | identify the line type. |
---|
1282 | |
---|
1283 | Note that DIMACS requires all numerical quantities to be integers in |
---|
1284 | the range $[-2^{31},\ 2^{31}-1]$ while GLPK allows the quantities to be |
---|
1285 | floating-point numbers. |
---|
1286 | |
---|
1287 | \newpage |
---|
1288 | |
---|
1289 | \paragraph{Comment lines.} Comment lines give human-readable information |
---|
1290 | about the file and are ignored by programs. Comment lines can appear |
---|
1291 | anywhere in the file. Each comment line begins with a lower-case |
---|
1292 | character \verb|c|. |
---|
1293 | |
---|
1294 | \begin{verbatim} |
---|
1295 | c This is a comment line |
---|
1296 | \end{verbatim} |
---|
1297 | |
---|
1298 | \paragraph{Problem line.} There is one problem line per data file. The |
---|
1299 | problem line must appear before any node or arc descriptor lines. It has |
---|
1300 | the following format: |
---|
1301 | |
---|
1302 | \begin{verbatim} |
---|
1303 | p min NODES ARCS |
---|
1304 | \end{verbatim} |
---|
1305 | |
---|
1306 | \noindent |
---|
1307 | The lower-case character \verb|p| signifies that this is a problem line. |
---|
1308 | The three-character problem designator \verb|min| identifies the file as |
---|
1309 | containing specification information for the minimum cost flow problem. |
---|
1310 | The \verb|NODES| field contains an integer value specifying the number |
---|
1311 | of nodes in the network. The \verb|ARCS| field contains an integer value |
---|
1312 | specifying the number of arcs in the network. |
---|
1313 | |
---|
1314 | \paragraph{Node descriptors.} All node descriptor lines must appear |
---|
1315 | before all arc descriptor lines. The node descriptor lines describe |
---|
1316 | supply and demand nodes, but not transshipment nodes. That is, only |
---|
1317 | nodes with non-zero node supply/demand values appear. There is one node |
---|
1318 | descriptor line for each such node, with the following format: |
---|
1319 | |
---|
1320 | \begin{verbatim} |
---|
1321 | n ID FLOW |
---|
1322 | \end{verbatim} |
---|
1323 | |
---|
1324 | \noindent |
---|
1325 | The lower-case character \verb|n| signifies that this is a node |
---|
1326 | descriptor line. The \verb|ID| field gives a node identification number, |
---|
1327 | an integer between 1 and \verb|NODES|. The \verb|FLOW| field gives the |
---|
1328 | amount of supply (if positive) or demand (if negative) at node |
---|
1329 | \verb|ID|. |
---|
1330 | |
---|
1331 | \paragraph{Arc descriptors.} There is one arc descriptor line for each |
---|
1332 | arc in the network. Arc descriptor lines are of the following format: |
---|
1333 | |
---|
1334 | \begin{verbatim} |
---|
1335 | a SRC DST LOW CAP COST |
---|
1336 | \end{verbatim} |
---|
1337 | |
---|
1338 | \noindent |
---|
1339 | The lower-case character \verb|a| signifies that this is an arc |
---|
1340 | descriptor line. For a directed arc $(i,j)$ the \verb|SRC| field gives |
---|
1341 | the identification number $i$ for the tail endpoint, and the \verb|DST| |
---|
1342 | field gives the identification number $j$ for the head endpoint. |
---|
1343 | Identification numbers are integers between 1 and \verb|NODES|. The |
---|
1344 | \verb|LOW| field specifies the minimum amount of flow that can be sent |
---|
1345 | along arc $(i,j)$, and the \verb|CAP| field gives the maximum amount of |
---|
1346 | flow that can be sent along arc $(i,j)$ in a feasible flow. The |
---|
1347 | \verb|COST| field contains the per-unit cost of flow sent along arc |
---|
1348 | $(i,j)$. |
---|
1349 | |
---|
1350 | \paragraph{Example.} Below here is an example of the data file in |
---|
1351 | DIMACS format corresponding to the minimum cost flow problem shown on |
---|
1352 | Fig~1. |
---|
1353 | |
---|
1354 | \begin{footnotesize} |
---|
1355 | \begin{verbatim} |
---|
1356 | c sample.min |
---|
1357 | c |
---|
1358 | c This is an example of the minimum cost flow problem data |
---|
1359 | c in DIMACS format. |
---|
1360 | c |
---|
1361 | p min 9 14 |
---|
1362 | c |
---|
1363 | n 1 20 |
---|
1364 | n 9 -20 |
---|
1365 | c |
---|
1366 | a 1 2 0 14 0 |
---|
1367 | a 1 4 0 23 0 |
---|
1368 | a 2 3 0 10 2 |
---|
1369 | a 2 4 0 9 3 |
---|
1370 | a 3 5 2 12 1 |
---|
1371 | a 3 8 0 18 0 |
---|
1372 | a 4 5 0 26 0 |
---|
1373 | a 5 2 0 11 1 |
---|
1374 | a 5 6 0 25 5 |
---|
1375 | a 5 7 0 4 7 |
---|
1376 | a 6 7 0 7 0 |
---|
1377 | a 6 8 4 8 0 |
---|
1378 | a 7 9 0 15 3 |
---|
1379 | a 8 9 0 20 9 |
---|
1380 | c |
---|
1381 | c eof |
---|
1382 | \end{verbatim} |
---|
1383 | \end{footnotesize} |
---|
1384 | |
---|
1385 | \newpage |
---|
1386 | |
---|
1387 | \subsection{glp\_write\_mincost---write minimum cost flow problem\\data |
---|
1388 | in DIMACS format} |
---|
1389 | |
---|
1390 | \subsubsection*{Synopsis} |
---|
1391 | |
---|
1392 | \begin{verbatim} |
---|
1393 | int glp_write_mincost(glp_graph *G, int v_rhs, int a_low, |
---|
1394 | int a_cap, int a_cost, const char *fname); |
---|
1395 | \end{verbatim} |
---|
1396 | |
---|
1397 | \subsubsection*{Description} |
---|
1398 | |
---|
1399 | The routine \verb|glp_write_mincost| writes the minimum cost flow |
---|
1400 | problem data to a text file in DIMACS format. |
---|
1401 | |
---|
1402 | The parameter \verb|G| is the graph (network) program object, which |
---|
1403 | specifies the minimum cost flow problem instance. |
---|
1404 | |
---|
1405 | The parameter \verb|v_rhs| specifies an offset of the field of type |
---|
1406 | \verb|double| in the vertex data block, which contains $b_i$, the |
---|
1407 | supply/demand value. If \verb|v_rhs| $<0$, it is assumed that $b_i=0$ |
---|
1408 | for all nodes. |
---|
1409 | |
---|
1410 | The parameter \verb|a_low| specifies an offset of the field of type |
---|
1411 | \verb|double| in the arc data block, which contains $l_{ij}$, the lower |
---|
1412 | bound to the arc flow. If \verb|a_low| $<0$, it is assumed that |
---|
1413 | $l_{ij}=0$ for all arcs. |
---|
1414 | |
---|
1415 | The parameter \verb|a_cap| specifies an offset of the field of type |
---|
1416 | \verb|double| in the arc data block, which contains $u_{ij}$, the upper |
---|
1417 | bound to the arc flow (the arc capacity). If the upper bound is |
---|
1418 | specified as \verb|DBL_MAX|, it is assumed that $u_{ij}=\infty$, i.e. |
---|
1419 | the arc is uncapacitated. If \verb|a_cap| $<0$, it is assumed that |
---|
1420 | $u_{ij}=1$ for all arcs. |
---|
1421 | |
---|
1422 | The parameter \verb|a_cost| specifies an offset of the field of type |
---|
1423 | \verb|double| in the arc data block, which contains $c_{ij}$, the |
---|
1424 | per-unit cost of the arc flow. If \verb|a_cost| $<0$, it is assumed that |
---|
1425 | $c_{ij}=0$ for all arcs. |
---|
1426 | |
---|
1427 | The character string \verb|fname| specifies a name of the text file to |
---|
1428 | be written out. (If the file name ends with suffix `\verb|.gz|', the |
---|
1429 | file is assumed to be compressed, in which case the routine performs |
---|
1430 | automatic compression on writing it.) |
---|
1431 | |
---|
1432 | \subsubsection*{Returns} |
---|
1433 | |
---|
1434 | If the operation was successful, the routine returns zero. Otherwise, |
---|
1435 | it prints an error message and returns non-zero. |
---|
1436 | |
---|
1437 | \newpage |
---|
1438 | |
---|
1439 | \subsection{glp\_mincost\_lp---convert minimum cost flow problem\\to LP} |
---|
1440 | |
---|
1441 | \subsubsection*{Synopsis} |
---|
1442 | |
---|
1443 | \begin{verbatim} |
---|
1444 | void glp_mincost_lp(glp_prob *lp, glp_graph *G, int names, |
---|
1445 | int v_rhs, int a_low, int a_cap, int a_cost); |
---|
1446 | \end{verbatim} |
---|
1447 | |
---|
1448 | \subsubsection*{Description} |
---|
1449 | |
---|
1450 | The routine \verb|glp_mincost_lp| builds LP problem (1)---(3), which |
---|
1451 | corresponds to the specified minimum cost flow problem. |
---|
1452 | |
---|
1453 | The parameter \verb|lp| is the resultant LP problem object to be built. |
---|
1454 | Note that on entry its current content is erased with the routine |
---|
1455 | \verb|glp_erase_prob|. |
---|
1456 | |
---|
1457 | The parameter \verb|G| is the graph (network) program object, which |
---|
1458 | specifies the minimum cost flow problem instance. |
---|
1459 | |
---|
1460 | The parameter \verb|names| is a flag. If it is \verb|GLP_ON|, the |
---|
1461 | routine uses symbolic names of the graph object components to assign |
---|
1462 | symbolic names to the LP problem object components. If the flag is |
---|
1463 | \verb|GLP_OFF|, no symbolic names are assigned. |
---|
1464 | |
---|
1465 | The parameter \verb|v_rhs| specifies an offset of the field of type |
---|
1466 | \verb|double| in the vertex data block, which contains $b_i$, the |
---|
1467 | supply/demand value. If \verb|v_rhs| $<0$, it is assumed that $b_i=0$ |
---|
1468 | for all nodes. |
---|
1469 | |
---|
1470 | The parameter \verb|a_low| specifies an offset of the field of type |
---|
1471 | \verb|double| in the arc data block, which contains $l_{ij}$, the lower |
---|
1472 | bound to the arc flow. If \verb|a_low| $<0$, it is assumed that |
---|
1473 | $l_{ij}=0$ for all arcs. |
---|
1474 | |
---|
1475 | The parameter \verb|a_cap| specifies an offset of the field of type |
---|
1476 | \verb|double| in the arc data block, which contains $u_{ij}$, the upper |
---|
1477 | bound to the arc flow (the arc capacity). If the upper bound is |
---|
1478 | specified as \verb|DBL_MAX|, it is assumed that $u_{ij}=\infty$, i.e. |
---|
1479 | the arc is uncapacitated. If \verb|a_cap| $<0$, it is assumed that |
---|
1480 | $u_{ij}=1$ for all arcs. |
---|
1481 | |
---|
1482 | The parameter \verb|a_cost| specifies an offset of the field of type |
---|
1483 | \verb|double| in the arc data block, which contains $c_{ij}$, the |
---|
1484 | per-unit cost of the arc flow. If \verb|a_cost| $<0$, it is assumed that |
---|
1485 | $c_{ij}=0$ for all arcs. |
---|
1486 | |
---|
1487 | \subsubsection*{Example} |
---|
1488 | |
---|
1489 | The example program below reads the minimum cost problem instance in |
---|
1490 | DIMACS format from file `\verb|sample.min|', converts the instance to |
---|
1491 | LP, and then writes the resultant LP in CPLEX format to file |
---|
1492 | `\verb|mincost.lp|'. |
---|
1493 | |
---|
1494 | \newpage |
---|
1495 | |
---|
1496 | \begin{footnotesize} |
---|
1497 | \begin{verbatim} |
---|
1498 | #include <stddef.h> |
---|
1499 | #include <glpk.h> |
---|
1500 | |
---|
1501 | typedef struct { double rhs; } v_data; |
---|
1502 | typedef struct { double low, cap, cost; } a_data; |
---|
1503 | |
---|
1504 | int main(void) |
---|
1505 | { glp_graph *G; |
---|
1506 | glp_prob *lp; |
---|
1507 | G = glp_create_graph(sizeof(v_data), sizeof(a_data)); |
---|
1508 | glp_read_mincost(G, offsetof(v_data, rhs), |
---|
1509 | offsetof(a_data, low), offsetof(a_data, cap), |
---|
1510 | offsetof(a_data, cost), "sample.min"); |
---|
1511 | lp = glp_create_prob(); |
---|
1512 | glp_mincost_lp(lp, G, GLP_ON, offsetof(v_data, rhs), |
---|
1513 | offsetof(a_data, low), offsetof(a_data, cap), |
---|
1514 | offsetof(a_data, cost)); |
---|
1515 | glp_delete_graph(G); |
---|
1516 | glp_write_lp(lp, NULL, "mincost.lp"); |
---|
1517 | glp_delete_prob(lp); |
---|
1518 | return 0; |
---|
1519 | } |
---|
1520 | \end{verbatim} |
---|
1521 | \end{footnotesize} |
---|
1522 | |
---|
1523 | If `\verb|sample.min|' is the example data file from the subsection |
---|
1524 | describing the routine \verb|glp_read_mincost|, file `\verb|mincost.lp|' |
---|
1525 | may look like follows: |
---|
1526 | |
---|
1527 | \begin{footnotesize} |
---|
1528 | \begin{verbatim} |
---|
1529 | Minimize |
---|
1530 | obj: + 3 x(2,4) + 2 x(2,3) + x(3,5) + 7 x(5,7) + 5 x(5,6) |
---|
1531 | + x(5,2) + 3 x(7,9) + 9 x(8,9) |
---|
1532 | |
---|
1533 | Subject To |
---|
1534 | r_1: + x(1,2) + x(1,4) = 20 |
---|
1535 | r_2: - x(5,2) + x(2,3) + x(2,4) - x(1,2) = 0 |
---|
1536 | r_3: + x(3,5) + x(3,8) - x(2,3) = 0 |
---|
1537 | r_4: + x(4,5) - x(2,4) - x(1,4) = 0 |
---|
1538 | r_5: + x(5,2) + x(5,6) + x(5,7) - x(4,5) - x(3,5) = 0 |
---|
1539 | r_6: + x(6,7) + x(6,8) - x(5,6) = 0 |
---|
1540 | r_7: + x(7,9) - x(6,7) - x(5,7) = 0 |
---|
1541 | r_8: + x(8,9) - x(6,8) - x(3,8) = 0 |
---|
1542 | r_9: - x(8,9) - x(7,9) = -20 |
---|
1543 | |
---|
1544 | Bounds |
---|
1545 | 0 <= x(1,4) <= 23 |
---|
1546 | 0 <= x(1,2) <= 14 |
---|
1547 | 0 <= x(2,4) <= 9 |
---|
1548 | 0 <= x(2,3) <= 10 |
---|
1549 | 0 <= x(3,8) <= 18 |
---|
1550 | 2 <= x(3,5) <= 12 |
---|
1551 | 0 <= x(4,5) <= 26 |
---|
1552 | 0 <= x(5,7) <= 4 |
---|
1553 | 0 <= x(5,6) <= 25 |
---|
1554 | 0 <= x(5,2) <= 11 |
---|
1555 | 4 <= x(6,8) <= 8 |
---|
1556 | 0 <= x(6,7) <= 7 |
---|
1557 | 0 <= x(7,9) <= 15 |
---|
1558 | 0 <= x(8,9) <= 20 |
---|
1559 | |
---|
1560 | End |
---|
1561 | \end{verbatim} |
---|
1562 | \end{footnotesize} |
---|
1563 | |
---|
1564 | \subsection{glp\_mincost\_okalg---solve minimum cost flow problem with |
---|
1565 | out-of-kilter algorithm} |
---|
1566 | |
---|
1567 | \subsubsection*{Synopsis} |
---|
1568 | |
---|
1569 | \begin{verbatim} |
---|
1570 | int glp_mincost_okalg(glp_graph *G, int v_rhs, int a_low, |
---|
1571 | int a_cap, int a_cost, double *sol, int a_x, int v_pi); |
---|
1572 | \end{verbatim} |
---|
1573 | |
---|
1574 | \subsubsection*{Description} |
---|
1575 | |
---|
1576 | The routine \verb|glp_mincost_okalg| finds optimal solution to the |
---|
1577 | minimum cost flow problem with the out-of-kilter |
---|
1578 | algorithm.\footnote{GLPK implementation of the out-of-kilter algorithm |
---|
1579 | is based on the following book: L.~R.~Ford,~Jr., and D.~R.~Fulkerson, |
---|
1580 | ``Flows in Networks,'' The RAND Corp., Report R-375-PR (August 1962), |
---|
1581 | Chap. III ``Minimal Cost Flow Problems,'' pp.~113-26.} Note that this |
---|
1582 | routine requires all the problem data to be integer-valued. |
---|
1583 | |
---|
1584 | The parameter \verb|G| is a graph (network) program object which |
---|
1585 | specifies the minimum cost flow problem instance to be solved. |
---|
1586 | |
---|
1587 | The parameter \verb|v_rhs| specifies an offset of the field of type |
---|
1588 | \verb|double| in the vertex data block, which contains $b_i$, the |
---|
1589 | supply/demand value. This value must be integer in the range |
---|
1590 | [$-$\verb|INT_MAX|, $+$\verb|INT_MAX|]. If \verb|v_rhs| $<0$, it is |
---|
1591 | assumed that $b_i=0$ for all nodes. |
---|
1592 | |
---|
1593 | The parameter \verb|a_low| specifies an offset of the field of type |
---|
1594 | \verb|double| in the arc data block, which contains $l_{ij}$, the lower |
---|
1595 | bound to the arc flow. This bound must be integer in the range |
---|
1596 | [$0$, \verb|INT_MAX|]. If \verb|a_low| $<0$, it is assumed that |
---|
1597 | $l_{ij}=0$ for all arcs. |
---|
1598 | |
---|
1599 | The parameter \verb|a_cap| specifies an offset of the field of type |
---|
1600 | \verb|double| in the arc data block, which contains $u_{ij}$, the upper |
---|
1601 | bound to the arc flow (the arc capacity). This bound must be integer in |
---|
1602 | the range [$l_{ij}$, \verb|INT_MAX|]. If \verb|a_cap| $<0$, it is |
---|
1603 | assumed that $u_{ij}=1$ for all arcs. |
---|
1604 | |
---|
1605 | The parameter \verb|a_cost| specifies an offset of the field of type |
---|
1606 | \verb|double| in the arc data block, which contains $c_{ij}$, the |
---|
1607 | per-unit cost of the arc flow. This value must be integer in the range |
---|
1608 | [$-$\verb|INT_MAX|, $+$\verb|INT_MAX|]. If \verb|a_cost| $<0$, it is |
---|
1609 | assumed that $c_{ij}=0$ for all arcs. |
---|
1610 | |
---|
1611 | The parameter \verb|sol| specifies a location, to which the routine |
---|
1612 | stores the objective value (that is, the total cost) found. If |
---|
1613 | \verb|sol| is NULL, the objective value is not stored. |
---|
1614 | |
---|
1615 | The parameter \verb|a_x| specifies an offset of the field of type |
---|
1616 | \verb|double| in the arc data block, to which the routine stores |
---|
1617 | $x_{ij}$, the arc flow found. If \verb|a_x| $<0$, the arc flow value is |
---|
1618 | not stored. |
---|
1619 | |
---|
1620 | The parameter \verb|v_pi| specifies an offset of the field of type |
---|
1621 | \verb|double| in the vertex data block, to which the routine stores |
---|
1622 | $\pi_i$, the node potential, which is the Lagrange multiplier for the |
---|
1623 | corresponding flow conservation equality constraint (see (2) in |
---|
1624 | Subsection ``Background''). If necessary, the application program may |
---|
1625 | use the node potentials to compute $\lambda_{ij}$, reduced costs of the |
---|
1626 | arc flows $x_{ij}$, which are the Lagrange multipliers for the arc flow |
---|
1627 | bound constraints (see (3) ibid.), using the following formula: |
---|
1628 | $$\lambda_{ij}=c_{ij}-(\pi_i-\pi_j),$$ |
---|
1629 | where $c_{ij}$ is the per-unit cost for arc $(i,j)$. |
---|
1630 | |
---|
1631 | Note that all solution components (the objective value, arc flows, and |
---|
1632 | node potentials) computed by the routine are always integer-valued. |
---|
1633 | |
---|
1634 | \subsubsection*{Returns} |
---|
1635 | |
---|
1636 | \def\arraystretch{1} |
---|
1637 | |
---|
1638 | \begin{tabular}{@{}p{25mm}p{97.3mm}@{}} |
---|
1639 | 0 & Optimal solution found.\\ |
---|
1640 | \verb|GLP_ENOPFS| & No (primal) feasible solution exists.\\ |
---|
1641 | \verb|GLP_EDATA| & Unable to start the search, because some problem |
---|
1642 | data are either not integer-valued or out of range. This code is also |
---|
1643 | returned if the total supply, which is the sum of $b_i$ over all source |
---|
1644 | nodes (nodes with $b_i>0$), exceeds \verb|INT_MAX|.\\ |
---|
1645 | \end{tabular} |
---|
1646 | |
---|
1647 | \noindent |
---|
1648 | \begin{tabular}{@{}p{25mm}p{97.3mm}@{}} |
---|
1649 | \verb|GLP_ERANGE| & The search was prematurely terminated because of |
---|
1650 | integer overflow.\\ |
---|
1651 | \verb|GLP_EFAIL| & An error has been detected in the program logic. |
---|
1652 | (If this code is returned for your problem instance, please report to |
---|
1653 | \verb|<bug-glpk@gnu.org>|.)\\ |
---|
1654 | \end{tabular} |
---|
1655 | |
---|
1656 | \subsubsection*{Comments} |
---|
1657 | |
---|
1658 | By design the out-of-kilter algorithm is applicable only to networks, |
---|
1659 | where $b_i=0$ for {\it all} nodes, i.e. actually this algorithm finds a |
---|
1660 | minimal cost {\it circulation}. Due to this requirement the routine |
---|
1661 | \verb|glp_mincost_okalg| converts the original network to a network |
---|
1662 | suitable for the out-of-kilter algorithm in the following |
---|
1663 | way:\footnote{The conversion is performed internally and does not change |
---|
1664 | the original network program object passed to the routine.} |
---|
1665 | |
---|
1666 | 1) it adds two auxiliary nodes $s$ and $t$; |
---|
1667 | |
---|
1668 | 2) for each original node $i$ with $b_i>0$ the routine adds auxiliary |
---|
1669 | supply arc $(s\rightarrow i)$, flow $x_{si}$ through which is costless |
---|
1670 | ($c_{si}=0$) and fixed to $+b_i$ ($l_{si}=u_{si}=+b_i$); |
---|
1671 | |
---|
1672 | 3) for each original node $i$ with $b_i<0$ the routine adds auxiliary |
---|
1673 | demand arc $(i\rightarrow t)$, flow $x_{it}$ through which is costless |
---|
1674 | ($c_{it}=0$) and fixed to $-b_i$ ($l_{it}=u_{it}=-b_i$); |
---|
1675 | |
---|
1676 | 4) finally, the routine adds auxiliary feedback arc $(t\rightarrow s)$, |
---|
1677 | flow $x_{ts}$ through which is also costless ($c_{ts}=0$) and fixed to |
---|
1678 | $F$ ($l_{ts}=u_{ts}=F$), where $\displaystyle F=\sum_{b_i>0}b_i$ is the |
---|
1679 | total supply. |
---|
1680 | |
---|
1681 | \subsubsection*{Example} |
---|
1682 | |
---|
1683 | The example program below reads the minimum cost problem instance in |
---|
1684 | DIMACS format from file `\verb|sample.min|', solves it by using the |
---|
1685 | routine \verb|glp_mincost_okalg|, and writes the solution found to the |
---|
1686 | standard output. |
---|
1687 | |
---|
1688 | \begin{footnotesize} |
---|
1689 | \begin{verbatim} |
---|
1690 | #include <stddef.h> |
---|
1691 | #include <stdio.h> |
---|
1692 | #include <stdlib.h> |
---|
1693 | #include <glpk.h> |
---|
1694 | |
---|
1695 | typedef struct { double rhs, pi; } v_data; |
---|
1696 | typedef struct { double low, cap, cost, x; } a_data; |
---|
1697 | |
---|
1698 | #define node(v) ((v_data *)((v)->data)) |
---|
1699 | #define arc(a) ((a_data *)((a)->data)) |
---|
1700 | |
---|
1701 | int main(void) |
---|
1702 | { glp_graph *G; |
---|
1703 | glp_vertex *v, *w; |
---|
1704 | glp_arc *a; |
---|
1705 | int i, ret; |
---|
1706 | double sol; |
---|
1707 | G = glp_create_graph(sizeof(v_data), sizeof(a_data)); |
---|
1708 | glp_read_mincost(G, offsetof(v_data, rhs), |
---|
1709 | offsetof(a_data, low), offsetof(a_data, cap), |
---|
1710 | offsetof(a_data, cost), "sample.min"); |
---|
1711 | ret = glp_mincost_okalg(G, offsetof(v_data, rhs), |
---|
1712 | offsetof(a_data, low), offsetof(a_data, cap), |
---|
1713 | offsetof(a_data, cost), &sol, offsetof(a_data, x), |
---|
1714 | offsetof(v_data, pi)); |
---|
1715 | printf("ret = %d; sol = %5g\n", ret, sol); |
---|
1716 | for (i = 1; i <= G->nv; i++) |
---|
1717 | { v = G->v[i]; |
---|
1718 | printf("node %d: pi = %5g\n", i, node(v)->pi); |
---|
1719 | for (a = v->out; a != NULL; a = a->t_next) |
---|
1720 | { w = a->head; |
---|
1721 | printf("arc %d->%d: x = %5g; lambda = %5g\n", |
---|
1722 | v->i, w->i, arc(a)->x, |
---|
1723 | arc(a)->cost - (node(v)->pi - node(w)->pi)); |
---|
1724 | } |
---|
1725 | } |
---|
1726 | glp_delete_graph(G); |
---|
1727 | return 0; |
---|
1728 | } |
---|
1729 | \end{verbatim} |
---|
1730 | \end{footnotesize} |
---|
1731 | |
---|
1732 | If `\verb|sample.min|' is the example data file from the subsection |
---|
1733 | describing the routine \verb|glp_read_mincost|, the output may look like |
---|
1734 | follows: |
---|
1735 | |
---|
1736 | \begin{footnotesize} |
---|
1737 | \begin{verbatim} |
---|
1738 | Reading min-cost flow problem data from `sample.min'... |
---|
1739 | Flow network has 9 nodes and 14 arcs |
---|
1740 | 24 lines were read |
---|
1741 | ret = 0; sol = 213 |
---|
1742 | node 1: pi = -12 |
---|
1743 | arc 1->4: x = 13; lambda = 0 |
---|
1744 | arc 1->2: x = 7; lambda = 0 |
---|
1745 | node 2: pi = -12 |
---|
1746 | arc 2->4: x = 0; lambda = 3 |
---|
1747 | arc 2->3: x = 7; lambda = 0 |
---|
1748 | node 3: pi = -14 |
---|
1749 | arc 3->8: x = 5; lambda = 0 |
---|
1750 | arc 3->5: x = 2; lambda = 3 |
---|
1751 | node 4: pi = -12 |
---|
1752 | arc 4->5: x = 13; lambda = 0 |
---|
1753 | node 5: pi = -12 |
---|
1754 | arc 5->7: x = 4; lambda = -1 |
---|
1755 | arc 5->6: x = 11; lambda = 0 |
---|
1756 | arc 5->2: x = 0; lambda = 1 |
---|
1757 | node 6: pi = -17 |
---|
1758 | arc 6->8: x = 4; lambda = 3 |
---|
1759 | arc 6->7: x = 7; lambda = -3 |
---|
1760 | node 7: pi = -20 |
---|
1761 | arc 7->9: x = 11; lambda = 0 |
---|
1762 | node 8: pi = -14 |
---|
1763 | arc 8->9: x = 9; lambda = 0 |
---|
1764 | node 9: pi = -23 |
---|
1765 | \end{verbatim} |
---|
1766 | \end{footnotesize} |
---|
1767 | |
---|
1768 | \subsection{glp\_netgen---Klingman's network problem generator} |
---|
1769 | |
---|
1770 | \subsubsection*{Synopsis} |
---|
1771 | |
---|
1772 | \begin{verbatim} |
---|
1773 | int glp_netgen(glp_graph *G, int v_rhs, int a_cap, int a_cost, |
---|
1774 | const int parm[1+15]); |
---|
1775 | \end{verbatim} |
---|
1776 | |
---|
1777 | \subsubsection*{Description} |
---|
1778 | |
---|
1779 | The routine \verb|glp_netgen| is a GLPK version of the network problem |
---|
1780 | generator developed by Dr.~Darwin~Klingman.\footnote{D.~Klingman, |
---|
1781 | A.~Napier, and J.~Stutz. NETGEN: A program for generating large scale |
---|
1782 | capacitated assignment, transportation, and minimum cost flow networks. |
---|
1783 | Management Science 20 (1974), 814-20.} It can create capacitated and |
---|
1784 | uncapacitated minimum cost flow (or transshipment), transportation, and |
---|
1785 | assignment problems. |
---|
1786 | |
---|
1787 | The parameter \verb|G| specifies the graph object, to which the |
---|
1788 | generated problem data have to be stored. Note that on entry the graph |
---|
1789 | object is erased with the routine \verb|glp_erase_graph|. |
---|
1790 | |
---|
1791 | The parameter \verb|v_rhs| specifies an offset of the field of type |
---|
1792 | \verb|double| in the vertex data block, to which the routine stores the |
---|
1793 | supply or demand value. If \verb|v_rhs| $<0$, the value is not stored. |
---|
1794 | |
---|
1795 | The parameter \verb|a_cap| specifies an offset of the field of type |
---|
1796 | \verb|double| in the arc data block, to which the routine stores the |
---|
1797 | arc capacity. If \verb|a_cap| $<0$, the capacity is not stored. |
---|
1798 | |
---|
1799 | The parameter \verb|a_cost| specifies an offset of the field of type |
---|
1800 | \verb|double| in the arc data block, to which the routine stores the |
---|
1801 | per-unit cost if the arc flow. If \verb|a_cost| $<0$, the cost is not |
---|
1802 | stored. |
---|
1803 | |
---|
1804 | The array \verb|parm| contains description of the network to be |
---|
1805 | generated: |
---|
1806 | |
---|
1807 | \begin{tabular}{@{}lll@{}} |
---|
1808 | \verb|parm[0] |& ¬ used\\ |
---|
1809 | \verb|parm[1] |&\verb|iseed |&8-digit positive random number seed\\ |
---|
1810 | \verb|parm[2] |&\verb|nprob |&8-digit problem id number\\ |
---|
1811 | \verb|parm[3] |&\verb|nodes |&total number of nodes\\ |
---|
1812 | \verb|parm[4] |&\verb|nsorc |&total number of source nodes\\ |
---|
1813 | &&(including transshipment nodes)\\ |
---|
1814 | \verb|parm[5] |&\verb|nsink |&total number of sink nodes\\ |
---|
1815 | &&(including transshipment nodes)\\ |
---|
1816 | \verb|parm[6] |&\verb|iarcs |&number of arc\\ |
---|
1817 | \verb|parm[7] |&\verb|mincst|&minimum cost for arcs\\ |
---|
1818 | \verb|parm[8] |&\verb|maxcst|&maximum cost for arcs\\ |
---|
1819 | \verb|parm[9] |&\verb|itsup |&total supply\\ |
---|
1820 | \end{tabular} |
---|
1821 | |
---|
1822 | \begin{tabular}{@{}lll@{}} |
---|
1823 | \verb|parm[10]|&\verb|ntsorc|&number of transshipment source nodes\\ |
---|
1824 | \verb|parm[11]|&\verb|ntsink|&number of transshipment sink nodes\\ |
---|
1825 | \verb|parm[12]|&\verb|iphic |&percentage of skeleton arcs to be given |
---|
1826 | the maxi-\\&&mum cost\\ |
---|
1827 | \verb|parm[13]|&\verb|ipcap |&percentage of arcs to be capacitated\\ |
---|
1828 | \verb|parm[14]|&\verb|mincap|&minimum upper bound for capacitated arcs\\ |
---|
1829 | \verb|parm[15]|&\verb|maxcap|&maximum upper bound for capacitated arcs\\ |
---|
1830 | \end{tabular} |
---|
1831 | |
---|
1832 | \subsubsection*{Notes} |
---|
1833 | |
---|
1834 | \noindent\indent |
---|
1835 | 1. The routine generates a transportation problem if: |
---|
1836 | $${\tt nsorc}+{\tt nsink}={\tt nodes}, |
---|
1837 | \ {\tt ntsorc}=0,\ \mbox{and}\ {\tt ntsink}=0.$$ |
---|
1838 | |
---|
1839 | 2. The routine generates an assignment problem if the requirements for |
---|
1840 | a transportation problem are met and: |
---|
1841 | $${\tt nsorc}={\tt nsink}\ \mbox{and}\ {\tt itsup}={\tt nsorc}.$$ |
---|
1842 | |
---|
1843 | 3. The routine always generates connected graphs. So, if the number of |
---|
1844 | requested arcs has been reached and the generated instance is not fully |
---|
1845 | connected, the routine generates a few remaining arcs to ensure |
---|
1846 | connectedness. Thus, the actual number of arcs generated by the routine |
---|
1847 | may be greater than the requested number of arcs. |
---|
1848 | |
---|
1849 | \subsubsection*{Returns} |
---|
1850 | |
---|
1851 | If the instance was successfully generated, the routine |
---|
1852 | \verb|glp_netgen| returns zero; otherwise, if specified parameters are |
---|
1853 | inconsistent, the routine returns a non-zero error code. |
---|
1854 | |
---|
1855 | \subsection{glp\_gridgen---grid-like network problem generator} |
---|
1856 | |
---|
1857 | \subsubsection*{Synopsis} |
---|
1858 | |
---|
1859 | \begin{verbatim} |
---|
1860 | int glp_gridgen(glp_graph *G, int v_rhs, int a_cap, int a_cost, |
---|
1861 | const int parm[1+14]); |
---|
1862 | \end{verbatim} |
---|
1863 | |
---|
1864 | \subsubsection*{Description} |
---|
1865 | |
---|
1866 | The routine \verb|glp_gridgen| is a GLPK version of the grid-like |
---|
1867 | network problem generator developed by Yusin Lee and Jim |
---|
1868 | Orlin.\footnote{Y.~Lee and J.~Orlin. GRIDGEN generator., 1991. The |
---|
1869 | original code is publically available from |
---|
1870 | {\tt<ftp://dimacs.rutgers.edu/pub/netflow/generators/network/gridgen>}.} |
---|
1871 | |
---|
1872 | The parameter \verb|G| specifies the graph object, to which the |
---|
1873 | generated problem data have to be stored. Note that on entry the graph |
---|
1874 | object is erased with the routine \verb|glp_erase_graph|. |
---|
1875 | |
---|
1876 | The parameter \verb|v_rhs| specifies an offset of the field of type |
---|
1877 | \verb|double| in the vertex data block, to which the routine stores the |
---|
1878 | supply or demand value. If \verb|v_rhs| $<0$, the value is not stored. |
---|
1879 | |
---|
1880 | The parameter \verb|a_cap| specifies an offset of the field of type |
---|
1881 | \verb|double| in the arc data block, to which the routine stores the |
---|
1882 | arc capacity. If \verb|a_cap| $<0$, the capacity is not stored. |
---|
1883 | |
---|
1884 | The parameter \verb|a_cost| specifies an offset of the field of type |
---|
1885 | \verb|double| in the arc data block, to which the routine stores the |
---|
1886 | per-unit cost if the arc flow. If \verb|a_cost| $<0$, the cost is not |
---|
1887 | stored. |
---|
1888 | |
---|
1889 | The array \verb|parm| contains parameters of the network to be |
---|
1890 | generated: |
---|
1891 | |
---|
1892 | \begin{tabular}{@{}ll@{}} |
---|
1893 | \verb|parm[0] |¬ used\\ |
---|
1894 | \verb|parm[1] |&two-ways arcs indicator:\\ |
---|
1895 | &1 --- if links in both direction should be generated\\ |
---|
1896 | &0 --- otherwise\\ |
---|
1897 | \verb|parm[2] |&random number seed (a positive integer)\\ |
---|
1898 | \verb|parm[3] |&number of nodes (the number of nodes generated might |
---|
1899 | be\\&slightly different to make the network a grid)\\ |
---|
1900 | \verb|parm[4] |&grid width\\ |
---|
1901 | \verb|parm[5] |&number of sources\\ |
---|
1902 | \verb|parm[6] |&number of sinks\\ |
---|
1903 | \verb|parm[7] |&average degree\\ |
---|
1904 | \verb|parm[8] |&total flow\\ |
---|
1905 | \verb|parm[9] |&distribution of arc costs:\\ |
---|
1906 | &1 --- uniform\\ |
---|
1907 | &2 --- exponential\\ |
---|
1908 | \verb|parm[10]|&lower bound for arc cost (uniform)\\ |
---|
1909 | &$100\lambda$ (exponential)\\ |
---|
1910 | \verb|parm[11]|&upper bound for arc cost (uniform)\\ |
---|
1911 | ¬ used (exponential)\\ |
---|
1912 | \verb|parm[12]|&distribution of arc capacities:\\ |
---|
1913 | &1 --- uniform\\ |
---|
1914 | &2 --- exponential\\ |
---|
1915 | \verb|parm[13]|&lower bound for arc capacity (uniform)\\ |
---|
1916 | &$100\lambda$ (exponential)\\ |
---|
1917 | \verb|parm[14]|&upper bound for arc capacity (uniform)\\ |
---|
1918 | ¬ used (exponential)\\ |
---|
1919 | \end{tabular} |
---|
1920 | |
---|
1921 | \subsubsection*{Returns} |
---|
1922 | |
---|
1923 | If the instance was successfully generated, the routine |
---|
1924 | \verb|glp_gridgen| returns zero; otherwise, if specified parameters are |
---|
1925 | inconsistent, the routine returns a non-zero error code. |
---|
1926 | |
---|
1927 | \subsubsection*{Comments\footnote{This material is based on comments |
---|
1928 | to the original version of GRIDGEN.}} |
---|
1929 | |
---|
1930 | This network generator generates a grid-like network plus a super node. |
---|
1931 | In additional to the arcs connecting the nodes in the grid, there is an |
---|
1932 | arc from each supply node to the super node and from the super node to |
---|
1933 | each demand node to guarantee feasiblity. These arcs have very high |
---|
1934 | costs and very big capacities. |
---|
1935 | |
---|
1936 | The idea of this network generator is as follows: First, a grid of |
---|
1937 | $n_1\times n_2$ is generated. For example, $5\times 3$. The nodes are |
---|
1938 | numbered as 1 to 15, and the supernode is numbered as $n_1\times n_2+1$. |
---|
1939 | Then arcs between adjacent nodes are generated. For these arcs, the user |
---|
1940 | is allowed to specify either to generate two-way arcs or one-way arcs. |
---|
1941 | If two-way arcs are to be generated, two arcs, one in each direction, |
---|
1942 | will be generated between each adjacent node pairs. Otherwise, only one |
---|
1943 | arc will be generated. If this is the case, the arcs will be generated |
---|
1944 | in alterntive directions as shown below. |
---|
1945 | |
---|
1946 | \bigskip |
---|
1947 | |
---|
1948 | \noindent\hfil |
---|
1949 | \xymatrix |
---|
1950 | {1\ar[r]\ar[d]&2\ar[r]&3\ar[r]\ar[d]&4\ar[r]&5\ar[d]\\ |
---|
1951 | 6\ar[d]&7\ar[l]\ar[u]&8\ar[l]\ar[d]&9\ar[l]\ar[u]&10\ar[l]\ar[d]\\ |
---|
1952 | 11\ar[r]&12\ar[r]\ar[u]&13\ar[r]&14\ar[r]\ar[u]&15\\ |
---|
1953 | } |
---|
1954 | |
---|
1955 | \bigskip |
---|
1956 | |
---|
1957 | Then the arcs between the super node and the source/sink nodes are added |
---|
1958 | as mentioned before. If the number of arcs still doesn't reach the |
---|
1959 | requirement, additional arcs will be added by uniformly picking random |
---|
1960 | node pairs. There is no checking to prevent multiple arcs between any |
---|
1961 | pair of nodes. However, there will be no self-arcs (arcs that poins back |
---|
1962 | to its tail node) in the network. |
---|
1963 | |
---|
1964 | The source and sink nodes are selected uniformly in the network, and |
---|
1965 | the imbalances of each source/sink node are also assigned by uniform |
---|
1966 | distribution. |
---|
1967 | |
---|
1968 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
1969 | |
---|
1970 | \newpage |
---|
1971 | |
---|
1972 | \section{Maximum flow problem} |
---|
1973 | |
---|
1974 | \subsection{Background} |
---|
1975 | |
---|
1976 | The {\it maximum flow problem} (MAXFLOW) is stated as follows. Let |
---|
1977 | there be given a directed graph (flow network) $G=(V,A)$, where $V$ is |
---|
1978 | a set of vertices (nodes), and $A\subseteq V\times V$ is a set of arcs. |
---|
1979 | Let also for each arc $a=(i,j)\in A$ there be given its capacity |
---|
1980 | $u_{ij}$. The problem is, for given {\it source} node $s\in V$ and |
---|
1981 | {\it sink} node $t\in V$, to find flows $x_{ij}$ through every arc of |
---|
1982 | the network, which satisfy the specified arc capacities and the |
---|
1983 | conservation constraints at all nodes, and maximize the total flow $F$ |
---|
1984 | through the network from $s$ to $t$. Here the conservation constraint |
---|
1985 | at a node means that the total flow entering this node through its |
---|
1986 | incoming arcs (plus $F$, if it is the source node) must be equal to the |
---|
1987 | total flow leaving this node through its outgoing arcs (plus $F$, if it |
---|
1988 | is the sink node). |
---|
1989 | |
---|
1990 | An example of the maximum flow problem, where $s=v_1$ and $t=v_9$, is |
---|
1991 | shown on Fig.~2. |
---|
1992 | |
---|
1993 | \bigskip |
---|
1994 | |
---|
1995 | \noindent\hfil |
---|
1996 | \xymatrix @C=48pt |
---|
1997 | {_{F}\ar@{~>}[d]& |
---|
1998 | v_2\ar[r]|{_{10}}\ar[dd]|{_{9}}& |
---|
1999 | v_3\ar[dd]|{_{12}}\ar[r]|{_{18}}& |
---|
2000 | v_8\ar[rd]|{_{20}}&\\ |
---|
2001 | v_1\ar[ru]|{_{14}}\ar[rd]|{_{23}}&&& |
---|
2002 | v_6\ar[d]|{_{7}}\ar[u]|{_{8}}& |
---|
2003 | v_9\ar@{~>}[d]\\ |
---|
2004 | &v_4\ar[r]|{_{26}}& |
---|
2005 | v_5\ar[luu]|{_{11}}\ar[ru]|{_{25}}\ar[r]|{_{4}}& |
---|
2006 | v_7\ar[ru]|{_{15}}&_{F}\\ |
---|
2007 | } |
---|
2008 | |
---|
2009 | \bigskip |
---|
2010 | |
---|
2011 | \noindent\hfil |
---|
2012 | Fig.~2. An example of the maximum flow problem. |
---|
2013 | |
---|
2014 | \bigskip |
---|
2015 | |
---|
2016 | The maximum flow problem can be naturally formulated as the following |
---|
2017 | LP problem: |
---|
2018 | |
---|
2019 | \medskip |
---|
2020 | |
---|
2021 | \noindent |
---|
2022 | \hspace{.5in}maximize |
---|
2023 | $$F\eqno(4)$$ |
---|
2024 | \hspace{.5in}subject to |
---|
2025 | $$\sum_{(i,j)\in A}x_{ij}-\sum_{(j,i)\in A}x_{ji}=\left\{ |
---|
2026 | \begin{array}{@{\ }rl} |
---|
2027 | +F,&\hbox{for}\ i=s\\ |
---|
2028 | 0,&\hbox{for all}\ i\in V\backslash\{s,t\}\\ |
---|
2029 | -F,&\hbox{for}\ i=t\\ |
---|
2030 | \end{array} |
---|
2031 | \right.\eqno(5) |
---|
2032 | $$ |
---|
2033 | $$0\leq x_{ij}\leq u_{ij}\ \ \ \hbox{for all}\ (i,j)\in A |
---|
2034 | \eqno(6)$$ |
---|
2035 | |
---|
2036 | \medskip |
---|
2037 | |
---|
2038 | \noindent |
---|
2039 | where $F\geq 0$ is an additional variable playing the role of the |
---|
2040 | objective. |
---|
2041 | |
---|
2042 | \newpage |
---|
2043 | |
---|
2044 | Another LP formulation of the maximum flow problem, which does not |
---|
2045 | include the variable $F$, is the following: |
---|
2046 | |
---|
2047 | \medskip |
---|
2048 | |
---|
2049 | \noindent |
---|
2050 | \hspace{.5in}maximize |
---|
2051 | $$z=\sum_{(s,j)\in A}x_{sj}-\sum_{(j,s)\in A}x_{js}\ (=F)\eqno(7)$$ |
---|
2052 | \hspace{.5in}subject to |
---|
2053 | $$\sum_{(i,j)\in A}x_{ij}-\sum_{(j,i)\in A}x_{ji}\left\{ |
---|
2054 | \begin{array}{@{\ }rl} |
---|
2055 | \geq 0,&\hbox{for}\ i=s\\ |
---|
2056 | =0,&\hbox{for all}\ i\in V\backslash\{s,t\}\\ |
---|
2057 | \leq 0,&\hbox{for}\ i=t\\ |
---|
2058 | \end{array} |
---|
2059 | \right.\eqno(8) |
---|
2060 | $$ |
---|
2061 | $$0\leq x_{ij}\leq u_{ij}\ \ \ \hbox{for all}\ (i,j)\in A |
---|
2062 | \eqno(9)$$ |
---|
2063 | |
---|
2064 | \subsection{glp\_read\_maxflow---read maximum flow problem data\\in |
---|
2065 | DIMACS format} |
---|
2066 | |
---|
2067 | \subsubsection*{Synopsis} |
---|
2068 | |
---|
2069 | \begin{verbatim} |
---|
2070 | int glp_read_maxflow(glp_graph *G, int *s, int *t, int a_cap, |
---|
2071 | const char *fname); |
---|
2072 | \end{verbatim} |
---|
2073 | |
---|
2074 | \subsubsection*{Description} |
---|
2075 | |
---|
2076 | The routine \verb|glp_read_maxflow| reads the maximum flow problem |
---|
2077 | data from a text file in DIMACS format. |
---|
2078 | |
---|
2079 | The parameter \verb|G| specifies the graph object, to which the problem |
---|
2080 | data have to be stored. Note that before reading data the current |
---|
2081 | content of the graph object is completely erased with the routine |
---|
2082 | \verb|glp_erase_graph|. |
---|
2083 | |
---|
2084 | The pointer \verb|s| specifies a location, to which the routine stores |
---|
2085 | the ordinal number of the source node. If \verb|s| is \verb|NULL|, the |
---|
2086 | source node number is not stored. |
---|
2087 | |
---|
2088 | The pointer \verb|t| specifies a location, to which the routine stores |
---|
2089 | the ordinal number of the sink node. If \verb|t| is \verb|NULL|, the |
---|
2090 | sink node number is not stored. |
---|
2091 | |
---|
2092 | The parameter \verb|a_cap| specifies an offset of the field of type |
---|
2093 | \verb|double| in the arc data block, to which the routine stores |
---|
2094 | $u_{ij}$, the arc capacity. If \verb|a_cap| $<0$, the arc capacity is |
---|
2095 | not stored. |
---|
2096 | |
---|
2097 | The character string \verb|fname| specifies the name of a text file to |
---|
2098 | be read in. (If the file name name ends with the suffix `\verb|.gz|', |
---|
2099 | the file is assumed to be compressed, in which case the routine |
---|
2100 | decompresses it ``on the fly''.) |
---|
2101 | |
---|
2102 | \subsubsection*{Returns} |
---|
2103 | |
---|
2104 | If the operation was successful, the routine returns zero. Otherwise, |
---|
2105 | it prints an error message and returns non-zero. |
---|
2106 | |
---|
2107 | \subsubsection*{Example} |
---|
2108 | |
---|
2109 | \begin{footnotesize} |
---|
2110 | \begin{verbatim} |
---|
2111 | typedef struct |
---|
2112 | { /* arc data block */ |
---|
2113 | ... |
---|
2114 | double cap; |
---|
2115 | ... |
---|
2116 | } a_data; |
---|
2117 | |
---|
2118 | int main(void) |
---|
2119 | { glp_graph *G; |
---|
2120 | int s, t, ret; |
---|
2121 | G = glp_create_graph(..., sizeof(a_data)); |
---|
2122 | ret = glp_read_maxflow(G, &s, &t, offsetof(a_data, cap), |
---|
2123 | "sample.max"); |
---|
2124 | if (ret != 0) goto ... |
---|
2125 | ... |
---|
2126 | } |
---|
2127 | \end{verbatim} |
---|
2128 | \end{footnotesize} |
---|
2129 | |
---|
2130 | \subsubsection*{DIMACS maximum flow problem format\footnote{This |
---|
2131 | material is based on the paper ``The First DIMACS International |
---|
2132 | Algorithm Implementation Challenge: Problem Definitions and |
---|
2133 | Specifications'', which is publically available at |
---|
2134 | {\tt http://dimacs.rutgers.edu/Challenges/}.}} |
---|
2135 | \label{subsecmaxflow} |
---|
2136 | |
---|
2137 | The DIMACS input file is a plain ASCII text file. It contains |
---|
2138 | {\it lines} of several types described below. A line is terminated with |
---|
2139 | an end-of-line character. Fields in each line are separated by at least |
---|
2140 | one blank space. Each line begins with a one-character designator to |
---|
2141 | identify the line type. |
---|
2142 | |
---|
2143 | Note that DIMACS requires all numerical quantities to be integers in |
---|
2144 | the range $[-2^{31},\ 2^{31}-1]$ while GLPK allows the quantities to be |
---|
2145 | floating-point numbers. |
---|
2146 | |
---|
2147 | \paragraph{Comment lines.} Comment lines give human-readable information |
---|
2148 | about the file and are ignored by programs. Comment lines can appear |
---|
2149 | anywhere in the file. Each comment line begins with a lower-case |
---|
2150 | character \verb|c|. |
---|
2151 | |
---|
2152 | \begin{verbatim} |
---|
2153 | c This is a comment line |
---|
2154 | \end{verbatim} |
---|
2155 | |
---|
2156 | \newpage |
---|
2157 | |
---|
2158 | \paragraph{Problem line.} There is one problem line per data file. The |
---|
2159 | problem line must appear before any node or arc descriptor lines. It has |
---|
2160 | the following format: |
---|
2161 | |
---|
2162 | \begin{verbatim} |
---|
2163 | p max NODES ARCS |
---|
2164 | \end{verbatim} |
---|
2165 | |
---|
2166 | \noindent |
---|
2167 | The lower-case character \verb|p| signifies that this is a problem line. |
---|
2168 | The three-character problem designator \verb|max| identifies the file as |
---|
2169 | containing specification information for the maximum flow problem. The |
---|
2170 | \verb|NODES| field contains an integer value specifying the number of |
---|
2171 | nodes in the network. The \verb|ARCS| field contains an integer value |
---|
2172 | specifying the number of arcs in the network. |
---|
2173 | |
---|
2174 | \paragraph{Node descriptors.} Two node descriptor lines for the source |
---|
2175 | and sink nodes must appear before all arc descriptor lines. They may |
---|
2176 | appear in either order, each with the following format: |
---|
2177 | |
---|
2178 | \begin{verbatim} |
---|
2179 | n ID WHICH |
---|
2180 | \end{verbatim} |
---|
2181 | |
---|
2182 | \noindent |
---|
2183 | The lower-case character \verb|n| signifies that this a node descriptor |
---|
2184 | line. The \verb|ID| field gives a node identification number, an integer |
---|
2185 | between 1 and \verb|NODES|. The \verb|WHICH| field gives either a |
---|
2186 | lower-case \verb|s| or \verb|t|, designating the source and sink, |
---|
2187 | respectively. |
---|
2188 | |
---|
2189 | \paragraph{Arc descriptors.} There is one arc descriptor line for each |
---|
2190 | arc in the network. Arc descriptor lines are of the following format: |
---|
2191 | |
---|
2192 | \begin{verbatim} |
---|
2193 | a SRC DST CAP |
---|
2194 | \end{verbatim} |
---|
2195 | |
---|
2196 | \noindent |
---|
2197 | The lower-case character \verb|a| signifies that this is an arc |
---|
2198 | descriptor line. For a directed arc $(i,j)$ the \verb|SRC| field gives |
---|
2199 | the identification number $i$ for the tail endpoint, and the \verb|DST| |
---|
2200 | field gives the identification number $j$ for the head endpoint. |
---|
2201 | Identification numbers are integers between 1 and \verb|NODES|. The |
---|
2202 | \verb|CAP| field gives the arc capacity, i.e. maximum amount of flow |
---|
2203 | that can be sent along arc $(i,j)$ in a feasible flow. |
---|
2204 | |
---|
2205 | \paragraph{Example.} Below here is an example of the data file in |
---|
2206 | DIMACS format corresponding to the maximum flow problem shown on Fig~2. |
---|
2207 | |
---|
2208 | \newpage |
---|
2209 | |
---|
2210 | \begin{footnotesize} |
---|
2211 | \begin{verbatim} |
---|
2212 | c sample.max |
---|
2213 | c |
---|
2214 | c This is an example of the maximum flow problem data |
---|
2215 | c in DIMACS format. |
---|
2216 | c |
---|
2217 | p max 9 14 |
---|
2218 | c |
---|
2219 | n 1 s |
---|
2220 | n 9 t |
---|
2221 | c |
---|
2222 | a 1 2 14 |
---|
2223 | a 1 4 23 |
---|
2224 | a 2 3 10 |
---|
2225 | a 2 4 9 |
---|
2226 | a 3 5 12 |
---|
2227 | a 3 8 18 |
---|
2228 | a 4 5 26 |
---|
2229 | a 5 2 11 |
---|
2230 | a 5 6 25 |
---|
2231 | a 5 7 4 |
---|
2232 | a 6 7 7 |
---|
2233 | a 6 8 8 |
---|
2234 | a 7 9 15 |
---|
2235 | a 8 9 20 |
---|
2236 | c |
---|
2237 | c eof |
---|
2238 | \end{verbatim} |
---|
2239 | \end{footnotesize} |
---|
2240 | |
---|
2241 | \subsection{glp\_write\_maxflow---write maximum flow problem data\\ |
---|
2242 | in DIMACS format} |
---|
2243 | |
---|
2244 | \subsubsection*{Synopsis} |
---|
2245 | |
---|
2246 | \begin{verbatim} |
---|
2247 | int glp_write_maxflow(glp_graph *G, int s, int t, int a_cap, |
---|
2248 | const char *fname); |
---|
2249 | \end{verbatim} |
---|
2250 | |
---|
2251 | \subsubsection*{Description} |
---|
2252 | |
---|
2253 | The routine \verb|glp_write_maxflow| writes the maximum flow problem |
---|
2254 | data to a text file in DIMACS format. |
---|
2255 | |
---|
2256 | The parameter \verb|G| is the graph (network) program object, which |
---|
2257 | specifies the maximum flow problem instance. |
---|
2258 | |
---|
2259 | The parameter \verb|s| specifies the ordinal number of the source node. |
---|
2260 | |
---|
2261 | The parameter \verb|t| specifies the ordinal number of the sink node. |
---|
2262 | |
---|
2263 | The parameter \verb|a_cap| specifies an offset of the field of type |
---|
2264 | \verb|double| in the arc data block, which contains $u_{ij}$, the upper |
---|
2265 | bound to the arc flow (the arc capacity). If the upper bound is |
---|
2266 | specified as \verb|DBL_MAX|, it is assumed that $u_{ij}=\infty$, i.e. |
---|
2267 | the arc is uncapacitated. If \verb|a_cap| $<0$, it is assumed that |
---|
2268 | $u_{ij}=1$ for all arcs. |
---|
2269 | |
---|
2270 | The character string \verb|fname| specifies a name of the text file to |
---|
2271 | be written out. (If the file name ends with suffix `\verb|.gz|', the |
---|
2272 | file is assumed to be compressed, in which case the routine performs |
---|
2273 | automatic compression on writing it.) |
---|
2274 | |
---|
2275 | \subsubsection*{Returns} |
---|
2276 | |
---|
2277 | If the operation was successful, the routine returns zero. Otherwise, |
---|
2278 | it prints an error message and returns non-zero. |
---|
2279 | |
---|
2280 | \subsection{glp\_maxflow\_lp---convert maximum flow problem to LP} |
---|
2281 | |
---|
2282 | \subsubsection*{Synopsis} |
---|
2283 | |
---|
2284 | \begin{verbatim} |
---|
2285 | void glp_maxflow_lp(glp_prob *lp, glp_graph *G, int names, |
---|
2286 | int s, int t, int a_cap); |
---|
2287 | \end{verbatim} |
---|
2288 | |
---|
2289 | \subsubsection*{Description} |
---|
2290 | |
---|
2291 | The routine \verb|glp_maxflow_lp| builds LP problem (7)---(9), which |
---|
2292 | corresponds to the specified maximum flow problem. |
---|
2293 | |
---|
2294 | The parameter \verb|lp| is the resultant LP problem object to be built. |
---|
2295 | Note that on entry its current content is erased with the routine |
---|
2296 | \verb|glp_erase_prob|. |
---|
2297 | |
---|
2298 | The parameter \verb|G| is the graph (network) program object, which |
---|
2299 | specifies the maximum flow problem instance. |
---|
2300 | |
---|
2301 | The parameter \verb|names| is a flag. If it is \verb|GLP_ON|, the |
---|
2302 | routine uses symbolic names of the graph object components to assign |
---|
2303 | symbolic names to the LP problem object components. If the flag is |
---|
2304 | \verb|GLP_OFF|, no symbolic names are assigned. |
---|
2305 | |
---|
2306 | The parameter \verb|s| specifies the ordinal number of the source node. |
---|
2307 | |
---|
2308 | The parameter \verb|t| specifies the ordinal number of the sink node. |
---|
2309 | |
---|
2310 | The parameter \verb|a_cap| specifies an offset of the field of type |
---|
2311 | \verb|double| in the arc data block, which contains $u_{ij}$, the upper |
---|
2312 | bound to the arc flow (the arc capacity). If the upper bound is |
---|
2313 | specified as \verb|DBL_MAX|, it is assumed that $u_{ij}=\infty$, i.e. |
---|
2314 | the arc is uncapacitated. If \verb|a_cap| $<0$, it is assumed that |
---|
2315 | $u_{ij}=1$ for all arcs. |
---|
2316 | |
---|
2317 | \subsubsection*{Example} |
---|
2318 | |
---|
2319 | The example program below reads the maximum flow problem in DIMACS |
---|
2320 | format from file `\verb|sample.max|', converts the instance to LP, and |
---|
2321 | then writes the resultant LP in CPLEX format to file |
---|
2322 | `\verb|maxflow.lp|'. |
---|
2323 | |
---|
2324 | \begin{footnotesize} |
---|
2325 | \begin{verbatim} |
---|
2326 | #include <stddef.h> |
---|
2327 | #include <glpk.h> |
---|
2328 | |
---|
2329 | int main(void) |
---|
2330 | { glp_graph *G; |
---|
2331 | glp_prob *lp; |
---|
2332 | int s, t; |
---|
2333 | G = glp_create_graph(0, sizeof(double)); |
---|
2334 | glp_read_maxflow(G, &s, &t, 0, "sample.max"); |
---|
2335 | lp = glp_create_prob(); |
---|
2336 | glp_maxflow_lp(lp, G, GLP_ON, s, t, 0); |
---|
2337 | glp_delete_graph(G); |
---|
2338 | glp_write_lp(lp, NULL, "maxflow.lp"); |
---|
2339 | glp_delete_prob(lp); |
---|
2340 | return 0; |
---|
2341 | } |
---|
2342 | \end{verbatim} |
---|
2343 | \end{footnotesize} |
---|
2344 | |
---|
2345 | If `\verb|sample.max|' is the example data file from the previous |
---|
2346 | subsection, the output `\verb|maxflow.lp|' may look like follows: |
---|
2347 | |
---|
2348 | \begin{footnotesize} |
---|
2349 | \begin{verbatim} |
---|
2350 | Maximize |
---|
2351 | obj: + x(1,4) + x(1,2) |
---|
2352 | |
---|
2353 | Subject To |
---|
2354 | r_1: + x(1,2) + x(1,4) >= 0 |
---|
2355 | r_2: - x(5,2) + x(2,3) + x(2,4) - x(1,2) = 0 |
---|
2356 | r_3: + x(3,5) + x(3,8) - x(2,3) = 0 |
---|
2357 | r_4: + x(4,5) - x(2,4) - x(1,4) = 0 |
---|
2358 | r_5: + x(5,2) + x(5,6) + x(5,7) - x(4,5) - x(3,5) = 0 |
---|
2359 | r_6: + x(6,7) + x(6,8) - x(5,6) = 0 |
---|
2360 | r_7: + x(7,9) - x(6,7) - x(5,7) = 0 |
---|
2361 | r_8: + x(8,9) - x(6,8) - x(3,8) = 0 |
---|
2362 | r_9: - x(8,9) - x(7,9) <= 0 |
---|
2363 | |
---|
2364 | Bounds |
---|
2365 | 0 <= x(1,4) <= 23 |
---|
2366 | 0 <= x(1,2) <= 14 |
---|
2367 | 0 <= x(2,4) <= 9 |
---|
2368 | 0 <= x(2,3) <= 10 |
---|
2369 | 0 <= x(3,8) <= 18 |
---|
2370 | 0 <= x(3,5) <= 12 |
---|
2371 | 0 <= x(4,5) <= 26 |
---|
2372 | 0 <= x(5,7) <= 4 |
---|
2373 | 0 <= x(5,6) <= 25 |
---|
2374 | 0 <= x(5,2) <= 11 |
---|
2375 | 0 <= x(6,8) <= 8 |
---|
2376 | 0 <= x(6,7) <= 7 |
---|
2377 | 0 <= x(7,9) <= 15 |
---|
2378 | 0 <= x(8,9) <= 20 |
---|
2379 | |
---|
2380 | End |
---|
2381 | \end{verbatim} |
---|
2382 | \end{footnotesize} |
---|
2383 | |
---|
2384 | \subsection{glp\_maxflow\_ffalg---solve maximum flow problem with |
---|
2385 | Ford-Fulkerson algorithm} |
---|
2386 | |
---|
2387 | \subsubsection*{Synopsis} |
---|
2388 | |
---|
2389 | \begin{verbatim} |
---|
2390 | int glp_maxflow_ffalg(glp_graph *G, int s, int t, int a_cap, |
---|
2391 | double *sol, int a_x, int v_cut); |
---|
2392 | \end{verbatim} |
---|
2393 | |
---|
2394 | \subsubsection*{Description} |
---|
2395 | |
---|
2396 | The routine \verb|glp_mincost_ffalg| finds optimal solution to the |
---|
2397 | maximum flow problem with the Ford-Fulkerson algorithm.\footnote{GLPK |
---|
2398 | implementation of the Ford-Fulkerson algorithm is based on the following |
---|
2399 | book: L.~R.~Ford,~Jr., and D.~R.~Fulkerson, ``Flows in Networks,'' The |
---|
2400 | RAND Corp., Report\linebreak R-375-PR (August 1962), Chap. I |
---|
2401 | ``Static Maximal Flow,'' pp.~30-33.} Note that this routine requires all |
---|
2402 | the problem data to be integer-valued. |
---|
2403 | |
---|
2404 | The parameter \verb|G| is a graph (network) program object which |
---|
2405 | specifies the maximum flow problem instance to be solved. |
---|
2406 | |
---|
2407 | The parameter $s$ specifies the ordinal number of the source node. |
---|
2408 | |
---|
2409 | The parameter $t$ specifies the ordinal number of the sink node. |
---|
2410 | |
---|
2411 | The parameter \verb|a_cap| specifies an offset of the field of type |
---|
2412 | \verb|double| in the arc data block, which contains $u_{ij}$, the upper |
---|
2413 | bound to the arc flow (the arc capacity). This bound must be integer in |
---|
2414 | the range [0, \verb|INT_MAX|]. If \verb|a_cap| $<0$, it is assumed that |
---|
2415 | $u_{ij}=1$ for all arcs. |
---|
2416 | |
---|
2417 | The parameter \verb|sol| specifies a location, to which the routine |
---|
2418 | stores the objective value (that is, the total flow from $s$ to $t$) |
---|
2419 | found. If \verb|sol| is NULL, the objective value is not stored. |
---|
2420 | |
---|
2421 | The parameter \verb|a_x| specifies an offset of the field of type |
---|
2422 | \verb|double| in the arc data block, to which the routine stores |
---|
2423 | $x_{ij}$, the arc flow found. If \verb|a_x| $<0$, the arc flow values |
---|
2424 | are not stored. |
---|
2425 | |
---|
2426 | The parameter \verb|v_cut| specifies an offset of the field of type |
---|
2427 | \verb|int| in the vertex data block, to which the routine stores node |
---|
2428 | flags corresponding to the optimal solution found: if the node flag is |
---|
2429 | 1, the node is labelled, and if the node flag is 0, the node is |
---|
2430 | unlabelled. The calling program may use these node flags to determine |
---|
2431 | the {\it minimal cut}, which is a subset of arcs whose one endpoint is |
---|
2432 | labelled and other is not. If \verb|v_cut| $<0$, the node flags are not |
---|
2433 | stored. |
---|
2434 | |
---|
2435 | Note that all solution components (the objective value and arc flows) |
---|
2436 | computed by the routine are always integer-valued. |
---|
2437 | |
---|
2438 | \subsubsection*{Returns} |
---|
2439 | |
---|
2440 | \def\arraystretch{1} |
---|
2441 | |
---|
2442 | \begin{tabular}{@{}p{25mm}p{97.3mm}@{}} |
---|
2443 | 0 & Optimal solution found.\\ |
---|
2444 | \verb|GLP_EDATA| & Unable to start the search, because some problem |
---|
2445 | data are either not integer-valued or out of range.\\ |
---|
2446 | \end{tabular} |
---|
2447 | |
---|
2448 | \subsubsection*{Example} |
---|
2449 | |
---|
2450 | The example program shown below reads the maximum flow problem instance |
---|
2451 | in DIMACS format from file `\verb|sample.max|', solves it using the |
---|
2452 | routine \verb|glp_maxflow_ffalg|, and write the solution found to the |
---|
2453 | standard output. |
---|
2454 | |
---|
2455 | \begin{footnotesize} |
---|
2456 | \begin{verbatim} |
---|
2457 | #include <stddef.h> |
---|
2458 | #include <stdio.h> |
---|
2459 | #include <stdlib.h> |
---|
2460 | #include <glpk.h> |
---|
2461 | |
---|
2462 | typedef struct { int cut; } v_data; |
---|
2463 | typedef struct { double cap, x; } a_data; |
---|
2464 | |
---|
2465 | #define node(v) ((v_data *)((v)->data)) |
---|
2466 | #define arc(a) ((a_data *)((a)->data)) |
---|
2467 | |
---|
2468 | int main(void) |
---|
2469 | { glp_graph *G; |
---|
2470 | glp_vertex *v, *w; |
---|
2471 | glp_arc *a; |
---|
2472 | int i, s, t, ret; |
---|
2473 | double sol; |
---|
2474 | G = glp_create_graph(sizeof(v_data), sizeof(a_data)); |
---|
2475 | glp_read_maxflow(G, &s, &t, offsetof(a_data, cap), |
---|
2476 | "sample.max"); |
---|
2477 | ret = glp_maxflow_ffalg(G, s, t, offsetof(a_data, cap), |
---|
2478 | &sol, offsetof(a_data, x), offsetof(v_data, cut)); |
---|
2479 | printf("ret = %d; sol = %5g\n", ret, sol); |
---|
2480 | for (i = 1; i <= G->nv; i++) |
---|
2481 | { v = G->v[i]; |
---|
2482 | for (a = v->out; a != NULL; a = a->t_next) |
---|
2483 | { w = a->head; |
---|
2484 | printf("x[%d->%d] = %5g (%d)\n", v->i, w->i, |
---|
2485 | arc(a)->x, node(v)->cut ^ node(w)->cut); |
---|
2486 | } |
---|
2487 | } |
---|
2488 | glp_delete_graph(G); |
---|
2489 | return 0; |
---|
2490 | } |
---|
2491 | \end{verbatim} |
---|
2492 | \end{footnotesize} |
---|
2493 | |
---|
2494 | If `\verb|sample.max|' is the example data file from the subsection |
---|
2495 | describing the routine \verb|glp_read_maxflow|, the output may look like |
---|
2496 | follows: |
---|
2497 | |
---|
2498 | \begin{footnotesize} |
---|
2499 | \begin{verbatim} |
---|
2500 | Reading maximum flow problem data from `sample.max'... |
---|
2501 | Flow network has 9 nodes and 14 arcs |
---|
2502 | 24 lines were read |
---|
2503 | ret = 0; sol = 29 |
---|
2504 | x[1->4] = 19 (0) |
---|
2505 | x[1->2] = 10 (0) |
---|
2506 | x[2->4] = 0 (0) |
---|
2507 | x[2->3] = 10 (1) |
---|
2508 | x[3->8] = 10 (0) |
---|
2509 | x[3->5] = 0 (1) |
---|
2510 | x[4->5] = 19 (0) |
---|
2511 | x[5->7] = 4 (1) |
---|
2512 | x[5->6] = 15 (0) |
---|
2513 | x[5->2] = 0 (0) |
---|
2514 | x[6->8] = 8 (1) |
---|
2515 | x[6->7] = 7 (1) |
---|
2516 | x[7->9] = 11 (0) |
---|
2517 | x[8->9] = 18 (0) |
---|
2518 | \end{verbatim} |
---|
2519 | \end{footnotesize} |
---|
2520 | |
---|
2521 | \newpage |
---|
2522 | |
---|
2523 | \subsection{glp\_rmfgen---Goldfarb's maximum flow problem generator} |
---|
2524 | |
---|
2525 | \subsubsection*{Synopsis} |
---|
2526 | |
---|
2527 | \begin{verbatim} |
---|
2528 | int glp_rmfgen(glp_graph *G, int *s, int *t, int a_cap, |
---|
2529 | const int parm[1+5]); |
---|
2530 | \end{verbatim} |
---|
2531 | |
---|
2532 | \subsubsection*{Description} |
---|
2533 | |
---|
2534 | The routine \verb|glp_rmfgen| is a GLPK version of the maximum flow |
---|
2535 | problem generator developed by D.~Goldfarb and |
---|
2536 | M.~Grigoriadis.\footnote{D.~Goldfarb and M.~D.~Grigoriadis, |
---|
2537 | ``A computational comparison of the Dinic and network simplex methods |
---|
2538 | for maximum flow.'' Annals of Op. Res. 13 (1988), |
---|
2539 | pp.~83-123.}$^{,}$\footnote{U.~Derigs and W.~Meier, ``Implementing |
---|
2540 | Goldberg's max-flow algorithm: A computational investigation.'' |
---|
2541 | Zeitschrift f\"ur Operations Research 33 (1989), |
---|
2542 | pp.~383-403.}$^{,}$\footnote{The original code of RMFGEN implemented by |
---|
2543 | Tamas Badics is publically available from |
---|
2544 | {\tt <ftp://dimacs.rutgers.edu/pub/netflow/generators/network/genrmf>}.} |
---|
2545 | |
---|
2546 | The parameter \verb|G| specifies the graph object, to which the |
---|
2547 | generated problem data have to be stored. Note that on entry the graph |
---|
2548 | object is erased with the routine \verb|glp_erase_graph|. |
---|
2549 | |
---|
2550 | The pointers \verb|s| and \verb|t| specify locations, to which the |
---|
2551 | routine stores the source and sink node numbers, respectively. If |
---|
2552 | \verb|s| or \verb|t| is \verb|NULL|, corresponding node number is not |
---|
2553 | stored. |
---|
2554 | |
---|
2555 | The parameter \verb|a_cap| specifies an offset of the field of type |
---|
2556 | \verb|double| in the arc data block, to which the routine stores the arc |
---|
2557 | capacity. If \verb|a_cap| $<0$, the capacity is not stored. |
---|
2558 | |
---|
2559 | The array \verb|parm| contains description of the network to be |
---|
2560 | generated: |
---|
2561 | |
---|
2562 | \begin{tabular}{@{}lll@{}} |
---|
2563 | \verb|parm[0]|& ¬ used\\ |
---|
2564 | \verb|parm[1]|&\verb|seed|&random number seed (a positive integer)\\ |
---|
2565 | \verb|parm[2]|&\verb|a |&frame size\\ |
---|
2566 | \verb|parm[3]|&\verb|b |&depth\\ |
---|
2567 | \verb|parm[4]|&\verb|c1 |&minimal arc capacity\\ |
---|
2568 | \verb|parm[5]|&\verb|c2 |&maximal arc capacity\\ |
---|
2569 | \end{tabular} |
---|
2570 | |
---|
2571 | \subsubsection*{Returns} |
---|
2572 | |
---|
2573 | If the instance was successfully generated, the routine |
---|
2574 | \verb|glp_netgen| returns zero; otherwise, if specified parameters are |
---|
2575 | inconsistent, the routine returns a non-zero error code. |
---|
2576 | |
---|
2577 | \newpage |
---|
2578 | |
---|
2579 | \subsubsection*{Comments\footnote{This material is based on comments |
---|
2580 | to the original version of RMFGEN.}} |
---|
2581 | |
---|
2582 | The generated network is as follows. It has $b$ pieces of frames of |
---|
2583 | size $a\times a$. (So alltogether the number of vertices is |
---|
2584 | $a\times a\times b$.) |
---|
2585 | |
---|
2586 | In each frame all the vertices are connected with their neighbours |
---|
2587 | (forth and back). In addition the vertices of a frame are connected |
---|
2588 | one to one with the vertices of next frame using a random permutation |
---|
2589 | of those vertices. |
---|
2590 | |
---|
2591 | The source is the lower left vertex of the first frame, the sink is |
---|
2592 | the upper right vertex of the $b$-th frame. |
---|
2593 | |
---|
2594 | \begin{verbatim} |
---|
2595 | t |
---|
2596 | +-------+ |
---|
2597 | | .| |
---|
2598 | | . | |
---|
2599 | / | / | |
---|
2600 | +-------+/ -+ b |
---|
2601 | | | |/. |
---|
2602 | a | -v- |/ |
---|
2603 | | | |/ |
---|
2604 | +-------+ 1 |
---|
2605 | s a |
---|
2606 | \end{verbatim} |
---|
2607 | |
---|
2608 | The capacities are randomly chosen integers from the range of |
---|
2609 | $[c_1,c_2]$ in the case of interconnecting edges, and $c_2\cdot a^2$ |
---|
2610 | for the in-frame edges. |
---|
2611 | |
---|
2612 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
2613 | |
---|
2614 | \newpage |
---|
2615 | |
---|
2616 | \section{Assignment problem} |
---|
2617 | |
---|
2618 | \subsection{Background} |
---|
2619 | |
---|
2620 | Let there be given an undirected bipartite graph $G=(R\cup S,E)$, where |
---|
2621 | $R$ and $S$ are disjoint sets of vertices (nodes), and |
---|
2622 | $E\subseteq R\times S$ is a set of edges. Let also for each edge |
---|
2623 | $e=(i,j)\in E$ there be given its cost $c_{ij}$. A {\it matching} |
---|
2624 | (which in case of bipartite graph is also called {\it assignment}) |
---|
2625 | $M\subseteq E$ in $G$ is a set of pairwise non-adjacent edges, that is, |
---|
2626 | no two edges in $M$ share a common vertex. A matching, which matches |
---|
2627 | all vertices of the graph, is called a {\it perfect matching}. |
---|
2628 | Obviously, a perfect matching in bipartite graph $G=(R\cup S,E)$ |
---|
2629 | defines some bijection $R\leftrightarrow S$. |
---|
2630 | |
---|
2631 | The {\it assignment problem} has two different variants. In the first |
---|
2632 | variant the problem is to find matching (assignment) $M$, which |
---|
2633 | maximizes the sum: |
---|
2634 | $$\sum_{(i,j)\in M}c_{ij}\eqno(10)$$ |
---|
2635 | (so this variant is also called the {\it maximum weighted bipartite |
---|
2636 | matching problem} or, if all $c_{ij}=1$, the {\it maximum cardinality |
---|
2637 | bipartite matching problem}). In the second, classic variant the |
---|
2638 | problem is to find {\it perfect} matching (assignment) $M$, which |
---|
2639 | minimizes or maximizes the sum (10). |
---|
2640 | |
---|
2641 | An example of the assignment problem, which is the maximum weighted |
---|
2642 | bipartite matching problem, is shown on Fig. 3. |
---|
2643 | |
---|
2644 | The maximum weighted bipartite matching problem can be naturally |
---|
2645 | formulated as the following LP problem: |
---|
2646 | |
---|
2647 | \medskip |
---|
2648 | |
---|
2649 | \noindent |
---|
2650 | \hspace{.5in}maximize |
---|
2651 | $$z=\sum_{(i,j)\in E}c_{ij}x_{ij}\eqno(11)$$ |
---|
2652 | \hspace{.5in}subject to |
---|
2653 | $$\sum_{(i,j)\in E}x_{ij}\leq 1\ \ \ \hbox{for all}\ i\in R\eqno(12)$$ |
---|
2654 | $$\sum_{(i,j)\in E}x_{ij}\leq 1\ \ \ \hbox{for all}\ j\in S\eqno(13)$$ |
---|
2655 | $$\ \ \ \ \ \ \ \ 0\leq x_{ij}\leq 1\ \ \ \hbox{for all}\ (i,j)\in E |
---|
2656 | \eqno(14)$$ |
---|
2657 | |
---|
2658 | \medskip |
---|
2659 | |
---|
2660 | \noindent |
---|
2661 | where $x_{ij}=1$ means that $(i,j)\in M$, and $x_{ij}=0$ means that |
---|
2662 | $(i,j)\notin M$.\footnote{The constraint matrix of LP formulation |
---|
2663 | (11)---(14) is totally unimodular, due to which $x_{ij}\in\{0,1\}$ for |
---|
2664 | any basic solution.} |
---|
2665 | |
---|
2666 | \newpage |
---|
2667 | |
---|
2668 | \bigskip |
---|
2669 | |
---|
2670 | \noindent\hfil |
---|
2671 | \xymatrix @C=48pt |
---|
2672 | {v_1\ar@{-}[rr]|{_{13}}\ar@{-}[rrd]|{_{21}}\ar@{-}[rrddd]|(.2){_{20}}&& |
---|
2673 | v_9\\ |
---|
2674 | v_2\ar@{-}[rr]|{_{12}}\ar@{-}[rrdd]|(.3){_{8}} |
---|
2675 | \ar@{-}[rrddd]|(.4){_{26}}&&v_{10}\\ |
---|
2676 | v_3\ar@{-}[rr]|(.2){_{22}}\ar@{-}[rrdd]|(.3){_{11}}&&v_{11}\\ |
---|
2677 | v_4\ar@{-}[rruuu]|(.6){_{12}}\ar@{-}[rr]|(.2){_{36}} |
---|
2678 | \ar@{-}[rrdd]|(.7){_{25}}&&v_{12}\\ |
---|
2679 | v_5\ar@{-}[rruu]|(.42){_{41}}\ar@{-}[rru]|(.4){_{40}} |
---|
2680 | \ar@{-}[rr]|(.75){_{11}}\ar@{-}[rrd]|(.6){_{4}}\ar@{-}[rrdd]|{_{8}} |
---|
2681 | \ar@{-}[rrddd]|{_{35}}\ar@{-}[rrdddd]|{_{32}}&&v_{13}\\ |
---|
2682 | v_6\ar@{-}[rruuuuu]|(.7){_{13}}&&v_{14}\\ |
---|
2683 | v_7\ar@{-}[rruuuuu]|(.15){_{19}}&&v_{15}\\ |
---|
2684 | v_8\ar@{-}[rruuuuuu]|(.25){_{39}}\ar@{-}[rruuuuu]|(.65){_{15}}&& |
---|
2685 | v_{16}\\ |
---|
2686 | &&v_{17}\\ |
---|
2687 | } |
---|
2688 | |
---|
2689 | \bigskip |
---|
2690 | |
---|
2691 | \noindent\hfil |
---|
2692 | Fig.~3. An example of the assignment problem. |
---|
2693 | |
---|
2694 | \bigskip |
---|
2695 | |
---|
2696 | Similarly, the perfect assignment problem can be naturally formulated |
---|
2697 | as the following LP problem: |
---|
2698 | |
---|
2699 | \medskip |
---|
2700 | |
---|
2701 | \noindent |
---|
2702 | \hspace{.5in}minimize (or maximize) |
---|
2703 | $$z=\sum_{(i,j)\in E}c_{ij}x_{ij}\eqno(15)$$ |
---|
2704 | \hspace{.5in}subject to |
---|
2705 | $$\sum_{(i,j)\in E}x_{ij}=1\ \ \ \hbox{for all}\ i\in R\eqno(16)$$ |
---|
2706 | $$\sum_{(i,j)\in E}x_{ij}=1\ \ \ \hbox{for all}\ j\in S\eqno(17)$$ |
---|
2707 | $$\ \ \ \ \ \ \ \ 0\leq x_{ij}\leq 1\ \ \ \hbox{for all}\ (i,j)\in E |
---|
2708 | \eqno(18)$$ |
---|
2709 | |
---|
2710 | \medskip |
---|
2711 | |
---|
2712 | \noindent |
---|
2713 | where variables $x_{ij}$ have the same meaning as for (11)---(14) |
---|
2714 | above. |
---|
2715 | |
---|
2716 | \newpage |
---|
2717 | |
---|
2718 | In GLPK an undirected bipartite graph $G=(R\cup S,E)$ is represented as |
---|
2719 | directed graph $\overline{G}=(V,A)$, where $V=R\cup S$ and |
---|
2720 | $A=\{(i,j):(i,j)\in E\}$, i.e. every edge $(i,j)\in E$ in $G$ |
---|
2721 | corresponds to arc $(i\rightarrow j)\in A$ in $\overline{G}$. |
---|
2722 | |
---|
2723 | \subsection{glp\_read\_asnprob---read assignment problem data in\\DIMACS |
---|
2724 | format} |
---|
2725 | |
---|
2726 | \subsubsection*{Synopsis} |
---|
2727 | |
---|
2728 | \begin{verbatim} |
---|
2729 | int glp_read_asnprob(glp_graph *G, int v_set, int a_cost, |
---|
2730 | const char *fname); |
---|
2731 | \end{verbatim} |
---|
2732 | |
---|
2733 | \subsubsection*{Description} |
---|
2734 | |
---|
2735 | The routine \verb|glp_read_asnprob| reads the assignment problem data |
---|
2736 | from a text file in DIMACS format. |
---|
2737 | |
---|
2738 | The parameter \verb|G| specifies the graph object, to which the problem |
---|
2739 | data have to be stored. Note that before reading data the current |
---|
2740 | content of the graph object is completely erased with the routine |
---|
2741 | \verb|glp_erase_graph|. |
---|
2742 | |
---|
2743 | The parameter \verb|v_set| specifies an offset of the field of type |
---|
2744 | \verb|int| in the vertex data block, to which the routine stores the |
---|
2745 | node set indicator: |
---|
2746 | |
---|
2747 | 0 --- the node is in set $R$; |
---|
2748 | |
---|
2749 | 1 --- the node is in set $S$. |
---|
2750 | |
---|
2751 | \noindent |
---|
2752 | If \verb|v_set| $<0$, the node set indicator is not stored. |
---|
2753 | |
---|
2754 | The parameter \verb|a_cost| specifies an offset of the field of type |
---|
2755 | \verb|double| in the arc data block, to which the routine stores the |
---|
2756 | edge cost $c_{ij}$. If \verb|a_cost| $<0$, the edge cost is not stored. |
---|
2757 | |
---|
2758 | The character string \verb|fname| specifies the name of a text file to |
---|
2759 | be read in. (If the file name name ends with the suffix `\verb|.gz|', |
---|
2760 | the file is assumed to be compressed, in which case the routine |
---|
2761 | decompresses it ``on the fly''.) |
---|
2762 | |
---|
2763 | \subsubsection*{Returns} |
---|
2764 | |
---|
2765 | If the operation was successful, the routine returns zero. Otherwise, |
---|
2766 | it prints an error message and returns non-zero. |
---|
2767 | |
---|
2768 | \newpage |
---|
2769 | |
---|
2770 | \subsubsection*{Example} |
---|
2771 | |
---|
2772 | \begin{footnotesize} |
---|
2773 | \begin{verbatim} |
---|
2774 | typedef struct |
---|
2775 | { /* vertex data block */ |
---|
2776 | ... |
---|
2777 | int set; |
---|
2778 | ... |
---|
2779 | } v_data; |
---|
2780 | |
---|
2781 | typedef struct |
---|
2782 | { /* arc data block */ |
---|
2783 | ... |
---|
2784 | double cost; |
---|
2785 | ... |
---|
2786 | } a_data; |
---|
2787 | |
---|
2788 | int main(void) |
---|
2789 | { glp_graph *G; |
---|
2790 | int ret; |
---|
2791 | G = glp_create_graph(sizeof(v_data), sizeof(a_data)); |
---|
2792 | ret = glp_read_asnprob(G, offsetof(v_data, set), |
---|
2793 | offsetof(a_data, cost), "sample.asn"); |
---|
2794 | if (ret != 0) goto ... |
---|
2795 | ... |
---|
2796 | } |
---|
2797 | \end{verbatim} |
---|
2798 | \end{footnotesize} |
---|
2799 | |
---|
2800 | \subsubsection*{DIMACS assignment problem format\footnote{This |
---|
2801 | material is based on the paper ``The First DIMACS International |
---|
2802 | Algorithm Implementation Challenge: Problem Definitions and |
---|
2803 | Specifications'', which is publically available at |
---|
2804 | {\tt http://dimacs.rutgers.edu/Challenges/}.}} |
---|
2805 | \label{subsecasnprob} |
---|
2806 | |
---|
2807 | The DIMACS input file is a plain ASCII text file. It contains |
---|
2808 | {\it lines} of several types described below. A line is terminated with |
---|
2809 | an end-of-line character. Fields in each line are separated by at least |
---|
2810 | one blank space. Each line begins with a one-character designator to |
---|
2811 | identify the line type. |
---|
2812 | |
---|
2813 | Note that DIMACS requires all numerical quantities to be integers in |
---|
2814 | the range $[-2^{31},\ 2^{31}-1]$ while GLPK allows the quantities to be |
---|
2815 | floating-point numbers. |
---|
2816 | |
---|
2817 | \paragraph{Comment lines.} Comment lines give human-readable information |
---|
2818 | about the file and are ignored by programs. Comment lines can appear |
---|
2819 | anywhere in the file. Each comment line begins with a lower-case |
---|
2820 | character \verb|c|. |
---|
2821 | |
---|
2822 | \begin{verbatim} |
---|
2823 | c This is a comment line |
---|
2824 | \end{verbatim} |
---|
2825 | |
---|
2826 | \newpage |
---|
2827 | |
---|
2828 | \paragraph{Problem line.} There is one problem line per data file. The |
---|
2829 | problem line must appear before any node or arc descriptor lines. It has |
---|
2830 | the following format: |
---|
2831 | |
---|
2832 | \begin{verbatim} |
---|
2833 | p asn NODES EDGES |
---|
2834 | \end{verbatim} |
---|
2835 | |
---|
2836 | \noindent |
---|
2837 | The lower-case character \verb|p| signifies that this is a problem line. |
---|
2838 | The three-character problem designator \verb|asn| identifies the file as |
---|
2839 | containing specification information for the assignment problem. |
---|
2840 | The \verb|NODES| field contains an integer value specifying the total |
---|
2841 | number of nodes in the graph (i.e. in both sets $R$ and $S$). The |
---|
2842 | \verb|EDGES| field contains an integer value specifying the number of |
---|
2843 | edges in the graph. |
---|
2844 | |
---|
2845 | \paragraph{Node descriptors.} All node descriptor lines must appear |
---|
2846 | before all edge descriptor lines. The node descriptor lines lists the |
---|
2847 | nodes in set $R$ only, and all other nodes are assumed to be in set |
---|
2848 | $S$. There is one node descriptor line for each such node, with the |
---|
2849 | following format: |
---|
2850 | |
---|
2851 | \begin{verbatim} |
---|
2852 | n ID |
---|
2853 | \end{verbatim} |
---|
2854 | |
---|
2855 | \noindent |
---|
2856 | The lower-case character \verb|n| signifies that this is a node |
---|
2857 | descriptor line. The \verb|ID| field gives a node identification number, |
---|
2858 | an integer between 1 and \verb|NODES|. |
---|
2859 | |
---|
2860 | \paragraph{Edge descriptors.} There is one edge descriptor line for |
---|
2861 | each edge in the graph. Edge descriptor lines are of the following |
---|
2862 | format: |
---|
2863 | |
---|
2864 | \begin{verbatim} |
---|
2865 | a SRC DST COST |
---|
2866 | \end{verbatim} |
---|
2867 | |
---|
2868 | \noindent |
---|
2869 | The lower-case character \verb|a| signifies that this is an edge |
---|
2870 | descriptor line. For each edge $(i,j)$, where $i\in R$ and $j\in S$, |
---|
2871 | the \verb|SRC| field gives the identification number of vertex $i$, and |
---|
2872 | the \verb|DST| field gives the identification number of vertex $j$. |
---|
2873 | Identification numbers are integers between 1 and \verb|NODES|. The |
---|
2874 | \verb|COST| field contains the cost of edge $(i,j)$. |
---|
2875 | |
---|
2876 | \paragraph{Example.} Below here is an example of the data file in |
---|
2877 | DIMACS format corresponding to the assignment problem shown on Fig~3. |
---|
2878 | |
---|
2879 | \newpage |
---|
2880 | |
---|
2881 | \begin{footnotesize} |
---|
2882 | \begin{verbatim} |
---|
2883 | c sample.asn |
---|
2884 | c |
---|
2885 | c This is an example of the assignment problem data |
---|
2886 | c in DIMACS format. |
---|
2887 | c |
---|
2888 | p asn 17 22 |
---|
2889 | c |
---|
2890 | n 1 |
---|
2891 | n 2 |
---|
2892 | n 3 |
---|
2893 | n 4 |
---|
2894 | n 5 |
---|
2895 | n 6 |
---|
2896 | n 7 |
---|
2897 | n 8 |
---|
2898 | c |
---|
2899 | a 1 9 13 |
---|
2900 | a 1 10 21 |
---|
2901 | a 1 12 20 |
---|
2902 | a 2 10 12 |
---|
2903 | a 2 12 8 |
---|
2904 | a 2 13 26 |
---|
2905 | a 3 11 22 |
---|
2906 | a 3 13 11 |
---|
2907 | a 4 9 12 |
---|
2908 | a 4 12 36 |
---|
2909 | a 4 14 25 |
---|
2910 | a 5 11 41 |
---|
2911 | a 5 12 40 |
---|
2912 | a 5 13 11 |
---|
2913 | a 5 14 4 |
---|
2914 | a 5 15 8 |
---|
2915 | a 5 16 35 |
---|
2916 | a 5 17 32 |
---|
2917 | a 6 9 13 |
---|
2918 | a 7 10 19 |
---|
2919 | a 8 10 39 |
---|
2920 | a 8 11 15 |
---|
2921 | c |
---|
2922 | c eof |
---|
2923 | \end{verbatim} |
---|
2924 | \end{footnotesize} |
---|
2925 | |
---|
2926 | \newpage |
---|
2927 | |
---|
2928 | \subsection{glp\_write\_asnprob---write assignment problem data in\\ |
---|
2929 | DIMACS format} |
---|
2930 | |
---|
2931 | \subsubsection*{Synopsis} |
---|
2932 | |
---|
2933 | \begin{verbatim} |
---|
2934 | int glp_write_asnprob(glp_graph *G, int v_set, int a_cost, |
---|
2935 | const char *fname); |
---|
2936 | \end{verbatim} |
---|
2937 | |
---|
2938 | \subsubsection*{Description} |
---|
2939 | |
---|
2940 | The routine \verb|glp_write_asnprob| writes the assignment problem data |
---|
2941 | to a text file in DIMACS format. |
---|
2942 | |
---|
2943 | The parameter \verb|G| is the graph program object, which specifies the |
---|
2944 | assignment problem instance. |
---|
2945 | |
---|
2946 | The parameter \verb|v_set| specifies an offset of the field of type |
---|
2947 | \verb|int| in the vertex data block, which contains the node set |
---|
2948 | indicator: |
---|
2949 | |
---|
2950 | 0 --- the node is in set $R$; |
---|
2951 | |
---|
2952 | 1 --- the node is in set $S$. |
---|
2953 | |
---|
2954 | \noindent |
---|
2955 | If \verb|v_set| $<0$, it is assumed that a node having no incoming arcs |
---|
2956 | is in set $R$, and a node having no outgoing arcs is in set $S$. |
---|
2957 | |
---|
2958 | The parameter \verb|a_cost| specifies an offset of the field of type |
---|
2959 | \verb|double| in the arc data block, which contains $c_{ij}$, the edge |
---|
2960 | cost. If \verb|a_cost| $<0$, it is assumed that $c_{ij}=1$ for all |
---|
2961 | edges. |
---|
2962 | |
---|
2963 | The character string \verb|fname| specifies a name of the text file to |
---|
2964 | be written out. (If the file name ends with suffix `\verb|.gz|', the |
---|
2965 | file is assumed to be compressed, in which case the routine performs |
---|
2966 | automatic compression on writing it.) |
---|
2967 | |
---|
2968 | \subsubsection*{Note} |
---|
2969 | |
---|
2970 | The routine \verb|glp_write_asnprob| does not check that the specified |
---|
2971 | graph object correctly represents a bipartite graph. To make sure that |
---|
2972 | the problem data are correct, use the routine \verb|glp_check_asnprob|. |
---|
2973 | |
---|
2974 | \subsubsection*{Returns} |
---|
2975 | |
---|
2976 | If the operation was successful, the routine returns zero. Otherwise, |
---|
2977 | it prints an error message and returns non-zero. |
---|
2978 | |
---|
2979 | \newpage |
---|
2980 | |
---|
2981 | \subsection{glp\_check\_asnprob---check correctness of assignment |
---|
2982 | problem data} |
---|
2983 | |
---|
2984 | \subsubsection*{Synopsis} |
---|
2985 | |
---|
2986 | \begin{verbatim} |
---|
2987 | int glp_check_asnprob(glp_graph *G, int v_set); |
---|
2988 | \end{verbatim} |
---|
2989 | |
---|
2990 | \subsubsection*{Description} |
---|
2991 | |
---|
2992 | The routine \verb|glp_check_asnprob| checks that the specified graph |
---|
2993 | object \verb|G| correctly represents a bipartite graph. |
---|
2994 | |
---|
2995 | The parameter \verb|v_set| specifies an offset of the field of type |
---|
2996 | \verb|int| in the vertex data block, which contains the node set |
---|
2997 | indicator: |
---|
2998 | |
---|
2999 | 0 --- the node is in set $R$; |
---|
3000 | |
---|
3001 | 1 --- the node is in set $S$. |
---|
3002 | |
---|
3003 | \noindent |
---|
3004 | If \verb|v_set| $<0$, it is assumed that a node having no incoming arcs |
---|
3005 | is in set $R$, and a node having no outgoing arcs is in set $S$. |
---|
3006 | |
---|
3007 | \subsubsection*{Returns} |
---|
3008 | |
---|
3009 | The routine \verb|glp_check_asnprob| may return the following codes: |
---|
3010 | |
---|
3011 | 0 --- the data are correct; |
---|
3012 | |
---|
3013 | 1 --- the set indicator of some node is 0, however, that node has one |
---|
3014 | or more incoming arcs; |
---|
3015 | |
---|
3016 | 2 --- the set indicator of some node is 1, however, that node has one |
---|
3017 | or more outgoing arcs; |
---|
3018 | |
---|
3019 | 3 --- the set indicator of some node is invalid (neither 0 nor 1); |
---|
3020 | |
---|
3021 | 4 --- some node has both incoming and outgoing arcs. |
---|
3022 | |
---|
3023 | \subsection{glp\_asnprob\_lp---convert assignment problem to LP} |
---|
3024 | |
---|
3025 | \subsubsection*{Synopsis} |
---|
3026 | |
---|
3027 | \begin{verbatim} |
---|
3028 | int glp_asnprob_lp(glp_prob *P, int form, glp_graph *G, |
---|
3029 | int names, int v_set, int a_cost); |
---|
3030 | \end{verbatim} |
---|
3031 | |
---|
3032 | \subsubsection*{Description} |
---|
3033 | |
---|
3034 | The routine \verb|glp_asnprob_lp| builds LP problem, which corresponds |
---|
3035 | to the specified assignment problem. |
---|
3036 | |
---|
3037 | The parameter \verb|lp| is the resultant LP problem object to be built. |
---|
3038 | Note that on entry its current content is erased with the routine |
---|
3039 | \verb|glp_erase_prob|. |
---|
3040 | |
---|
3041 | The parameter \verb|form| defines which LP formulation should be used: |
---|
3042 | |
---|
3043 | \verb|GLP_ASN_MIN| --- perfect matching (15)---(18), minimization; |
---|
3044 | |
---|
3045 | \verb|GLP_ASN_MAX| --- perfect matching (15)---(18), maximization; |
---|
3046 | |
---|
3047 | \verb|GLP_ASN_MMP| --- maximum weighted matching (11)---(14). |
---|
3048 | |
---|
3049 | The parameter \verb|G| is the graph program object, which specifies the |
---|
3050 | assignment problem instance. |
---|
3051 | |
---|
3052 | The parameter \verb|names| is a flag. If it is \verb|GLP_ON|, the |
---|
3053 | routine uses symbolic names of the graph object components to assign |
---|
3054 | symbolic names to the LP problem object components. If the \verb|flag| |
---|
3055 | is \verb|GLP_OFF|, no symbolic names are assigned. |
---|
3056 | |
---|
3057 | The parameter \verb|v_set| specifies an offset of the field of type |
---|
3058 | \verb|int| in the vertex data block, which contains the node set |
---|
3059 | indicator: |
---|
3060 | |
---|
3061 | 0 --- the node is in set $R$; |
---|
3062 | |
---|
3063 | 1 --- the node is in set $S$. |
---|
3064 | |
---|
3065 | \noindent |
---|
3066 | If \verb|v_set| $<0$, it is assumed that a node having no incoming arcs |
---|
3067 | is in set $R$, and a node having no outgoing arcs is in set $S$. |
---|
3068 | |
---|
3069 | The parameter \verb|a_cost| specifies an offset of the field of type |
---|
3070 | \verb|double| in the arc data block, which contains $c_{ij}$, the edge |
---|
3071 | cost. If \verb|a_cost| $<0$, it is assumed that $c_{ij}=1$ for all |
---|
3072 | edges. |
---|
3073 | |
---|
3074 | \subsubsection*{Returns} |
---|
3075 | |
---|
3076 | If the LP problem has been successfully built, the routine |
---|
3077 | \verb|glp_asnprob_lp| returns zero, otherwise, non-zero (see the |
---|
3078 | routine \verb|glp_check_asnprob|). |
---|
3079 | |
---|
3080 | \subsubsection*{Example} |
---|
3081 | |
---|
3082 | The example program below reads the assignment problem instance in |
---|
3083 | DIMACS format from file `\verb|sample.asn|', converts the instance to |
---|
3084 | LP (11)---(14), and writes the resultant LP in CPLEX format to file |
---|
3085 | `\verb|matching.lp|'. |
---|
3086 | |
---|
3087 | \begin{footnotesize} |
---|
3088 | \begin{verbatim} |
---|
3089 | #include <stddef.h> |
---|
3090 | #include <glpk.h> |
---|
3091 | |
---|
3092 | typedef struct { int set; } v_data; |
---|
3093 | typedef struct { double cost; } a_data; |
---|
3094 | |
---|
3095 | int main(void) |
---|
3096 | { glp_graph *G; |
---|
3097 | glp_prob *P; |
---|
3098 | G = glp_create_graph(sizeof(v_data), sizeof(a_data)); |
---|
3099 | glp_read_asnprob(G, offsetof(v_data, set), |
---|
3100 | offsetof(a_data, cost), "sample.asn"); |
---|
3101 | P = glp_create_prob(); |
---|
3102 | glp_asnprob_lp(P, GLP_ASN_MMP, G, GLP_ON, |
---|
3103 | offsetof(v_data, set), offsetof(a_data, cost)); |
---|
3104 | glp_delete_graph(G); |
---|
3105 | glp_write_lp(P, NULL, "matching.lp"); |
---|
3106 | glp_delete_prob(P); |
---|
3107 | return 0; |
---|
3108 | } |
---|
3109 | \end{verbatim} |
---|
3110 | \end{footnotesize} |
---|
3111 | |
---|
3112 | If `\verb|sample.asn|' is the example data file from the subsection |
---|
3113 | describing the routine \verb|glp_read_asnprob|, file |
---|
3114 | `\verb|matching.lp|' may look like follows: |
---|
3115 | |
---|
3116 | \begin{footnotesize} |
---|
3117 | \begin{verbatim} |
---|
3118 | Maximize |
---|
3119 | obj: + 20 x(1,12) + 21 x(1,10) + 13 x(1,9) + 26 x(2,13) + 8 x(2,12) |
---|
3120 | + 12 x(2,10) + 11 x(3,13) + 22 x(3,11) + 25 x(4,14) + 36 x(4,12) |
---|
3121 | + 12 x(4,9) + 32 x(5,17) + 35 x(5,16) + 8 x(5,15) + 4 x(5,14) |
---|
3122 | + 11 x(5,13) + 40 x(5,12) + 41 x(5,11) + 13 x(6,9) + 19 x(7,10) |
---|
3123 | + 15 x(8,11) + 39 x(8,10) |
---|
3124 | |
---|
3125 | Subject To |
---|
3126 | r_1: + x(1,9) + x(1,10) + x(1,12) <= 1 |
---|
3127 | r_2: + x(2,10) + x(2,12) + x(2,13) <= 1 |
---|
3128 | r_3: + x(3,11) + x(3,13) <= 1 |
---|
3129 | r_4: + x(4,9) + x(4,12) + x(4,14) <= 1 |
---|
3130 | r_5: + x(5,11) + x(5,12) + x(5,13) + x(5,14) + x(5,15) + x(5,16) |
---|
3131 | + x(5,17) <= 1 |
---|
3132 | r_6: + x(6,9) <= 1 |
---|
3133 | r_7: + x(7,10) <= 1 |
---|
3134 | r_8: + x(8,10) + x(8,11) <= 1 |
---|
3135 | r_9: + x(6,9) + x(4,9) + x(1,9) <= 1 |
---|
3136 | r_10: + x(8,10) + x(7,10) + x(2,10) + x(1,10) <= 1 |
---|
3137 | r_11: + x(8,11) + x(5,11) + x(3,11) <= 1 |
---|
3138 | r_12: + x(5,12) + x(4,12) + x(2,12) + x(1,12) <= 1 |
---|
3139 | r_13: + x(5,13) + x(3,13) + x(2,13) <= 1 |
---|
3140 | r_14: + x(5,14) + x(4,14) <= 1 |
---|
3141 | r_15: + x(5,15) <= 1 |
---|
3142 | r_16: + x(5,16) <= 1 |
---|
3143 | r_17: + x(5,17) <= 1 |
---|
3144 | |
---|
3145 | Bounds |
---|
3146 | 0 <= x(1,12) <= 1 |
---|
3147 | 0 <= x(1,10) <= 1 |
---|
3148 | 0 <= x(1,9) <= 1 |
---|
3149 | 0 <= x(2,13) <= 1 |
---|
3150 | 0 <= x(2,12) <= 1 |
---|
3151 | 0 <= x(2,10) <= 1 |
---|
3152 | 0 <= x(3,13) <= 1 |
---|
3153 | 0 <= x(3,11) <= 1 |
---|
3154 | 0 <= x(4,14) <= 1 |
---|
3155 | 0 <= x(4,12) <= 1 |
---|
3156 | 0 <= x(4,9) <= 1 |
---|
3157 | 0 <= x(5,17) <= 1 |
---|
3158 | 0 <= x(5,16) <= 1 |
---|
3159 | 0 <= x(5,15) <= 1 |
---|
3160 | 0 <= x(5,14) <= 1 |
---|
3161 | 0 <= x(5,13) <= 1 |
---|
3162 | 0 <= x(5,12) <= 1 |
---|
3163 | 0 <= x(5,11) <= 1 |
---|
3164 | 0 <= x(6,9) <= 1 |
---|
3165 | 0 <= x(7,10) <= 1 |
---|
3166 | 0 <= x(8,11) <= 1 |
---|
3167 | 0 <= x(8,10) <= 1 |
---|
3168 | |
---|
3169 | End |
---|
3170 | \end{verbatim} |
---|
3171 | \end{footnotesize} |
---|
3172 | |
---|
3173 | \subsection{glp\_asnprob\_okalg---solve assignment problem with |
---|
3174 | out-of-kilter algorithm} |
---|
3175 | |
---|
3176 | \subsubsection*{Synopsis} |
---|
3177 | |
---|
3178 | \begin{verbatim} |
---|
3179 | int glp_asnprob_okalg(int form, glp_graph *G, int v_set, |
---|
3180 | int a_cost, double *sol, int a_x); |
---|
3181 | \end{verbatim} |
---|
3182 | |
---|
3183 | \subsubsection*{Description} |
---|
3184 | |
---|
3185 | The routine \verb|glp_mincost_okalg| finds optimal solution to the |
---|
3186 | assignment problem with the out-of-kilter |
---|
3187 | algorithm.\footnote{GLPK implementation of the out-of-kilter algorithm |
---|
3188 | is based on the following book: L.~R.~Ford,~Jr., and D.~R.~Fulkerson, |
---|
3189 | ``Flows in Networks,'' The RAND Corp., Report R-375-PR (August 1962), |
---|
3190 | Chap. III ``Minimal Cost Flow Problems,'' pp.~113-26.} Note that this |
---|
3191 | routine requires all the problem data to be integer-valued. |
---|
3192 | |
---|
3193 | The parameter \verb|form| defines which LP formulation should be used: |
---|
3194 | |
---|
3195 | \verb|GLP_ASN_MIN| --- perfect matching (15)---(18), minimization; |
---|
3196 | |
---|
3197 | \verb|GLP_ASN_MAX| --- perfect matching (15)---(18), maximization; |
---|
3198 | |
---|
3199 | \verb|GLP_ASN_MMP| --- maximum weighted matching (11)---(14). |
---|
3200 | |
---|
3201 | The parameter \verb|G| is the graph program object, which specifies the |
---|
3202 | assignment problem instance. |
---|
3203 | |
---|
3204 | The parameter \verb|v_set| specifies an offset of the field of type |
---|
3205 | \verb|int| in the vertex data block, which contains the node set |
---|
3206 | indicator: |
---|
3207 | |
---|
3208 | 0 --- the node is in set $R$; |
---|
3209 | |
---|
3210 | 1 --- the node is in set $S$. |
---|
3211 | |
---|
3212 | \newpage |
---|
3213 | |
---|
3214 | \noindent |
---|
3215 | If \verb|v_set| $<0$, it is assumed that a node having no incoming arcs |
---|
3216 | is in set $R$, and a node having no outgoing arcs is in set $S$. |
---|
3217 | |
---|
3218 | The parameter \verb|a_cost| specifies an offset of the field of type |
---|
3219 | \verb|double| in the arc data block, which contains $c_{ij}$, the edge |
---|
3220 | cost. This value must be integer in the range [\verb|-INT_MAX|, |
---|
3221 | \verb|+INT_MAX|]. If \verb|a_cost| $<0$, it is assumed that $c_{ij}=1$ |
---|
3222 | for all edges. |
---|
3223 | |
---|
3224 | The parameter \verb|sol| specifies a location, to which the routine |
---|
3225 | stores the objective value (that is, the total cost) found. |
---|
3226 | If \verb|sol| is \verb|NULL|, the objective value is not stored. |
---|
3227 | |
---|
3228 | The parameter \verb|a_x| specifies an offset of the field of type |
---|
3229 | \verb|int| in the arc data block, to which the routine stores $x_{ij}$. |
---|
3230 | If \verb|a_x| $<0$, this value is not stored. |
---|
3231 | |
---|
3232 | \subsubsection*{Returns} |
---|
3233 | |
---|
3234 | \def\arraystretch{1} |
---|
3235 | |
---|
3236 | \begin{tabular}{@{}p{25mm}p{97.3mm}@{}} |
---|
3237 | 0 & Optimal solution found.\\ |
---|
3238 | \verb|GLP_ENOPFS| & No (primal) feasible solution exists.\\ |
---|
3239 | \verb|GLP_EDATA| & Unable to start the search, because the assignment |
---|
3240 | problem data are either incorrect (this error is detected by the |
---|
3241 | routine \verb|glp_check_asnprob|), not integer-valued or out of range.\\ |
---|
3242 | \verb|GLP_ERANGE| & The search was prematurely terminated because of |
---|
3243 | integer overflow.\\ |
---|
3244 | \verb|GLP_EFAIL| & An error has been detected in the program logic. |
---|
3245 | (If this code is returned for your problem instance, please report to |
---|
3246 | \verb|<bug-glpk@gnu.org>|.)\\ |
---|
3247 | \end{tabular} |
---|
3248 | |
---|
3249 | \subsubsection*{Comments} |
---|
3250 | |
---|
3251 | Since the out-of-kilter algorithm is designed to find a minimal cost |
---|
3252 | circulation, the routine \verb|glp_asnprob_okalg| converts the original |
---|
3253 | graph to a network suitable for this algorithm in the following |
---|
3254 | way:\footnote{The conversion is performed internally and does not change |
---|
3255 | the original graph program object passed to the routine.} |
---|
3256 | |
---|
3257 | 1) it replaces each edge $(i,j)$ by arc $(i\rightarrow j)$, |
---|
3258 | flow $x_{ij}$ through which has zero lower bound ($l_{ij}=0$), unity |
---|
3259 | upper bound ($u_{ij}=1$), and per-unit cost $+c_{ij}$ (in case of |
---|
3260 | \verb|GLP_ASN_MIN|), or $-c_{ij}$ (in case of \verb|GLP_ASN_MAX| and |
---|
3261 | \verb|GLP_ASN_MMP|); |
---|
3262 | |
---|
3263 | 2) then it adds one auxiliary feedback node $k$; |
---|
3264 | |
---|
3265 | \newpage |
---|
3266 | |
---|
3267 | 3) for each original node $i\in R$ the routine adds auxiliary supply |
---|
3268 | arc $(k\rightarrow i)$, flow $x_{ki}$ through which is costless |
---|
3269 | ($c_{ki}=0$) and either fixed at 1 ($l_{ki}=u_{ki}=1$, in case of |
---|
3270 | \verb|GLP_ASN_MIN| and \verb|GLP_ASN_MAX|) or has zero lower bound and |
---|
3271 | unity upper bound ($l_{ij}=0$, $u_{ij}=1$, in case of |
---|
3272 | \verb|GLP_ASN_MMP|); |
---|
3273 | |
---|
3274 | 4) similarly, for each original node $j\in S$ the routine adds |
---|
3275 | auxiliary demand arc $(j\rightarrow k)$, flow $x_{jk}$ through which is |
---|
3276 | costless ($c_{jk}=0$) and either fixed at 1 ($l_{jk}=u_{jk}=1$, in case |
---|
3277 | of \verb|GLP_ASN_MIN| and \verb|GLP_ASN_MAX|) or has zero lower bound |
---|
3278 | and unity upper bound ($l_{jk}=0$, $u_{jk}=1$, in case of |
---|
3279 | \verb|GLP_ASN_MMP|). |
---|
3280 | |
---|
3281 | \subsubsection*{Example} |
---|
3282 | |
---|
3283 | The example program shown below reads the assignment problem instance |
---|
3284 | in DIMACS format from file `\verb|sample.asn|', solves it by using the |
---|
3285 | routine \verb|glp_asnprob_okalg|, and writes the solution found to the |
---|
3286 | standard output. |
---|
3287 | |
---|
3288 | \begin{footnotesize} |
---|
3289 | \begin{verbatim} |
---|
3290 | #include <stddef.h> |
---|
3291 | #include <stdio.h> |
---|
3292 | #include <stdlib.h> |
---|
3293 | #include <glpk.h> |
---|
3294 | |
---|
3295 | typedef struct { int set; } v_data; |
---|
3296 | typedef struct { double cost; int x; } e_data; |
---|
3297 | |
---|
3298 | #define node(v) ((v_data *)((v)->data)) |
---|
3299 | #define edge(e) ((e_data *)((e)->data)) |
---|
3300 | |
---|
3301 | int main(void) |
---|
3302 | { glp_graph *G; |
---|
3303 | glp_vertex *v; |
---|
3304 | glp_arc *e; |
---|
3305 | int i, ret; |
---|
3306 | double sol; |
---|
3307 | G = glp_create_graph(sizeof(v_data), sizeof(e_data)); |
---|
3308 | glp_read_asnprob(G, offsetof(v_data, set), |
---|
3309 | offsetof(e_data, cost), "sample.asn"); |
---|
3310 | ret = glp_asnprob_okalg(GLP_ASN_MMP, G, |
---|
3311 | offsetof(v_data, set), offsetof(e_data, cost), &sol, |
---|
3312 | offsetof(e_data, x)); |
---|
3313 | printf("ret = %d; sol = %5g\n", ret, sol); |
---|
3314 | for (i = 1; i <= G->nv; i++) |
---|
3315 | { v = G->v[i]; |
---|
3316 | for (e = v->out; e != NULL; e = e->t_next) |
---|
3317 | printf("edge %2d %2d: x = %d; c = %g\n", |
---|
3318 | e->tail->i, e->head->i, edge(e)->x, edge(e)->cost); |
---|
3319 | } |
---|
3320 | glp_delete_graph(G); |
---|
3321 | return 0; |
---|
3322 | } |
---|
3323 | \end{verbatim} |
---|
3324 | \end{footnotesize} |
---|
3325 | |
---|
3326 | If `\verb|sample.asn|' is the example data file from the subsection |
---|
3327 | describing the routine \verb|glp_read_asnprob|, the output may look |
---|
3328 | like follows: |
---|
3329 | |
---|
3330 | \begin{footnotesize} |
---|
3331 | \begin{verbatim} |
---|
3332 | Reading assignment problem data from `sample.asn'... |
---|
3333 | Assignment problem has 8 + 9 = 17 nodes and 22 arcs |
---|
3334 | 38 lines were read |
---|
3335 | ret = 0; sol = 180 |
---|
3336 | edge 1 12: x = 1; c = 20 |
---|
3337 | edge 1 10: x = 0; c = 21 |
---|
3338 | edge 1 9: x = 0; c = 13 |
---|
3339 | edge 2 13: x = 1; c = 26 |
---|
3340 | edge 2 12: x = 0; c = 8 |
---|
3341 | edge 2 10: x = 0; c = 12 |
---|
3342 | edge 3 13: x = 0; c = 11 |
---|
3343 | edge 3 11: x = 1; c = 22 |
---|
3344 | edge 4 14: x = 1; c = 25 |
---|
3345 | edge 4 12: x = 0; c = 36 |
---|
3346 | edge 4 9: x = 0; c = 12 |
---|
3347 | edge 5 17: x = 0; c = 32 |
---|
3348 | edge 5 16: x = 1; c = 35 |
---|
3349 | edge 5 15: x = 0; c = 8 |
---|
3350 | edge 5 14: x = 0; c = 4 |
---|
3351 | edge 5 13: x = 0; c = 11 |
---|
3352 | edge 5 12: x = 0; c = 40 |
---|
3353 | edge 5 11: x = 0; c = 41 |
---|
3354 | edge 6 9: x = 1; c = 13 |
---|
3355 | edge 7 10: x = 0; c = 19 |
---|
3356 | edge 8 11: x = 0; c = 15 |
---|
3357 | edge 8 10: x = 1; c = 39 |
---|
3358 | \end{verbatim} |
---|
3359 | \end{footnotesize} |
---|
3360 | |
---|
3361 | \newpage |
---|
3362 | |
---|
3363 | \subsection{glp\_asnprob\_hall---find bipartite matching of maximum |
---|
3364 | cardinality} |
---|
3365 | |
---|
3366 | \subsubsection*{Synopsis} |
---|
3367 | |
---|
3368 | \begin{verbatim} |
---|
3369 | int glp_asnprob_hall(glp_graph *G, int v_set, int a_x); |
---|
3370 | \end{verbatim} |
---|
3371 | |
---|
3372 | \subsubsection*{Description} |
---|
3373 | |
---|
3374 | The routine \verb|glp_asnprob_hall| finds a matching of maximal |
---|
3375 | cardinality in the specified bipartite graph. It uses a version of the |
---|
3376 | Fortran routine \verb|MC21A| developed by |
---|
3377 | I.~S.~Duff\footnote{I.~S.~Duff, Algorithm 575: Permutations for |
---|
3378 | zero-free diagonal, ACM Trans. on Math. Softw. 7 (1981), pp.~387-390.}, |
---|
3379 | which implements Hall's algorithm.\footnote{M.~Hall, ``An Algorithm for |
---|
3380 | Distinct Representatives,'' Am. Math. Monthly 63 (1956), pp.~716-717.} |
---|
3381 | |
---|
3382 | The parameter \verb|G| is a pointer to the graph program object. |
---|
3383 | |
---|
3384 | The parameter \verb|v_set| specifies an offset of the field of type |
---|
3385 | \verb|int| in the vertex data block, which contains the node set |
---|
3386 | indicator: |
---|
3387 | |
---|
3388 | 0 --- the node is in set $R$; |
---|
3389 | |
---|
3390 | 1 --- the node is in set $S$. |
---|
3391 | |
---|
3392 | \noindent |
---|
3393 | If \verb|v_set| $<0$, it is assumed that a node having no incoming arcs |
---|
3394 | is in set $R$, and a node having no outgoing arcs is in set $S$. |
---|
3395 | |
---|
3396 | The parameter \verb|a_x| specifies an offset of the field of type |
---|
3397 | \verb|int| in the arc data block, to which the routine stores $x_{ij}$. |
---|
3398 | If \verb|a_x| $<0$, this value is not stored. |
---|
3399 | |
---|
3400 | \subsubsection*{Returns} |
---|
3401 | |
---|
3402 | The routine \verb|glp_asnprob_hall| returns the cardinality of the |
---|
3403 | matching found. However, if the specified graph is incorrect (as |
---|
3404 | detected by the routine \verb|glp_check_asnprob|), this routine returns |
---|
3405 | a negative value. |
---|
3406 | |
---|
3407 | \subsubsection*{Comments} |
---|
3408 | |
---|
3409 | The same solution may be obtained with the routine |
---|
3410 | \verb|glp_asnprob_okalg| (for LP formulation \verb|GLP_ASN_MMP| and |
---|
3411 | all edge costs equal to 1). However, the routine \verb|glp_asnprob_hall| |
---|
3412 | is much faster. |
---|
3413 | |
---|
3414 | \newpage |
---|
3415 | |
---|
3416 | \subsubsection*{Example} |
---|
3417 | |
---|
3418 | The example program shown below reads the assignment problem instance |
---|
3419 | in DIMACS format from file `\verb|sample.asn|', finds a bipartite |
---|
3420 | matching of maximal cardinality by using the routine |
---|
3421 | \verb|glp_asnprob_hall|, and writes the solution found to the standard |
---|
3422 | output. |
---|
3423 | |
---|
3424 | \begin{footnotesize} |
---|
3425 | \begin{verbatim} |
---|
3426 | #include <stddef.h> |
---|
3427 | #include <stdio.h> |
---|
3428 | #include <stdlib.h> |
---|
3429 | #include <glpk.h> |
---|
3430 | |
---|
3431 | typedef struct { int set; } v_data; |
---|
3432 | typedef struct { int x; } e_data; |
---|
3433 | |
---|
3434 | #define node(v) ((v_data *)((v)->data)) |
---|
3435 | #define edge(e) ((e_data *)((e)->data)) |
---|
3436 | |
---|
3437 | int main(void) |
---|
3438 | { glp_graph *G; |
---|
3439 | glp_vertex *v; |
---|
3440 | glp_arc *e; |
---|
3441 | int i, card; |
---|
3442 | G = glp_create_graph(sizeof(v_data), sizeof(e_data)); |
---|
3443 | glp_read_asnprob(G, offsetof(v_data, set), -1, |
---|
3444 | "sample.asn"); |
---|
3445 | card = glp_asnprob_hall(G, offsetof(v_data, set), |
---|
3446 | offsetof(e_data, x)); |
---|
3447 | printf("card = %d\n", card); |
---|
3448 | for (i = 1; i <= G->nv; i++) |
---|
3449 | { v = G->v[i]; |
---|
3450 | for (e = v->out; e != NULL; e = e->t_next) |
---|
3451 | printf("edge %2d %2d: x = %d\n", |
---|
3452 | e->tail->i, e->head->i, edge(e)->x); |
---|
3453 | } |
---|
3454 | glp_delete_graph(G); |
---|
3455 | return 0; |
---|
3456 | } |
---|
3457 | \end{verbatim} |
---|
3458 | \end{footnotesize} |
---|
3459 | |
---|
3460 | If `\verb|sample.asn|' is the example data file from the subsection |
---|
3461 | describing the routine \verb|glp_read_asnprob|, the output may look |
---|
3462 | like follows: |
---|
3463 | |
---|
3464 | \begin{footnotesize} |
---|
3465 | \begin{verbatim} |
---|
3466 | Reading assignment problem data from `sample.asn'... |
---|
3467 | Assignment problem has 8 + 9 = 17 nodes and 22 arcs |
---|
3468 | 38 lines were read |
---|
3469 | card = 7 |
---|
3470 | edge 1 12: x = 1 |
---|
3471 | edge 1 10: x = 0 |
---|
3472 | edge 1 9: x = 0 |
---|
3473 | edge 2 13: x = 1 |
---|
3474 | edge 2 12: x = 0 |
---|
3475 | edge 2 10: x = 0 |
---|
3476 | edge 3 13: x = 0 |
---|
3477 | edge 3 11: x = 1 |
---|
3478 | edge 4 14: x = 1 |
---|
3479 | edge 4 12: x = 0 |
---|
3480 | edge 4 9: x = 0 |
---|
3481 | edge 5 17: x = 1 |
---|
3482 | edge 5 16: x = 0 |
---|
3483 | edge 5 15: x = 0 |
---|
3484 | edge 5 14: x = 0 |
---|
3485 | edge 5 13: x = 0 |
---|
3486 | edge 5 12: x = 0 |
---|
3487 | edge 5 11: x = 0 |
---|
3488 | edge 6 9: x = 1 |
---|
3489 | edge 7 10: x = 1 |
---|
3490 | edge 8 11: x = 0 |
---|
3491 | edge 8 10: x = 0 |
---|
3492 | \end{verbatim} |
---|
3493 | \end{footnotesize} |
---|
3494 | |
---|
3495 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
3496 | |
---|
3497 | \newpage |
---|
3498 | |
---|
3499 | \section{Critical path problem} |
---|
3500 | |
---|
3501 | \subsection{Background} |
---|
3502 | |
---|
3503 | The {\it critical path problem} (CPP) is stated as follows. Let there |
---|
3504 | be given a project $J$, which a set of jobs (tasks, activities, etc.). |
---|
3505 | Performing each job $i\in J$ requires time $t_i\geq 0$. Besides, over |
---|
3506 | the set $J$ there is given a precedence relation $R\subseteq J\times J$, |
---|
3507 | where $(i,j)\in R$ means that job $i$ immediately precedes job $j$, i.e. |
---|
3508 | performing job $j$ cannot start until job $i$ has been completely |
---|
3509 | performed. The problem is to find starting times $x_i$ for each job |
---|
3510 | $i\in J$, which satisfy to the precedence relation and minimize the |
---|
3511 | total duration (makespan) of the project. |
---|
3512 | |
---|
3513 | The following is an example of the critical path problem: |
---|
3514 | |
---|
3515 | \begin{center} |
---|
3516 | \begin{tabular}{|c|l|c|c|} |
---|
3517 | \hline |
---|
3518 | Job&Desription&Time&Predecessors\\ |
---|
3519 | \hline |
---|
3520 | A&Excavate&3&---\\ |
---|
3521 | B&Lay foundation&4&A\\ |
---|
3522 | C&Rough plumbing&3&B\\ |
---|
3523 | D&Frame&10&B\\ |
---|
3524 | E&Finish exterior&8&D\\ |
---|
3525 | F&Install HVAC&4&D\\ |
---|
3526 | G&Rough electric&6&D\\ |
---|
3527 | H&Sheet rock&8&C, E, F, G\\ |
---|
3528 | I&Install cabinets&5&H\\ |
---|
3529 | J&Paint&5&H\\ |
---|
3530 | K&Final plumbing&4&I\\ |
---|
3531 | L&Final electric&2&J\\ |
---|
3532 | M&Install flooring&4&K, L\\ |
---|
3533 | \hline |
---|
3534 | \end{tabular} |
---|
3535 | \end{center} |
---|
3536 | |
---|
3537 | Obviously, the project along with the precedence relation can be |
---|
3538 | represented as a directed graph $G=(J,R)$ called {\it project network}, |
---|
3539 | where each node $i\in J$ corresponds to a job, and arc |
---|
3540 | $(i\rightarrow j)\in R$ means that job $i$ immediately precedes job |
---|
3541 | $j$.\footnote{There exists another network representation of the |
---|
3542 | critical path problem, where jobs correspond to arcs while nodes |
---|
3543 | correspond to events introduced to express the precedence relation. |
---|
3544 | That representation, however, is much less convenient than the one, |
---|
3545 | where jobs are represented as nodes of the network.} The project network |
---|
3546 | for the example above is shown on Fig.~4. |
---|
3547 | |
---|
3548 | May note that the project network must be acyclic; otherwise, it would |
---|
3549 | be impossible to satisfy to the precedence relation for any job that |
---|
3550 | belongs to a cycle. |
---|
3551 | |
---|
3552 | \newpage |
---|
3553 | |
---|
3554 | \xymatrix |
---|
3555 | {&&&C|3\ar[rd]&&I|5\ar[r]&K|4\ar[rd]&\\ |
---|
3556 | A|3\ar[r]&B|4\ar[rru]\ar[rd]&&E|8\ar[r]&H|8\ar[ru]\ar[rd]&&&M|4\\ |
---|
3557 | &&D|10\ar[ru]\ar[r]\ar[rd]&F|4\ar[ru]&&J|5\ar[r]&L|2\ar[ru]&\\ |
---|
3558 | &&&G|6\ar[ruu]&&&&\\ |
---|
3559 | } |
---|
3560 | |
---|
3561 | \bigskip |
---|
3562 | |
---|
3563 | \noindent\hfil |
---|
3564 | Fig.~4. An example of the project network. |
---|
3565 | |
---|
3566 | \bigskip |
---|
3567 | |
---|
3568 | The critical path problem can be naturally formulated as the following |
---|
3569 | LP problem: |
---|
3570 | |
---|
3571 | \medskip |
---|
3572 | |
---|
3573 | \noindent |
---|
3574 | \hspace{.5in}minimize |
---|
3575 | $$z\eqno(19)$$ |
---|
3576 | \hspace{.5in}subject to |
---|
3577 | $$x_i+t_i\leq z\ \ \ \hbox{for all}\ i\in J\ \ \ \ \eqno(20)$$ |
---|
3578 | $$x_i+t_i\leq x_j\ \ \ \hbox{for all}\ (i,j)\in R\eqno(21)$$ |
---|
3579 | $$x_i\geq 0\ \ \ \ \ \ \ \hbox{for all}\ i\in J\ \ \eqno(22)$$ |
---|
3580 | |
---|
3581 | The inequality constraints (21), which are active in the optimal |
---|
3582 | solution, define so called {\it critical path} having the following |
---|
3583 | property: the minimal project duration $z$ can be decreased only by |
---|
3584 | decreasing the times $t_j$ for jobs on the critical path, and delaying |
---|
3585 | any critical job delays the entire project. |
---|
3586 | |
---|
3587 | \subsection{glp\_cpp---solve critical path problem} |
---|
3588 | |
---|
3589 | \subsubsection{Synopsis} |
---|
3590 | |
---|
3591 | \begin{verbatim} |
---|
3592 | double glp_cpp(glp_graph *G, int v_t, int v_es, int v_ls); |
---|
3593 | \end{verbatim} |
---|
3594 | |
---|
3595 | \subsubsection{Description} |
---|
3596 | |
---|
3597 | The routine \verb|glp_cpp| solves the critical path problem represented |
---|
3598 | in the form of the project network. |
---|
3599 | |
---|
3600 | The parameter \verb|G| is a pointer to the graph object, which |
---|
3601 | specifies the project network. This graph must be acyclic. Multiple |
---|
3602 | arcs are allowed being considered as single arcs. |
---|
3603 | |
---|
3604 | The parameter \verb|v_t| specifies an offset of the field of type |
---|
3605 | \verb|double| in the vertex data block, which contains time $t_i\geq 0$ |
---|
3606 | needed to perform corresponding job $j\in J$. If \verb|v_t| $<0$, it is |
---|
3607 | assumed that $t_i=1$ for all jobs. |
---|
3608 | |
---|
3609 | The parameter \verb|v_es| specifies an offset of the field of type |
---|
3610 | \verb|double| in the vertex data block, to which the routine stores |
---|
3611 | the {\it earliest start time} for corresponding job. If \verb|v_es| |
---|
3612 | $<0$, this time is not stored. |
---|
3613 | |
---|
3614 | The parameter \verb|v_ls| specifies an offset of the field of type |
---|
3615 | \verb|double| in the vertex data block, to which the routine stores |
---|
3616 | the {\it latest start time} for corresponding job. If \verb|v_ls| |
---|
3617 | $<0$, this time is not stored. |
---|
3618 | |
---|
3619 | The difference between the latest and earliest start times of some job |
---|
3620 | is called its {\it time reserve}. Delaying a job within its time reserve |
---|
3621 | does not affect the project duration, so if the time reserve is zero, |
---|
3622 | the corresponding job is critical. |
---|
3623 | |
---|
3624 | \subsubsection{Returns} |
---|
3625 | |
---|
3626 | The routine \verb|glp_cpp| returns the minimal project duration, i.e. |
---|
3627 | minimal time needed to perform all jobs in the project. |
---|
3628 | |
---|
3629 | \subsubsection{Example} |
---|
3630 | |
---|
3631 | The example program below solves the critical path problem shown on |
---|
3632 | Fig.~4 by using the routine \verb|glp_cpp| and writes the solution found |
---|
3633 | to the standard output. |
---|
3634 | |
---|
3635 | \begin{footnotesize} |
---|
3636 | \begin{verbatim} |
---|
3637 | #include <stddef.h> |
---|
3638 | #include <stdio.h> |
---|
3639 | #include <stdlib.h> |
---|
3640 | #include <glpk.h> |
---|
3641 | |
---|
3642 | typedef struct { double t, es, ls; } v_data; |
---|
3643 | |
---|
3644 | #define node(v) ((v_data *)((v)->data)) |
---|
3645 | |
---|
3646 | int main(void) |
---|
3647 | { glp_graph *G; |
---|
3648 | int i; |
---|
3649 | double t, es, ef, ls, lf, total; |
---|
3650 | G = glp_create_graph(sizeof(v_data), 0); |
---|
3651 | glp_add_vertices(G, 13); |
---|
3652 | node(G->v[1])->t = 3; /* A: Excavate */ |
---|
3653 | node(G->v[2])->t = 4; /* B: Lay foundation */ |
---|
3654 | node(G->v[3])->t = 3; /* C: Rough plumbing */ |
---|
3655 | node(G->v[4])->t = 10; /* D: Frame */ |
---|
3656 | node(G->v[5])->t = 8; /* E: Finish exterior */ |
---|
3657 | node(G->v[6])->t = 4; /* F: Install HVAC */ |
---|
3658 | node(G->v[7])->t = 6; /* G: Rough elecrtic */ |
---|
3659 | node(G->v[8])->t = 8; /* H: Sheet rock */ |
---|
3660 | node(G->v[9])->t = 5; /* I: Install cabinets */ |
---|
3661 | node(G->v[10])->t = 5; /* J: Paint */ |
---|
3662 | node(G->v[11])->t = 4; /* K: Final plumbing */ |
---|
3663 | node(G->v[12])->t = 2; /* L: Final electric */ |
---|
3664 | node(G->v[13])->t = 4; /* M: Install flooring */ |
---|
3665 | glp_add_arc(G, 1, 2); /* A precedes B */ |
---|
3666 | glp_add_arc(G, 2, 3); /* B precedes C */ |
---|
3667 | glp_add_arc(G, 2, 4); /* B precedes D */ |
---|
3668 | glp_add_arc(G, 4, 5); /* D precedes E */ |
---|
3669 | glp_add_arc(G, 4, 6); /* D precedes F */ |
---|
3670 | glp_add_arc(G, 4, 7); /* D precedes G */ |
---|
3671 | glp_add_arc(G, 3, 8); /* C precedes H */ |
---|
3672 | glp_add_arc(G, 5, 8); /* E precedes H */ |
---|
3673 | glp_add_arc(G, 6, 8); /* F precedes H */ |
---|
3674 | glp_add_arc(G, 7, 8); /* G precedes H */ |
---|
3675 | glp_add_arc(G, 8, 9); /* H precedes I */ |
---|
3676 | glp_add_arc(G, 8, 10); /* H precedes J */ |
---|
3677 | glp_add_arc(G, 9, 11); /* I precedes K */ |
---|
3678 | glp_add_arc(G, 10, 12); /* J precedes L */ |
---|
3679 | glp_add_arc(G, 11, 13); /* K precedes M */ |
---|
3680 | glp_add_arc(G, 12, 13); /* L precedes M */ |
---|
3681 | total = glp_cpp(G, offsetof(v_data, t), offsetof(v_data, es), |
---|
3682 | offsetof(v_data, ls)); |
---|
3683 | printf("Minimal project duration is %.2f\n\n", total); |
---|
3684 | printf("Job Time ES EF LS LF\n"); |
---|
3685 | printf("--- ------ ------ ------ ------ ------\n"); |
---|
3686 | for (i = 1; i <= G->nv; i++) |
---|
3687 | { t = node(G->v[i])->t; |
---|
3688 | es = node(G->v[i])->es; |
---|
3689 | ef = es + node(G->v[i])->t; |
---|
3690 | ls = node(G->v[i])->ls; |
---|
3691 | lf = ls + node(G->v[i])->t; |
---|
3692 | printf("%3d %6.2f %s %6.2f %6.2f %6.2f %6.2f\n", |
---|
3693 | i, t, ls - es < 0.001 ? "*" : " ", es, ef, ls, lf); |
---|
3694 | } |
---|
3695 | glp_delete_graph(G); |
---|
3696 | return 0; |
---|
3697 | } |
---|
3698 | \end{verbatim} |
---|
3699 | \end{footnotesize} |
---|
3700 | |
---|
3701 | The output from the example program shown below includes job number, |
---|
3702 | the time needed to perform a job, earliest start time (\verb|ES|), |
---|
3703 | earliest finish time (\verb|EF|), latest start time (\verb|LS|), and |
---|
3704 | latest finish time (\verb|LF|) for each job in the project. Critical |
---|
3705 | jobs are marked by asterisks. |
---|
3706 | |
---|
3707 | \newpage |
---|
3708 | |
---|
3709 | \begin{footnotesize} |
---|
3710 | \begin{verbatim} |
---|
3711 | Minimal project duration is 46.00 |
---|
3712 | |
---|
3713 | Job Time ES EF LS LF |
---|
3714 | --- ------ ------ ------ ------ ------ |
---|
3715 | 1 3.00 * 0.00 3.00 0.00 3.00 |
---|
3716 | 2 4.00 * 3.00 7.00 3.00 7.00 |
---|
3717 | 3 3.00 7.00 10.00 22.00 25.00 |
---|
3718 | 4 10.00 * 7.00 17.00 7.00 17.00 |
---|
3719 | 5 8.00 * 17.00 25.00 17.00 25.00 |
---|
3720 | 6 4.00 17.00 21.00 21.00 25.00 |
---|
3721 | 7 6.00 17.00 23.00 19.00 25.00 |
---|
3722 | 8 8.00 * 25.00 33.00 25.00 33.00 |
---|
3723 | 9 5.00 * 33.00 38.00 33.00 38.00 |
---|
3724 | 10 5.00 33.00 38.00 35.00 40.00 |
---|
3725 | 11 4.00 * 38.00 42.00 38.00 42.00 |
---|
3726 | 12 2.00 38.00 40.00 40.00 42.00 |
---|
3727 | 13 4.00 * 42.00 46.00 42.00 46.00 |
---|
3728 | \end{verbatim} |
---|
3729 | \end{footnotesize} |
---|
3730 | |
---|
3731 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
3732 | |
---|
3733 | \chapter{Graph Optimization API Routines} |
---|
3734 | |
---|
3735 | \section{Maximum clique problem} |
---|
3736 | |
---|
3737 | \subsection{Background} |
---|
3738 | |
---|
3739 | The {\it maximum clique problem (MCP)} is a classic combinatorial |
---|
3740 | optimization problem. Given an undirected graph $G=(V,E)$, where $V$ is |
---|
3741 | a set of vertices, and $E$ is a set of edges, this problem is to find |
---|
3742 | the largest {\it clique} $C\subseteq G$, i.e. the largest induced |
---|
3743 | complete subgraph. A generalization of this problem is the {\it maximum |
---|
3744 | weight clique problem (MWCP)}, which is to find a clique $C\subseteq G$ |
---|
3745 | of the largest weight $\displaystyle\sum_{v\in C}w(v)\rightarrow\max$, |
---|
3746 | where $w(v)$ is a weight of vertex $v\in V$. |
---|
3747 | |
---|
3748 | An example of the maximum weight clique problem is shown on Fig.~5. |
---|
3749 | |
---|
3750 | \begin{figure} |
---|
3751 | \noindent\hfil |
---|
3752 | \begin{tabular}{c} |
---|
3753 | {\xymatrix %@C=16pt |
---|
3754 | {&&&{v_1}\ar@{-}[lllddd]\ar@{-}[llddddd]\ar@{-}[dddddd] |
---|
3755 | \ar@{-}[rrrddd]&&&\\ |
---|
3756 | &{v_2}\ar@{-}[rrrr]\ar@{-}[rrrrdddd]\ar@{-}[rrddddd]\ar@{-}[dddd]&&&& |
---|
3757 | {v_3}\ar@{-}[llllldd]\ar@{-}[lllldddd]\ar@{-}[dddd]&\\ |
---|
3758 | &&&&&&\\ |
---|
3759 | {v_4}\ar@{-}[rrrrrr]\ar@{-}[rrrddd]&&&&&&{v_5}\ar@{-}[lllddd] |
---|
3760 | \ar@{-}[ldd]\\ |
---|
3761 | &&&&&&\\ |
---|
3762 | &{v_6}\ar@{-}[rrrr]&&&&{v_7}&\\ |
---|
3763 | &&&{v_8}&&&\\ |
---|
3764 | }} |
---|
3765 | \end{tabular} |
---|
3766 | \begin{tabular}{r@{\ }c@{\ }l} |
---|
3767 | $w(v_1)$&=&3\\$w(v_2)$&=&4\\$w(v_3)$&=&8\\$w(v_4)$&=&1\\ |
---|
3768 | $w(v_5)$&=&5\\$w(v_6)$&=&2\\$w(v_7)$&=&1\\$w(v_8)$&=&3\\ |
---|
3769 | \end{tabular} |
---|
3770 | |
---|
3771 | \begin{center} |
---|
3772 | Fig.~5. An example of the maximum weight clique problem. |
---|
3773 | \end{center} |
---|
3774 | \end{figure} |
---|
3775 | |
---|
3776 | \subsection{glp\_wclique\_exact---find maximum weight clique with exact |
---|
3777 | algorithm} |
---|
3778 | |
---|
3779 | \subsubsection*{Synopsis} |
---|
3780 | |
---|
3781 | \begin{verbatim} |
---|
3782 | int glp_wclique_exact(glp_graph *G, int v_wgt, double *sol, |
---|
3783 | int v_set); |
---|
3784 | \end{verbatim} |
---|
3785 | |
---|
3786 | \subsection*{Description} |
---|
3787 | |
---|
3788 | The routine {\it glp\_wclique\_exact} finds a maximum weight clique in |
---|
3789 | the specified undirected graph with the exact algorithm developed by |
---|
3790 | Patric \"Osterg{\aa}rd.\footnote{P.~R.~J.~\"Osterg{\aa}rd, A new |
---|
3791 | algorithm for the maximum-weight clique problem, Nordic J. of Computing, |
---|
3792 | Vol.~8, No.~4, 2001, pp.~424--36.} |
---|
3793 | |
---|
3794 | The parameter $G$ is the program object, which specifies an undirected |
---|
3795 | graph. Each arc $(x\rightarrow y)$ in $G$ is considered as edge |
---|
3796 | $(x,y)$, self-loops are ignored, and multiple edges, if present, are |
---|
3797 | replaced (internally) by simple edges. |
---|
3798 | |
---|
3799 | The parameter {\it v\_wgt} specifies an offset of the field of type |
---|
3800 | {\bf double} in the vertex data block, which contains a weight of |
---|
3801 | corresponding vertex. Vertex weights must be integer-valued in the |
---|
3802 | range $[0,$ {\it INT\_MAX}$]$. If {\it v\_wgt} $<0$, it is assumed that |
---|
3803 | all vertices of the graph have the weight 1. |
---|
3804 | |
---|
3805 | The parameter {\it sol} specifies a location, to which the routine |
---|
3806 | stores the weight of the clique found (the clique weight is the sum |
---|
3807 | of weights of all vertices included in the clique.) If {\it sol} is |
---|
3808 | {\it NULL}, the solution is not stored. |
---|
3809 | |
---|
3810 | The parameter {\it v\_set} specifies an offset of the field of type |
---|
3811 | {\bf int} in the vertex data block, to which the routines stores a |
---|
3812 | vertex flag: 1 means that the corresponding vertex is included in the |
---|
3813 | clique found, and 0 otherwise. If {\it v\_set} $<0$, vertex flags are |
---|
3814 | not stored. |
---|
3815 | |
---|
3816 | \subsubsection*{Returns} |
---|
3817 | |
---|
3818 | \def\arraystretch{1} |
---|
3819 | |
---|
3820 | \begin{tabular}{@{}p{25mm}p{97.3mm}@{}} |
---|
3821 | 0 & Optimal solution found.\\ |
---|
3822 | \verb|GLP_EDATA| & Unable to start the search, because some vertex |
---|
3823 | weights are either not integer-valued or out of range. This code is |
---|
3824 | also returned if the sum of weights of all vertices exceeds |
---|
3825 | {\it INT\_MAX}. \\ |
---|
3826 | \end{tabular} |
---|
3827 | |
---|
3828 | \subsubsection*{Notes} |
---|
3829 | |
---|
3830 | \noindent\indent |
---|
3831 | 1. The routine {\it glp\_wclique\_exact} finds exact solution. Since |
---|
3832 | both MCP and MWCP problems are NP-complete, the algorithm may require |
---|
3833 | exponential time in worst cases. |
---|
3834 | |
---|
3835 | 2. Internally the specified graph is converted to an adjacency matrix |
---|
3836 | in {\it dense} format. This requires about $|V|^2/16$ bytes of memory, |
---|
3837 | where $|V|$ is the number of vertices in the graph. |
---|
3838 | |
---|
3839 | \subsubsection*{Example} |
---|
3840 | |
---|
3841 | The example program shown below reads a MWCP instance in DIMACS |
---|
3842 | clique/coloring format from file `\verb|sample.clq|', finds the clique |
---|
3843 | of largest weight, and writes the solution found to the standard output. |
---|
3844 | |
---|
3845 | \begin{footnotesize} |
---|
3846 | \begin{verbatim} |
---|
3847 | #include <stddef.h> |
---|
3848 | #include <stdio.h> |
---|
3849 | #include <stdlib.h> |
---|
3850 | #include <glpk.h> |
---|
3851 | |
---|
3852 | typedef struct { double wgt; int set; } v_data; |
---|
3853 | |
---|
3854 | #define vertex(v) ((v_data *)((v)->data)) |
---|
3855 | |
---|
3856 | int main(void) |
---|
3857 | { glp_graph *G; |
---|
3858 | glp_vertex *v; |
---|
3859 | int i, ret; |
---|
3860 | double sol; |
---|
3861 | G = glp_create_graph(sizeof(v_data), 0); |
---|
3862 | glp_read_ccdata(G, offsetof(v_data, wgt), "sample.clq"); |
---|
3863 | ret = glp_wclique_exact(G, offsetof(v_data, wgt), &sol, |
---|
3864 | offsetof(v_data, set)); |
---|
3865 | printf("ret = %d; sol = %g\n", ret, sol); |
---|
3866 | for (i = 1; i <= G->nv; i++) |
---|
3867 | { v = G->v[i]; |
---|
3868 | printf("vertex %d: weight = %g, flag = %d\n", |
---|
3869 | i, vertex(v)->wgt, vertex(v)->set); |
---|
3870 | } |
---|
3871 | glp_delete_graph(G); |
---|
3872 | return 0; |
---|
3873 | } |
---|
3874 | \end{verbatim} |
---|
3875 | \end{footnotesize} |
---|
3876 | |
---|
3877 | \noindent |
---|
3878 | For the example shown on Fig.~5 the data file may look like follows: |
---|
3879 | |
---|
3880 | \begin{footnotesize} |
---|
3881 | \begin{verbatim} |
---|
3882 | c sample.clq |
---|
3883 | c |
---|
3884 | c This is an example of the maximum weight clique |
---|
3885 | c problem in DIMACS clique/coloring format. |
---|
3886 | c |
---|
3887 | p edge 8 16 |
---|
3888 | n 1 3 |
---|
3889 | n 2 4 |
---|
3890 | n 3 8 |
---|
3891 | n 5 5 |
---|
3892 | n 6 2 |
---|
3893 | n 8 3 |
---|
3894 | e 1 4 |
---|
3895 | e 1 5 |
---|
3896 | e 1 6 |
---|
3897 | e 1 8 |
---|
3898 | e 2 3 |
---|
3899 | e 2 6 |
---|
3900 | e 2 7 |
---|
3901 | e 2 8 |
---|
3902 | e 3 4 |
---|
3903 | e 3 6 |
---|
3904 | e 3 7 |
---|
3905 | e 4 5 |
---|
3906 | e 4 8 |
---|
3907 | e 5 7 |
---|
3908 | e 5 8 |
---|
3909 | e 6 7 |
---|
3910 | c |
---|
3911 | c eof |
---|
3912 | \end{verbatim} |
---|
3913 | \end{footnotesize} |
---|
3914 | |
---|
3915 | \noindent |
---|
3916 | The corresponding output from the example program is the following: |
---|
3917 | |
---|
3918 | \begin{footnotesize} |
---|
3919 | \begin{verbatim} |
---|
3920 | Reading graph from `sample.clq'... |
---|
3921 | Graph has 8 vertices and 16 edges |
---|
3922 | 28 lines were read |
---|
3923 | ret = 0; sol = 15 |
---|
3924 | vertex 1: weight = 3, flag = 0 |
---|
3925 | vertex 2: weight = 4, flag = 1 |
---|
3926 | vertex 3: weight = 8, flag = 1 |
---|
3927 | vertex 4: weight = 1, flag = 0 |
---|
3928 | vertex 5: weight = 5, flag = 0 |
---|
3929 | vertex 6: weight = 2, flag = 1 |
---|
3930 | vertex 7: weight = 1, flag = 1 |
---|
3931 | vertex 8: weight = 3, flag = 0 |
---|
3932 | \end{verbatim} |
---|
3933 | \end{footnotesize} |
---|
3934 | |
---|
3935 | \end{document} |
---|