lemon-project-template-glpk
view deps/glpk/doc/graphs.tex @ 9:33de93886c88
Import GLPK 4.47
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 20:59:10 +0100 |
| parents | |
| children |
line source
1 %* graphs.tex *%
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 %***********************************************************************
25 \documentclass[11pt]{report}
26 \usepackage{amssymb}
27 \usepackage[dvipdfm,linktocpage,colorlinks,linkcolor=blue,
28 urlcolor=blue]{hyperref}
29 \usepackage[all]{xy}
31 \renewcommand\contentsname{\sf\bfseries Contents}
32 \renewcommand\chaptername{\sf\bfseries Chapter}
33 \renewcommand\appendixname{\sf\bfseries Appendix}
35 \begin{document}
37 \thispagestyle{empty}
39 \begin{center}
41 \vspace*{1in}
43 \begin{huge}
44 \sf\bfseries GNU Linear Programming Kit
45 \end{huge}
47 \vspace{0.5in}
49 \begin{LARGE}
50 \sf Graph and Network Routines
51 \end{LARGE}
53 \vspace{0.5in}
55 \begin{LARGE}
56 \sf for GLPK Version 4.45
57 \end{LARGE}
59 \vspace{0.5in}
60 \begin{Large}
61 \sf (DRAFT, December 2010)
62 \end{Large}
63 \end{center}
65 \newpage
67 \vspace*{1in}
69 \vfill
71 \noindent
72 The GLPK package is part of the GNU Project released under the aegis of
73 GNU.
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.
80 \medskip \noindent
81 Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
82 02110-1301, USA.
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.
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.
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.
99 \tableofcontents
101 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
103 \chapter{Basic Graph API Routines}
105 \section{Graph program object}
107 In GLPK the base program object used to represent graphs and networks
108 is a directed graph (digraph).
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}.
116 Representation of a graph in the program includes three structs defined
117 by typedef in the header \verb|glpk.h|:
119 \medskip
121 $\bullet$ \verb|glp_graph|, which represents the graph in a whole,
123 $\bullet$ \verb|glp_vertex|, which represents a vertex of the graph, and
125 $\bullet$ \verb|glp_arc|, which represents an arc of the graph.
127 \medskip
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.
134 \newpage
136 \newenvironment{comment}
137 {\addtolength{\leftskip}{17pt}\noindent}
138 {\par\addtolength{\leftskip}{-17pt}}
140 \noindent
141 {\bf glp\_graph.} The struct \verb|glp_graph| has the following
142 fields available to the application program:
144 \medskip
146 \noindent
147 \verb|char *name;|
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}
154 \medskip
156 \noindent
157 \verb|int nv;|
159 \begin{comment}The number of vertices in the graph, $nv\geq 0$.
160 \end{comment}
162 \medskip
164 \noindent
165 \verb|int na;|
167 \begin{comment}The number of arcs in the graph, $na\geq 0$.
168 \end{comment}
170 \medskip
172 \noindent
173 \verb|glp_vertex **v;|
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}
183 \medskip
185 \noindent
186 \verb|int v_size;|
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}
193 \medskip
195 \noindent
196 \verb|int a_size;|
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}
203 \bigskip
205 \noindent
206 {\bf glp\_vertex.} The struct \verb|glp_vertex| has the following
207 fields available to the application program:
209 \medskip
211 \noindent
212 \verb|int i;|
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}
219 \medskip
221 \noindent
222 \verb|char *name;|
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}
229 \medskip
231 \noindent
232 \verb|void *data;|
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}
240 \medskip
242 \noindent
243 \verb|void *temp;|
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}
249 \medskip
251 \noindent
252 \verb|glp_arc *in;|
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}
258 \medskip
260 \noindent
261 \verb|glp_arc *out;|
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}
267 \bigskip
269 \noindent
270 {\bf glp\_arc.} The struct \verb|glp_arc| has the following fields
271 available to the application program:
273 \medskip
275 \noindent
276 \verb|glp_vertex *tail;|
278 \begin{comment}Pointer to a vertex, which is tail endpoint of the arc.
279 \end{comment}
281 \medskip
283 \noindent
284 \verb|glp_vertex *head;|
286 \begin{comment}Pointer to a vertex, which is head endpoint of the arc.
287 \end{comment}
289 \medskip
291 \noindent
292 \verb|void *data;|
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}
300 \medskip
302 \noindent
303 \verb|void *temp;|
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}
309 \medskip
311 \noindent
312 \verb|glp_arc *t_next;|
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}
319 \medskip
321 \noindent
322 \verb|glp_arc *h_next;|
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}
329 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
331 \newpage
333 \section{Graph creating and modifying routines}
335 \subsection{glp\_create\_graph---create graph}
337 \subsubsection*{Synopsis}
339 \begin{verbatim}
340 glp_graph *glp_create_graph(int v_size, int a_size);
341 \end{verbatim}
343 \subsubsection*{Description}
345 The routine \verb|glp_create_graph| creates a new graph, which
346 initially is\linebreak empty, i.e. has no vertices and arcs.
348 The parameter \verb|v_size| specifies the size of vertex data blocks,
349 in bytes, $0\leq v\_size\leq 256$.
351 The parameter \verb|a_size| specifies the size of arc data blocks, in
352 bytes, $0\leq a\_size\leq 256$.
354 \subsubsection*{Returns}
356 The routine returns a pointer to the graph created.
358 \subsection{glp\_set\_graph\_name---assign (change) graph name}
360 \subsubsection*{Synopsis}
362 \begin{verbatim}
363 void glp_set_graph_name(glp_graph *G, const char *name);
364 \end{verbatim}
366 \subsubsection*{Description}
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.
371 If the parameter \verb|name| is \verb|NULL| or an empty string, the
372 routine erases the existing symbolic name of the graph.
374 \newpage
376 \subsection{glp\_add\_vertices---add new vertices to graph}
378 \subsubsection*{Synopsis}
380 \begin{verbatim}
381 int glp_add_vertices(glp_graph *G, int nadd);
382 \end{verbatim}
384 \subsubsection*{Description}
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.
392 Being added each new vertex is isolated, i.e. has no incident arcs.
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|.
400 \subsubsection*{Returns}
402 The routine \verb|glp_add_vertices| returns the ordinal number of the
403 first new vertex added to the graph.
405 \subsection{glp\_set\_vertex\_name---assign (change) vertex name}
407 \subsubsection*{Synopsis}
409 \begin{verbatim}
410 void glp_set_vertex_name(glp_graph *G, int i, const char *name);
411 \end{verbatim}
413 \subsubsection*{Description}
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.
418 If the parameter \verb|name| is \verb|NULL| or empty string, the
419 routine erases an existing name of \verb|i|-th vertex.
421 \newpage
423 \subsection{glp\_add\_arc---add new arc to graph}
425 \subsubsection*{Synopsis}
427 \begin{verbatim}
428 glp_arc *glp_add_arc(glp_graph *G, int i, int j);
429 \end{verbatim}
431 \subsubsection*{Description}
433 The routine \verb|glp_add_arc| adds one new arc to the specified graph.
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.
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|.
445 \subsection{glp\_del\_vertices---delete vertices from graph}
447 \subsubsection*{Synopsis}
449 \begin{verbatim}
450 void glp_del_vertices(glp_graph *G, int ndel, const int num[]);
451 \end{verbatim}
453 \subsubsection*{Description}
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$.
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.
465 \subsection{glp\_del\_arc---delete arc from graph}
467 \subsubsection*{Synopsis}
469 \begin{verbatim}
470 void glp_del_arc(glp_graph *G, glp_arc *a);
471 \end{verbatim}
473 \subsubsection*{Description}
475 The routine \verb|glp_del_arc| deletes an arc from the specified graph.
476 The arc to be deleted must exist.
478 \subsection{glp\_erase\_graph---erase graph content}
480 \subsubsection*{Synopsis}
482 \begin{verbatim}
483 void glp_erase_graph(glp_graph *G, int v_size, int a_size);
484 \end{verbatim}
486 \subsubsection*{Description}
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.
494 The parameters \verb|v_size| and \verb|a_size| have the same meaning as
495 for the routine \verb|glp_create_graph|.
497 \subsection{glp\_delete\_graph---delete graph}
499 \subsubsection*{Synopsis}
501 \begin{verbatim}
502 void glp_delete_graph(glp_graph *G);
503 \end{verbatim}
505 \subsubsection*{Description}
507 The routine \verb|glp_delete_graph| deletes the specified graph and
508 frees all the memory allocated to this program object.
510 \newpage
512 \section{Graph searching routines}
514 \subsection{glp\_create\_v\_index---create vertex name index}
516 \subsubsection*{Synopsis}
518 \begin{verbatim}
519 void glp_create_v_index(glp_graph *G);
520 \end{verbatim}
522 \subsubsection*{Description}
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.
529 This routine can be called at any time. If the name index already
530 exists, the routine does nothing.
532 \subsection{glp\_find\_vertex---find vertex by its name}
534 \subsubsection*{Synopsis}
536 \begin{verbatim}
537 int glp_find_vertex(glp_graph *G, const char *name);
538 \end{verbatim}
540 \subsubsection*{Returns}
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.
547 \subsection{glp\_delete\_v\_index---delete vertex name index}
549 \subsubsection*{Synopsis}
551 \begin{verbatim}
552 void glp_delete_v_index(glp_graph *G);
553 \end{verbatim}
555 \subsubsection*{Description}
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.
561 This routine can be called at any time. If the name index does not
562 exist, the routine does nothing.
564 \newpage
566 \section{Graph reading/writing routines}
568 \subsection{glp\_read\_graph---read graph from plain text file}
570 \subsubsection*{Synopsis}
572 \begin{verbatim}
573 int glp_read_graph(glp_graph *G, const char *fname);
574 \end{verbatim}
576 \subsubsection*{Description}
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|.
583 For the file format see description of the routine
584 \verb|glp_write_graph|.
586 \subsubsection*{Returns}
588 If the operation was successful, the routine returns zero. Otherwise
589 it prints an error message and returns non-zero.
591 \subsection{glp\_write\_graph---write graph to plain text file}
593 \subsubsection*{Synopsis}
595 \begin{verbatim}
596 int glp_write_graph(glp_graph *G, const char *fname);
597 \end{verbatim}
599 \subsubsection*{Description}
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|.
604 \subsubsection*{Returns}
606 If the operation was successful, the routine returns zero. Otherwise
607 it prints an error message and returns non-zero.
609 \subsubsection*{File format}
611 The file created by the routine \verb|glp_write_graph| is a plain text
612 file, which contains the following information:
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}
622 \noindent
623 where:
625 \noindent
626 \verb|nv| is the number of vertices (nodes);
628 \noindent
629 \verb|na| is the number of arcs;
631 \noindent
632 \verb|i[k]|, $k=1,\dots,na$, is the index of tail vertex of arc $k$;
634 \noindent
635 \verb|j[k]|, $k=1,\dots,na$, is the index of head vertex of arc $k$.
637 \subsection{glp\_read\_ccdata---read graph from text file in DIMACS
638 clique/coloring format}
640 \subsubsection*{Synopsis}
642 \begin{verbatim}
643 int glp_read_ccdata(glp_graph *G, int v_wgt,
644 const char *fname);
645 \end{verbatim}
647 \subsubsection*{Description}
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.)
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}.
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.
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''.)
670 \subsubsection*{Returns}
672 If the operation was successful, the routine returns zero. Otherwise,
673 it prints an error message and returns non-zero.
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/}.}}
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.
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.
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|.
695 \begin{verbatim}
696 c This is a comment line
697 \end{verbatim}
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:
703 \begin{verbatim}
704 p edge NODES EDGES
705 \end{verbatim}
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.
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.
720 \begin{verbatim}
721 n ID VALUE
722 \end{verbatim}
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).
731 \paragraph{Edge descriptors.} There is one edge descriptor line for
732 each edge (arc) of the graph, each with the following format:
734 \begin{verbatim}
735 e I J
736 \end{verbatim}
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.
743 \paragraph{Example.} The following example of an undirected graph:
745 \bigskip
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 }
758 \bigskip
760 \noindent
761 might be coded in DIMACS clique/coloring format as follows:
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}
798 \subsection{glp\_write\_ccdata---write graph to text file in DIMACS
799 clique/coloring format}
801 \subsubsection*{Synopsis}
803 \begin{verbatim}
804 int glp_write_ccdata(glp_graph *G, int v_wgt,
805 const char *fname);
806 \end{verbatim}
808 \subsection*{Description}
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.)
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.
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.)
827 \subsubsection*{Returns}
829 If the operation was successful, the routine returns zero. Otherwise,
830 it prints an error message and returns non-zero.
832 \newpage
834 \section{Graph analysis routines}
836 \subsection{glp\_weak\_comp---find all weakly connected components of
837 graph}
839 \subsubsection*{Synopsis}
841 \begin{verbatim}
842 int glp_weak_comp(glp_graph *G, int v_num);
843 \end{verbatim}
845 \subsubsection*{Description}
847 The routine \verb|glp_weak_comp| finds all weakly connected components
848 of the specified graph.
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.
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|$.
859 \subsubsection*{Returns}
861 The routine returns \verb|nc|, the total number of components found.
863 \subsection{glp\_strong\_comp---find all strongly connected components
864 of graph}
866 \subsubsection*{Synopsis}
868 \begin{verbatim}
869 int glp_strong_comp(glp_graph *G, int v_num);
870 \end{verbatim}
872 \subsubsection*{Description}
874 The routine \verb|glp_strong_comp| finds all strongly connected
875 components of the specified graph.
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.
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.
888 \subsubsection*{Returns}
890 The routine returns \verb|nc|, the total number of components found.
892 \subsubsection*{References}
894 I.~S.~Duff, J.~K.~Reid, Algorithm 529: Permutations to block triangular
895 form, ACM Trans. on Math. Softw. 4 (1978), 189-92.
897 \subsubsection*{Example}
899 The following program reads a graph from a plain text file
900 `\verb|graph.txt|' and finds all its strongly connected components.
902 \begin{footnotesize}
903 \begin{verbatim}
904 #include <stddef.h>
905 #include <stdio.h>
906 #include <stdlib.h>
907 #include <glpk.h>
909 typedef struct { int num; } v_data;
911 #define vertex(v) ((v_data *)((v)->data))
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}
928 \noindent
929 If the file `\verb|graph.txt|' contains the graph shown below:
931 \bigskip
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 }
942 \bigskip\bigskip
944 \noindent
945 the program output may look like follows:
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}
971 \subsection{glp\_top\_sort---topological sorting of acyclic digraph}
973 \subsubsection*{Synopsis}
975 \begin{verbatim}
976 int glp_top_sort(glp_graph *G, int v_num);
977 \end{verbatim}
979 \subsubsection*{Description}
981 The routine \verb|glp_top_sort| performs topological sorting of
982 vertices of the specified acyclic digraph.
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.
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.
995 \subsubsection*{Returns}
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$.
1002 \subsubsection*{Example}
1004 The following program reads a digraph from a plain text file
1005 `\verb|graph.txt|' and performs topological sorting of its vertices.
1007 \begin{footnotesize}
1008 \begin{verbatim}
1009 #include <stddef.h>
1010 #include <stdio.h>
1011 #include <stdlib.h>
1012 #include <glpk.h>
1014 typedef struct { int num; } v_data;
1016 #define vertex(v) ((v_data *)((v)->data))
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}
1033 \noindent
1034 If the file `\verb|graph.txt|' contains the graph shown below:
1036 \bigskip
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 }
1048 \bigskip\bigskip
1050 \noindent
1051 the program output may look like follows:
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}
1079 \noindent
1080 The output corresponds to the following vertex numbering:
1082 \bigskip
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 }
1094 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1096 \chapter{Network optimization API routines}
1098 \section{Minimum cost flow problem}
1100 \subsection{Background}
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:
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);
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);
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.
1119 Let also for each arc $a=(i,j)\in A$ there be given the following three
1120 quantities:
1122 $l_{ij}$, a (non-negative) lower bound to the flow through arc $(i,j)$;
1124 $u_{ij}$, an upper bound to the flow through arc $(i,j)$, which is the
1125 {\it arc capacity};
1127 $c_{ij}$, a per-unit cost of the flow through arc $(i,j)$.
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.
1137 An example of the minimum cost flow problem is shown on Fig.~1.
1139 \bigskip
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 }
1155 \medskip
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}
1164 \bigskip
1166 \noindent\hfil
1167 Fig.~1. An example of the minimum cost flow problem.
1169 \bigskip
1171 The minimum cost flow problem can be naturally formulated as the
1172 following LP problem:
1174 \medskip
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)$$
1185 \newpage
1187 \subsection{glp\_read\_mincost---read minimum cost flow problem\\data
1188 in DIMACS format}
1190 \subsubsection*{Synopsis}
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}
1197 \subsubsection*{Description}
1199 The routine \verb|glp_read_mincost| reads the minimum cost flow problem
1200 data from a text file in DIMACS format.
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|.
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.
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.
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.
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.
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''.)
1232 \subsubsection*{Returns}
1234 If the operation was successful, the routine returns zero. Otherwise,
1235 it prints an error message and returns non-zero.
1237 \newpage
1239 \subsubsection*{Example}
1241 \begin{footnotesize}
1242 \begin{verbatim}
1243 typedef struct
1244 { /* vertex data block */
1245 ...
1246 double rhs;
1247 ...
1248 } v_data;
1250 typedef struct
1251 { /* arc data block */
1252 ...
1253 double low, cap, cost;
1254 ...
1255 } a_data;
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}
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}
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.
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.
1287 \newpage
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|.
1294 \begin{verbatim}
1295 c This is a comment line
1296 \end{verbatim}
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:
1302 \begin{verbatim}
1303 p min NODES ARCS
1304 \end{verbatim}
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.
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:
1320 \begin{verbatim}
1321 n ID FLOW
1322 \end{verbatim}
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|.
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:
1334 \begin{verbatim}
1335 a SRC DST LOW CAP COST
1336 \end{verbatim}
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)$.
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.
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}
1385 \newpage
1387 \subsection{glp\_write\_mincost---write minimum cost flow problem\\data
1388 in DIMACS format}
1390 \subsubsection*{Synopsis}
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}
1397 \subsubsection*{Description}
1399 The routine \verb|glp_write_mincost| writes the minimum cost flow
1400 problem data to a text file in DIMACS format.
1402 The parameter \verb|G| is the graph (network) program object, which
1403 specifies the minimum cost flow problem instance.
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.
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.
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.
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.
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.)
1432 \subsubsection*{Returns}
1434 If the operation was successful, the routine returns zero. Otherwise,
1435 it prints an error message and returns non-zero.
1437 \newpage
1439 \subsection{glp\_mincost\_lp---convert minimum cost flow problem\\to LP}
1441 \subsubsection*{Synopsis}
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}
1448 \subsubsection*{Description}
1450 The routine \verb|glp_mincost_lp| builds LP problem (1)---(3), which
1451 corresponds to the specified minimum cost flow problem.
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|.
1457 The parameter \verb|G| is the graph (network) program object, which
1458 specifies the minimum cost flow problem instance.
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.
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.
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.
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.
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.
1487 \subsubsection*{Example}
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|'.
1494 \newpage
1496 \begin{footnotesize}
1497 \begin{verbatim}
1498 #include <stddef.h>
1499 #include <glpk.h>
1501 typedef struct { double rhs; } v_data;
1502 typedef struct { double low, cap, cost; } a_data;
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}
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:
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)
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
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
1560 End
1561 \end{verbatim}
1562 \end{footnotesize}
1564 \subsection{glp\_mincost\_okalg---solve minimum cost flow problem with
1565 out-of-kilter algorithm}
1567 \subsubsection*{Synopsis}
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}
1574 \subsubsection*{Description}
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.
1584 The parameter \verb|G| is a graph (network) program object which
1585 specifies the minimum cost flow problem instance to be solved.
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.
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.
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.
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.
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.
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.
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)$.
1631 Note that all solution components (the objective value, arc flows, and
1632 node potentials) computed by the routine are always integer-valued.
1634 \subsubsection*{Returns}
1636 \def\arraystretch{1}
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}
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}
1656 \subsubsection*{Comments}
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.}
1666 1) it adds two auxiliary nodes $s$ and $t$;
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$);
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$);
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.
1681 \subsubsection*{Example}
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.
1688 \begin{footnotesize}
1689 \begin{verbatim}
1690 #include <stddef.h>
1691 #include <stdio.h>
1692 #include <stdlib.h>
1693 #include <glpk.h>
1695 typedef struct { double rhs, pi; } v_data;
1696 typedef struct { double low, cap, cost, x; } a_data;
1698 #define node(v) ((v_data *)((v)->data))
1699 #define arc(a) ((a_data *)((a)->data))
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}
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:
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}
1768 \subsection{glp\_netgen---Klingman's network problem generator}
1770 \subsubsection*{Synopsis}
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}
1777 \subsubsection*{Description}
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.
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|.
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.
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.
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.
1804 The array \verb|parm| contains description of the network to be
1805 generated:
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}
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}
1832 \subsubsection*{Notes}
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.$$
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}.$$
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.
1849 \subsubsection*{Returns}
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.
1855 \subsection{glp\_gridgen---grid-like network problem generator}
1857 \subsubsection*{Synopsis}
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}
1864 \subsubsection*{Description}
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>}.}
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|.
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.
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.
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.
1889 The array \verb|parm| contains parameters of the network to be
1890 generated:
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}
1921 \subsubsection*{Returns}
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.
1927 \subsubsection*{Comments\footnote{This material is based on comments
1928 to the original version of GRIDGEN.}}
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.
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.
1946 \bigskip
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 }
1955 \bigskip
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.
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.
1968 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1970 \newpage
1972 \section{Maximum flow problem}
1974 \subsection{Background}
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).
1990 An example of the maximum flow problem, where $s=v_1$ and $t=v_9$, is
1991 shown on Fig.~2.
1993 \bigskip
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 }
2009 \bigskip
2011 \noindent\hfil
2012 Fig.~2. An example of the maximum flow problem.
2014 \bigskip
2016 The maximum flow problem can be naturally formulated as the following
2017 LP problem:
2019 \medskip
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)$$
2036 \medskip
2038 \noindent
2039 where $F\geq 0$ is an additional variable playing the role of the
2040 objective.
2042 \newpage
2044 Another LP formulation of the maximum flow problem, which does not
2045 include the variable $F$, is the following:
2047 \medskip
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)$$
2064 \subsection{glp\_read\_maxflow---read maximum flow problem data\\in
2065 DIMACS format}
2067 \subsubsection*{Synopsis}
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}
2074 \subsubsection*{Description}
2076 The routine \verb|glp_read_maxflow| reads the maximum flow problem
2077 data from a text file in DIMACS format.
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|.
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.
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.
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.
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''.)
2102 \subsubsection*{Returns}
2104 If the operation was successful, the routine returns zero. Otherwise,
2105 it prints an error message and returns non-zero.
2107 \subsubsection*{Example}
2109 \begin{footnotesize}
2110 \begin{verbatim}
2111 typedef struct
2112 { /* arc data block */
2113 ...
2114 double cap;
2115 ...
2116 } a_data;
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}
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}
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.
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.
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|.
2152 \begin{verbatim}
2153 c This is a comment line
2154 \end{verbatim}
2156 \newpage
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:
2162 \begin{verbatim}
2163 p max NODES ARCS
2164 \end{verbatim}
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.
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:
2178 \begin{verbatim}
2179 n ID WHICH
2180 \end{verbatim}
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.
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:
2192 \begin{verbatim}
2193 a SRC DST CAP
2194 \end{verbatim}
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.
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.
2208 \newpage
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}
2241 \subsection{glp\_write\_maxflow---write maximum flow problem data\\
2242 in DIMACS format}
2244 \subsubsection*{Synopsis}
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}
2251 \subsubsection*{Description}
2253 The routine \verb|glp_write_maxflow| writes the maximum flow problem
2254 data to a text file in DIMACS format.
2256 The parameter \verb|G| is the graph (network) program object, which
2257 specifies the maximum flow problem instance.
2259 The parameter \verb|s| specifies the ordinal number of the source node.
2261 The parameter \verb|t| specifies the ordinal number of the sink node.
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.
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.)
2275 \subsubsection*{Returns}
2277 If the operation was successful, the routine returns zero. Otherwise,
2278 it prints an error message and returns non-zero.
2280 \subsection{glp\_maxflow\_lp---convert maximum flow problem to LP}
2282 \subsubsection*{Synopsis}
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}
2289 \subsubsection*{Description}
2291 The routine \verb|glp_maxflow_lp| builds LP problem (7)---(9), which
2292 corresponds to the specified maximum flow problem.
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|.
2298 The parameter \verb|G| is the graph (network) program object, which
2299 specifies the maximum flow problem instance.
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.
2306 The parameter \verb|s| specifies the ordinal number of the source node.
2308 The parameter \verb|t| specifies the ordinal number of the sink node.
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.
2317 \subsubsection*{Example}
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|'.
2324 \begin{footnotesize}
2325 \begin{verbatim}
2326 #include <stddef.h>
2327 #include <glpk.h>
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}
2345 If `\verb|sample.max|' is the example data file from the previous
2346 subsection, the output `\verb|maxflow.lp|' may look like follows:
2348 \begin{footnotesize}
2349 \begin{verbatim}
2350 Maximize
2351 obj: + x(1,4) + x(1,2)
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
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
2380 End
2381 \end{verbatim}
2382 \end{footnotesize}
2384 \subsection{glp\_maxflow\_ffalg---solve maximum flow problem with
2385 Ford-Fulkerson algorithm}
2387 \subsubsection*{Synopsis}
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}
2394 \subsubsection*{Description}
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.
2404 The parameter \verb|G| is a graph (network) program object which
2405 specifies the maximum flow problem instance to be solved.
2407 The parameter $s$ specifies the ordinal number of the source node.
2409 The parameter $t$ specifies the ordinal number of the sink node.
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.
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.
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.
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.
2435 Note that all solution components (the objective value and arc flows)
2436 computed by the routine are always integer-valued.
2438 \subsubsection*{Returns}
2440 \def\arraystretch{1}
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}
2448 \subsubsection*{Example}
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.
2455 \begin{footnotesize}
2456 \begin{verbatim}
2457 #include <stddef.h>
2458 #include <stdio.h>
2459 #include <stdlib.h>
2460 #include <glpk.h>
2462 typedef struct { int cut; } v_data;
2463 typedef struct { double cap, x; } a_data;
2465 #define node(v) ((v_data *)((v)->data))
2466 #define arc(a) ((a_data *)((a)->data))
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}
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:
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}
2521 \newpage
2523 \subsection{glp\_rmfgen---Goldfarb's maximum flow problem generator}
2525 \subsubsection*{Synopsis}
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}
2532 \subsubsection*{Description}
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>}.}
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|.
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.
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.
2559 The array \verb|parm| contains description of the network to be
2560 generated:
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}
2571 \subsubsection*{Returns}
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.
2577 \newpage
2579 \subsubsection*{Comments\footnote{This material is based on comments
2580 to the original version of RMFGEN.}}
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$.)
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.
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.
2594 \begin{verbatim}
2595 t
2596 +-------+
2597 | .|
2598 | . |
2599 / | / |
2600 +-------+/ -+ b
2601 | | |/.
2602 a | -v- |/
2603 | | |/
2604 +-------+ 1
2605 s a
2606 \end{verbatim}
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.
2612 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2614 \newpage
2616 \section{Assignment problem}
2618 \subsection{Background}
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$.
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).
2641 An example of the assignment problem, which is the maximum weighted
2642 bipartite matching problem, is shown on Fig. 3.
2644 The maximum weighted bipartite matching problem can be naturally
2645 formulated as the following LP problem:
2647 \medskip
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)$$
2658 \medskip
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.}
2666 \newpage
2668 \bigskip
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 }
2689 \bigskip
2691 \noindent\hfil
2692 Fig.~3. An example of the assignment problem.
2694 \bigskip
2696 Similarly, the perfect assignment problem can be naturally formulated
2697 as the following LP problem:
2699 \medskip
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)$$
2710 \medskip
2712 \noindent
2713 where variables $x_{ij}$ have the same meaning as for (11)---(14)
2714 above.
2716 \newpage
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}$.
2723 \subsection{glp\_read\_asnprob---read assignment problem data in\\DIMACS
2724 format}
2726 \subsubsection*{Synopsis}
2728 \begin{verbatim}
2729 int glp_read_asnprob(glp_graph *G, int v_set, int a_cost,
2730 const char *fname);
2731 \end{verbatim}
2733 \subsubsection*{Description}
2735 The routine \verb|glp_read_asnprob| reads the assignment problem data
2736 from a text file in DIMACS format.
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|.
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:
2747 0 --- the node is in set $R$;
2749 1 --- the node is in set $S$.
2751 \noindent
2752 If \verb|v_set| $<0$, the node set indicator is not stored.
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.
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''.)
2763 \subsubsection*{Returns}
2765 If the operation was successful, the routine returns zero. Otherwise,
2766 it prints an error message and returns non-zero.
2768 \newpage
2770 \subsubsection*{Example}
2772 \begin{footnotesize}
2773 \begin{verbatim}
2774 typedef struct
2775 { /* vertex data block */
2776 ...
2777 int set;
2778 ...
2779 } v_data;
2781 typedef struct
2782 { /* arc data block */
2783 ...
2784 double cost;
2785 ...
2786 } a_data;
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}
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}
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.
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.
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|.
2822 \begin{verbatim}
2823 c This is a comment line
2824 \end{verbatim}
2826 \newpage
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:
2832 \begin{verbatim}
2833 p asn NODES EDGES
2834 \end{verbatim}
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.
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:
2851 \begin{verbatim}
2852 n ID
2853 \end{verbatim}
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|.
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:
2864 \begin{verbatim}
2865 a SRC DST COST
2866 \end{verbatim}
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)$.
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.
2879 \newpage
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}
2926 \newpage
2928 \subsection{glp\_write\_asnprob---write assignment problem data in\\
2929 DIMACS format}
2931 \subsubsection*{Synopsis}
2933 \begin{verbatim}
2934 int glp_write_asnprob(glp_graph *G, int v_set, int a_cost,
2935 const char *fname);
2936 \end{verbatim}
2938 \subsubsection*{Description}
2940 The routine \verb|glp_write_asnprob| writes the assignment problem data
2941 to a text file in DIMACS format.
2943 The parameter \verb|G| is the graph program object, which specifies the
2944 assignment problem instance.
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:
2950 0 --- the node is in set $R$;
2952 1 --- the node is in set $S$.
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$.
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.
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.)
2968 \subsubsection*{Note}
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|.
2974 \subsubsection*{Returns}
2976 If the operation was successful, the routine returns zero. Otherwise,
2977 it prints an error message and returns non-zero.
2979 \newpage
2981 \subsection{glp\_check\_asnprob---check correctness of assignment
2982 problem data}
2984 \subsubsection*{Synopsis}
2986 \begin{verbatim}
2987 int glp_check_asnprob(glp_graph *G, int v_set);
2988 \end{verbatim}
2990 \subsubsection*{Description}
2992 The routine \verb|glp_check_asnprob| checks that the specified graph
2993 object \verb|G| correctly represents a bipartite graph.
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:
2999 0 --- the node is in set $R$;
3001 1 --- the node is in set $S$.
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$.
3007 \subsubsection*{Returns}
3009 The routine \verb|glp_check_asnprob| may return the following codes:
3011 0 --- the data are correct;
3013 1 --- the set indicator of some node is 0, however, that node has one
3014 or more incoming arcs;
3016 2 --- the set indicator of some node is 1, however, that node has one
3017 or more outgoing arcs;
3019 3 --- the set indicator of some node is invalid (neither 0 nor 1);
3021 4 --- some node has both incoming and outgoing arcs.
3023 \subsection{glp\_asnprob\_lp---convert assignment problem to LP}
3025 \subsubsection*{Synopsis}
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}
3032 \subsubsection*{Description}
3034 The routine \verb|glp_asnprob_lp| builds LP problem, which corresponds
3035 to the specified assignment problem.
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|.
3041 The parameter \verb|form| defines which LP formulation should be used:
3043 \verb|GLP_ASN_MIN| --- perfect matching (15)---(18), minimization;
3045 \verb|GLP_ASN_MAX| --- perfect matching (15)---(18), maximization;
3047 \verb|GLP_ASN_MMP| --- maximum weighted matching (11)---(14).
3049 The parameter \verb|G| is the graph program object, which specifies the
3050 assignment problem instance.
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.
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:
3061 0 --- the node is in set $R$;
3063 1 --- the node is in set $S$.
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$.
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.
3074 \subsubsection*{Returns}
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|).
3080 \subsubsection*{Example}
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|'.
3087 \begin{footnotesize}
3088 \begin{verbatim}
3089 #include <stddef.h>
3090 #include <glpk.h>
3092 typedef struct { int set; } v_data;
3093 typedef struct { double cost; } a_data;
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}
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:
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)
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
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
3169 End
3170 \end{verbatim}
3171 \end{footnotesize}
3173 \subsection{glp\_asnprob\_okalg---solve assignment problem with
3174 out-of-kilter algorithm}
3176 \subsubsection*{Synopsis}
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}
3183 \subsubsection*{Description}
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.
3193 The parameter \verb|form| defines which LP formulation should be used:
3195 \verb|GLP_ASN_MIN| --- perfect matching (15)---(18), minimization;
3197 \verb|GLP_ASN_MAX| --- perfect matching (15)---(18), maximization;
3199 \verb|GLP_ASN_MMP| --- maximum weighted matching (11)---(14).
3201 The parameter \verb|G| is the graph program object, which specifies the
3202 assignment problem instance.
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:
3208 0 --- the node is in set $R$;
3210 1 --- the node is in set $S$.
3212 \newpage
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$.
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.
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.
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.
3232 \subsubsection*{Returns}
3234 \def\arraystretch{1}
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}
3249 \subsubsection*{Comments}
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.}
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|);
3263 2) then it adds one auxiliary feedback node $k$;
3265 \newpage
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|);
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|).
3281 \subsubsection*{Example}
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.
3288 \begin{footnotesize}
3289 \begin{verbatim}
3290 #include <stddef.h>
3291 #include <stdio.h>
3292 #include <stdlib.h>
3293 #include <glpk.h>
3295 typedef struct { int set; } v_data;
3296 typedef struct { double cost; int x; } e_data;
3298 #define node(v) ((v_data *)((v)->data))
3299 #define edge(e) ((e_data *)((e)->data))
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}
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:
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}
3361 \newpage
3363 \subsection{glp\_asnprob\_hall---find bipartite matching of maximum
3364 cardinality}
3366 \subsubsection*{Synopsis}
3368 \begin{verbatim}
3369 int glp_asnprob_hall(glp_graph *G, int v_set, int a_x);
3370 \end{verbatim}
3372 \subsubsection*{Description}
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.}
3382 The parameter \verb|G| is a pointer to the graph program object.
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:
3388 0 --- the node is in set $R$;
3390 1 --- the node is in set $S$.
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$.
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.
3400 \subsubsection*{Returns}
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.
3407 \subsubsection*{Comments}
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.
3414 \newpage
3416 \subsubsection*{Example}
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.
3424 \begin{footnotesize}
3425 \begin{verbatim}
3426 #include <stddef.h>
3427 #include <stdio.h>
3428 #include <stdlib.h>
3429 #include <glpk.h>
3431 typedef struct { int set; } v_data;
3432 typedef struct { int x; } e_data;
3434 #define node(v) ((v_data *)((v)->data))
3435 #define edge(e) ((e_data *)((e)->data))
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}
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:
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}
3495 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3497 \newpage
3499 \section{Critical path problem}
3501 \subsection{Background}
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.
3513 The following is an example of the critical path problem:
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}
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.
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.
3552 \newpage
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 }
3561 \bigskip
3563 \noindent\hfil
3564 Fig.~4. An example of the project network.
3566 \bigskip
3568 The critical path problem can be naturally formulated as the following
3569 LP problem:
3571 \medskip
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)$$
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.
3587 \subsection{glp\_cpp---solve critical path problem}
3589 \subsubsection{Synopsis}
3591 \begin{verbatim}
3592 double glp_cpp(glp_graph *G, int v_t, int v_es, int v_ls);
3593 \end{verbatim}
3595 \subsubsection{Description}
3597 The routine \verb|glp_cpp| solves the critical path problem represented
3598 in the form of the project network.
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.
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.
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.
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.
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.
3624 \subsubsection{Returns}
3626 The routine \verb|glp_cpp| returns the minimal project duration, i.e.
3627 minimal time needed to perform all jobs in the project.
3629 \subsubsection{Example}
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.
3635 \begin{footnotesize}
3636 \begin{verbatim}
3637 #include <stddef.h>
3638 #include <stdio.h>
3639 #include <stdlib.h>
3640 #include <glpk.h>
3642 typedef struct { double t, es, ls; } v_data;
3644 #define node(v) ((v_data *)((v)->data))
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}
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.
3707 \newpage
3709 \begin{footnotesize}
3710 \begin{verbatim}
3711 Minimal project duration is 46.00
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}
3731 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3733 \chapter{Graph Optimization API Routines}
3735 \section{Maximum clique problem}
3737 \subsection{Background}
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$.
3748 An example of the maximum weight clique problem is shown on Fig.~5.
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}
3771 \begin{center}
3772 Fig.~5. An example of the maximum weight clique problem.
3773 \end{center}
3774 \end{figure}
3776 \subsection{glp\_wclique\_exact---find maximum weight clique with exact
3777 algorithm}
3779 \subsubsection*{Synopsis}
3781 \begin{verbatim}
3782 int glp_wclique_exact(glp_graph *G, int v_wgt, double *sol,
3783 int v_set);
3784 \end{verbatim}
3786 \subsection*{Description}
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.}
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.
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.
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.
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.
3816 \subsubsection*{Returns}
3818 \def\arraystretch{1}
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}
3828 \subsubsection*{Notes}
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.
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.
3839 \subsubsection*{Example}
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.
3845 \begin{footnotesize}
3846 \begin{verbatim}
3847 #include <stddef.h>
3848 #include <stdio.h>
3849 #include <stdlib.h>
3850 #include <glpk.h>
3852 typedef struct { double wgt; int set; } v_data;
3854 #define vertex(v) ((v_data *)((v)->data))
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}
3877 \noindent
3878 For the example shown on Fig.~5 the data file may look like follows:
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}
3915 \noindent
3916 The corresponding output from the example program is the following:
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}
3935 \end{document}