1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/doc/graphs.tex	Sun Nov 06 20:59:10 2011 +0100
     1.3 @@ -0,0 +1,3935 @@
     1.4 +%* graphs.tex *%
     1.5 +
     1.6 +%***********************************************************************
     1.7 +%  This code is part of GLPK (GNU Linear Programming Kit).
     1.8 +%
     1.9 +%  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
    1.10 +%  2009, 2010 Andrew Makhorin, Department for Applied Informatics,
    1.11 +%  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
    1.12 +%  E-mail: <mao@gnu.org>.
    1.13 +%
    1.14 +%  GLPK is free software: you can redistribute it and/or modify it
    1.15 +%  under the terms of the GNU General Public License as published by
    1.16 +%  the Free Software Foundation, either version 3 of the License, or
    1.17 +%  (at your option) any later version.
    1.18 +%
    1.19 +%  GLPK is distributed in the hope that it will be useful, but WITHOUT
    1.20 +%  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    1.21 +%  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
    1.22 +%  License for more details.
    1.23 +%
    1.24 +%  You should have received a copy of the GNU General Public License
    1.25 +%  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
    1.26 +%***********************************************************************
    1.27 +
    1.28 +\documentclass[11pt]{report}
    1.29 +\usepackage{amssymb}
    1.30 +\usepackage[dvipdfm,linktocpage,colorlinks,linkcolor=blue,
    1.31 +urlcolor=blue]{hyperref}
    1.32 +\usepackage[all]{xy}
    1.33 +
    1.34 +\renewcommand\contentsname{\sf\bfseries Contents}
    1.35 +\renewcommand\chaptername{\sf\bfseries Chapter}
    1.36 +\renewcommand\appendixname{\sf\bfseries Appendix}
    1.37 +
    1.38 +\begin{document}
    1.39 +
    1.40 +\thispagestyle{empty}
    1.41 +
    1.42 +\begin{center}
    1.43 +
    1.44 +\vspace*{1in}
    1.45 +
    1.46 +\begin{huge}
    1.47 +\sf\bfseries GNU Linear Programming Kit
    1.48 +\end{huge}
    1.49 +
    1.50 +\vspace{0.5in}
    1.51 +
    1.52 +\begin{LARGE}
    1.53 +\sf Graph and Network Routines
    1.54 +\end{LARGE}
    1.55 +
    1.56 +\vspace{0.5in}
    1.57 +
    1.58 +\begin{LARGE}
    1.59 +\sf for GLPK Version 4.45
    1.60 +\end{LARGE}
    1.61 +
    1.62 +\vspace{0.5in}
    1.63 +\begin{Large}
    1.64 +\sf (DRAFT, December 2010)
    1.65 +\end{Large}
    1.66 +\end{center}
    1.67 +
    1.68 +\newpage
    1.69 +
    1.70 +\vspace*{1in}
    1.71 +
    1.72 +\vfill
    1.73 +
    1.74 +\noindent
    1.75 +The GLPK package is part of the GNU Project released under the aegis of
    1.76 +GNU.
    1.77 +
    1.78 +\medskip \noindent
    1.79 +Copyright \copyright{} 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
    1.80 +2008, 2009, 2010 Andrew Makhorin, Department for Applied Informatics,
    1.81 +Moscow Aviation Institute, Moscow, Russia. All rights reserved.
    1.82 +
    1.83 +\medskip \noindent
    1.84 +Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
    1.85 +02110-1301, USA.
    1.86 +
    1.87 +\medskip \noindent
    1.88 +Permission is granted to make and distribute verbatim copies of this
    1.89 +manual provided the copyright notice and this permission notice are
    1.90 +preserved on all copies.
    1.91 +
    1.92 +\medskip \noindent
    1.93 +Permission is granted to copy and distribute modified versions of this
    1.94 +manual under the conditions for verbatim copying, provided also that the
    1.95 +entire resulting derived work is distributed under the terms of
    1.96 +a permission notice identical to this one.
    1.97 +
    1.98 +\medskip \noindent
    1.99 +Permission is granted to copy and distribute translations of this manual
   1.100 +into another language, under the above conditions for modified versions.
   1.101 +
   1.102 +\tableofcontents
   1.103 +
   1.104 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   1.105 +
   1.106 +\chapter{Basic Graph API Routines}
   1.107 +
   1.108 +\section{Graph program object}
   1.109 +
   1.110 +In GLPK the base program object used to represent graphs and networks
   1.111 +is a directed graph (digraph).
   1.112 +
   1.113 +Formally, {\it digraph} (or simply, {\it graph}) is a pair $G=(V,A)$,
   1.114 +where $V$ is a set of {\it vertices}, and $A$ is a set
   1.115 +{\it arcs}.\footnote{$A$ may be a multiset.} Each arc $a\in A$ is an
   1.116 +ordered pair of vertices $a=(x,y)$, where $x\in V$ is called {\it tail
   1.117 +vertex} of arc $a$, and $y\in V$ is called its {\it head vertex}.
   1.118 +
   1.119 +Representation of a graph in the program includes three structs defined
   1.120 +by typedef in the header \verb|glpk.h|:
   1.121 +
   1.122 +\medskip
   1.123 +
   1.124 +$\bullet$ \verb|glp_graph|, which represents the graph in a whole,
   1.125 +
   1.126 +$\bullet$ \verb|glp_vertex|, which represents a vertex of the graph, and
   1.127 +
   1.128 +$\bullet$ \verb|glp_arc|, which represents an arc of the graph.
   1.129 +
   1.130 +\medskip
   1.131 +
   1.132 +All these three structs are ``semi-opaque'', i.e. the application
   1.133 +program can directly access their fields through pointers, however,
   1.134 +changing the fields directly is not allowed---all changes should be
   1.135 +performed only with appropriate GLPK API routines.
   1.136 +
   1.137 +\newpage
   1.138 +
   1.139 +\newenvironment{comment}
   1.140 +{\addtolength{\leftskip}{17pt}\noindent}
   1.141 +{\par\addtolength{\leftskip}{-17pt}}
   1.142 +
   1.143 +\noindent
   1.144 +{\bf glp\_graph.} The struct \verb|glp_graph| has the following
   1.145 +fields available to the application program:
   1.146 +
   1.147 +\medskip
   1.148 +
   1.149 +\noindent
   1.150 +\verb|char *name;|
   1.151 +
   1.152 +\begin{comment}Symbolic name assigned to the graph. It is a pointer to
   1.153 +a null terminated character string of length from 1 to 255 characters.
   1.154 +If no name is assigned to the graph, this field contains \verb|NULL|.
   1.155 +\end{comment}
   1.156 +
   1.157 +\medskip
   1.158 +
   1.159 +\noindent
   1.160 +\verb|int nv;|
   1.161 +
   1.162 +\begin{comment}The number of vertices in the graph, $nv\geq 0$.
   1.163 +\end{comment}
   1.164 +
   1.165 +\medskip
   1.166 +
   1.167 +\noindent
   1.168 +\verb|int na;|
   1.169 +
   1.170 +\begin{comment}The number of arcs in the graph, $na\geq 0$.
   1.171 +\end{comment}
   1.172 +
   1.173 +\medskip
   1.174 +
   1.175 +\noindent
   1.176 +\verb|glp_vertex **v;|
   1.177 +
   1.178 +\begin{comment}Pointer to an array containing the list of vertices.
   1.179 +Element $v[0]$ is not used. Element $v[i]$, $1\leq i\leq nv$, is a
   1.180 +pointer to $i$-th vertex of the graph. Note that on adding new vertices
   1.181 +to the graph the field $v$ may be altered due to reallocation. However,
   1.182 +pointers $v[i]$ are not changed while corresponding vertices exist in
   1.183 +the graph.
   1.184 +\end{comment}
   1.185 +
   1.186 +\medskip
   1.187 +
   1.188 +\noindent
   1.189 +\verb|int v_size;|
   1.190 +
   1.191 +\begin{comment}Size of vertex data blocks, in bytes,
   1.192 +$0\leq v\_size\leq 256$. (See also the field \verb|data| in the struct
   1.193 +\verb|glp_vertex|.)
   1.194 +\end{comment}
   1.195 +
   1.196 +\medskip
   1.197 +
   1.198 +\noindent
   1.199 +\verb|int a_size;|
   1.200 +
   1.201 +\begin{comment}Size of arc data blocks, in bytes,
   1.202 +$0\leq v\_size\leq 256$. (See also the field \verb|data| in the struct
   1.203 +\verb|glp_arc|.)
   1.204 +\end{comment}
   1.205 +
   1.206 +\bigskip
   1.207 +
   1.208 +\noindent
   1.209 +{\bf glp\_vertex.} The struct \verb|glp_vertex| has the following
   1.210 +fields available to the application program:
   1.211 +
   1.212 +\medskip
   1.213 +
   1.214 +\noindent
   1.215 +\verb|int i;|
   1.216 +
   1.217 +\begin{comment}Ordinal number of the vertex, $1\leq i\leq nv$. Note
   1.218 +that element $v[i]$ in the struct \verb|glp_graph| points to the vertex,
   1.219 +whose ordinal number is $i$.
   1.220 +\end{comment}
   1.221 +
   1.222 +\medskip
   1.223 +
   1.224 +\noindent
   1.225 +\verb|char *name;|
   1.226 +
   1.227 +\begin{comment}Symbolic name assigned to the vertex. It is a pointer to
   1.228 +a null terminated character string of length from 1 to 255 characters.
   1.229 +If no name is assigned to the vertex, this field contains \verb|NULL|.
   1.230 +\end{comment}
   1.231 +
   1.232 +\medskip
   1.233 +
   1.234 +\noindent
   1.235 +\verb|void *data;|
   1.236 +
   1.237 +\begin{comment}Pointer to a data block associated with the vertex. This
   1.238 +data block is automatically allocated on creating a new vertex and freed
   1.239 +on deleting the vertex. If $v\_size=0$, the block is not allocated, and
   1.240 +this field contains \verb|NULL|.
   1.241 +\end{comment}
   1.242 +
   1.243 +\medskip
   1.244 +
   1.245 +\noindent
   1.246 +\verb|void *temp;|
   1.247 +
   1.248 +\begin{comment}Working pointer, which may be used freely for any
   1.249 +purposes. The application program can change this field directly.
   1.250 +\end{comment}
   1.251 +
   1.252 +\medskip
   1.253 +
   1.254 +\noindent
   1.255 +\verb|glp_arc *in;|
   1.256 +
   1.257 +\begin{comment}Pointer to the (unordered) list of incoming arcs. If the
   1.258 +vertex has no incoming arcs, this field contains \verb|NULL|.
   1.259 +\end{comment}
   1.260 +
   1.261 +\medskip
   1.262 +
   1.263 +\noindent
   1.264 +\verb|glp_arc *out;|
   1.265 +
   1.266 +\begin{comment}Pointer to the (unordered) list of outgoing arcs. If the
   1.267 +vertex has no outgoing arcs, this field contains \verb|NULL|.
   1.268 +\end{comment}
   1.269 +
   1.270 +\bigskip
   1.271 +
   1.272 +\noindent
   1.273 +{\bf glp\_arc.} The struct \verb|glp_arc| has the following fields
   1.274 +available to the application program:
   1.275 +
   1.276 +\medskip
   1.277 +
   1.278 +\noindent
   1.279 +\verb|glp_vertex *tail;|
   1.280 +
   1.281 +\begin{comment}Pointer to a vertex, which is tail endpoint of the arc.
   1.282 +\end{comment}
   1.283 +
   1.284 +\medskip
   1.285 +
   1.286 +\noindent
   1.287 +\verb|glp_vertex *head;|
   1.288 +
   1.289 +\begin{comment}Pointer to a vertex, which is head endpoint of the arc.
   1.290 +\end{comment}
   1.291 +
   1.292 +\medskip
   1.293 +
   1.294 +\noindent
   1.295 +\verb|void *data;|
   1.296 +
   1.297 +\begin{comment}Pointer to a data block associated with the arc. This
   1.298 +data block is automatically allocated on creating a new arc and freed on
   1.299 +deleting the arc. If $v\_size=0$, the block is not allocated, and this
   1.300 +field contains \verb|NULL|.
   1.301 +\end{comment}
   1.302 +
   1.303 +\medskip
   1.304 +
   1.305 +\noindent
   1.306 +\verb|void *temp;|
   1.307 +
   1.308 +\begin{comment}Working pointer, which may be used freely for any
   1.309 +purposes. The application program can change this field directly.
   1.310 +\end{comment}
   1.311 +
   1.312 +\medskip
   1.313 +
   1.314 +\noindent
   1.315 +\verb|glp_arc *t_next;|
   1.316 +
   1.317 +\begin{comment}Pointer to another arc, which has the same tail endpoint
   1.318 +as this one. \verb|NULL| in this field indicates the end of the list of
   1.319 +outgoing arcs.
   1.320 +\end{comment}
   1.321 +
   1.322 +\medskip
   1.323 +
   1.324 +\noindent
   1.325 +\verb|glp_arc *h_next;|
   1.326 +
   1.327 +\begin{comment}Pointer to another arc, which has the same head endpoint
   1.328 +as this one. \verb|NULL| in this field indicates the end of the list of
   1.329 +incoming arcs.
   1.330 +\end{comment}
   1.331 +
   1.332 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   1.333 +
   1.334 +\newpage
   1.335 +
   1.336 +\section{Graph creating and modifying routines}
   1.337 +
   1.338 +\subsection{glp\_create\_graph---create graph}
   1.339 +
   1.340 +\subsubsection*{Synopsis}
   1.341 +
   1.342 +\begin{verbatim}
   1.343 +glp_graph *glp_create_graph(int v_size, int a_size);
   1.344 +\end{verbatim}
   1.345 +
   1.346 +\subsubsection*{Description}
   1.347 +
   1.348 +The routine \verb|glp_create_graph| creates a new graph, which
   1.349 +initially is\linebreak empty, i.e. has no vertices and arcs.
   1.350 +
   1.351 +The parameter \verb|v_size| specifies the size of vertex data blocks,
   1.352 +in bytes, $0\leq v\_size\leq 256$.
   1.353 +
   1.354 +The parameter \verb|a_size| specifies the size of arc data blocks, in
   1.355 +bytes, $0\leq a\_size\leq 256$.
   1.356 +
   1.357 +\subsubsection*{Returns}
   1.358 +
   1.359 +The routine returns a pointer to the graph created.
   1.360 +
   1.361 +\subsection{glp\_set\_graph\_name---assign (change) graph name}
   1.362 +
   1.363 +\subsubsection*{Synopsis}
   1.364 +
   1.365 +\begin{verbatim}
   1.366 +void glp_set_graph_name(glp_graph *G, const char *name);
   1.367 +\end{verbatim}
   1.368 +
   1.369 +\subsubsection*{Description}
   1.370 +
   1.371 +The routine \verb|glp_set_graph_name| assigns a symbolic name specified
   1.372 +by the character string \verb|name| (1 to 255 chars) to the graph.
   1.373 +
   1.374 +If the parameter \verb|name| is \verb|NULL| or an empty string, the
   1.375 +routine erases the existing symbolic name of the graph.
   1.376 +
   1.377 +\newpage
   1.378 +
   1.379 +\subsection{glp\_add\_vertices---add new vertices to graph}
   1.380 +
   1.381 +\subsubsection*{Synopsis}
   1.382 +
   1.383 +\begin{verbatim}
   1.384 +int glp_add_vertices(glp_graph *G, int nadd);
   1.385 +\end{verbatim}
   1.386 +
   1.387 +\subsubsection*{Description}
   1.388 +
   1.389 +The routine \verb|glp_add_vertices| adds \verb|nadd| vertices to the
   1.390 +specified graph. New vertices are always added to the end of the vertex
   1.391 +list, so ordinal numbers of existing vertices remain unchanged. Note
   1.392 +that this operation may change the field \verb|v| in the struct
   1.393 +\verb|glp_graph| (pointer to the vertex array) due to reallocation.
   1.394 +
   1.395 +Being added each new vertex is isolated, i.e. has no incident arcs.
   1.396 +
   1.397 +If the size of vertex data blocks specified on creating the graph is
   1.398 +non-zero, the routine also allocates a memory block of that size for
   1.399 +each new vertex added, fills it by binary zeros, and stores a pointer to
   1.400 +it in the field \verb|data| of the struct \verb|glp_vertex|. Otherwise,
   1.401 +if the block size is zero, the field \verb|data| is set to \verb|NULL|.
   1.402 +
   1.403 +\subsubsection*{Returns}
   1.404 +
   1.405 +The routine \verb|glp_add_vertices| returns the ordinal number of the
   1.406 +first new vertex added to the graph.
   1.407 +
   1.408 +\subsection{glp\_set\_vertex\_name---assign (change) vertex name}
   1.409 +
   1.410 +\subsubsection*{Synopsis}
   1.411 +
   1.412 +\begin{verbatim}
   1.413 +void glp_set_vertex_name(glp_graph *G, int i, const char *name);
   1.414 +\end{verbatim}
   1.415 +
   1.416 +\subsubsection*{Description}
   1.417 +
   1.418 +The routine \verb|glp_set_vertex_name| assigns a given symbolic name
   1.419 +(1 up to 255 characters) to \verb|i|-th vertex of the specified graph.
   1.420 +
   1.421 +If the parameter \verb|name| is \verb|NULL| or empty string, the
   1.422 +routine erases an existing name of \verb|i|-th vertex.
   1.423 +
   1.424 +\newpage
   1.425 +
   1.426 +\subsection{glp\_add\_arc---add new arc to graph}
   1.427 +
   1.428 +\subsubsection*{Synopsis}
   1.429 +
   1.430 +\begin{verbatim}
   1.431 +glp_arc *glp_add_arc(glp_graph *G, int i, int j);
   1.432 +\end{verbatim}
   1.433 +
   1.434 +\subsubsection*{Description}
   1.435 +
   1.436 +The routine \verb|glp_add_arc| adds one new arc to the specified graph.
   1.437 +
   1.438 +The parameters \verb|i| and \verb|j| specify the ordinal numbers of,
   1.439 +resp., tail and head endpoints (vertices) of the arc. Note that
   1.440 +self-loops and multiple arcs are allowed.
   1.441 +
   1.442 +If the size of arc data blocks specified on creating the graph is
   1.443 +non-zero, the routine also allocates a memory block of that size, fills
   1.444 +it by binary zeros, and stores a pointer to it in the field \verb|data|
   1.445 +of the struct \verb|glp_arc|. Otherwise, if the block size is zero, the
   1.446 +field \verb|data| is set to \verb|NULL|.
   1.447 +
   1.448 +\subsection{glp\_del\_vertices---delete vertices from graph}
   1.449 +
   1.450 +\subsubsection*{Synopsis}
   1.451 +
   1.452 +\begin{verbatim}
   1.453 +void glp_del_vertices(glp_graph *G, int ndel, const int num[]);
   1.454 +\end{verbatim}
   1.455 +
   1.456 +\subsubsection*{Description}
   1.457 +
   1.458 +The routine \verb|glp_del_vertices| deletes vertices along with all
   1.459 +incident arcs from the specified graph. Ordinal numbers of vertices to
   1.460 +be deleted should be placed in locations \verb|num[1]|, \dots,
   1.461 +\verb|num[ndel]|, \verb|ndel| $>0$.
   1.462 +
   1.463 +Note that deleting vertices involves changing ordinal numbers of other
   1.464 +vertices remaining in the graph. New ordinal numbers of the remaining
   1.465 +vertices are assigned under the assumption that the original order of
   1.466 +vertices is not changed.
   1.467 +
   1.468 +\subsection{glp\_del\_arc---delete arc from graph}
   1.469 +
   1.470 +\subsubsection*{Synopsis}
   1.471 +
   1.472 +\begin{verbatim}
   1.473 +void glp_del_arc(glp_graph *G, glp_arc *a);
   1.474 +\end{verbatim}
   1.475 +
   1.476 +\subsubsection*{Description}
   1.477 +
   1.478 +The routine \verb|glp_del_arc| deletes an arc from the specified graph.
   1.479 +The arc to be deleted must exist.
   1.480 +
   1.481 +\subsection{glp\_erase\_graph---erase graph content}
   1.482 +
   1.483 +\subsubsection*{Synopsis}
   1.484 +
   1.485 +\begin{verbatim}
   1.486 +void glp_erase_graph(glp_graph *G, int v_size, int a_size);
   1.487 +\end{verbatim}
   1.488 +
   1.489 +\subsubsection*{Description}
   1.490 +
   1.491 +The routine \verb|glp_erase_graph| erases the content of the specified
   1.492 +graph. The effect of this operation is the same as if the graph would be
   1.493 +deleted with the routine \verb|glp_delete_graph| and then created anew
   1.494 +with the routine \verb|glp_create_graph|, with exception that the handle
   1.495 +(pointer) to the graph remains valid.
   1.496 +
   1.497 +The parameters \verb|v_size| and \verb|a_size| have the same meaning as
   1.498 +for the routine \verb|glp_create_graph|.
   1.499 +
   1.500 +\subsection{glp\_delete\_graph---delete graph}
   1.501 +
   1.502 +\subsubsection*{Synopsis}
   1.503 +
   1.504 +\begin{verbatim}
   1.505 +void glp_delete_graph(glp_graph *G);
   1.506 +\end{verbatim}
   1.507 +
   1.508 +\subsubsection*{Description}
   1.509 +
   1.510 +The routine \verb|glp_delete_graph| deletes the specified graph and
   1.511 +frees all the memory allocated to this program object.
   1.512 +
   1.513 +\newpage
   1.514 +
   1.515 +\section{Graph searching routines}
   1.516 +
   1.517 +\subsection{glp\_create\_v\_index---create vertex name index}
   1.518 +
   1.519 +\subsubsection*{Synopsis}
   1.520 +
   1.521 +\begin{verbatim}
   1.522 +void glp_create_v_index(glp_graph *G);
   1.523 +\end{verbatim}
   1.524 +
   1.525 +\subsubsection*{Description}
   1.526 +
   1.527 +The routine \verb|glp_create_v_index| creates the name index for the
   1.528 +specified graph. The name index is an auxiliary data structure, which
   1.529 +is intended to quickly (i.e. for logarithmic time) find vertices by
   1.530 +their names.
   1.531 +
   1.532 +This routine can be called at any time. If the name index already
   1.533 +exists, the routine does nothing.
   1.534 +
   1.535 +\subsection{glp\_find\_vertex---find vertex by its name}
   1.536 +
   1.537 +\subsubsection*{Synopsis}
   1.538 +
   1.539 +\begin{verbatim}
   1.540 +int glp_find_vertex(glp_graph *G, const char *name);
   1.541 +\end{verbatim}
   1.542 +
   1.543 +\subsubsection*{Returns}
   1.544 +
   1.545 +The routine \verb|glp_find_vertex| returns the ordinal number of
   1.546 +a vertex, which is assigned (by the routine \verb|glp_set_vertex_name|)
   1.547 +the specified symbolic \verb|name|. If no such vertex exists, the
   1.548 +routine returns 0.
   1.549 +
   1.550 +\subsection{glp\_delete\_v\_index---delete vertex name index}
   1.551 +
   1.552 +\subsubsection*{Synopsis}
   1.553 +
   1.554 +\begin{verbatim}
   1.555 +void glp_delete_v_index(glp_graph *G);
   1.556 +\end{verbatim}
   1.557 +
   1.558 +\subsubsection*{Description}
   1.559 +
   1.560 +The routine \verb|glp_delete_v_index| deletes the name index previously
   1.561 +created by the routine \verb|glp_create_v_index| and frees the memory
   1.562 +allocated to this auxiliary data structure.
   1.563 +
   1.564 +This routine can be called at any time. If the name index does not
   1.565 +exist, the routine does nothing.
   1.566 +
   1.567 +\newpage
   1.568 +
   1.569 +\section{Graph reading/writing routines}
   1.570 +
   1.571 +\subsection{glp\_read\_graph---read graph from plain text file}
   1.572 +
   1.573 +\subsubsection*{Synopsis}
   1.574 +
   1.575 +\begin{verbatim}
   1.576 +int glp_read_graph(glp_graph *G, const char *fname);
   1.577 +\end{verbatim}
   1.578 +
   1.579 +\subsubsection*{Description}
   1.580 +
   1.581 +The routine \verb|glp_read_graph| reads a graph from a plain text file,
   1.582 +whose name is specified by the parameter \verb|fname|. Note that before
   1.583 +reading data the current content of the graph object is completely
   1.584 +erased with the routine \verb|glp_erase_graph|.
   1.585 +
   1.586 +For the file format see description of the routine
   1.587 +\verb|glp_write_graph|.
   1.588 +
   1.589 +\subsubsection*{Returns}
   1.590 +
   1.591 +If the operation was successful, the routine returns zero. Otherwise
   1.592 +it prints an error message and returns non-zero.
   1.593 +
   1.594 +\subsection{glp\_write\_graph---write graph to plain text file}
   1.595 +
   1.596 +\subsubsection*{Synopsis}
   1.597 +
   1.598 +\begin{verbatim}
   1.599 +int glp_write_graph(glp_graph *G, const char *fname);
   1.600 +\end{verbatim}
   1.601 +
   1.602 +\subsubsection*{Description}
   1.603 +
   1.604 +The routine \verb|glp_write_graph| writes the graph to a plain text
   1.605 +file, whose name is specified by the parameter \verb|fname|.
   1.606 +
   1.607 +\subsubsection*{Returns}
   1.608 +
   1.609 +If the operation was successful, the routine returns zero. Otherwise
   1.610 +it prints an error message and returns non-zero.
   1.611 +
   1.612 +\subsubsection*{File format}
   1.613 +
   1.614 +The file created by the routine \verb|glp_write_graph| is a plain text
   1.615 +file, which contains the following information:
   1.616 +
   1.617 +\begin{verbatim}
   1.618 +   nv na
   1.619 +   i[1] j[1]
   1.620 +   i[2] j[2]
   1.621 +   . . .
   1.622 +   i[na] j[na]
   1.623 +\end{verbatim}
   1.624 +
   1.625 +\noindent
   1.626 +where:
   1.627 +
   1.628 +\noindent
   1.629 +\verb|nv| is the number of vertices (nodes);
   1.630 +
   1.631 +\noindent
   1.632 +\verb|na| is the number of arcs;
   1.633 +
   1.634 +\noindent
   1.635 +\verb|i[k]|, $k=1,\dots,na$, is the index of tail vertex of arc $k$;
   1.636 +
   1.637 +\noindent
   1.638 +\verb|j[k]|, $k=1,\dots,na$, is the index of head vertex of arc $k$.
   1.639 +
   1.640 +\subsection{glp\_read\_ccdata---read graph from text file in DIMACS
   1.641 +clique/coloring format}
   1.642 +
   1.643 +\subsubsection*{Synopsis}
   1.644 +
   1.645 +\begin{verbatim}
   1.646 +int glp_read_ccdata(glp_graph *G, int v_wgt,
   1.647 +      const char *fname);
   1.648 +\end{verbatim}
   1.649 +
   1.650 +\subsubsection*{Description}
   1.651 +
   1.652 +The routine {\it glp\_read\_ccdata} reads a graph from a text file in
   1.653 +DIMACS clique/coloring format. (Though this format is originally
   1.654 +designed to represent data for the minimal vertex coloring and maximal
   1.655 +clique problems, it may be used to represent general undirected and
   1.656 +directed graphs, because the routine allows reading self-loops and
   1.657 +multiple edges/arcs keeping the order of vertices specified for each
   1.658 +edge/arc of the graph.)
   1.659 +
   1.660 +The parameter $G$ specifies the graph object to be read in. Note that
   1.661 +before reading data the current content of the graph object is
   1.662 +completely erased with the routine {\it glp\_erase\_graph}.
   1.663 +
   1.664 +The parameter {\it v\_wgt} specifies an offset of the field of type
   1.665 +{\bf double} in the vertex data block, to which the routine stores the
   1.666 +vertex weight. If {\it v\_wgt} $<0$, the vertex weights are not stored.
   1.667 +
   1.668 +The character string {\it fname} specifies the name of a text file to
   1.669 +be read in. (If the file name ends with the suffix `\verb|.gz|', the
   1.670 +file is assumed to be compressed, in which case the routine decompresses
   1.671 +it ``on the fly''.)
   1.672 +
   1.673 +\subsubsection*{Returns}
   1.674 +
   1.675 +If the operation was successful, the routine returns zero. Otherwise,
   1.676 +it prints an error message and returns non-zero.
   1.677 +
   1.678 +\subsubsection*{DIMACS clique/coloring format\footnote{This material is
   1.679 +based on the paper ``Clique and Coloring Problems Graph Format'', which
   1.680 +is publically available at
   1.681 +{\tt http://dimacs.rutgers.edu/Challenges/}.}}
   1.682 +
   1.683 +The DIMACS input file is a plain ASCII text file. It contains
   1.684 +{\it lines} of several types described below. A line is terminated with
   1.685 +an end-of-line character. Fields in each line are separated by at least
   1.686 +one blank space. Each line begins with a one-character designator to
   1.687 +identify the line type.
   1.688 +
   1.689 +Note that DIMACS requires all numerical quantities to be integers in
   1.690 +the range $[-2^{31},2^{31}-1]$ while GLPK allows the quantities to be
   1.691 +floating-point numbers.
   1.692 +
   1.693 +\paragraph{Comment lines.} Comment lines give human-readable information
   1.694 +about the file and are ignored by programs. Comment lines can appear
   1.695 +anywhere in the file. Each comment line begins with a lower-case
   1.696 +character \verb|c|.
   1.697 +
   1.698 +\begin{verbatim}
   1.699 +   c This is a comment line
   1.700 +\end{verbatim}
   1.701 +
   1.702 +\paragraph{Problem line.} There is one problem line per data file. The
   1.703 +problem line must appear before any node or edge descriptor lines. It
   1.704 +has the following format:
   1.705 +
   1.706 +\begin{verbatim}
   1.707 +   p edge NODES EDGES
   1.708 +\end{verbatim}
   1.709 +
   1.710 +\noindent
   1.711 +The lower-case letter \verb|p| signifies that this is a problem line.
   1.712 +The four-character problem designator \verb|edge| identifies the file
   1.713 +as containing data for the minimal vertex coloring or maximal clique
   1.714 +problem. The \verb|NODES| field contains an integer value specifying
   1.715 +the number of vertices in the graph. The \verb|EDGES| field contains an
   1.716 +integer value specifying the number of edges (arcs) in the graph.
   1.717 +
   1.718 +\paragraph{Vertex descriptors.} These lines give the weight assigned to
   1.719 +a vertex of the graph. There is one vertex descriptor line for each
   1.720 +vertex, with the following format. Vertices without a descriptor take on
   1.721 +a default value of 1.
   1.722 +
   1.723 +\begin{verbatim}
   1.724 +   n ID VALUE
   1.725 +\end{verbatim}
   1.726 +
   1.727 +\noindent
   1.728 +The lower-case character \verb|n| signifies that this is a vertex
   1.729 +descriptor line. The \verb|ID| field gives a vertex identification
   1.730 +number, an integer between 1 and $n$, where $n$ is the number of
   1.731 +vertices in the graph. The \verb|VALUE| field gives a vertex weight,
   1.732 +which can either positive or negative (or zero).
   1.733 +
   1.734 +\paragraph{Edge descriptors.} There is one edge descriptor line for
   1.735 +each edge (arc) of the graph, each with the following format:
   1.736 +
   1.737 +\begin{verbatim}
   1.738 +   e I J
   1.739 +\end{verbatim}
   1.740 +
   1.741 +\noindent
   1.742 +The lower-case character \verb|e| signifies that this is an edge
   1.743 +descriptor line. For an edge (arc) $(i,j)$ the fields \verb|I| and
   1.744 +\verb|J| specify its endpoints.
   1.745 +
   1.746 +\paragraph{Example.} The following example of an undirected graph:
   1.747 +
   1.748 +\bigskip
   1.749 +
   1.750 +\noindent\hfil
   1.751 +\xymatrix %@C=32pt
   1.752 +{&{v_1}\ar@{-}[ldd]\ar@{-}[dd]\ar@{-}[rd]\ar@{-}[rr]&&{v_2}\ar@{-}[ld]
   1.753 +\ar@{-}[dd]\ar@{-}[rdd]&\\
   1.754 +&&{v_7}\ar@{-}[ld]\ar@{-}[rd]&&\\
   1.755 +{v_6}\ar@{-}[r]\ar@{-}[rdd]&{v_{10}}\ar@{-}[rr]\ar@{-}[rd]\ar@{-}[dd]&&
   1.756 +{v_8}\ar@{-}[ld]\ar@{-}[dd]\ar@{-}[r]&{v_3}\ar@{-}[ldd]\\
   1.757 +&&{v_9}\ar@{-}[ld]\ar@{-}[rd]&&\\
   1.758 +&{v_5}\ar@{-}[rr]&&{v_4}&\\
   1.759 +}
   1.760 +
   1.761 +\bigskip
   1.762 +
   1.763 +\noindent
   1.764 +might be coded in DIMACS clique/coloring format as follows:
   1.765 +
   1.766 +\begin{footnotesize}
   1.767 +\begin{verbatim}
   1.768 +c sample.col
   1.769 +c
   1.770 +c This is an example of the vertex coloring problem data
   1.771 +c in DIMACS format.
   1.772 +c
   1.773 +p edge 10 21
   1.774 +c
   1.775 +e 1 2
   1.776 +e 1 6
   1.777 +e 1 7
   1.778 +e 1 10
   1.779 +e 2 3
   1.780 +e 2 7
   1.781 +e 2 8
   1.782 +e 3 4
   1.783 +e 3 8
   1.784 +e 4 5
   1.785 +e 4 8
   1.786 +e 4 9
   1.787 +e 5 6
   1.788 +e 5 9
   1.789 +e 5 10
   1.790 +e 6 10
   1.791 +e 7 8
   1.792 +e 7 10
   1.793 +e 8 9
   1.794 +e 8 10
   1.795 +e 9 10
   1.796 +c
   1.797 +c eof
   1.798 +\end{verbatim}
   1.799 +\end{footnotesize}
   1.800 +
   1.801 +\subsection{glp\_write\_ccdata---write graph to text file in DIMACS
   1.802 +clique/coloring format}
   1.803 +
   1.804 +\subsubsection*{Synopsis}
   1.805 +
   1.806 +\begin{verbatim}
   1.807 +int glp_write_ccdata(glp_graph *G, int v_wgt,
   1.808 +      const char *fname);
   1.809 +\end{verbatim}
   1.810 +
   1.811 +\subsection*{Description}
   1.812 +
   1.813 +The routine {\it glp\_write\_ccdata} writes the graph object specified
   1.814 +by the parameter $G$ to a text file in DIMACS clique/coloring format.
   1.815 +(Though this format is originally designed to represent data for the
   1.816 +minimal vertex coloring and maximal clique problems, it may be used to
   1.817 +represent general undirected and directed graphs, because the routine
   1.818 +allows writing self-loops and multiple edges/arcs keeping the order of
   1.819 +vertices specified for each edge/arc of the graph.)
   1.820 +
   1.821 +The parameter {\it v\_wgt} specifies an offset of the field of type
   1.822 +{\bf double} in the vertex data block, which contains the vertex weight.
   1.823 +If {\it v\_wgt} $<0$, it is assumed that the weight of each vertex is 1.
   1.824 +
   1.825 +The character string {\it fname} specifies a name of the text file to be
   1.826 +written out. (If the file name ends with suffix `\verb|.gz|', the file
   1.827 +is assumed to be compressed, in which case the routine performs
   1.828 +automatic compression on writing it.)
   1.829 +
   1.830 +\subsubsection*{Returns}
   1.831 +
   1.832 +If the operation was successful, the routine returns zero. Otherwise,
   1.833 +it prints an error message and returns non-zero.
   1.834 +
   1.835 +\newpage
   1.836 +
   1.837 +\section{Graph analysis routines}
   1.838 +
   1.839 +\subsection{glp\_weak\_comp---find all weakly connected components of
   1.840 +graph}
   1.841 +
   1.842 +\subsubsection*{Synopsis}
   1.843 +
   1.844 +\begin{verbatim}
   1.845 +int glp_weak_comp(glp_graph *G, int v_num);
   1.846 +\end{verbatim}
   1.847 +
   1.848 +\subsubsection*{Description}
   1.849 +
   1.850 +The routine \verb|glp_weak_comp| finds all weakly connected components
   1.851 +of the specified graph.
   1.852 +
   1.853 +The parameter \verb|v_num| specifies an offset of the field of type
   1.854 +\verb|int| in the vertex data block, to which the routine stores the
   1.855 +number of a weakly connected component containing that vertex. If
   1.856 +\verb|v_num| $<0$, no component numbers are stored.
   1.857 +
   1.858 +The components are numbered in arbitrary order from 1 to \verb|nc|,
   1.859 +where \verb|nc| is the total number of components found,
   1.860 +$0\leq$ \verb|nc| $\leq|V|$.
   1.861 +
   1.862 +\subsubsection*{Returns}
   1.863 +
   1.864 +The routine returns \verb|nc|, the total number of components found.
   1.865 +
   1.866 +\subsection{glp\_strong\_comp---find all strongly connected components
   1.867 +of graph}
   1.868 +
   1.869 +\subsubsection*{Synopsis}
   1.870 +
   1.871 +\begin{verbatim}
   1.872 +int glp_strong_comp(glp_graph *G, int v_num);
   1.873 +\end{verbatim}
   1.874 +
   1.875 +\subsubsection*{Description}
   1.876 +
   1.877 +The routine \verb|glp_strong_comp| finds all strongly connected
   1.878 +components of the specified graph.
   1.879 +
   1.880 +The parameter \verb|v_num| specifies an offset of the field of type
   1.881 +\verb|int| in the vertex data block, to which the routine stores the
   1.882 +number of a strongly connected component containing that vertex. If
   1.883 +\verb|v_num| $<0$, no component numbers are stored.
   1.884 +
   1.885 +The components are numbered in arbitrary order from 1 to \verb|nc|,
   1.886 +where \verb|nc| is the total number of components found,
   1.887 +$0\leq$ \verb|nc| $\leq|V|$. However, the component numbering has the
   1.888 +property that for every arc $(i\rightarrow j)$ in the graph the
   1.889 +condition $num(i)\geq num(j)$ holds.
   1.890 +
   1.891 +\subsubsection*{Returns}
   1.892 +
   1.893 +The routine returns \verb|nc|, the total number of components found.
   1.894 +
   1.895 +\subsubsection*{References}
   1.896 +
   1.897 +I.~S.~Duff, J.~K.~Reid, Algorithm 529: Permutations to block triangular
   1.898 +form, ACM Trans. on Math. Softw. 4 (1978), 189-92.
   1.899 +
   1.900 +\subsubsection*{Example}
   1.901 +
   1.902 +The following program reads a graph from a plain text file
   1.903 +`\verb|graph.txt|' and finds all its strongly connected components.
   1.904 +
   1.905 +\begin{footnotesize}
   1.906 +\begin{verbatim}
   1.907 +#include <stddef.h>
   1.908 +#include <stdio.h>
   1.909 +#include <stdlib.h>
   1.910 +#include <glpk.h>
   1.911 +
   1.912 +typedef struct { int num; } v_data;
   1.913 +
   1.914 +#define vertex(v) ((v_data *)((v)->data))
   1.915 +
   1.916 +int main(void)
   1.917 +{     glp_graph *G;
   1.918 +      int i, nc;
   1.919 +      G = glp_create_graph(sizeof(v_data), 0);
   1.920 +      glp_read_graph(G, "graph.txt");
   1.921 +      nc = glp_strong_comp(G, offsetof(v_data, num));
   1.922 +      printf("nc = %d\n", nc);
   1.923 +      for (i = 1; i <= G->nv; i++)
   1.924 +         printf("num[%d] = %d\n", i, vertex(G->v[i])->num);
   1.925 +      glp_delete_graph(G);
   1.926 +      return 0;
   1.927 +}
   1.928 +\end{verbatim}
   1.929 +\end{footnotesize}
   1.930 +
   1.931 +\noindent
   1.932 +If the file `\verb|graph.txt|' contains the graph shown below:
   1.933 +
   1.934 +\bigskip
   1.935 +
   1.936 +\noindent\hfil
   1.937 +\xymatrix
   1.938 +{1\ar[r]&2\ar[r]&3\ar[r]\ar[dd]&4\ar[dd]\\
   1.939 +5\ar[u]&6\ar[l]\\
   1.940 +7\ar[u]&&8\ar[lu]\ar[ll]\ar[r]&9\ar[r]&10\ar[r]\ar[d]&11\ar[d]\\
   1.941 +12\ar[u]\ar[rru]\ar@/_/[rr]&&13\ar[ll]\ar[u]\ar[rr]&&14\ar[lu]&15\ar[l]
   1.942 +\\
   1.943 +}
   1.944 +
   1.945 +\bigskip\bigskip
   1.946 +
   1.947 +\noindent
   1.948 +the program output may look like follows:
   1.949 +
   1.950 +\begin{footnotesize}
   1.951 +\begin{verbatim}
   1.952 +Reading graph from `graph.txt'...
   1.953 +Graph has 15 vertices and 30 arcs
   1.954 +31 lines were read
   1.955 +nc = 4
   1.956 +num[1] = 3
   1.957 +num[2] = 3
   1.958 +num[3] = 3
   1.959 +num[4] = 2
   1.960 +num[5] = 3
   1.961 +num[6] = 3
   1.962 +num[7] = 3
   1.963 +num[8] = 3
   1.964 +num[9] = 1
   1.965 +num[10] = 1
   1.966 +num[11] = 1
   1.967 +num[12] = 4
   1.968 +num[13] = 4
   1.969 +num[14] = 1
   1.970 +num[15] = 1
   1.971 +\end{verbatim}
   1.972 +\end{footnotesize}
   1.973 +
   1.974 +\subsection{glp\_top\_sort---topological sorting of acyclic digraph}
   1.975 +
   1.976 +\subsubsection*{Synopsis}
   1.977 +
   1.978 +\begin{verbatim}
   1.979 +int glp_top_sort(glp_graph *G, int v_num);
   1.980 +\end{verbatim}
   1.981 +
   1.982 +\subsubsection*{Description}
   1.983 +
   1.984 +The routine \verb|glp_top_sort| performs topological sorting of
   1.985 +vertices of the specified acyclic digraph.
   1.986 +
   1.987 +The parameter \verb|v_num| specifies an offset of the field of type
   1.988 +\verb|int| in the vertex data block, to which the routine stores the
   1.989 +vertex number assigned. If \verb|v_num| $<0$, vertex numbers are not
   1.990 +stored.
   1.991 +
   1.992 +The vertices are numbered from 1 to $n$, where $n$ is the total number
   1.993 +of vertices in the graph. The vertex numbering has the property that
   1.994 +for every arc $(i\rightarrow j)$ in the graph the condition
   1.995 +$num(i)<num(j)$ holds. Special case $num(i)=0$ means that vertex $i$ is
   1.996 +not assigned a number, because the graph is {\it not} acyclic.
   1.997 +
   1.998 +\subsubsection*{Returns}
   1.999 +
  1.1000 +If the graph is acyclic and therefore all the vertices have been
  1.1001 +assigned numbers, the routine \verb|glp_top_sort| returns zero.
  1.1002 +Otherwise, if the graph is not acyclic, the routine returns the number
  1.1003 +of vertices which have not been numbered, i.e. for which $num(i)=0$.
  1.1004 +
  1.1005 +\subsubsection*{Example}
  1.1006 +
  1.1007 +The following program reads a digraph from a plain text file
  1.1008 +`\verb|graph.txt|' and performs topological sorting of its vertices.
  1.1009 +
  1.1010 +\begin{footnotesize}
  1.1011 +\begin{verbatim}
  1.1012 +#include <stddef.h>
  1.1013 +#include <stdio.h>
  1.1014 +#include <stdlib.h>
  1.1015 +#include <glpk.h>
  1.1016 +
  1.1017 +typedef struct { int num; } v_data;
  1.1018 +
  1.1019 +#define vertex(v) ((v_data *)((v)->data))
  1.1020 +
  1.1021 +int main(void)
  1.1022 +{     glp_graph *G;
  1.1023 +      int i, cnt;
  1.1024 +      G = glp_create_graph(sizeof(v_data), 0);
  1.1025 +      glp_read_graph(G, "graph.txt");
  1.1026 +      cnt = glp_top_sort(G, offsetof(v_data, num));
  1.1027 +      printf("cnt = %d\n", cnt);
  1.1028 +      for (i = 1; i <= G->nv; i++)
  1.1029 +         printf("num[%d] = %d\n", i, vertex(G->v[i])->num);
  1.1030 +      glp_delete_graph(G);
  1.1031 +      return 0;
  1.1032 +}
  1.1033 +\end{verbatim}
  1.1034 +\end{footnotesize}
  1.1035 +
  1.1036 +\noindent
  1.1037 +If the file `\verb|graph.txt|' contains the graph shown below:
  1.1038 +
  1.1039 +\bigskip
  1.1040 +
  1.1041 +\noindent\hfil
  1.1042 +\xymatrix @=20pt
  1.1043 +{
  1.1044 +1\ar[rrr]&&&2\ar[r]\ar[rddd]&3\ar[rd]&&&&\\
  1.1045 +&&&4\ar[ru]&&5\ar[r]&6\ar[rd]\ar[dd]&&\\
  1.1046 +7\ar[r]&8\ar[r]&9\ar[ruu]\ar[ru]\ar[r]\ar[rd]&10\ar[rr]\ar[rru]&&
  1.1047 +11\ar[ru]&&12\ar[r]&13\\
  1.1048 +&&&14\ar[r]&15\ar[rrru]\ar[rr]&&16\ar[rru]\ar[rr]&&17\\
  1.1049 +}
  1.1050 +
  1.1051 +\bigskip\bigskip
  1.1052 +
  1.1053 +\noindent
  1.1054 +the program output may look like follows:
  1.1055 +
  1.1056 +\begin{footnotesize}
  1.1057 +\begin{verbatim}
  1.1058 +Reading graph from `graph.txt'...
  1.1059 +Graph has 17 vertices and 23 arcs
  1.1060 +24 lines were read
  1.1061 +cnt = 0
  1.1062 +num[1] = 8
  1.1063 +num[2] = 9
  1.1064 +num[3] = 10
  1.1065 +num[4] = 4
  1.1066 +num[5] = 11
  1.1067 +num[6] = 12
  1.1068 +num[7] = 1
  1.1069 +num[8] = 2
  1.1070 +num[9] = 3
  1.1071 +num[10] = 5
  1.1072 +num[11] = 6
  1.1073 +num[12] = 14
  1.1074 +num[13] = 16
  1.1075 +num[14] = 7
  1.1076 +num[15] = 13
  1.1077 +num[16] = 15
  1.1078 +num[17] = 17
  1.1079 +\end{verbatim}
  1.1080 +\end{footnotesize}
  1.1081 +
  1.1082 +\noindent
  1.1083 +The output corresponds to the following vertex numbering:
  1.1084 +
  1.1085 +\bigskip
  1.1086 +
  1.1087 +\noindent\hfil
  1.1088 +\xymatrix @=20pt
  1.1089 +{
  1.1090 +8\ar[rrr]&&&9\ar[r]\ar[rddd]&10\ar[rd]&&&&\\
  1.1091 +&&&4\ar[ru]&&11\ar[r]&12\ar[rd]\ar[dd]&&\\
  1.1092 +1\ar[r]&2\ar[r]&3\ar[ruu]\ar[ru]\ar[r]\ar[rd]&5\ar[rr]\ar[rru]&&
  1.1093 +6\ar[ru]&&14\ar[r]&16\\
  1.1094 +&&&7\ar[r]&13\ar[rrru]\ar[rr]&&15\ar[rru]\ar[rr]&&17\\
  1.1095 +}
  1.1096 +
  1.1097 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1.1098 +
  1.1099 +\chapter{Network optimization API routines}
  1.1100 +
  1.1101 +\section{Minimum cost flow problem}
  1.1102 +
  1.1103 +\subsection{Background}
  1.1104 +
  1.1105 +The {\it minimum cost flow problem} (MCFP) is stated as follows. Let
  1.1106 +there be given a directed graph (flow network) $G=(V,A)$, where $V$ is
  1.1107 +a set of vertices (nodes), and $A\subseteq V\times V$ is a set of arcs.
  1.1108 +Let for each node $i\in V$ there be given a quantity $b_i$ having the
  1.1109 +following meaning:
  1.1110 +
  1.1111 +if $b_i>0$, then $|b_i|$ is a {\it supply} at node $i$, which shows
  1.1112 +how many flow units are {\it generated} at node $i$ (or, equivalently,
  1.1113 +entering the network through node $i$ from the outside);
  1.1114 +
  1.1115 +if $b_i<0$, then $|b_i|$ is a {\it demand} at node $i$, which shows how
  1.1116 +many flow units are {\it lost} at node $i$ (or, equivalently, leaving
  1.1117 +the network through node $i$ to the outside);
  1.1118 +
  1.1119 +if $b_i=0$, then $i$ is a {\it transshipment} node, at which the flow
  1.1120 +is conserved, i.e. neither generated nor lost.
  1.1121 +
  1.1122 +Let also for each arc $a=(i,j)\in A$ there be given the following three
  1.1123 +quantities:
  1.1124 +
  1.1125 +$l_{ij}$, a (non-negative) lower bound to the flow through arc $(i,j)$;
  1.1126 +
  1.1127 +$u_{ij}$, an upper bound to the flow through arc $(i,j)$, which is the
  1.1128 +{\it arc capacity};
  1.1129 +
  1.1130 +$c_{ij}$, a per-unit cost of the flow through arc $(i,j)$.
  1.1131 +
  1.1132 +The problem is to find flows $x_{ij}$ through every arc of the network,
  1.1133 +which satisfy the specified bounds and the conservation constraints at
  1.1134 +all nodes, and minimize the total flow cost. Here the conservation
  1.1135 +constraint at a node means that the total flow entering this node
  1.1136 +through its incoming arcs plus the supply at this node must be equal to
  1.1137 +the total flow leaving this node through its outgoing arcs plus the
  1.1138 +demand at this node.
  1.1139 +
  1.1140 +An example of the minimum cost flow problem is shown on Fig.~1.
  1.1141 +
  1.1142 +\bigskip
  1.1143 +
  1.1144 +\noindent\hfil
  1.1145 +\xymatrix @C=48pt
  1.1146 +{_{20}\ar@{~>}[d]&
  1.1147 +v_2\ar[r]|{_{0,10,\$2}}\ar[dd]|{_{0,9,\$3}}&
  1.1148 +v_3\ar[dd]|{_{2,12,\$1}}\ar[r]|{_{0,18,\$0}}&
  1.1149 +v_8\ar[rd]|{_{0,20,\$9}}&\\
  1.1150 +v_1\ar[ru]|{_{0,14,\$0}}\ar[rd]|{_{0,23,\$0}}&&&
  1.1151 +v_6\ar[d]|{_{0,7,\$0}}\ar[u]|{_{4,8,\$0}}&
  1.1152 +v_9\ar@{~>}[d]\\
  1.1153 +&v_4\ar[r]|{_{0,26,\$0}}&
  1.1154 +v_5\ar[luu]|{_{0,11,\$1}}\ar[ru]|{_{0,25,\$5}}\ar[r]|{_{0,4,\$7}}&
  1.1155 +v_7\ar[ru]|{_{0,15,\$3}}&_{20}\\
  1.1156 +}
  1.1157 +
  1.1158 +\medskip
  1.1159 +
  1.1160 +\noindent\hfil
  1.1161 +\begin{tabular}{ccc}
  1.1162 +\xymatrix @C=48pt{v_i\ar[r]|{\ l,u,\$c\ }&v_j\\}&
  1.1163 +\xymatrix{\hbox{\footnotesize supply}\ar@{~>}[r]&v_i\\}&
  1.1164 +\xymatrix{v_i\ar@{~>}[r]&\hbox{\footnotesize demand}\\}\\
  1.1165 +\end{tabular}
  1.1166 +
  1.1167 +\bigskip
  1.1168 +
  1.1169 +\noindent\hfil
  1.1170 +Fig.~1. An example of the minimum cost flow problem.
  1.1171 +
  1.1172 +\bigskip
  1.1173 +
  1.1174 +The minimum cost flow problem can be naturally formulated as the
  1.1175 +following LP problem:
  1.1176 +
  1.1177 +\medskip
  1.1178 +
  1.1179 +\noindent
  1.1180 +\hspace{.5in}minimize
  1.1181 +$$z=\sum_{(i,j)\in A}c_{ij}x_{ij}\eqno(1)$$
  1.1182 +\hspace{.5in}subject to
  1.1183 +$$\sum_{(i,j)\in A}x_{ij}-\sum_{(j,i)\in A}x_{ji}=b_i\ \ \ \hbox
  1.1184 +{for all}\ i\in V\eqno(2)$$
  1.1185 +$$l_{ij}\leq x_{ij}\leq u_{ij}\ \ \ \hbox{for all}\ (i,j)\in A
  1.1186 +\eqno(3)$$
  1.1187 +
  1.1188 +\newpage
  1.1189 +
  1.1190 +\subsection{glp\_read\_mincost---read minimum cost flow problem\\data
  1.1191 +in DIMACS format}
  1.1192 +
  1.1193 +\subsubsection*{Synopsis}
  1.1194 +
  1.1195 +\begin{verbatim}
  1.1196 +int glp_read_mincost(glp_graph *G, int v_rhs, int a_low,
  1.1197 +      int a_cap, int a_cost, const char *fname);
  1.1198 +\end{verbatim}
  1.1199 +
  1.1200 +\subsubsection*{Description}
  1.1201 +
  1.1202 +The routine \verb|glp_read_mincost| reads the minimum cost flow problem
  1.1203 +data from a text file in DIMACS format.
  1.1204 +
  1.1205 +The parameter \verb|G| specifies the graph object, to which the problem
  1.1206 +data have to be stored. Note that before reading data the current
  1.1207 +content of the graph object is completely erased with the routine
  1.1208 +\verb|glp_erase_graph|.
  1.1209 +
  1.1210 +The parameter \verb|v_rhs| specifies an offset of the field of type
  1.1211 +\verb|double| in the vertex data block, to which the routine stores
  1.1212 +$b_i$, the supply/demand value. If \verb|v_rhs| $<0$, the value is not
  1.1213 +stored.
  1.1214 +
  1.1215 +The parameter \verb|a_low| specifies an offset of the field of type
  1.1216 +\verb|double| in the arc data block, to which the routine stores
  1.1217 +$l_{ij}$, the lower bound to the arc flow. If \verb|a_low| $<0$, the
  1.1218 +lower bound is not stored.
  1.1219 +
  1.1220 +The parameter \verb|a_cap| specifies an offset of the field of type
  1.1221 +\verb|double| in the arc data block, to which the routine stores
  1.1222 +$u_{ij}$, the upper bound to the arc flow (the arc capacity). If
  1.1223 +\verb|a_cap| $<0$, the upper bound is not stored.
  1.1224 +
  1.1225 +The parameter \verb|a_cost| specifies an offset of the field of type
  1.1226 +\verb|double| in the arc data block, to which the routine stores
  1.1227 +$c_{ij}$, the per-unit cost of the arc flow. If \verb|a_cost| $<0$, the
  1.1228 +cost is not stored.
  1.1229 +
  1.1230 +The character string \verb|fname| specifies the name of a text file to
  1.1231 +be read in. (If the file name name ends with the suffix `\verb|.gz|',
  1.1232 +the file is assumed to be compressed, in which case the routine
  1.1233 +decompresses it ``on the fly''.)
  1.1234 +
  1.1235 +\subsubsection*{Returns}
  1.1236 +
  1.1237 +If the operation was successful, the routine returns zero. Otherwise,
  1.1238 +it prints an error message and returns non-zero.
  1.1239 +
  1.1240 +\newpage
  1.1241 +
  1.1242 +\subsubsection*{Example}
  1.1243 +
  1.1244 +\begin{footnotesize}
  1.1245 +\begin{verbatim}
  1.1246 +typedef struct
  1.1247 +{     /* vertex data block */
  1.1248 +      ...
  1.1249 +      double rhs;
  1.1250 +      ...
  1.1251 +} v_data;
  1.1252 +
  1.1253 +typedef struct
  1.1254 +{     /* arc data block */
  1.1255 +      ...
  1.1256 +      double low, cap, cost;
  1.1257 +      ...
  1.1258 +} a_data;
  1.1259 +
  1.1260 +int main(void)
  1.1261 +{     glp_graph *G;
  1.1262 +      int ret;
  1.1263 +      G = glp_create_graph(sizeof(v_data), sizeof(a_data));
  1.1264 +      ret = glp_read_mincost(G, offsetof(v_data, rhs),
  1.1265 +         offsetof(a_data, low), offsetof(a_data, cap),
  1.1266 +         offsetof(a_data, cost), "sample.min");
  1.1267 +      if (ret != 0) goto ...
  1.1268 +      ...
  1.1269 +}
  1.1270 +\end{verbatim}
  1.1271 +\end{footnotesize}
  1.1272 +
  1.1273 +\subsubsection*{DIMACS minimum cost flow problem format\footnote{This
  1.1274 +material is based on the paper ``The First DIMACS International
  1.1275 +Algorithm Implementation Challenge: Problem Definitions and
  1.1276 +Specifications'', which is publically available at
  1.1277 +{\tt http://dimacs.rutgers.edu/Challenges/}.}}
  1.1278 +\label{subsecmincost}
  1.1279 +
  1.1280 +The DIMACS input file is a plain ASCII text file. It contains
  1.1281 +{\it lines} of several types described below. A line is terminated with
  1.1282 +an end-of-line character. Fields in each line are separated by at least
  1.1283 +one blank space. Each line begins with a one-character designator to
  1.1284 +identify the line type.
  1.1285 +
  1.1286 +Note that DIMACS requires all numerical quantities to be integers in
  1.1287 +the range $[-2^{31},\ 2^{31}-1]$ while GLPK allows the quantities to be
  1.1288 +floating-point numbers.
  1.1289 +
  1.1290 +\newpage
  1.1291 +
  1.1292 +\paragraph{Comment lines.} Comment lines give human-readable information
  1.1293 +about the file and are ignored by programs. Comment lines can appear
  1.1294 +anywhere in the file. Each comment line begins with a lower-case
  1.1295 +character \verb|c|.
  1.1296 +
  1.1297 +\begin{verbatim}
  1.1298 +   c This is a comment line
  1.1299 +\end{verbatim}
  1.1300 +
  1.1301 +\paragraph{Problem line.} There is one problem line per data file. The
  1.1302 +problem line must appear before any node or arc descriptor lines. It has
  1.1303 +the following format:
  1.1304 +
  1.1305 +\begin{verbatim}
  1.1306 +   p min NODES ARCS
  1.1307 +\end{verbatim}
  1.1308 +
  1.1309 +\noindent
  1.1310 +The lower-case character \verb|p| signifies that this is a problem line.
  1.1311 +The three-character problem designator \verb|min| identifies the file as
  1.1312 +containing specification information for the minimum cost flow problem.
  1.1313 +The \verb|NODES| field contains an integer value specifying the number
  1.1314 +of nodes in the network. The \verb|ARCS| field contains an integer value
  1.1315 +specifying the number of arcs in the network.
  1.1316 +
  1.1317 +\paragraph{Node descriptors.} All node descriptor lines must appear
  1.1318 +before all arc descriptor lines. The node descriptor lines describe
  1.1319 +supply and demand nodes, but not transshipment nodes. That is, only
  1.1320 +nodes with non-zero node supply/demand values appear. There is one node
  1.1321 +descriptor line for each such node, with the following format:
  1.1322 +
  1.1323 +\begin{verbatim}
  1.1324 +   n ID FLOW
  1.1325 +\end{verbatim}
  1.1326 +
  1.1327 +\noindent
  1.1328 +The lower-case character \verb|n| signifies that this is a node
  1.1329 +descriptor line. The \verb|ID| field gives a node identification number,
  1.1330 +an integer between 1 and \verb|NODES|. The \verb|FLOW| field gives the
  1.1331 +amount of supply (if positive) or demand (if negative) at node
  1.1332 +\verb|ID|.
  1.1333 +
  1.1334 +\paragraph{Arc descriptors.} There is one arc descriptor line for each
  1.1335 +arc in the network. Arc descriptor lines are of the following format:
  1.1336 +
  1.1337 +\begin{verbatim}
  1.1338 +   a SRC DST LOW CAP COST
  1.1339 +\end{verbatim}
  1.1340 +
  1.1341 +\noindent
  1.1342 +The lower-case character \verb|a| signifies that this is an arc
  1.1343 +descriptor line. For a directed arc $(i,j)$ the \verb|SRC| field gives
  1.1344 +the identification number $i$ for the tail endpoint, and the \verb|DST|
  1.1345 +field gives the identification number $j$ for the head endpoint.
  1.1346 +Identification numbers are integers between 1 and \verb|NODES|. The
  1.1347 +\verb|LOW| field specifies the minimum amount of flow that can be sent
  1.1348 +along arc $(i,j)$, and the \verb|CAP| field gives the maximum amount of
  1.1349 +flow that can be sent along arc $(i,j)$ in a feasible flow. The
  1.1350 +\verb|COST| field contains the per-unit cost of flow sent along arc
  1.1351 +$(i,j)$.
  1.1352 +
  1.1353 +\paragraph{Example.} Below here is an example of the data file in
  1.1354 +DIMACS format corresponding to the minimum cost flow problem shown on
  1.1355 +Fig~1.
  1.1356 +
  1.1357 +\begin{footnotesize}
  1.1358 +\begin{verbatim}
  1.1359 +c sample.min
  1.1360 +c
  1.1361 +c This is an example of the minimum cost flow problem data
  1.1362 +c in DIMACS format.
  1.1363 +c
  1.1364 +p min 9 14
  1.1365 +c
  1.1366 +n 1 20
  1.1367 +n 9 -20
  1.1368 +c
  1.1369 +a 1 2 0 14 0
  1.1370 +a 1 4 0 23 0
  1.1371 +a 2 3 0 10 2
  1.1372 +a 2 4 0  9 3
  1.1373 +a 3 5 2 12 1
  1.1374 +a 3 8 0 18 0
  1.1375 +a 4 5 0 26 0
  1.1376 +a 5 2 0 11 1
  1.1377 +a 5 6 0 25 5
  1.1378 +a 5 7 0  4 7
  1.1379 +a 6 7 0  7 0
  1.1380 +a 6 8 4  8 0
  1.1381 +a 7 9 0 15 3
  1.1382 +a 8 9 0 20 9
  1.1383 +c
  1.1384 +c eof
  1.1385 +\end{verbatim}
  1.1386 +\end{footnotesize}
  1.1387 +
  1.1388 +\newpage
  1.1389 +
  1.1390 +\subsection{glp\_write\_mincost---write minimum cost flow problem\\data
  1.1391 +in DIMACS format}
  1.1392 +
  1.1393 +\subsubsection*{Synopsis}
  1.1394 +
  1.1395 +\begin{verbatim}
  1.1396 +int glp_write_mincost(glp_graph *G, int v_rhs, int a_low,
  1.1397 +      int a_cap, int a_cost, const char *fname);
  1.1398 +\end{verbatim}
  1.1399 +
  1.1400 +\subsubsection*{Description}
  1.1401 +
  1.1402 +The routine \verb|glp_write_mincost| writes the minimum cost flow
  1.1403 +problem data to a text file in DIMACS format.
  1.1404 +
  1.1405 +The parameter \verb|G| is the graph (network) program object, which
  1.1406 +specifies the minimum cost flow problem instance.
  1.1407 +
  1.1408 +The parameter \verb|v_rhs| specifies an offset of the field of type
  1.1409 +\verb|double| in the vertex data block, which contains $b_i$, the
  1.1410 +supply/demand value. If \verb|v_rhs| $<0$, it is assumed that $b_i=0$
  1.1411 +for all nodes.
  1.1412 +
  1.1413 +The parameter \verb|a_low| specifies an offset of the field of type
  1.1414 +\verb|double| in the arc data block, which contains $l_{ij}$, the lower
  1.1415 +bound to the arc flow. If \verb|a_low| $<0$, it is assumed that
  1.1416 +$l_{ij}=0$ for all arcs.
  1.1417 +
  1.1418 +The parameter \verb|a_cap| specifies an offset of the field of type
  1.1419 +\verb|double| in the arc data block, which contains $u_{ij}$, the upper
  1.1420 +bound to the arc flow (the arc capacity). If the upper bound is
  1.1421 +specified as \verb|DBL_MAX|, it is assumed that $u_{ij}=\infty$, i.e.
  1.1422 +the arc is uncapacitated. If \verb|a_cap| $<0$, it is assumed that
  1.1423 +$u_{ij}=1$ for all arcs.
  1.1424 +
  1.1425 +The parameter \verb|a_cost| specifies an offset of the field of type
  1.1426 +\verb|double| in the arc data block, which contains $c_{ij}$, the
  1.1427 +per-unit cost of the arc flow. If \verb|a_cost| $<0$, it is assumed that
  1.1428 +$c_{ij}=0$ for all arcs.
  1.1429 +
  1.1430 +The character string \verb|fname| specifies a name of the text file to
  1.1431 +be written out. (If the file name ends with suffix `\verb|.gz|', the
  1.1432 +file is assumed to be compressed, in which case the routine performs
  1.1433 +automatic compression on writing it.)
  1.1434 +
  1.1435 +\subsubsection*{Returns}
  1.1436 +
  1.1437 +If the operation was successful, the routine returns zero. Otherwise,
  1.1438 +it prints an error message and returns non-zero.
  1.1439 +
  1.1440 +\newpage
  1.1441 +
  1.1442 +\subsection{glp\_mincost\_lp---convert minimum cost flow problem\\to LP}
  1.1443 +
  1.1444 +\subsubsection*{Synopsis}
  1.1445 +
  1.1446 +\begin{verbatim}
  1.1447 +void glp_mincost_lp(glp_prob *lp, glp_graph *G, int names,
  1.1448 +      int v_rhs, int a_low, int a_cap, int a_cost);
  1.1449 +\end{verbatim}
  1.1450 +
  1.1451 +\subsubsection*{Description}
  1.1452 +
  1.1453 +The routine \verb|glp_mincost_lp| builds LP problem (1)---(3), which
  1.1454 +corresponds to the specified minimum cost flow problem.
  1.1455 +
  1.1456 +The parameter \verb|lp| is the resultant LP problem object to be built.
  1.1457 +Note that on entry its current content is erased with the routine
  1.1458 +\verb|glp_erase_prob|.
  1.1459 +
  1.1460 +The parameter \verb|G| is the graph (network) program object, which
  1.1461 +specifies the minimum cost flow problem instance.
  1.1462 +
  1.1463 +The parameter \verb|names| is a flag. If it is \verb|GLP_ON|, the
  1.1464 +routine uses symbolic names of the graph object components to assign
  1.1465 +symbolic names to the LP problem object components. If the flag is
  1.1466 +\verb|GLP_OFF|, no symbolic names are assigned.
  1.1467 +
  1.1468 +The parameter \verb|v_rhs| specifies an offset of the field of type
  1.1469 +\verb|double| in the vertex data block, which contains $b_i$, the
  1.1470 +supply/demand value. If \verb|v_rhs| $<0$, it is assumed that $b_i=0$
  1.1471 +for all nodes.
  1.1472 +
  1.1473 +The parameter \verb|a_low| specifies an offset of the field of type
  1.1474 +\verb|double| in the arc data block, which contains $l_{ij}$, the lower
  1.1475 +bound to the arc flow. If \verb|a_low| $<0$, it is assumed that
  1.1476 +$l_{ij}=0$ for all arcs.
  1.1477 +
  1.1478 +The parameter \verb|a_cap| specifies an offset of the field of type
  1.1479 +\verb|double| in the arc data block, which contains $u_{ij}$, the upper
  1.1480 +bound to the arc flow (the arc capacity). If the upper bound is
  1.1481 +specified as \verb|DBL_MAX|, it is assumed that $u_{ij}=\infty$, i.e.
  1.1482 +the arc is uncapacitated. If \verb|a_cap| $<0$, it is assumed that
  1.1483 +$u_{ij}=1$ for all arcs.
  1.1484 +
  1.1485 +The parameter \verb|a_cost| specifies an offset of the field of type
  1.1486 +\verb|double| in the arc data block, which contains $c_{ij}$, the
  1.1487 +per-unit cost of the arc flow. If \verb|a_cost| $<0$, it is assumed that
  1.1488 +$c_{ij}=0$ for all arcs.
  1.1489 +
  1.1490 +\subsubsection*{Example}
  1.1491 +
  1.1492 +The example program below reads the minimum cost problem instance in
  1.1493 +DIMACS format from file `\verb|sample.min|', converts the instance to
  1.1494 +LP, and then writes the resultant LP in CPLEX format to file
  1.1495 +`\verb|mincost.lp|'.
  1.1496 +
  1.1497 +\newpage
  1.1498 +
  1.1499 +\begin{footnotesize}
  1.1500 +\begin{verbatim}
  1.1501 +#include <stddef.h>
  1.1502 +#include <glpk.h>
  1.1503 +
  1.1504 +typedef struct { double rhs; } v_data;
  1.1505 +typedef struct { double low, cap, cost; } a_data;
  1.1506 +
  1.1507 +int main(void)
  1.1508 +{     glp_graph *G;
  1.1509 +      glp_prob *lp;
  1.1510 +      G = glp_create_graph(sizeof(v_data), sizeof(a_data));
  1.1511 +      glp_read_mincost(G, offsetof(v_data, rhs),
  1.1512 +         offsetof(a_data, low), offsetof(a_data, cap),
  1.1513 +         offsetof(a_data, cost), "sample.min");
  1.1514 +      lp = glp_create_prob();
  1.1515 +      glp_mincost_lp(lp, G, GLP_ON, offsetof(v_data, rhs),
  1.1516 +         offsetof(a_data, low), offsetof(a_data, cap),
  1.1517 +         offsetof(a_data, cost));
  1.1518 +      glp_delete_graph(G);
  1.1519 +      glp_write_lp(lp, NULL, "mincost.lp");
  1.1520 +      glp_delete_prob(lp);
  1.1521 +      return 0;
  1.1522 +}
  1.1523 +\end{verbatim}
  1.1524 +\end{footnotesize}
  1.1525 +
  1.1526 +If `\verb|sample.min|' is the example data file from the subsection
  1.1527 +describing the routine \verb|glp_read_mincost|, file `\verb|mincost.lp|'
  1.1528 +may look like follows:
  1.1529 +
  1.1530 +\begin{footnotesize}
  1.1531 +\begin{verbatim}
  1.1532 +Minimize
  1.1533 + obj: + 3 x(2,4) + 2 x(2,3) + x(3,5) + 7 x(5,7) + 5 x(5,6)
  1.1534 + + x(5,2) + 3 x(7,9) + 9 x(8,9)
  1.1535 +
  1.1536 +Subject To
  1.1537 + r_1: + x(1,2) + x(1,4) = 20
  1.1538 + r_2: - x(5,2) + x(2,3) + x(2,4) - x(1,2) = 0
  1.1539 + r_3: + x(3,5) + x(3,8) - x(2,3) = 0
  1.1540 + r_4: + x(4,5) - x(2,4) - x(1,4) = 0
  1.1541 + r_5: + x(5,2) + x(5,6) + x(5,7) - x(4,5) - x(3,5) = 0
  1.1542 + r_6: + x(6,7) + x(6,8) - x(5,6) = 0
  1.1543 + r_7: + x(7,9) - x(6,7) - x(5,7) = 0
  1.1544 + r_8: + x(8,9) - x(6,8) - x(3,8) = 0
  1.1545 + r_9: - x(8,9) - x(7,9) = -20
  1.1546 +
  1.1547 +Bounds
  1.1548 + 0 <= x(1,4) <= 23
  1.1549 + 0 <= x(1,2) <= 14
  1.1550 + 0 <= x(2,4) <= 9
  1.1551 + 0 <= x(2,3) <= 10
  1.1552 + 0 <= x(3,8) <= 18
  1.1553 + 2 <= x(3,5) <= 12
  1.1554 + 0 <= x(4,5) <= 26
  1.1555 + 0 <= x(5,7) <= 4
  1.1556 + 0 <= x(5,6) <= 25
  1.1557 + 0 <= x(5,2) <= 11
  1.1558 + 4 <= x(6,8) <= 8
  1.1559 + 0 <= x(6,7) <= 7
  1.1560 + 0 <= x(7,9) <= 15
  1.1561 + 0 <= x(8,9) <= 20
  1.1562 +
  1.1563 +End
  1.1564 +\end{verbatim}
  1.1565 +\end{footnotesize}
  1.1566 +
  1.1567 +\subsection{glp\_mincost\_okalg---solve minimum cost flow problem with
  1.1568 +out-of-kilter algorithm}
  1.1569 +
  1.1570 +\subsubsection*{Synopsis}
  1.1571 +
  1.1572 +\begin{verbatim}
  1.1573 +int glp_mincost_okalg(glp_graph *G, int v_rhs, int a_low,
  1.1574 +      int a_cap, int a_cost, double *sol, int a_x, int v_pi);
  1.1575 +\end{verbatim}
  1.1576 +
  1.1577 +\subsubsection*{Description}
  1.1578 +
  1.1579 +The routine \verb|glp_mincost_okalg| finds optimal solution to the
  1.1580 +minimum cost flow problem with the out-of-kilter
  1.1581 +algorithm.\footnote{GLPK implementation of the out-of-kilter algorithm
  1.1582 +is based on the following book: L.~R.~Ford,~Jr., and D.~R.~Fulkerson,
  1.1583 +``Flows in Networks,'' The RAND Corp., Report R-375-PR (August 1962),
  1.1584 +Chap. III ``Minimal Cost Flow Problems,'' pp.~113-26.} Note that this
  1.1585 +routine requires all the problem data to be integer-valued.
  1.1586 +
  1.1587 +The parameter \verb|G| is a graph (network) program object which
  1.1588 +specifies the minimum cost flow problem instance to be solved.
  1.1589 +
  1.1590 +The parameter \verb|v_rhs| specifies an offset of the field of type
  1.1591 +\verb|double| in the vertex data block, which contains $b_i$, the
  1.1592 +supply/demand value. This value must be integer in the range
  1.1593 +[$-$\verb|INT_MAX|, $+$\verb|INT_MAX|]. If \verb|v_rhs| $<0$, it is
  1.1594 +assumed that $b_i=0$ for all nodes.
  1.1595 +
  1.1596 +The parameter \verb|a_low| specifies an offset of the field of type
  1.1597 +\verb|double| in the arc data block, which contains $l_{ij}$, the lower
  1.1598 +bound to the arc flow. This bound must be integer in the range
  1.1599 +[$0$, \verb|INT_MAX|]. If \verb|a_low| $<0$, it is assumed that
  1.1600 +$l_{ij}=0$ for all arcs.
  1.1601 +
  1.1602 +The parameter \verb|a_cap| specifies an offset of the field of type
  1.1603 +\verb|double| in the arc data block, which contains $u_{ij}$, the upper
  1.1604 +bound to the arc flow (the arc capacity). This bound must be integer in
  1.1605 +the range [$l_{ij}$, \verb|INT_MAX|]. If \verb|a_cap| $<0$, it is
  1.1606 +assumed that $u_{ij}=1$ for all arcs.
  1.1607 +
  1.1608 +The parameter \verb|a_cost| specifies an offset of the field of type
  1.1609 +\verb|double| in the arc data block, which contains $c_{ij}$, the
  1.1610 +per-unit cost of the arc flow. This value must be integer in the range
  1.1611 +[$-$\verb|INT_MAX|, $+$\verb|INT_MAX|]. If \verb|a_cost| $<0$, it is
  1.1612 +assumed that $c_{ij}=0$ for all arcs.
  1.1613 +
  1.1614 +The parameter \verb|sol| specifies a location, to which the routine
  1.1615 +stores the objective value (that is, the total cost) found. If
  1.1616 +\verb|sol| is NULL, the objective value is not stored.
  1.1617 +
  1.1618 +The parameter \verb|a_x| specifies an offset of the field of type
  1.1619 +\verb|double| in the arc data block, to which the routine stores
  1.1620 +$x_{ij}$, the arc flow found. If \verb|a_x| $<0$, the arc flow value is
  1.1621 +not stored.
  1.1622 +
  1.1623 +The parameter \verb|v_pi| specifies an offset of the field of type
  1.1624 +\verb|double| in the vertex data block, to which the routine stores
  1.1625 +$\pi_i$, the node potential, which is the Lagrange multiplier for the
  1.1626 +corresponding flow conservation equality constraint (see (2) in
  1.1627 +Subsection ``Background''). If necessary, the application program may
  1.1628 +use the node potentials to compute $\lambda_{ij}$, reduced costs of the
  1.1629 +arc flows $x_{ij}$, which are the Lagrange multipliers for the arc flow
  1.1630 +bound constraints (see (3) ibid.), using the following formula:
  1.1631 +$$\lambda_{ij}=c_{ij}-(\pi_i-\pi_j),$$
  1.1632 +where $c_{ij}$ is the per-unit cost for arc $(i,j)$.
  1.1633 +
  1.1634 +Note that all solution components (the objective value, arc flows, and
  1.1635 +node potentials) computed by the routine are always integer-valued.
  1.1636 +
  1.1637 +\subsubsection*{Returns}
  1.1638 +
  1.1639 +\def\arraystretch{1}
  1.1640 +
  1.1641 +\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
  1.1642 +0 & Optimal solution found.\\
  1.1643 +\verb|GLP_ENOPFS| & No (primal) feasible solution exists.\\
  1.1644 +\verb|GLP_EDATA| & Unable to start the search, because some problem
  1.1645 +data are either not integer-valued or out of range. This code is also
  1.1646 +returned if the total supply, which is the sum of $b_i$ over all source
  1.1647 +nodes (nodes with $b_i>0$), exceeds \verb|INT_MAX|.\\
  1.1648 +\end{tabular}
  1.1649 +
  1.1650 +\noindent
  1.1651 +\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
  1.1652 +\verb|GLP_ERANGE| & The search was prematurely terminated because of
  1.1653 +integer overflow.\\
  1.1654 +\verb|GLP_EFAIL| & An error has been detected in the program logic.
  1.1655 +(If this code is returned for your problem instance, please report to
  1.1656 +\verb|<bug-glpk@gnu.org>|.)\\
  1.1657 +\end{tabular}
  1.1658 +
  1.1659 +\subsubsection*{Comments}
  1.1660 +
  1.1661 +By design the out-of-kilter algorithm is applicable only to networks,
  1.1662 +where $b_i=0$ for {\it all} nodes, i.e. actually this algorithm finds a
  1.1663 +minimal cost {\it circulation}. Due to this requirement the routine
  1.1664 +\verb|glp_mincost_okalg| converts the original network to a network
  1.1665 +suitable for the out-of-kilter algorithm in the following
  1.1666 +way:\footnote{The conversion is performed internally and does not change
  1.1667 +the original network program object passed to the routine.}
  1.1668 +
  1.1669 +1) it adds two auxiliary nodes $s$ and $t$;
  1.1670 +
  1.1671 +2) for each original node $i$ with $b_i>0$ the routine adds auxiliary
  1.1672 +supply arc $(s\rightarrow i)$, flow $x_{si}$ through which is costless
  1.1673 +($c_{si}=0$) and fixed to $+b_i$ ($l_{si}=u_{si}=+b_i$);
  1.1674 +
  1.1675 +3) for each original node $i$ with $b_i<0$ the routine adds auxiliary
  1.1676 +demand arc $(i\rightarrow t)$, flow $x_{it}$ through which is costless
  1.1677 +($c_{it}=0$) and fixed to $-b_i$ ($l_{it}=u_{it}=-b_i$);
  1.1678 +
  1.1679 +4) finally, the routine adds auxiliary feedback arc $(t\rightarrow s)$,
  1.1680 +flow $x_{ts}$ through which is also costless ($c_{ts}=0$) and fixed to
  1.1681 +$F$ ($l_{ts}=u_{ts}=F$), where $\displaystyle F=\sum_{b_i>0}b_i$ is the
  1.1682 +total supply.
  1.1683 +
  1.1684 +\subsubsection*{Example}
  1.1685 +
  1.1686 +The example program below reads the minimum cost problem instance in
  1.1687 +DIMACS format from file `\verb|sample.min|', solves it by using the
  1.1688 +routine \verb|glp_mincost_okalg|, and writes the solution found to the
  1.1689 +standard output.
  1.1690 +
  1.1691 +\begin{footnotesize}
  1.1692 +\begin{verbatim}
  1.1693 +#include <stddef.h>
  1.1694 +#include <stdio.h>
  1.1695 +#include <stdlib.h>
  1.1696 +#include <glpk.h>
  1.1697 +
  1.1698 +typedef struct { double rhs, pi; } v_data;
  1.1699 +typedef struct { double low, cap, cost, x; } a_data;
  1.1700 +
  1.1701 +#define node(v) ((v_data *)((v)->data))
  1.1702 +#define arc(a)  ((a_data *)((a)->data))
  1.1703 +
  1.1704 +int main(void)
  1.1705 +{     glp_graph *G;
  1.1706 +      glp_vertex *v, *w;
  1.1707 +      glp_arc *a;
  1.1708 +      int i, ret;
  1.1709 +      double sol;
  1.1710 +      G = glp_create_graph(sizeof(v_data), sizeof(a_data));
  1.1711 +      glp_read_mincost(G, offsetof(v_data, rhs),
  1.1712 +         offsetof(a_data, low), offsetof(a_data, cap),
  1.1713 +         offsetof(a_data, cost), "sample.min");
  1.1714 +      ret = glp_mincost_okalg(G, offsetof(v_data, rhs),
  1.1715 +         offsetof(a_data, low), offsetof(a_data, cap),
  1.1716 +         offsetof(a_data, cost), &sol, offsetof(a_data, x),
  1.1717 +         offsetof(v_data, pi));
  1.1718 +      printf("ret = %d; sol = %5g\n", ret, sol);
  1.1719 +      for (i = 1; i <= G->nv; i++)
  1.1720 +      {  v = G->v[i];
  1.1721 +         printf("node %d:    pi = %5g\n", i, node(v)->pi);
  1.1722 +         for (a = v->out; a != NULL; a = a->t_next)
  1.1723 +         {  w = a->head;
  1.1724 +            printf("arc  %d->%d: x  = %5g; lambda = %5g\n",
  1.1725 +               v->i, w->i, arc(a)->x,
  1.1726 +               arc(a)->cost - (node(v)->pi - node(w)->pi));
  1.1727 +         }
  1.1728 +      }
  1.1729 +      glp_delete_graph(G);
  1.1730 +      return 0;
  1.1731 +}
  1.1732 +\end{verbatim}
  1.1733 +\end{footnotesize}
  1.1734 +
  1.1735 +If `\verb|sample.min|' is the example data file from the subsection
  1.1736 +describing the routine \verb|glp_read_mincost|, the output may look like
  1.1737 +follows:
  1.1738 +
  1.1739 +\begin{footnotesize}
  1.1740 +\begin{verbatim}
  1.1741 +Reading min-cost flow problem data from `sample.min'...
  1.1742 +Flow network has 9 nodes and 14 arcs
  1.1743 +24 lines were read
  1.1744 +ret = 0; sol =   213
  1.1745 +node 1:    pi =   -12
  1.1746 +arc  1->4: x  =    13; lambda =     0
  1.1747 +arc  1->2: x  =     7; lambda =     0
  1.1748 +node 2:    pi =   -12
  1.1749 +arc  2->4: x  =     0; lambda =     3
  1.1750 +arc  2->3: x  =     7; lambda =     0
  1.1751 +node 3:    pi =   -14
  1.1752 +arc  3->8: x  =     5; lambda =     0
  1.1753 +arc  3->5: x  =     2; lambda =     3
  1.1754 +node 4:    pi =   -12
  1.1755 +arc  4->5: x  =    13; lambda =     0
  1.1756 +node 5:    pi =   -12
  1.1757 +arc  5->7: x  =     4; lambda =    -1
  1.1758 +arc  5->6: x  =    11; lambda =     0
  1.1759 +arc  5->2: x  =     0; lambda =     1
  1.1760 +node 6:    pi =   -17
  1.1761 +arc  6->8: x  =     4; lambda =     3
  1.1762 +arc  6->7: x  =     7; lambda =    -3
  1.1763 +node 7:    pi =   -20
  1.1764 +arc  7->9: x  =    11; lambda =     0
  1.1765 +node 8:    pi =   -14
  1.1766 +arc  8->9: x  =     9; lambda =     0
  1.1767 +node 9:    pi =   -23
  1.1768 +\end{verbatim}
  1.1769 +\end{footnotesize}
  1.1770 +
  1.1771 +\subsection{glp\_netgen---Klingman's network problem generator}
  1.1772 +
  1.1773 +\subsubsection*{Synopsis}
  1.1774 +
  1.1775 +\begin{verbatim}
  1.1776 +int glp_netgen(glp_graph *G, int v_rhs, int a_cap, int a_cost,
  1.1777 +      const int parm[1+15]);
  1.1778 +\end{verbatim}
  1.1779 +
  1.1780 +\subsubsection*{Description}
  1.1781 +
  1.1782 +The routine \verb|glp_netgen| is a GLPK version of the network problem
  1.1783 +generator developed by Dr.~Darwin~Klingman.\footnote{D.~Klingman,
  1.1784 +A.~Napier, and J.~Stutz. NETGEN: A program for generating large scale
  1.1785 +capacitated assignment, transportation, and minimum cost flow networks.
  1.1786 +Management Science 20 (1974), 814-20.} It can create capacitated and
  1.1787 +uncapacitated minimum cost flow (or transshipment), transportation, and
  1.1788 +assignment problems.
  1.1789 +
  1.1790 +The parameter \verb|G| specifies the graph object, to which the
  1.1791 +generated  problem data have to be stored. Note that on entry the graph
  1.1792 +object  is erased with the routine \verb|glp_erase_graph|.
  1.1793 +
  1.1794 +The parameter \verb|v_rhs| specifies an offset of the field of type
  1.1795 +\verb|double| in the vertex data block, to which the routine stores the
  1.1796 +supply or  demand value. If \verb|v_rhs| $<0$, the value is not stored.
  1.1797 +
  1.1798 +The parameter \verb|a_cap| specifies an offset of the field of type
  1.1799 +\verb|double| in the arc data block, to which the routine stores the
  1.1800 +arc capacity. If \verb|a_cap| $<0$, the capacity is not stored.
  1.1801 +
  1.1802 +The parameter \verb|a_cost| specifies an offset of the field of type
  1.1803 +\verb|double| in the arc data block, to which the routine stores the
  1.1804 +per-unit cost if the arc flow. If \verb|a_cost| $<0$, the cost is not
  1.1805 +stored.
  1.1806 +
  1.1807 +The array \verb|parm| contains description of the network to be
  1.1808 +generated:
  1.1809 +
  1.1810 +\begin{tabular}{@{}lll@{}}
  1.1811 +\verb|parm[0] |&             &not used\\
  1.1812 +\verb|parm[1] |&\verb|iseed |&8-digit positive random number seed\\
  1.1813 +\verb|parm[2] |&\verb|nprob |&8-digit problem id number\\
  1.1814 +\verb|parm[3] |&\verb|nodes |&total number of nodes\\
  1.1815 +\verb|parm[4] |&\verb|nsorc |&total number of source nodes\\
  1.1816 +&&(including transshipment nodes)\\
  1.1817 +\verb|parm[5] |&\verb|nsink |&total number of sink nodes\\
  1.1818 +&&(including transshipment nodes)\\
  1.1819 +\verb|parm[6] |&\verb|iarcs |&number of arc\\
  1.1820 +\verb|parm[7] |&\verb|mincst|&minimum cost for arcs\\
  1.1821 +\verb|parm[8] |&\verb|maxcst|&maximum cost for arcs\\
  1.1822 +\verb|parm[9] |&\verb|itsup |&total supply\\
  1.1823 +\end{tabular}
  1.1824 +
  1.1825 +\begin{tabular}{@{}lll@{}}
  1.1826 +\verb|parm[10]|&\verb|ntsorc|&number of transshipment source nodes\\
  1.1827 +\verb|parm[11]|&\verb|ntsink|&number of transshipment sink nodes\\
  1.1828 +\verb|parm[12]|&\verb|iphic |&percentage of skeleton arcs to be given
  1.1829 +the maxi-\\&&mum cost\\
  1.1830 +\verb|parm[13]|&\verb|ipcap |&percentage of arcs to be capacitated\\
  1.1831 +\verb|parm[14]|&\verb|mincap|&minimum upper bound for capacitated arcs\\
  1.1832 +\verb|parm[15]|&\verb|maxcap|&maximum upper bound for capacitated arcs\\
  1.1833 +\end{tabular}
  1.1834 +
  1.1835 +\subsubsection*{Notes}
  1.1836 +
  1.1837 +\noindent\indent
  1.1838 +1. The routine generates a transportation problem if:
  1.1839 +$${\tt nsorc}+{\tt nsink}={\tt nodes},
  1.1840 +\  {\tt ntsorc}=0,\ \mbox{and}\ {\tt ntsink}=0.$$
  1.1841 +
  1.1842 +2. The routine generates an assignment problem if the requirements for
  1.1843 +a transportation problem are met and:
  1.1844 +$${\tt nsorc}={\tt nsink}\ \mbox{and}\ {\tt itsup}={\tt nsorc}.$$
  1.1845 +
  1.1846 +3. The routine always generates connected graphs. So, if the number of
  1.1847 +requested arcs has been reached and the generated instance is not fully
  1.1848 +connected, the routine generates a few remaining arcs to ensure
  1.1849 +connectedness. Thus, the actual number of arcs generated by the routine
  1.1850 +may be greater than the requested number of arcs.
  1.1851 +
  1.1852 +\subsubsection*{Returns}
  1.1853 +
  1.1854 +If the instance was successfully generated, the routine
  1.1855 +\verb|glp_netgen| returns zero; otherwise, if specified parameters are
  1.1856 +inconsistent, the routine returns a non-zero error code.
  1.1857 +
  1.1858 +\subsection{glp\_gridgen---grid-like network problem generator}
  1.1859 +
  1.1860 +\subsubsection*{Synopsis}
  1.1861 +
  1.1862 +\begin{verbatim}
  1.1863 +int glp_gridgen(glp_graph *G, int v_rhs, int a_cap, int a_cost,
  1.1864 +      const int parm[1+14]);
  1.1865 +\end{verbatim}
  1.1866 +
  1.1867 +\subsubsection*{Description}
  1.1868 +
  1.1869 +The routine \verb|glp_gridgen| is a GLPK version of the grid-like
  1.1870 +network problem generator developed by Yusin Lee and Jim
  1.1871 +Orlin.\footnote{Y.~Lee and J.~Orlin. GRIDGEN generator., 1991. The
  1.1872 +original code is publically available from
  1.1873 +{\tt<ftp://dimacs.rutgers.edu/pub/netflow/generators/network/gridgen>}.}
  1.1874 +
  1.1875 +The parameter \verb|G| specifies the graph object, to which the
  1.1876 +generated  problem data have to be stored. Note that on entry the graph
  1.1877 +object  is erased with the routine \verb|glp_erase_graph|.
  1.1878 +
  1.1879 +The parameter \verb|v_rhs| specifies an offset of the field of type
  1.1880 +\verb|double| in the vertex data block, to which the routine stores the
  1.1881 +supply or  demand value. If \verb|v_rhs| $<0$, the value is not stored.
  1.1882 +
  1.1883 +The parameter \verb|a_cap| specifies an offset of the field of type
  1.1884 +\verb|double| in the arc data block, to which the routine stores the
  1.1885 +arc capacity. If \verb|a_cap| $<0$, the capacity is not stored.
  1.1886 +
  1.1887 +The parameter \verb|a_cost| specifies an offset of the field of type
  1.1888 +\verb|double| in the arc data block, to which the routine stores the
  1.1889 +per-unit cost if the arc flow. If \verb|a_cost| $<0$, the cost is not
  1.1890 +stored.
  1.1891 +
  1.1892 +The array \verb|parm| contains parameters of the network to be
  1.1893 +generated:
  1.1894 +
  1.1895 +\begin{tabular}{@{}ll@{}}
  1.1896 +\verb|parm[0] |&not used\\
  1.1897 +\verb|parm[1] |&two-ways arcs indicator:\\
  1.1898 +               &1 --- if links in both direction should be generated\\
  1.1899 +               &0 --- otherwise\\
  1.1900 +\verb|parm[2] |&random number seed (a positive integer)\\
  1.1901 +\verb|parm[3] |&number of nodes (the number of nodes generated might
  1.1902 +be\\&slightly different to make the network a grid)\\
  1.1903 +\verb|parm[4] |&grid width\\
  1.1904 +\verb|parm[5] |&number of sources\\
  1.1905 +\verb|parm[6] |&number of sinks\\
  1.1906 +\verb|parm[7] |&average degree\\
  1.1907 +\verb|parm[8] |&total flow\\
  1.1908 +\verb|parm[9] |&distribution of arc costs:\\
  1.1909 +               &1 --- uniform\\
  1.1910 +               &2 --- exponential\\
  1.1911 +\verb|parm[10]|&lower bound for arc cost (uniform)\\
  1.1912 +               &$100\lambda$ (exponential)\\
  1.1913 +\verb|parm[11]|&upper bound for arc cost (uniform)\\
  1.1914 +               &not used (exponential)\\
  1.1915 +\verb|parm[12]|&distribution of arc capacities:\\
  1.1916 +               &1 --- uniform\\
  1.1917 +               &2 --- exponential\\
  1.1918 +\verb|parm[13]|&lower bound for arc capacity (uniform)\\
  1.1919 +               &$100\lambda$ (exponential)\\
  1.1920 +\verb|parm[14]|&upper bound for arc capacity (uniform)\\
  1.1921 +               &not used (exponential)\\
  1.1922 +\end{tabular}
  1.1923 +
  1.1924 +\subsubsection*{Returns}
  1.1925 +
  1.1926 +If the instance was successfully generated, the routine
  1.1927 +\verb|glp_gridgen| returns zero; otherwise, if specified parameters are
  1.1928 +inconsistent, the routine returns a non-zero error code.
  1.1929 +
  1.1930 +\subsubsection*{Comments\footnote{This material is based on comments
  1.1931 +to the original version of GRIDGEN.}}
  1.1932 +
  1.1933 +This network generator generates a grid-like network plus a super node.
  1.1934 +In additional to the arcs connecting the nodes in the grid, there is an
  1.1935 +arc from each supply node to the super node and from the super node to
  1.1936 +each demand node to guarantee feasiblity. These arcs have very high
  1.1937 +costs and very big capacities.
  1.1938 +
  1.1939 +The idea of this network generator is as follows: First, a grid of
  1.1940 +$n_1\times n_2$ is generated. For example, $5\times 3$. The nodes are
  1.1941 +numbered as 1 to 15, and the supernode is numbered as $n_1\times n_2+1$.
  1.1942 +Then arcs between adjacent nodes are generated. For these arcs, the user
  1.1943 +is allowed to specify either to generate two-way arcs or one-way arcs.
  1.1944 +If two-way arcs are to be generated, two arcs, one in each direction,
  1.1945 +will be generated between each adjacent node pairs. Otherwise, only one
  1.1946 +arc will be generated. If this is the case, the arcs will be generated
  1.1947 +in alterntive directions as shown below.
  1.1948 +
  1.1949 +\bigskip
  1.1950 +
  1.1951 +\noindent\hfil
  1.1952 +\xymatrix
  1.1953 +{1\ar[r]\ar[d]&2\ar[r]&3\ar[r]\ar[d]&4\ar[r]&5\ar[d]\\
  1.1954 +6\ar[d]&7\ar[l]\ar[u]&8\ar[l]\ar[d]&9\ar[l]\ar[u]&10\ar[l]\ar[d]\\
  1.1955 +11\ar[r]&12\ar[r]\ar[u]&13\ar[r]&14\ar[r]\ar[u]&15\\
  1.1956 +}
  1.1957 +
  1.1958 +\bigskip
  1.1959 +
  1.1960 +Then the arcs between the super node and the source/sink nodes are added
  1.1961 +as mentioned before. If the number of arcs still doesn't reach the
  1.1962 +requirement, additional arcs will be added by uniformly picking random
  1.1963 +node pairs. There is no checking to prevent multiple arcs between any
  1.1964 +pair of nodes. However, there will be no self-arcs (arcs that poins back
  1.1965 +to its tail node) in the network.
  1.1966 +
  1.1967 +The source and sink nodes are selected uniformly in the network, and
  1.1968 +the imbalances of each source/sink node are also assigned by uniform
  1.1969 +distribution.
  1.1970 +
  1.1971 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1.1972 +
  1.1973 +\newpage
  1.1974 +
  1.1975 +\section{Maximum flow problem}
  1.1976 +
  1.1977 +\subsection{Background}
  1.1978 +
  1.1979 +The {\it maximum flow problem} (MAXFLOW) is stated as follows. Let
  1.1980 +there be given a directed graph (flow network) $G=(V,A)$, where $V$ is
  1.1981 +a set of vertices (nodes), and $A\subseteq V\times V$ is a set of arcs.
  1.1982 +Let also for each arc $a=(i,j)\in A$ there be given its capacity
  1.1983 +$u_{ij}$. The problem is, for given {\it source} node $s\in V$ and
  1.1984 +{\it sink} node $t\in V$, to find flows $x_{ij}$ through every arc of
  1.1985 +the network, which satisfy the specified arc capacities and the
  1.1986 +conservation constraints at all nodes, and maximize the total flow $F$
  1.1987 +through the network from $s$ to $t$. Here the conservation constraint
  1.1988 +at a node means that the total flow entering this node through its
  1.1989 +incoming arcs (plus $F$, if it is the source node) must be equal to the
  1.1990 +total flow leaving this node through its outgoing arcs (plus $F$, if it
  1.1991 +is the sink node).
  1.1992 +
  1.1993 +An example of the maximum flow problem, where $s=v_1$ and $t=v_9$, is
  1.1994 +shown on Fig.~2.
  1.1995 +
  1.1996 +\bigskip
  1.1997 +
  1.1998 +\noindent\hfil
  1.1999 +\xymatrix @C=48pt
  1.2000 +{_{F}\ar@{~>}[d]&
  1.2001 +v_2\ar[r]|{_{10}}\ar[dd]|{_{9}}&
  1.2002 +v_3\ar[dd]|{_{12}}\ar[r]|{_{18}}&
  1.2003 +v_8\ar[rd]|{_{20}}&\\
  1.2004 +v_1\ar[ru]|{_{14}}\ar[rd]|{_{23}}&&&
  1.2005 +v_6\ar[d]|{_{7}}\ar[u]|{_{8}}&
  1.2006 +v_9\ar@{~>}[d]\\
  1.2007 +&v_4\ar[r]|{_{26}}&
  1.2008 +v_5\ar[luu]|{_{11}}\ar[ru]|{_{25}}\ar[r]|{_{4}}&
  1.2009 +v_7\ar[ru]|{_{15}}&_{F}\\
  1.2010 +}
  1.2011 +
  1.2012 +\bigskip
  1.2013 +
  1.2014 +\noindent\hfil
  1.2015 +Fig.~2. An example of the maximum flow problem.
  1.2016 +
  1.2017 +\bigskip
  1.2018 +
  1.2019 +The maximum flow problem can be naturally formulated as the following
  1.2020 +LP problem:
  1.2021 +
  1.2022 +\medskip
  1.2023 +
  1.2024 +\noindent
  1.2025 +\hspace{.5in}maximize
  1.2026 +$$F\eqno(4)$$
  1.2027 +\hspace{.5in}subject to
  1.2028 +$$\sum_{(i,j)\in A}x_{ij}-\sum_{(j,i)\in A}x_{ji}=\left\{
  1.2029 +\begin{array}{@{\ }rl}
  1.2030 ++F,&\hbox{for}\ i=s\\
  1.2031 + 0,&\hbox{for all}\ i\in V\backslash\{s,t\}\\
  1.2032 +-F,&\hbox{for}\ i=t\\
  1.2033 +\end{array}
  1.2034 +\right.\eqno(5)
  1.2035 +$$
  1.2036 +$$0\leq x_{ij}\leq u_{ij}\ \ \ \hbox{for all}\ (i,j)\in A
  1.2037 +\eqno(6)$$
  1.2038 +
  1.2039 +\medskip
  1.2040 +
  1.2041 +\noindent
  1.2042 +where $F\geq 0$ is an additional variable playing the role of the
  1.2043 +objective.
  1.2044 +
  1.2045 +\newpage
  1.2046 +
  1.2047 +Another LP formulation of the maximum flow problem, which does not
  1.2048 +include the variable $F$, is the following:
  1.2049 +
  1.2050 +\medskip
  1.2051 +
  1.2052 +\noindent
  1.2053 +\hspace{.5in}maximize
  1.2054 +$$z=\sum_{(s,j)\in A}x_{sj}-\sum_{(j,s)\in A}x_{js}\ (=F)\eqno(7)$$
  1.2055 +\hspace{.5in}subject to
  1.2056 +$$\sum_{(i,j)\in A}x_{ij}-\sum_{(j,i)\in A}x_{ji}\left\{
  1.2057 +\begin{array}{@{\ }rl}
  1.2058 +\geq 0,&\hbox{for}\ i=s\\
  1.2059 +=0,&\hbox{for all}\ i\in V\backslash\{s,t\}\\
  1.2060 +\leq 0,&\hbox{for}\ i=t\\
  1.2061 +\end{array}
  1.2062 +\right.\eqno(8)
  1.2063 +$$
  1.2064 +$$0\leq x_{ij}\leq u_{ij}\ \ \ \hbox{for all}\ (i,j)\in A
  1.2065 +\eqno(9)$$
  1.2066 +
  1.2067 +\subsection{glp\_read\_maxflow---read maximum flow problem data\\in
  1.2068 +DIMACS format}
  1.2069 +
  1.2070 +\subsubsection*{Synopsis}
  1.2071 +
  1.2072 +\begin{verbatim}
  1.2073 +int glp_read_maxflow(glp_graph *G, int *s, int *t, int a_cap,
  1.2074 +      const char *fname);
  1.2075 +\end{verbatim}
  1.2076 +
  1.2077 +\subsubsection*{Description}
  1.2078 +
  1.2079 +The routine \verb|glp_read_maxflow| reads the maximum flow problem
  1.2080 +data from a text file in DIMACS format.
  1.2081 +
  1.2082 +The parameter \verb|G| specifies the graph object, to which the problem
  1.2083 +data have to be stored. Note that before reading data the current
  1.2084 +content of the graph object is completely erased with the routine
  1.2085 +\verb|glp_erase_graph|.
  1.2086 +
  1.2087 +The pointer \verb|s| specifies a location, to which the routine stores
  1.2088 +the ordinal number of the source node. If \verb|s| is \verb|NULL|, the
  1.2089 +source node number is not stored.
  1.2090 +
  1.2091 +The pointer \verb|t| specifies a location, to which the routine stores
  1.2092 +the ordinal number of the sink node. If \verb|t| is \verb|NULL|, the
  1.2093 +sink node number is not stored.
  1.2094 +
  1.2095 +The parameter \verb|a_cap| specifies an offset of the field of type
  1.2096 +\verb|double| in the arc data block, to which the routine stores
  1.2097 +$u_{ij}$, the arc capacity. If \verb|a_cap| $<0$, the arc capacity is
  1.2098 +not stored.
  1.2099 +
  1.2100 +The character string \verb|fname| specifies the name of a text file to
  1.2101 +be read in. (If the file name name ends with the suffix `\verb|.gz|',
  1.2102 +the file is assumed to be compressed, in which case the routine
  1.2103 +decompresses it ``on the fly''.)
  1.2104 +
  1.2105 +\subsubsection*{Returns}
  1.2106 +
  1.2107 +If the operation was successful, the routine returns zero. Otherwise,
  1.2108 +it prints an error message and returns non-zero.
  1.2109 +
  1.2110 +\subsubsection*{Example}
  1.2111 +
  1.2112 +\begin{footnotesize}
  1.2113 +\begin{verbatim}
  1.2114 +typedef struct
  1.2115 +{     /* arc data block */
  1.2116 +      ...
  1.2117 +      double cap;
  1.2118 +      ...
  1.2119 +} a_data;
  1.2120 +
  1.2121 +int main(void)
  1.2122 +{     glp_graph *G;
  1.2123 +      int s, t, ret;
  1.2124 +      G = glp_create_graph(..., sizeof(a_data));
  1.2125 +      ret = glp_read_maxflow(G, &s, &t, offsetof(a_data, cap),
  1.2126 +         "sample.max");
  1.2127 +      if (ret != 0) goto ...
  1.2128 +      ...
  1.2129 +}
  1.2130 +\end{verbatim}
  1.2131 +\end{footnotesize}
  1.2132 +
  1.2133 +\subsubsection*{DIMACS maximum flow problem format\footnote{This
  1.2134 +material is based on the paper ``The First DIMACS International
  1.2135 +Algorithm Implementation Challenge: Problem Definitions and
  1.2136 +Specifications'', which is publically available at
  1.2137 +{\tt http://dimacs.rutgers.edu/Challenges/}.}}
  1.2138 +\label{subsecmaxflow}
  1.2139 +
  1.2140 +The DIMACS input file is a plain ASCII text file. It contains
  1.2141 +{\it lines} of several types described below. A line is terminated with
  1.2142 +an end-of-line character. Fields in each line are separated by at least
  1.2143 +one blank space. Each line begins with a one-character designator to
  1.2144 +identify the line type.
  1.2145 +
  1.2146 +Note that DIMACS requires all numerical quantities to be integers in
  1.2147 +the range $[-2^{31},\ 2^{31}-1]$ while GLPK allows the quantities to be
  1.2148 +floating-point numbers.
  1.2149 +
  1.2150 +\paragraph{Comment lines.} Comment lines give human-readable information
  1.2151 +about the file and are ignored by programs. Comment lines can appear
  1.2152 +anywhere in the file. Each comment line begins with a lower-case
  1.2153 +character \verb|c|.
  1.2154 +
  1.2155 +\begin{verbatim}
  1.2156 +   c This is a comment line
  1.2157 +\end{verbatim}
  1.2158 +
  1.2159 +\newpage
  1.2160 +
  1.2161 +\paragraph{Problem line.} There is one problem line per data file. The
  1.2162 +problem line must appear before any node or arc descriptor lines. It has
  1.2163 +the following format:
  1.2164 +
  1.2165 +\begin{verbatim}
  1.2166 +   p max NODES ARCS
  1.2167 +\end{verbatim}
  1.2168 +
  1.2169 +\noindent
  1.2170 +The lower-case character \verb|p| signifies that this is a problem line.
  1.2171 +The three-character problem designator \verb|max| identifies the file as
  1.2172 +containing specification information for the maximum flow problem. The
  1.2173 +\verb|NODES| field contains an integer value specifying the number of
  1.2174 +nodes in the network. The \verb|ARCS| field contains an integer value
  1.2175 +specifying the number of arcs in the network.
  1.2176 +
  1.2177 +\paragraph{Node descriptors.} Two node descriptor lines for the source
  1.2178 +and sink nodes must appear before all arc descriptor lines. They may
  1.2179 +appear in either order, each with the following format:
  1.2180 +
  1.2181 +\begin{verbatim}
  1.2182 +   n ID WHICH
  1.2183 +\end{verbatim}
  1.2184 +
  1.2185 +\noindent
  1.2186 +The lower-case character \verb|n| signifies that this a node descriptor
  1.2187 +line. The \verb|ID| field gives a node identification number, an integer
  1.2188 +between 1 and \verb|NODES|. The \verb|WHICH| field gives either a
  1.2189 +lower-case \verb|s| or \verb|t|, designating the source and sink,
  1.2190 +respectively.
  1.2191 +
  1.2192 +\paragraph{Arc descriptors.} There is one arc descriptor line for each
  1.2193 +arc in the network. Arc descriptor lines are of the following format:
  1.2194 +
  1.2195 +\begin{verbatim}
  1.2196 +   a SRC DST CAP
  1.2197 +\end{verbatim}
  1.2198 +
  1.2199 +\noindent
  1.2200 +The lower-case character \verb|a| signifies that this is an arc
  1.2201 +descriptor line. For a directed arc $(i,j)$ the \verb|SRC| field gives
  1.2202 +the identification number $i$ for the tail endpoint, and the \verb|DST|
  1.2203 +field gives the identification number $j$ for the head endpoint.
  1.2204 +Identification numbers are integers between 1 and \verb|NODES|. The
  1.2205 +\verb|CAP| field gives the arc capacity, i.e. maximum amount of flow
  1.2206 +that can be sent along arc $(i,j)$ in a feasible flow.
  1.2207 +
  1.2208 +\paragraph{Example.} Below here is an example of the data file in
  1.2209 +DIMACS format corresponding to the maximum flow problem shown on Fig~2.
  1.2210 +
  1.2211 +\newpage
  1.2212 +
  1.2213 +\begin{footnotesize}
  1.2214 +\begin{verbatim}
  1.2215 +c sample.max
  1.2216 +c
  1.2217 +c This is an example of the maximum flow problem data
  1.2218 +c in DIMACS format.
  1.2219 +c
  1.2220 +p max 9 14
  1.2221 +c
  1.2222 +n 1 s
  1.2223 +n 9 t
  1.2224 +c
  1.2225 +a 1 2 14
  1.2226 +a 1 4 23
  1.2227 +a 2 3 10
  1.2228 +a 2 4  9
  1.2229 +a 3 5 12
  1.2230 +a 3 8 18
  1.2231 +a 4 5 26
  1.2232 +a 5 2 11
  1.2233 +a 5 6 25
  1.2234 +a 5 7  4
  1.2235 +a 6 7  7
  1.2236 +a 6 8  8
  1.2237 +a 7 9 15
  1.2238 +a 8 9 20
  1.2239 +c
  1.2240 +c eof
  1.2241 +\end{verbatim}
  1.2242 +\end{footnotesize}
  1.2243 +
  1.2244 +\subsection{glp\_write\_maxflow---write maximum flow problem data\\
  1.2245 +in DIMACS format}
  1.2246 +
  1.2247 +\subsubsection*{Synopsis}
  1.2248 +
  1.2249 +\begin{verbatim}
  1.2250 +int glp_write_maxflow(glp_graph *G, int s, int t, int a_cap,
  1.2251 +      const char *fname);
  1.2252 +\end{verbatim}
  1.2253 +
  1.2254 +\subsubsection*{Description}
  1.2255 +
  1.2256 +The routine \verb|glp_write_maxflow| writes the maximum flow problem
  1.2257 +data to a text file in DIMACS format.
  1.2258 +
  1.2259 +The parameter \verb|G| is the graph (network) program object, which
  1.2260 +specifies the maximum flow problem instance.
  1.2261 +
  1.2262 +The parameter \verb|s| specifies the ordinal number of the source node.
  1.2263 +
  1.2264 +The parameter \verb|t| specifies the ordinal number of the sink node.
  1.2265 +
  1.2266 +The parameter \verb|a_cap| specifies an offset of the field of type
  1.2267 +\verb|double| in the arc data block, which contains $u_{ij}$, the upper
  1.2268 +bound to the arc flow (the arc capacity). If the upper bound is
  1.2269 +specified as \verb|DBL_MAX|, it is assumed that $u_{ij}=\infty$, i.e.
  1.2270 +the arc is uncapacitated. If \verb|a_cap| $<0$, it is assumed that
  1.2271 +$u_{ij}=1$ for all arcs.
  1.2272 +
  1.2273 +The character string \verb|fname| specifies a name of the text file to
  1.2274 +be written out. (If the file name ends with suffix `\verb|.gz|', the
  1.2275 +file is assumed to be compressed, in which case the routine performs
  1.2276 +automatic compression on writing it.)
  1.2277 +
  1.2278 +\subsubsection*{Returns}
  1.2279 +
  1.2280 +If the operation was successful, the routine returns zero. Otherwise,
  1.2281 +it prints an error message and returns non-zero.
  1.2282 +
  1.2283 +\subsection{glp\_maxflow\_lp---convert maximum flow problem to LP}
  1.2284 +
  1.2285 +\subsubsection*{Synopsis}
  1.2286 +
  1.2287 +\begin{verbatim}
  1.2288 +void glp_maxflow_lp(glp_prob *lp, glp_graph *G, int names,
  1.2289 +      int s, int t, int a_cap);
  1.2290 +\end{verbatim}
  1.2291 +
  1.2292 +\subsubsection*{Description}
  1.2293 +
  1.2294 +The routine \verb|glp_maxflow_lp| builds LP problem (7)---(9), which
  1.2295 +corresponds to the specified maximum flow problem.
  1.2296 +
  1.2297 +The parameter \verb|lp| is the resultant LP problem object to be built.
  1.2298 +Note that on entry its current content is erased with the routine
  1.2299 +\verb|glp_erase_prob|.
  1.2300 +
  1.2301 +The parameter \verb|G| is the graph (network) program object, which
  1.2302 +specifies the maximum flow problem instance.
  1.2303 +
  1.2304 +The parameter \verb|names| is a flag. If it is \verb|GLP_ON|, the
  1.2305 +routine uses symbolic names of the graph object components to assign
  1.2306 +symbolic names to the LP problem object components. If the flag is
  1.2307 +\verb|GLP_OFF|, no symbolic names are assigned.
  1.2308 +
  1.2309 +The parameter \verb|s| specifies the ordinal number of the source node.
  1.2310 +
  1.2311 +The parameter \verb|t| specifies the ordinal number of the sink node.
  1.2312 +
  1.2313 +The parameter \verb|a_cap| specifies an offset of the field of type
  1.2314 +\verb|double| in the arc data block, which contains $u_{ij}$, the upper
  1.2315 +bound to the arc flow (the arc capacity). If the upper bound is
  1.2316 +specified as \verb|DBL_MAX|, it is assumed that $u_{ij}=\infty$, i.e.
  1.2317 +the arc is uncapacitated. If \verb|a_cap| $<0$, it is assumed that
  1.2318 +$u_{ij}=1$ for all arcs.
  1.2319 +
  1.2320 +\subsubsection*{Example}
  1.2321 +
  1.2322 +The example program below reads the maximum flow problem in DIMACS
  1.2323 +format from file `\verb|sample.max|', converts the instance to LP, and
  1.2324 +then writes the resultant LP in CPLEX format to file
  1.2325 +`\verb|maxflow.lp|'.
  1.2326 +
  1.2327 +\begin{footnotesize}
  1.2328 +\begin{verbatim}
  1.2329 +#include <stddef.h>
  1.2330 +#include <glpk.h>
  1.2331 +
  1.2332 +int main(void)
  1.2333 +{     glp_graph *G;
  1.2334 +      glp_prob *lp;
  1.2335 +      int s, t;
  1.2336 +      G = glp_create_graph(0, sizeof(double));
  1.2337 +      glp_read_maxflow(G, &s, &t, 0, "sample.max");
  1.2338 +      lp = glp_create_prob();
  1.2339 +      glp_maxflow_lp(lp, G, GLP_ON, s, t, 0);
  1.2340 +      glp_delete_graph(G);
  1.2341 +      glp_write_lp(lp, NULL, "maxflow.lp");
  1.2342 +      glp_delete_prob(lp);
  1.2343 +      return 0;
  1.2344 +}
  1.2345 +\end{verbatim}
  1.2346 +\end{footnotesize}
  1.2347 +
  1.2348 +If `\verb|sample.max|' is the example data file from the previous
  1.2349 +subsection, the output `\verb|maxflow.lp|' may look like follows:
  1.2350 +
  1.2351 +\begin{footnotesize}
  1.2352 +\begin{verbatim}
  1.2353 +Maximize
  1.2354 + obj: + x(1,4) + x(1,2)
  1.2355 +
  1.2356 +Subject To
  1.2357 + r_1: + x(1,2) + x(1,4) >= 0
  1.2358 + r_2: - x(5,2) + x(2,3) + x(2,4) - x(1,2) = 0
  1.2359 + r_3: + x(3,5) + x(3,8) - x(2,3) = 0
  1.2360 + r_4: + x(4,5) - x(2,4) - x(1,4) = 0
  1.2361 + r_5: + x(5,2) + x(5,6) + x(5,7) - x(4,5) - x(3,5) = 0
  1.2362 + r_6: + x(6,7) + x(6,8) - x(5,6) = 0
  1.2363 + r_7: + x(7,9) - x(6,7) - x(5,7) = 0
  1.2364 + r_8: + x(8,9) - x(6,8) - x(3,8) = 0
  1.2365 + r_9: - x(8,9) - x(7,9) <= 0
  1.2366 +
  1.2367 +Bounds
  1.2368 + 0 <= x(1,4) <= 23
  1.2369 + 0 <= x(1,2) <= 14
  1.2370 + 0 <= x(2,4) <= 9
  1.2371 + 0 <= x(2,3) <= 10
  1.2372 + 0 <= x(3,8) <= 18
  1.2373 + 0 <= x(3,5) <= 12
  1.2374 + 0 <= x(4,5) <= 26
  1.2375 + 0 <= x(5,7) <= 4
  1.2376 + 0 <= x(5,6) <= 25
  1.2377 + 0 <= x(5,2) <= 11
  1.2378 + 0 <= x(6,8) <= 8
  1.2379 + 0 <= x(6,7) <= 7
  1.2380 + 0 <= x(7,9) <= 15
  1.2381 + 0 <= x(8,9) <= 20
  1.2382 +
  1.2383 +End
  1.2384 +\end{verbatim}
  1.2385 +\end{footnotesize}
  1.2386 +
  1.2387 +\subsection{glp\_maxflow\_ffalg---solve maximum flow problem with
  1.2388 +Ford-Fulkerson algorithm}
  1.2389 +
  1.2390 +\subsubsection*{Synopsis}
  1.2391 +
  1.2392 +\begin{verbatim}
  1.2393 +int glp_maxflow_ffalg(glp_graph *G, int s, int t, int a_cap,
  1.2394 +      double *sol, int a_x, int v_cut);
  1.2395 +\end{verbatim}
  1.2396 +
  1.2397 +\subsubsection*{Description}
  1.2398 +
  1.2399 +The routine \verb|glp_mincost_ffalg| finds optimal solution to the
  1.2400 +maximum flow problem with the Ford-Fulkerson algorithm.\footnote{GLPK
  1.2401 +implementation of the Ford-Fulkerson algorithm is based on the following
  1.2402 +book: L.~R.~Ford,~Jr., and D.~R.~Fulkerson, ``Flows in Networks,'' The
  1.2403 +RAND Corp., Report\linebreak R-375-PR (August 1962), Chap. I
  1.2404 +``Static Maximal Flow,'' pp.~30-33.} Note that this routine requires all
  1.2405 +the problem data to be integer-valued.
  1.2406 +
  1.2407 +The parameter \verb|G| is a graph (network) program object which
  1.2408 +specifies the maximum flow problem instance to be solved.
  1.2409 +
  1.2410 +The parameter $s$ specifies the ordinal number of the source node.
  1.2411 +
  1.2412 +The parameter $t$ specifies the ordinal number of the sink node.
  1.2413 +
  1.2414 +The parameter \verb|a_cap| specifies an offset of the field of type
  1.2415 +\verb|double| in the arc data block, which contains $u_{ij}$, the upper
  1.2416 +bound to the arc flow (the arc capacity). This bound must be integer in
  1.2417 +the range [0, \verb|INT_MAX|]. If \verb|a_cap| $<0$, it is assumed that
  1.2418 +$u_{ij}=1$ for all arcs.
  1.2419 +
  1.2420 +The parameter \verb|sol| specifies a location, to which the routine
  1.2421 +stores the objective value (that is, the total flow from $s$ to $t$)
  1.2422 +found. If \verb|sol| is NULL, the objective value is not stored.
  1.2423 +
  1.2424 +The parameter \verb|a_x| specifies an offset of the field of type
  1.2425 +\verb|double| in the arc data block, to which the routine stores
  1.2426 +$x_{ij}$, the arc flow found. If \verb|a_x| $<0$, the arc flow values
  1.2427 +are not stored.
  1.2428 +
  1.2429 +The parameter \verb|v_cut| specifies an offset of the field of type
  1.2430 +\verb|int| in the vertex data block, to which the routine stores node
  1.2431 +flags corresponding to the optimal solution found: if the node flag is
  1.2432 +1, the node is labelled, and if the node flag is 0, the node is
  1.2433 +unlabelled. The calling program may use these node flags to determine
  1.2434 +the {\it minimal cut}, which is a subset of arcs whose one endpoint is
  1.2435 +labelled and other is not. If \verb|v_cut| $<0$, the node flags are not
  1.2436 +stored.
  1.2437 +
  1.2438 +Note that all solution components (the objective value and arc flows)
  1.2439 +computed by the routine are always integer-valued.
  1.2440 +
  1.2441 +\subsubsection*{Returns}
  1.2442 +
  1.2443 +\def\arraystretch{1}
  1.2444 +
  1.2445 +\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
  1.2446 +0 & Optimal solution found.\\
  1.2447 +\verb|GLP_EDATA| & Unable to start the search, because some problem
  1.2448 +data are either not integer-valued or out of range.\\
  1.2449 +\end{tabular}
  1.2450 +
  1.2451 +\subsubsection*{Example}
  1.2452 +
  1.2453 +The example program shown below reads the maximum flow problem instance
  1.2454 +in DIMACS format from file `\verb|sample.max|', solves it using the
  1.2455 +routine \verb|glp_maxflow_ffalg|, and write the solution found to the
  1.2456 +standard output.
  1.2457 +
  1.2458 +\begin{footnotesize}
  1.2459 +\begin{verbatim}
  1.2460 +#include <stddef.h>
  1.2461 +#include <stdio.h>
  1.2462 +#include <stdlib.h>
  1.2463 +#include <glpk.h>
  1.2464 +
  1.2465 +typedef struct { int cut; } v_data;
  1.2466 +typedef struct { double cap, x; } a_data;
  1.2467 +
  1.2468 +#define node(v) ((v_data *)((v)->data))
  1.2469 +#define arc(a)  ((a_data *)((a)->data))
  1.2470 +
  1.2471 +int main(void)
  1.2472 +{     glp_graph *G;
  1.2473 +      glp_vertex *v, *w;
  1.2474 +      glp_arc *a;
  1.2475 +      int i, s, t, ret;
  1.2476 +      double sol;
  1.2477 +      G = glp_create_graph(sizeof(v_data), sizeof(a_data));
  1.2478 +      glp_read_maxflow(G, &s, &t, offsetof(a_data, cap),
  1.2479 +         "sample.max");
  1.2480 +      ret = glp_maxflow_ffalg(G, s, t, offsetof(a_data, cap),
  1.2481 +         &sol, offsetof(a_data, x), offsetof(v_data, cut));
  1.2482 +      printf("ret = %d; sol = %5g\n", ret, sol);
  1.2483 +      for (i = 1; i <= G->nv; i++)
  1.2484 +      {  v = G->v[i];
  1.2485 +         for (a = v->out; a != NULL; a = a->t_next)
  1.2486 +         {  w = a->head;
  1.2487 +            printf("x[%d->%d] = %5g (%d)\n", v->i, w->i,
  1.2488 +               arc(a)->x, node(v)->cut ^ node(w)->cut);
  1.2489 +         }
  1.2490 +      }
  1.2491 +      glp_delete_graph(G);
  1.2492 +      return 0;
  1.2493 +}
  1.2494 +\end{verbatim}
  1.2495 +\end{footnotesize}
  1.2496 +
  1.2497 +If `\verb|sample.max|' is the example data file from the subsection
  1.2498 +describing the routine \verb|glp_read_maxflow|, the output may look like
  1.2499 +follows:
  1.2500 +
  1.2501 +\begin{footnotesize}
  1.2502 +\begin{verbatim}
  1.2503 +Reading maximum flow problem data from `sample.max'...
  1.2504 +Flow network has 9 nodes and 14 arcs
  1.2505 +24 lines were read
  1.2506 +ret = 0; sol =    29
  1.2507 +x[1->4] =    19 (0)
  1.2508 +x[1->2] =    10 (0)
  1.2509 +x[2->4] =     0 (0)
  1.2510 +x[2->3] =    10 (1)
  1.2511 +x[3->8] =    10 (0)
  1.2512 +x[3->5] =     0 (1)
  1.2513 +x[4->5] =    19 (0)
  1.2514 +x[5->7] =     4 (1)
  1.2515 +x[5->6] =    15 (0)
  1.2516 +x[5->2] =     0 (0)
  1.2517 +x[6->8] =     8 (1)
  1.2518 +x[6->7] =     7 (1)
  1.2519 +x[7->9] =    11 (0)
  1.2520 +x[8->9] =    18 (0)
  1.2521 +\end{verbatim}
  1.2522 +\end{footnotesize}
  1.2523 +
  1.2524 +\newpage
  1.2525 +
  1.2526 +\subsection{glp\_rmfgen---Goldfarb's maximum flow problem generator}
  1.2527 +
  1.2528 +\subsubsection*{Synopsis}
  1.2529 +
  1.2530 +\begin{verbatim}
  1.2531 +int glp_rmfgen(glp_graph *G, int *s, int *t, int a_cap,
  1.2532 +      const int parm[1+5]);
  1.2533 +\end{verbatim}
  1.2534 +
  1.2535 +\subsubsection*{Description}
  1.2536 +
  1.2537 +The routine \verb|glp_rmfgen| is a GLPK version of the maximum flow
  1.2538 +problem generator developed by D.~Goldfarb and
  1.2539 +M.~Grigoriadis.\footnote{D.~Goldfarb and M.~D.~Grigoriadis,
  1.2540 +``A computational comparison of the Dinic and network simplex methods
  1.2541 +for maximum flow.'' Annals of Op. Res. 13 (1988),
  1.2542 +pp.~83-123.}$^{,}$\footnote{U.~Derigs and W.~Meier, ``Implementing
  1.2543 +Goldberg's max-flow algorithm: A computational investigation.''
  1.2544 +Zeitschrift f\"ur Operations Research 33 (1989),
  1.2545 +pp.~383-403.}$^{,}$\footnote{The original code of RMFGEN implemented by
  1.2546 +Tamas Badics is publically available from
  1.2547 +{\tt <ftp://dimacs.rutgers.edu/pub/netflow/generators/network/genrmf>}.}
  1.2548 +
  1.2549 +The parameter \verb|G| specifies the graph object, to which the
  1.2550 +generated problem data have to be stored. Note that on entry the graph
  1.2551 +object is erased with the routine \verb|glp_erase_graph|.
  1.2552 +
  1.2553 +The pointers \verb|s| and \verb|t| specify locations, to which the
  1.2554 +routine stores the source and sink node numbers, respectively. If
  1.2555 +\verb|s| or \verb|t| is \verb|NULL|, corresponding node number is not
  1.2556 +stored.
  1.2557 +
  1.2558 +The parameter \verb|a_cap| specifies an offset of the field of type
  1.2559 +\verb|double| in the arc data block, to which the routine stores the arc
  1.2560 +capacity. If \verb|a_cap| $<0$, the capacity is not stored.
  1.2561 +
  1.2562 +The array \verb|parm| contains description of the network to be
  1.2563 +generated:
  1.2564 +
  1.2565 +\begin{tabular}{@{}lll@{}}
  1.2566 +\verb|parm[0]|&           &not used\\
  1.2567 +\verb|parm[1]|&\verb|seed|&random number seed (a positive integer)\\
  1.2568 +\verb|parm[2]|&\verb|a   |&frame size\\
  1.2569 +\verb|parm[3]|&\verb|b   |&depth\\
  1.2570 +\verb|parm[4]|&\verb|c1  |&minimal arc capacity\\
  1.2571 +\verb|parm[5]|&\verb|c2  |&maximal arc capacity\\
  1.2572 +\end{tabular}
  1.2573 +
  1.2574 +\subsubsection*{Returns}
  1.2575 +
  1.2576 +If the instance was successfully generated, the routine
  1.2577 +\verb|glp_netgen| returns zero; otherwise, if specified parameters are
  1.2578 +inconsistent, the routine returns a non-zero error code.
  1.2579 +
  1.2580 +\newpage
  1.2581 +
  1.2582 +\subsubsection*{Comments\footnote{This material is based on comments
  1.2583 +to the original version of RMFGEN.}}
  1.2584 +
  1.2585 +The generated network is as follows. It has $b$ pieces of frames of
  1.2586 +size $a\times a$. (So alltogether the number of vertices is
  1.2587 +$a\times a\times b$.)
  1.2588 +
  1.2589 +In each frame all the vertices are connected with their neighbours
  1.2590 +(forth and back). In addition the vertices of a frame are connected
  1.2591 +one to one with the vertices of next frame using a random permutation
  1.2592 +of those vertices.
  1.2593 +
  1.2594 +The source is the lower left vertex of the first frame, the sink is
  1.2595 +the upper right vertex of the $b$-th frame.
  1.2596 +
  1.2597 +\begin{verbatim}
  1.2598 +                              t
  1.2599 +                     +-------+
  1.2600 +                     |      .|
  1.2601 +                     |     . |
  1.2602 +                  /  |    /  |
  1.2603 +                 +-------+/ -+ b
  1.2604 +                 |    |  |/.
  1.2605 +               a |   -v- |/
  1.2606 +                 |    |  |/
  1.2607 +                 +-------+ 1
  1.2608 +                s    a
  1.2609 +\end{verbatim}
  1.2610 +
  1.2611 +The capacities are randomly chosen integers from the range of
  1.2612 +$[c_1,c_2]$  in the case of interconnecting edges, and $c_2\cdot a^2$
  1.2613 +for the in-frame edges.
  1.2614 +
  1.2615 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1.2616 +
  1.2617 +\newpage
  1.2618 +
  1.2619 +\section{Assignment problem}
  1.2620 +
  1.2621 +\subsection{Background}
  1.2622 +
  1.2623 +Let there be given an undirected bipartite graph $G=(R\cup S,E)$, where
  1.2624 +$R$ and $S$ are disjoint sets of vertices (nodes), and
  1.2625 +$E\subseteq R\times S$ is a set of edges. Let also for each edge
  1.2626 +$e=(i,j)\in E$ there be given its cost $c_{ij}$. A {\it matching}
  1.2627 +(which in case of bipartite graph is also called {\it assignment})
  1.2628 +$M\subseteq E$ in $G$ is a set of pairwise non-adjacent edges, that is,
  1.2629 +no two edges in $M$ share a common vertex. A matching, which matches
  1.2630 +all vertices of the graph, is called a {\it perfect matching}.
  1.2631 +Obviously, a perfect matching in bipartite graph $G=(R\cup S,E)$
  1.2632 +defines some bijection $R\leftrightarrow S$.
  1.2633 +
  1.2634 +The {\it assignment problem} has two different variants. In the first
  1.2635 +variant the problem is to find matching (assignment) $M$, which
  1.2636 +maximizes the sum:
  1.2637 +$$\sum_{(i,j)\in M}c_{ij}\eqno(10)$$
  1.2638 +(so this variant is also called the {\it maximum weighted bipartite
  1.2639 +matching problem} or, if all $c_{ij}=1$, the {\it maximum cardinality
  1.2640 +bipartite matching problem}). In the second, classic variant the
  1.2641 +problem is to find {\it perfect} matching (assignment) $M$, which
  1.2642 +minimizes or maximizes the sum (10).
  1.2643 +
  1.2644 +An example of the assignment problem, which is the maximum weighted
  1.2645 +bipartite matching problem, is shown on Fig. 3.
  1.2646 +
  1.2647 +The maximum weighted bipartite matching problem can be naturally
  1.2648 +formulated as the following LP problem:
  1.2649 +
  1.2650 +\medskip
  1.2651 +
  1.2652 +\noindent
  1.2653 +\hspace{.5in}maximize
  1.2654 +$$z=\sum_{(i,j)\in E}c_{ij}x_{ij}\eqno(11)$$
  1.2655 +\hspace{.5in}subject to
  1.2656 +$$\sum_{(i,j)\in E}x_{ij}\leq 1\ \ \ \hbox{for all}\ i\in R\eqno(12)$$
  1.2657 +$$\sum_{(i,j)\in E}x_{ij}\leq 1\ \ \ \hbox{for all}\ j\in S\eqno(13)$$
  1.2658 +$$\ \ \ \ \ \ \ \ 0\leq x_{ij}\leq 1\ \ \ \hbox{for all}\ (i,j)\in E
  1.2659 +\eqno(14)$$
  1.2660 +
  1.2661 +\medskip
  1.2662 +
  1.2663 +\noindent
  1.2664 +where $x_{ij}=1$ means that $(i,j)\in M$, and $x_{ij}=0$ means that
  1.2665 +$(i,j)\notin M$.\footnote{The constraint matrix of LP formulation
  1.2666 +(11)---(14) is totally unimodular, due to which $x_{ij}\in\{0,1\}$ for
  1.2667 +any basic solution.}
  1.2668 +
  1.2669 +\newpage
  1.2670 +
  1.2671 +\bigskip
  1.2672 +
  1.2673 +\noindent\hfil
  1.2674 +\xymatrix @C=48pt
  1.2675 +{v_1\ar@{-}[rr]|{_{13}}\ar@{-}[rrd]|{_{21}}\ar@{-}[rrddd]|(.2){_{20}}&&
  1.2676 +v_9\\
  1.2677 +v_2\ar@{-}[rr]|{_{12}}\ar@{-}[rrdd]|(.3){_{8}}
  1.2678 +\ar@{-}[rrddd]|(.4){_{26}}&&v_{10}\\
  1.2679 +v_3\ar@{-}[rr]|(.2){_{22}}\ar@{-}[rrdd]|(.3){_{11}}&&v_{11}\\
  1.2680 +v_4\ar@{-}[rruuu]|(.6){_{12}}\ar@{-}[rr]|(.2){_{36}}
  1.2681 +\ar@{-}[rrdd]|(.7){_{25}}&&v_{12}\\
  1.2682 +v_5\ar@{-}[rruu]|(.42){_{41}}\ar@{-}[rru]|(.4){_{40}}
  1.2683 +\ar@{-}[rr]|(.75){_{11}}\ar@{-}[rrd]|(.6){_{4}}\ar@{-}[rrdd]|{_{8}}
  1.2684 +\ar@{-}[rrddd]|{_{35}}\ar@{-}[rrdddd]|{_{32}}&&v_{13}\\
  1.2685 +v_6\ar@{-}[rruuuuu]|(.7){_{13}}&&v_{14}\\
  1.2686 +v_7\ar@{-}[rruuuuu]|(.15){_{19}}&&v_{15}\\
  1.2687 +v_8\ar@{-}[rruuuuuu]|(.25){_{39}}\ar@{-}[rruuuuu]|(.65){_{15}}&&
  1.2688 +v_{16}\\
  1.2689 +&&v_{17}\\
  1.2690 +}
  1.2691 +
  1.2692 +\bigskip
  1.2693 +
  1.2694 +\noindent\hfil
  1.2695 +Fig.~3. An example of the assignment problem.
  1.2696 +
  1.2697 +\bigskip
  1.2698 +
  1.2699 +Similarly, the perfect assignment problem can be naturally formulated
  1.2700 +as the following LP problem:
  1.2701 +
  1.2702 +\medskip
  1.2703 +
  1.2704 +\noindent
  1.2705 +\hspace{.5in}minimize (or maximize)
  1.2706 +$$z=\sum_{(i,j)\in E}c_{ij}x_{ij}\eqno(15)$$
  1.2707 +\hspace{.5in}subject to
  1.2708 +$$\sum_{(i,j)\in E}x_{ij}=1\ \ \ \hbox{for all}\ i\in R\eqno(16)$$
  1.2709 +$$\sum_{(i,j)\in E}x_{ij}=1\ \ \ \hbox{for all}\ j\in S\eqno(17)$$
  1.2710 +$$\ \ \ \ \ \ \ \ 0\leq x_{ij}\leq 1\ \ \ \hbox{for all}\ (i,j)\in E
  1.2711 +\eqno(18)$$
  1.2712 +
  1.2713 +\medskip
  1.2714 +
  1.2715 +\noindent
  1.2716 +where variables $x_{ij}$ have the same meaning as for (11)---(14)
  1.2717 +above.
  1.2718 +
  1.2719 +\newpage
  1.2720 +
  1.2721 +In GLPK an undirected bipartite graph $G=(R\cup S,E)$ is represented as
  1.2722 +directed graph $\overline{G}=(V,A)$, where $V=R\cup S$ and
  1.2723 +$A=\{(i,j):(i,j)\in E\}$, i.e. every edge $(i,j)\in E$ in $G$
  1.2724 +corresponds to arc $(i\rightarrow j)\in A$ in $\overline{G}$.
  1.2725 +
  1.2726 +\subsection{glp\_read\_asnprob---read assignment problem data in\\DIMACS
  1.2727 +format}
  1.2728 +
  1.2729 +\subsubsection*{Synopsis}
  1.2730 +
  1.2731 +\begin{verbatim}
  1.2732 +int glp_read_asnprob(glp_graph *G, int v_set, int a_cost,
  1.2733 +      const char *fname);
  1.2734 +\end{verbatim}
  1.2735 +
  1.2736 +\subsubsection*{Description}
  1.2737 +
  1.2738 +The routine \verb|glp_read_asnprob| reads the assignment problem data
  1.2739 +from a text file in DIMACS format.
  1.2740 +
  1.2741 +The parameter \verb|G| specifies the graph object, to which the problem
  1.2742 +data have to be stored. Note that before reading data the current
  1.2743 +content of the graph object is completely erased with the routine
  1.2744 +\verb|glp_erase_graph|.
  1.2745 +
  1.2746 +The parameter \verb|v_set| specifies an offset of the field of type
  1.2747 +\verb|int| in the vertex data block, to which the routine stores the
  1.2748 +node set indicator:
  1.2749 +
  1.2750 +0 --- the node is in set $R$;
  1.2751 +
  1.2752 +1 --- the node is in set $S$.
  1.2753 +
  1.2754 +\noindent
  1.2755 +If \verb|v_set| $<0$, the node set indicator is not stored.
  1.2756 +
  1.2757 +The parameter \verb|a_cost| specifies an offset of the field of type
  1.2758 +\verb|double| in the arc data block, to which the routine stores the
  1.2759 +edge cost $c_{ij}$. If \verb|a_cost| $<0$, the edge cost is not stored.
  1.2760 +
  1.2761 +The character string \verb|fname| specifies the name of a text file to
  1.2762 +be read in. (If the file name name ends with the suffix `\verb|.gz|',
  1.2763 +the file is assumed to be compressed, in which case the routine
  1.2764 +decompresses it ``on the fly''.)
  1.2765 +
  1.2766 +\subsubsection*{Returns}
  1.2767 +
  1.2768 +If the operation was successful, the routine returns zero. Otherwise,
  1.2769 +it prints an error message and returns non-zero.
  1.2770 +
  1.2771 +\newpage
  1.2772 +
  1.2773 +\subsubsection*{Example}
  1.2774 +
  1.2775 +\begin{footnotesize}
  1.2776 +\begin{verbatim}
  1.2777 +typedef struct
  1.2778 +{     /* vertex data block */
  1.2779 +      ...
  1.2780 +      int set;
  1.2781 +      ...
  1.2782 +} v_data;
  1.2783 +
  1.2784 +typedef struct
  1.2785 +{     /* arc data block */
  1.2786 +      ...
  1.2787 +      double cost;
  1.2788 +      ...
  1.2789 +} a_data;
  1.2790 +
  1.2791 +int main(void)
  1.2792 +{     glp_graph *G;
  1.2793 +      int ret;
  1.2794 +      G = glp_create_graph(sizeof(v_data), sizeof(a_data));
  1.2795 +      ret = glp_read_asnprob(G, offsetof(v_data, set),
  1.2796 +         offsetof(a_data, cost), "sample.asn");
  1.2797 +      if (ret != 0) goto ...
  1.2798 +      ...
  1.2799 +}
  1.2800 +\end{verbatim}
  1.2801 +\end{footnotesize}
  1.2802 +
  1.2803 +\subsubsection*{DIMACS assignment problem format\footnote{This
  1.2804 +material is based on the paper ``The First DIMACS International
  1.2805 +Algorithm Implementation Challenge: Problem Definitions and
  1.2806 +Specifications'', which is publically available at
  1.2807 +{\tt http://dimacs.rutgers.edu/Challenges/}.}}
  1.2808 +\label{subsecasnprob}
  1.2809 +
  1.2810 +The DIMACS input file is a plain ASCII text file. It contains
  1.2811 +{\it lines} of several types described below. A line is terminated with
  1.2812 +an end-of-line character. Fields in each line are separated by at least
  1.2813 +one blank space. Each line begins with a one-character designator to
  1.2814 +identify the line type.
  1.2815 +
  1.2816 +Note that DIMACS requires all numerical quantities to be integers in
  1.2817 +the range $[-2^{31},\ 2^{31}-1]$ while GLPK allows the quantities to be
  1.2818 +floating-point numbers.
  1.2819 +
  1.2820 +\paragraph{Comment lines.} Comment lines give human-readable information
  1.2821 +about the file and are ignored by programs. Comment lines can appear
  1.2822 +anywhere in the file. Each comment line begins with a lower-case
  1.2823 +character \verb|c|.
  1.2824 +
  1.2825 +\begin{verbatim}
  1.2826 +   c This is a comment line
  1.2827 +\end{verbatim}
  1.2828 +
  1.2829 +\newpage
  1.2830 +
  1.2831 +\paragraph{Problem line.} There is one problem line per data file. The
  1.2832 +problem line must appear before any node or arc descriptor lines. It has
  1.2833 +the following format:
  1.2834 +
  1.2835 +\begin{verbatim}
  1.2836 +   p asn NODES EDGES
  1.2837 +\end{verbatim}
  1.2838 +
  1.2839 +\noindent
  1.2840 +The lower-case character \verb|p| signifies that this is a problem line.
  1.2841 +The three-character problem designator \verb|asn| identifies the file as
  1.2842 +containing specification information for the assignment problem.
  1.2843 +The \verb|NODES| field contains an integer value specifying the total
  1.2844 +number of nodes in the graph (i.e. in both sets $R$ and $S$). The
  1.2845 +\verb|EDGES| field contains an integer value specifying the number of
  1.2846 +edges in the graph.
  1.2847 +
  1.2848 +\paragraph{Node descriptors.} All node descriptor lines must appear
  1.2849 +before all edge descriptor lines. The node descriptor lines lists the
  1.2850 +nodes in set $R$ only, and all other nodes are assumed to be in set
  1.2851 +$S$. There is one node descriptor line for each such node, with the
  1.2852 +following format:
  1.2853 +
  1.2854 +\begin{verbatim}
  1.2855 +   n ID
  1.2856 +\end{verbatim}
  1.2857 +
  1.2858 +\noindent
  1.2859 +The lower-case character \verb|n| signifies that this is a node
  1.2860 +descriptor line. The \verb|ID| field gives a node identification number,
  1.2861 +an integer between 1 and \verb|NODES|.
  1.2862 +
  1.2863 +\paragraph{Edge descriptors.} There is one edge descriptor line for
  1.2864 +each edge in the graph. Edge descriptor lines are of the following
  1.2865 +format:
  1.2866 +
  1.2867 +\begin{verbatim}
  1.2868 +   a SRC DST COST
  1.2869 +\end{verbatim}
  1.2870 +
  1.2871 +\noindent
  1.2872 +The lower-case character \verb|a| signifies that this is an edge
  1.2873 +descriptor line. For each edge $(i,j)$, where $i\in R$ and $j\in S$,
  1.2874 +the \verb|SRC| field gives the identification number of vertex $i$, and
  1.2875 +the \verb|DST| field gives the identification number of vertex $j$.
  1.2876 +Identification numbers are integers between 1 and \verb|NODES|. The
  1.2877 +\verb|COST| field contains the cost of edge $(i,j)$.
  1.2878 +
  1.2879 +\paragraph{Example.} Below here is an example of the data file in
  1.2880 +DIMACS format corresponding to the assignment problem shown on Fig~3.
  1.2881 +
  1.2882 +\newpage
  1.2883 +
  1.2884 +\begin{footnotesize}
  1.2885 +\begin{verbatim}
  1.2886 +c sample.asn
  1.2887 +c
  1.2888 +c This is an example of the assignment problem data
  1.2889 +c in DIMACS format.
  1.2890 +c
  1.2891 +p asn 17 22
  1.2892 +c
  1.2893 +n 1
  1.2894 +n 2
  1.2895 +n 3
  1.2896 +n 4
  1.2897 +n 5
  1.2898 +n 6
  1.2899 +n 7
  1.2900 +n 8
  1.2901 +c
  1.2902 +a 1  9 13
  1.2903 +a 1 10 21
  1.2904 +a 1 12 20
  1.2905 +a 2 10 12
  1.2906 +a 2 12  8
  1.2907 +a 2 13 26
  1.2908 +a 3 11 22
  1.2909 +a 3 13 11
  1.2910 +a 4  9 12
  1.2911 +a 4 12 36
  1.2912 +a 4 14 25
  1.2913 +a 5 11 41
  1.2914 +a 5 12 40
  1.2915 +a 5 13 11
  1.2916 +a 5 14  4
  1.2917 +a 5 15  8
  1.2918 +a 5 16 35
  1.2919 +a 5 17 32
  1.2920 +a 6  9 13
  1.2921 +a 7 10 19
  1.2922 +a 8 10 39
  1.2923 +a 8 11 15
  1.2924 +c
  1.2925 +c eof
  1.2926 +\end{verbatim}
  1.2927 +\end{footnotesize}
  1.2928 +
  1.2929 +\newpage
  1.2930 +
  1.2931 +\subsection{glp\_write\_asnprob---write assignment problem data in\\
  1.2932 +DIMACS format}
  1.2933 +
  1.2934 +\subsubsection*{Synopsis}
  1.2935 +
  1.2936 +\begin{verbatim}
  1.2937 +int glp_write_asnprob(glp_graph *G, int v_set, int a_cost,
  1.2938 +      const char *fname);
  1.2939 +\end{verbatim}
  1.2940 +
  1.2941 +\subsubsection*{Description}
  1.2942 +
  1.2943 +The routine \verb|glp_write_asnprob| writes the assignment problem data
  1.2944 +to a text file in DIMACS format.
  1.2945 +
  1.2946 +The parameter \verb|G| is the graph program object, which specifies the
  1.2947 +assignment problem instance.
  1.2948 +
  1.2949 +The parameter \verb|v_set| specifies an offset of the field of type
  1.2950 +\verb|int| in the vertex data block, which contains the node set
  1.2951 +indicator:
  1.2952 +
  1.2953 +0 --- the node is in set $R$;
  1.2954 +
  1.2955 +1 --- the node is in set $S$.
  1.2956 +
  1.2957 +\noindent
  1.2958 +If \verb|v_set| $<0$, it is assumed that a node having no incoming arcs
  1.2959 +is in set $R$, and a node having no outgoing arcs is in set $S$.
  1.2960 +
  1.2961 +The parameter \verb|a_cost| specifies an offset of the field of type
  1.2962 +\verb|double| in the arc data block, which contains $c_{ij}$, the edge
  1.2963 +cost. If \verb|a_cost| $<0$, it is assumed that $c_{ij}=1$ for all
  1.2964 +edges.
  1.2965 +
  1.2966 +The character string \verb|fname| specifies a name of the text file to
  1.2967 +be written out. (If the file name ends with suffix `\verb|.gz|', the
  1.2968 +file is assumed to be compressed, in which case the routine performs
  1.2969 +automatic compression on writing it.)
  1.2970 +
  1.2971 +\subsubsection*{Note}
  1.2972 +
  1.2973 +The routine \verb|glp_write_asnprob| does not check that the specified
  1.2974 +graph object correctly represents a bipartite graph. To make sure that
  1.2975 +the problem data are correct, use the routine \verb|glp_check_asnprob|.
  1.2976 +
  1.2977 +\subsubsection*{Returns}
  1.2978 +
  1.2979 +If the operation was successful, the routine returns zero. Otherwise,
  1.2980 +it prints an error message and returns non-zero.
  1.2981 +
  1.2982 +\newpage
  1.2983 +
  1.2984 +\subsection{glp\_check\_asnprob---check correctness of assignment
  1.2985 +problem data}
  1.2986 +
  1.2987 +\subsubsection*{Synopsis}
  1.2988 +
  1.2989 +\begin{verbatim}
  1.2990 +int glp_check_asnprob(glp_graph *G, int v_set);
  1.2991 +\end{verbatim}
  1.2992 +
  1.2993 +\subsubsection*{Description}
  1.2994 +
  1.2995 +The routine \verb|glp_check_asnprob| checks that the specified graph
  1.2996 +object \verb|G| correctly represents a bipartite graph.
  1.2997 +
  1.2998 +The parameter \verb|v_set| specifies an offset of the field of type
  1.2999 +\verb|int| in the vertex data block, which contains the node set
  1.3000 +indicator:
  1.3001 +
  1.3002 +0 --- the node is in set $R$;
  1.3003 +
  1.3004 +1 --- the node is in set $S$.
  1.3005 +
  1.3006 +\noindent
  1.3007 +If \verb|v_set| $<0$, it is assumed that a node having no incoming arcs
  1.3008 +is in set $R$, and a node having no outgoing arcs is in set $S$.
  1.3009 +
  1.3010 +\subsubsection*{Returns}
  1.3011 +
  1.3012 +The routine \verb|glp_check_asnprob| may return the following codes:
  1.3013 +
  1.3014 +0 --- the data are correct;
  1.3015 +
  1.3016 +1 --- the set indicator of some node is 0, however, that node has one
  1.3017 +or more incoming arcs;
  1.3018 +
  1.3019 +2 --- the set indicator of some node is 1, however, that node has one
  1.3020 +or more outgoing arcs;
  1.3021 +
  1.3022 +3 --- the set indicator of some node is invalid (neither 0 nor 1);
  1.3023 +
  1.3024 +4 --- some node has both incoming and outgoing arcs.
  1.3025 +
  1.3026 +\subsection{glp\_asnprob\_lp---convert assignment problem to LP}
  1.3027 +
  1.3028 +\subsubsection*{Synopsis}
  1.3029 +
  1.3030 +\begin{verbatim}
  1.3031 +int glp_asnprob_lp(glp_prob *P, int form, glp_graph *G,
  1.3032 +      int names, int v_set, int a_cost);
  1.3033 +\end{verbatim}
  1.3034 +
  1.3035 +\subsubsection*{Description}
  1.3036 +
  1.3037 +The routine \verb|glp_asnprob_lp| builds LP problem, which corresponds
  1.3038 +to the specified assignment problem.
  1.3039 +
  1.3040 +The parameter \verb|lp| is the resultant LP problem object to be built.
  1.3041 +Note that on entry its current content is erased with the routine
  1.3042 +\verb|glp_erase_prob|.
  1.3043 +
  1.3044 +The parameter \verb|form| defines which LP formulation should be used:
  1.3045 +
  1.3046 +\verb|GLP_ASN_MIN| --- perfect matching (15)---(18), minimization;
  1.3047 +
  1.3048 +\verb|GLP_ASN_MAX| --- perfect matching (15)---(18), maximization;
  1.3049 +
  1.3050 +\verb|GLP_ASN_MMP| --- maximum weighted matching (11)---(14).
  1.3051 +
  1.3052 +The parameter \verb|G| is the graph program object, which specifies the
  1.3053 +assignment problem instance.
  1.3054 +
  1.3055 +The parameter \verb|names| is a flag. If it is \verb|GLP_ON|, the
  1.3056 +routine uses symbolic names of the graph object components to assign
  1.3057 +symbolic names to the LP problem object components. If the \verb|flag|
  1.3058 +is \verb|GLP_OFF|, no symbolic names are assigned.
  1.3059 +
  1.3060 +The parameter \verb|v_set| specifies an offset of the field of type
  1.3061 +\verb|int| in the vertex data block, which contains the node set
  1.3062 +indicator:
  1.3063 +
  1.3064 +0 --- the node is in set $R$;
  1.3065 +
  1.3066 +1 --- the node is in set $S$.
  1.3067 +
  1.3068 +\noindent
  1.3069 +If \verb|v_set| $<0$, it is assumed that a node having no incoming arcs
  1.3070 +is in set $R$, and a node having no outgoing arcs is in set $S$.
  1.3071 +
  1.3072 +The parameter \verb|a_cost| specifies an offset of the field of type
  1.3073 +\verb|double| in the arc data block, which contains $c_{ij}$, the edge
  1.3074 +cost. If \verb|a_cost| $<0$, it is assumed that $c_{ij}=1$ for all
  1.3075 +edges.
  1.3076 +
  1.3077 +\subsubsection*{Returns}
  1.3078 +
  1.3079 +If the LP problem has been successfully built, the routine
  1.3080 +\verb|glp_asnprob_lp| returns zero, otherwise, non-zero (see the
  1.3081 +routine \verb|glp_check_asnprob|).
  1.3082 +
  1.3083 +\subsubsection*{Example}
  1.3084 +
  1.3085 +The example program below reads the assignment problem instance in
  1.3086 +DIMACS format from file `\verb|sample.asn|', converts the instance to
  1.3087 +LP (11)---(14), and writes the resultant LP in CPLEX format to file
  1.3088 +`\verb|matching.lp|'.
  1.3089 +
  1.3090 +\begin{footnotesize}
  1.3091 +\begin{verbatim}
  1.3092 +#include <stddef.h>
  1.3093 +#include <glpk.h>
  1.3094 +
  1.3095 +typedef struct { int set; } v_data;
  1.3096 +typedef struct { double cost; } a_data;
  1.3097 +
  1.3098 +int main(void)
  1.3099 +{     glp_graph *G;
  1.3100 +      glp_prob *P;
  1.3101 +      G = glp_create_graph(sizeof(v_data), sizeof(a_data));
  1.3102 +      glp_read_asnprob(G, offsetof(v_data, set),
  1.3103 +         offsetof(a_data, cost), "sample.asn");
  1.3104 +      P = glp_create_prob();
  1.3105 +      glp_asnprob_lp(P, GLP_ASN_MMP, G, GLP_ON,
  1.3106 +         offsetof(v_data, set), offsetof(a_data, cost));
  1.3107 +      glp_delete_graph(G);
  1.3108 +      glp_write_lp(P, NULL, "matching.lp");
  1.3109 +      glp_delete_prob(P);
  1.3110 +      return 0;
  1.3111 +}
  1.3112 +\end{verbatim}
  1.3113 +\end{footnotesize}
  1.3114 +
  1.3115 +If `\verb|sample.asn|' is the example data file from the subsection
  1.3116 +describing the routine \verb|glp_read_asnprob|, file
  1.3117 +`\verb|matching.lp|' may look like follows:
  1.3118 +
  1.3119 +\begin{footnotesize}
  1.3120 +\begin{verbatim}
  1.3121 +Maximize
  1.3122 + obj: + 20 x(1,12) + 21 x(1,10) + 13 x(1,9) + 26 x(2,13) + 8 x(2,12)
  1.3123 + + 12 x(2,10) + 11 x(3,13) + 22 x(3,11) + 25 x(4,14) + 36 x(4,12)
  1.3124 + + 12 x(4,9) + 32 x(5,17) + 35 x(5,16) + 8 x(5,15) + 4 x(5,14)
  1.3125 + + 11 x(5,13) + 40 x(5,12) + 41 x(5,11) + 13 x(6,9) + 19 x(7,10)
  1.3126 + + 15 x(8,11) + 39 x(8,10)
  1.3127 +
  1.3128 +Subject To
  1.3129 + r_1: + x(1,9) + x(1,10) + x(1,12) <= 1
  1.3130 + r_2: + x(2,10) + x(2,12) + x(2,13) <= 1
  1.3131 + r_3: + x(3,11) + x(3,13) <= 1
  1.3132 + r_4: + x(4,9) + x(4,12) + x(4,14) <= 1
  1.3133 + r_5: + x(5,11) + x(5,12) + x(5,13) + x(5,14) + x(5,15) + x(5,16)
  1.3134 + + x(5,17) <= 1
  1.3135 + r_6: + x(6,9) <= 1
  1.3136 + r_7: + x(7,10) <= 1
  1.3137 + r_8: + x(8,10) + x(8,11) <= 1
  1.3138 + r_9: + x(6,9) + x(4,9) + x(1,9) <= 1
  1.3139 + r_10: + x(8,10) + x(7,10) + x(2,10) + x(1,10) <= 1
  1.3140 + r_11: + x(8,11) + x(5,11) + x(3,11) <= 1
  1.3141 + r_12: + x(5,12) + x(4,12) + x(2,12) + x(1,12) <= 1
  1.3142 + r_13: + x(5,13) + x(3,13) + x(2,13) <= 1
  1.3143 + r_14: + x(5,14) + x(4,14) <= 1
  1.3144 + r_15: + x(5,15) <= 1
  1.3145 + r_16: + x(5,16) <= 1
  1.3146 + r_17: + x(5,17) <= 1
  1.3147 +
  1.3148 +Bounds
  1.3149 + 0 <= x(1,12) <= 1
  1.3150 + 0 <= x(1,10) <= 1
  1.3151 + 0 <= x(1,9) <= 1
  1.3152 + 0 <= x(2,13) <= 1
  1.3153 + 0 <= x(2,12) <= 1
  1.3154 + 0 <= x(2,10) <= 1
  1.3155 + 0 <= x(3,13) <= 1
  1.3156 + 0 <= x(3,11) <= 1
  1.3157 + 0 <= x(4,14) <= 1
  1.3158 + 0 <= x(4,12) <= 1
  1.3159 + 0 <= x(4,9) <= 1
  1.3160 + 0 <= x(5,17) <= 1
  1.3161 + 0 <= x(5,16) <= 1
  1.3162 + 0 <= x(5,15) <= 1
  1.3163 + 0 <= x(5,14) <= 1
  1.3164 + 0 <= x(5,13) <= 1
  1.3165 + 0 <= x(5,12) <= 1
  1.3166 + 0 <= x(5,11) <= 1
  1.3167 + 0 <= x(6,9) <= 1
  1.3168 + 0 <= x(7,10) <= 1
  1.3169 + 0 <= x(8,11) <= 1
  1.3170 + 0 <= x(8,10) <= 1
  1.3171 +
  1.3172 +End
  1.3173 +\end{verbatim}
  1.3174 +\end{footnotesize}
  1.3175 +
  1.3176 +\subsection{glp\_asnprob\_okalg---solve assignment problem with
  1.3177 +out-of-kilter algorithm}
  1.3178 +
  1.3179 +\subsubsection*{Synopsis}
  1.3180 +
  1.3181 +\begin{verbatim}
  1.3182 +int glp_asnprob_okalg(int form, glp_graph *G, int v_set,
  1.3183 +      int a_cost, double *sol, int a_x);
  1.3184 +\end{verbatim}
  1.3185 +
  1.3186 +\subsubsection*{Description}
  1.3187 +
  1.3188 +The routine \verb|glp_mincost_okalg| finds optimal solution to the
  1.3189 +assignment problem with the out-of-kilter
  1.3190 +algorithm.\footnote{GLPK implementation of the out-of-kilter algorithm
  1.3191 +is based on the following book: L.~R.~Ford,~Jr., and D.~R.~Fulkerson,
  1.3192 +``Flows in Networks,'' The RAND Corp., Report R-375-PR (August 1962),
  1.3193 +Chap. III ``Minimal Cost Flow Problems,'' pp.~113-26.} Note that this
  1.3194 +routine requires all the problem data to be integer-valued.
  1.3195 +
  1.3196 +The parameter \verb|form| defines which LP formulation should be used:
  1.3197 +
  1.3198 +\verb|GLP_ASN_MIN| --- perfect matching (15)---(18), minimization;
  1.3199 +
  1.3200 +\verb|GLP_ASN_MAX| --- perfect matching (15)---(18), maximization;
  1.3201 +
  1.3202 +\verb|GLP_ASN_MMP| --- maximum weighted matching (11)---(14).
  1.3203 +
  1.3204 +The parameter \verb|G| is the graph program object, which specifies the
  1.3205 +assignment problem instance.
  1.3206 +
  1.3207 +The parameter \verb|v_set| specifies an offset of the field of type
  1.3208 +\verb|int| in the vertex data block, which contains the node set
  1.3209 +indicator:
  1.3210 +
  1.3211 +0 --- the node is in set $R$;
  1.3212 +
  1.3213 +1 --- the node is in set $S$.
  1.3214 +
  1.3215 +\newpage
  1.3216 +
  1.3217 +\noindent
  1.3218 +If \verb|v_set| $<0$, it is assumed that a node having no incoming arcs
  1.3219 +is in set $R$, and a node having no outgoing arcs is in set $S$.
  1.3220 +
  1.3221 +The parameter \verb|a_cost| specifies an offset of the field of type
  1.3222 +\verb|double| in the arc data block, which contains $c_{ij}$, the edge
  1.3223 +cost. This value must be integer in the range [\verb|-INT_MAX|,
  1.3224 +\verb|+INT_MAX|]. If \verb|a_cost| $<0$, it is assumed that $c_{ij}=1$
  1.3225 +for all edges.
  1.3226 +
  1.3227 +The parameter \verb|sol| specifies a location, to which the routine
  1.3228 +stores the objective value (that is, the total cost) found.
  1.3229 +If \verb|sol| is \verb|NULL|, the objective value is not stored.
  1.3230 +
  1.3231 +The parameter \verb|a_x| specifies an offset of the field of type
  1.3232 +\verb|int| in the arc data block, to which the routine stores $x_{ij}$.
  1.3233 +If \verb|a_x| $<0$, this value is not stored.
  1.3234 +
  1.3235 +\subsubsection*{Returns}
  1.3236 +
  1.3237 +\def\arraystretch{1}
  1.3238 +
  1.3239 +\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
  1.3240 +0 & Optimal solution found.\\
  1.3241 +\verb|GLP_ENOPFS| & No (primal) feasible solution exists.\\
  1.3242 +\verb|GLP_EDATA| & Unable to start the search, because the assignment
  1.3243 +problem data are either incorrect (this error is detected by the
  1.3244 +routine \verb|glp_check_asnprob|), not integer-valued or out of range.\\
  1.3245 +\verb|GLP_ERANGE| & The search was prematurely terminated because of
  1.3246 +integer overflow.\\
  1.3247 +\verb|GLP_EFAIL| & An error has been detected in the program logic.
  1.3248 +(If this code is returned for your problem instance, please report to
  1.3249 +\verb|<bug-glpk@gnu.org>|.)\\
  1.3250 +\end{tabular}
  1.3251 +
  1.3252 +\subsubsection*{Comments}
  1.3253 +
  1.3254 +Since the out-of-kilter algorithm is designed to find a minimal cost
  1.3255 +circulation, the routine \verb|glp_asnprob_okalg| converts the original
  1.3256 +graph to a network suitable for this algorithm in the following
  1.3257 +way:\footnote{The conversion is performed internally and does not change
  1.3258 +the original graph program object passed to the routine.}
  1.3259 +
  1.3260 +1) it replaces each edge $(i,j)$ by arc $(i\rightarrow j)$,
  1.3261 +flow $x_{ij}$ through which has zero lower bound ($l_{ij}=0$), unity
  1.3262 +upper bound ($u_{ij}=1$), and per-unit cost $+c_{ij}$ (in case of
  1.3263 +\verb|GLP_ASN_MIN|), or $-c_{ij}$ (in case of \verb|GLP_ASN_MAX| and
  1.3264 +\verb|GLP_ASN_MMP|);
  1.3265 +
  1.3266 +2) then it adds one auxiliary feedback node $k$;
  1.3267 +
  1.3268 +\newpage
  1.3269 +
  1.3270 +3) for each original node $i\in R$ the routine adds auxiliary supply
  1.3271 +arc $(k\rightarrow i)$, flow $x_{ki}$ through which is costless
  1.3272 +($c_{ki}=0$) and either fixed at 1 ($l_{ki}=u_{ki}=1$, in case of
  1.3273 +\verb|GLP_ASN_MIN| and \verb|GLP_ASN_MAX|) or has zero lower bound and
  1.3274 +unity upper bound ($l_{ij}=0$, $u_{ij}=1$, in case of
  1.3275 +\verb|GLP_ASN_MMP|);
  1.3276 +
  1.3277 +4) similarly, for each original node $j\in S$ the routine adds
  1.3278 +auxiliary demand arc $(j\rightarrow k)$, flow $x_{jk}$ through which is
  1.3279 +costless ($c_{jk}=0$) and either fixed at 1 ($l_{jk}=u_{jk}=1$, in case
  1.3280 +of \verb|GLP_ASN_MIN| and \verb|GLP_ASN_MAX|) or has zero lower bound
  1.3281 +and unity upper bound ($l_{jk}=0$, $u_{jk}=1$, in case of
  1.3282 +\verb|GLP_ASN_MMP|).
  1.3283 +
  1.3284 +\subsubsection*{Example}
  1.3285 +
  1.3286 +The example program shown below reads the assignment problem instance
  1.3287 +in DIMACS format from file `\verb|sample.asn|', solves it by using the
  1.3288 +routine \verb|glp_asnprob_okalg|, and writes the solution found to the
  1.3289 +standard output.
  1.3290 +
  1.3291 +\begin{footnotesize}
  1.3292 +\begin{verbatim}
  1.3293 +#include <stddef.h>
  1.3294 +#include <stdio.h>
  1.3295 +#include <stdlib.h>
  1.3296 +#include <glpk.h>
  1.3297 +
  1.3298 +typedef struct { int set; } v_data;
  1.3299 +typedef struct { double cost; int x; } e_data;
  1.3300 +
  1.3301 +#define node(v) ((v_data *)((v)->data))
  1.3302 +#define edge(e) ((e_data *)((e)->data))
  1.3303 +
  1.3304 +int main(void)
  1.3305 +{     glp_graph *G;
  1.3306 +      glp_vertex *v;
  1.3307 +      glp_arc *e;
  1.3308 +      int i, ret;
  1.3309 +      double sol;
  1.3310 +      G = glp_create_graph(sizeof(v_data), sizeof(e_data));
  1.3311 +      glp_read_asnprob(G, offsetof(v_data, set),
  1.3312 +         offsetof(e_data, cost), "sample.asn");
  1.3313 +      ret = glp_asnprob_okalg(GLP_ASN_MMP, G,
  1.3314 +         offsetof(v_data, set), offsetof(e_data, cost), &sol,
  1.3315 +         offsetof(e_data, x));
  1.3316 +      printf("ret = %d; sol = %5g\n", ret, sol);
  1.3317 +      for (i = 1; i <= G->nv; i++)
  1.3318 +      {  v = G->v[i];
  1.3319 +         for (e = v->out; e != NULL; e = e->t_next)
  1.3320 +            printf("edge %2d %2d: x = %d; c = %g\n",
  1.3321 +               e->tail->i, e->head->i, edge(e)->x, edge(e)->cost);
  1.3322 +      }
  1.3323 +      glp_delete_graph(G);
  1.3324 +      return 0;
  1.3325 +}
  1.3326 +\end{verbatim}
  1.3327 +\end{footnotesize}
  1.3328 +
  1.3329 +If `\verb|sample.asn|' is the example data file from the subsection
  1.3330 +describing the routine \verb|glp_read_asnprob|, the output may look
  1.3331 +like follows:
  1.3332 +
  1.3333 +\begin{footnotesize}
  1.3334 +\begin{verbatim}
  1.3335 +Reading assignment problem data from `sample.asn'...
  1.3336 +Assignment problem has 8 + 9 = 17 nodes and 22 arcs
  1.3337 +38 lines were read
  1.3338 +ret = 0; sol =   180
  1.3339 +edge  1 12: x = 1; c = 20
  1.3340 +edge  1 10: x = 0; c = 21
  1.3341 +edge  1  9: x = 0; c = 13
  1.3342 +edge  2 13: x = 1; c = 26
  1.3343 +edge  2 12: x = 0; c = 8
  1.3344 +edge  2 10: x = 0; c = 12
  1.3345 +edge  3 13: x = 0; c = 11
  1.3346 +edge  3 11: x = 1; c = 22
  1.3347 +edge  4 14: x = 1; c = 25
  1.3348 +edge  4 12: x = 0; c = 36
  1.3349 +edge  4  9: x = 0; c = 12
  1.3350 +edge  5 17: x = 0; c = 32
  1.3351 +edge  5 16: x = 1; c = 35
  1.3352 +edge  5 15: x = 0; c = 8
  1.3353 +edge  5 14: x = 0; c = 4
  1.3354 +edge  5 13: x = 0; c = 11
  1.3355 +edge  5 12: x = 0; c = 40
  1.3356 +edge  5 11: x = 0; c = 41
  1.3357 +edge  6  9: x = 1; c = 13
  1.3358 +edge  7 10: x = 0; c = 19
  1.3359 +edge  8 11: x = 0; c = 15
  1.3360 +edge  8 10: x = 1; c = 39
  1.3361 +\end{verbatim}
  1.3362 +\end{footnotesize}
  1.3363 +
  1.3364 +\newpage
  1.3365 +
  1.3366 +\subsection{glp\_asnprob\_hall---find bipartite matching of maximum
  1.3367 +cardinality}
  1.3368 +
  1.3369 +\subsubsection*{Synopsis}
  1.3370 +
  1.3371 +\begin{verbatim}
  1.3372 +int glp_asnprob_hall(glp_graph *G, int v_set, int a_x);
  1.3373 +\end{verbatim}
  1.3374 +
  1.3375 +\subsubsection*{Description}
  1.3376 +
  1.3377 +The routine \verb|glp_asnprob_hall| finds a matching of maximal
  1.3378 +cardinality in the specified bipartite graph. It uses a version of the
  1.3379 +Fortran routine \verb|MC21A| developed by
  1.3380 +I.~S.~Duff\footnote{I.~S.~Duff, Algorithm 575: Permutations for
  1.3381 +zero-free diagonal, ACM Trans. on Math. Softw. 7 (1981), pp.~387-390.},
  1.3382 +which implements Hall's algorithm.\footnote{M.~Hall, ``An Algorithm for
  1.3383 +Distinct Representatives,'' Am. Math. Monthly 63 (1956), pp.~716-717.}
  1.3384 +
  1.3385 +The parameter \verb|G| is a pointer to the graph program object.
  1.3386 +
  1.3387 +The parameter \verb|v_set| specifies an offset of the field of type
  1.3388 +\verb|int| in the vertex data block, which contains the node set
  1.3389 +indicator:
  1.3390 +
  1.3391 +0 --- the node is in set $R$;
  1.3392 +
  1.3393 +1 --- the node is in set $S$.
  1.3394 +
  1.3395 +\noindent
  1.3396 +If \verb|v_set| $<0$, it is assumed that a node having no incoming arcs
  1.3397 +is in set $R$, and a node having no outgoing arcs is in set $S$.
  1.3398 +
  1.3399 +The parameter \verb|a_x| specifies an offset of the field of type
  1.3400 +\verb|int| in the arc data block, to which the routine stores $x_{ij}$.
  1.3401 +If \verb|a_x| $<0$, this value is not stored.
  1.3402 +
  1.3403 +\subsubsection*{Returns}
  1.3404 +
  1.3405 +The routine \verb|glp_asnprob_hall| returns the cardinality of the
  1.3406 +matching found. However, if the specified graph is incorrect (as
  1.3407 +detected by the routine \verb|glp_check_asnprob|), this routine returns
  1.3408 +a negative value.
  1.3409 +
  1.3410 +\subsubsection*{Comments}
  1.3411 +
  1.3412 +The same solution may be obtained with the routine
  1.3413 +\verb|glp_asnprob_okalg| (for LP formulation \verb|GLP_ASN_MMP| and
  1.3414 +all edge costs equal to 1). However, the routine \verb|glp_asnprob_hall|
  1.3415 +is much faster.
  1.3416 +
  1.3417 +\newpage
  1.3418 +
  1.3419 +\subsubsection*{Example}
  1.3420 +
  1.3421 +The example program shown below reads the assignment problem instance
  1.3422 +in DIMACS format from file `\verb|sample.asn|', finds a bipartite
  1.3423 +matching of maximal cardinality by using the routine
  1.3424 +\verb|glp_asnprob_hall|, and writes the solution found to the standard
  1.3425 +output.
  1.3426 +
  1.3427 +\begin{footnotesize}
  1.3428 +\begin{verbatim}
  1.3429 +#include <stddef.h>
  1.3430 +#include <stdio.h>
  1.3431 +#include <stdlib.h>
  1.3432 +#include <glpk.h>
  1.3433 +
  1.3434 +typedef struct { int set; } v_data;
  1.3435 +typedef struct { int x;   } e_data;
  1.3436 +
  1.3437 +#define node(v) ((v_data *)((v)->data))
  1.3438 +#define edge(e) ((e_data *)((e)->data))
  1.3439 +
  1.3440 +int main(void)
  1.3441 +{     glp_graph *G;
  1.3442 +      glp_vertex *v;
  1.3443 +      glp_arc *e;
  1.3444 +      int i, card;
  1.3445 +      G = glp_create_graph(sizeof(v_data), sizeof(e_data));
  1.3446 +      glp_read_asnprob(G, offsetof(v_data, set), -1,
  1.3447 +         "sample.asn");
  1.3448 +      card = glp_asnprob_hall(G, offsetof(v_data, set),
  1.3449 +         offsetof(e_data, x));
  1.3450 +      printf("card = %d\n", card);
  1.3451 +      for (i = 1; i <= G->nv; i++)
  1.3452 +      {  v = G->v[i];
  1.3453 +         for (e = v->out; e != NULL; e = e->t_next)
  1.3454 +            printf("edge %2d %2d: x = %d\n",
  1.3455 +               e->tail->i, e->head->i, edge(e)->x);
  1.3456 +      }
  1.3457 +      glp_delete_graph(G);
  1.3458 +      return 0;
  1.3459 +}
  1.3460 +\end{verbatim}
  1.3461 +\end{footnotesize}
  1.3462 +
  1.3463 +If `\verb|sample.asn|' is the example data file from the subsection
  1.3464 +describing the routine \verb|glp_read_asnprob|, the output may look
  1.3465 +like follows:
  1.3466 +
  1.3467 +\begin{footnotesize}
  1.3468 +\begin{verbatim}
  1.3469 +Reading assignment problem data from `sample.asn'...
  1.3470 +Assignment problem has 8 + 9 = 17 nodes and 22 arcs
  1.3471 +38 lines were read
  1.3472 +card = 7
  1.3473 +edge  1 12: x = 1
  1.3474 +edge  1 10: x = 0
  1.3475 +edge  1  9: x = 0
  1.3476 +edge  2 13: x = 1
  1.3477 +edge  2 12: x = 0
  1.3478 +edge  2 10: x = 0
  1.3479 +edge  3 13: x = 0
  1.3480 +edge  3 11: x = 1
  1.3481 +edge  4 14: x = 1
  1.3482 +edge  4 12: x = 0
  1.3483 +edge  4  9: x = 0
  1.3484 +edge  5 17: x = 1
  1.3485 +edge  5 16: x = 0
  1.3486 +edge  5 15: x = 0
  1.3487 +edge  5 14: x = 0
  1.3488 +edge  5 13: x = 0
  1.3489 +edge  5 12: x = 0
  1.3490 +edge  5 11: x = 0
  1.3491 +edge  6  9: x = 1
  1.3492 +edge  7 10: x = 1
  1.3493 +edge  8 11: x = 0
  1.3494 +edge  8 10: x = 0
  1.3495 +\end{verbatim}
  1.3496 +\end{footnotesize}
  1.3497 +
  1.3498 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1.3499 +
  1.3500 +\newpage
  1.3501 +
  1.3502 +\section{Critical path problem}
  1.3503 +
  1.3504 +\subsection{Background}
  1.3505 +
  1.3506 +The {\it critical path problem} (CPP) is stated as follows. Let there
  1.3507 +be given a project $J$, which a set of jobs (tasks, activities, etc.).
  1.3508 +Performing each job $i\in J$ requires time $t_i\geq 0$. Besides, over
  1.3509 +the set $J$ there is given a precedence relation $R\subseteq J\times J$,
  1.3510 +where $(i,j)\in R$ means that job $i$ immediately precedes job $j$, i.e.
  1.3511 +performing job $j$ cannot start until job $i$ has been completely
  1.3512 +performed. The problem is to find starting times $x_i$ for each job
  1.3513 +$i\in J$, which satisfy to the precedence relation and minimize the
  1.3514 +total duration (makespan) of the project.
  1.3515 +
  1.3516 +The following is an example of the critical path problem:
  1.3517 +
  1.3518 +\begin{center}
  1.3519 +\begin{tabular}{|c|l|c|c|}
  1.3520 +\hline
  1.3521 +Job&Desription&Time&Predecessors\\
  1.3522 +\hline
  1.3523 +A&Excavate&3&---\\
  1.3524 +B&Lay foundation&4&A\\
  1.3525 +C&Rough plumbing&3&B\\
  1.3526 +D&Frame&10&B\\
  1.3527 +E&Finish exterior&8&D\\
  1.3528 +F&Install HVAC&4&D\\
  1.3529 +G&Rough electric&6&D\\
  1.3530 +H&Sheet rock&8&C, E, F, G\\
  1.3531 +I&Install cabinets&5&H\\
  1.3532 +J&Paint&5&H\\
  1.3533 +K&Final plumbing&4&I\\
  1.3534 +L&Final electric&2&J\\
  1.3535 +M&Install flooring&4&K, L\\
  1.3536 +\hline
  1.3537 +\end{tabular}
  1.3538 +\end{center}
  1.3539 +
  1.3540 +Obviously, the project along with the precedence relation can be
  1.3541 +represented as a directed graph $G=(J,R)$ called {\it project network},
  1.3542 +where each node $i\in J$ corresponds to a job, and arc
  1.3543 +$(i\rightarrow j)\in R$ means that job $i$ immediately precedes job
  1.3544 +$j$.\footnote{There exists another network representation of the
  1.3545 +critical path problem, where jobs correspond to arcs while nodes
  1.3546 +correspond to events introduced to express the precedence relation.
  1.3547 +That representation, however, is much less convenient than the one,
  1.3548 +where jobs are represented as nodes of the network.} The project network
  1.3549 +for the example above is shown on Fig.~4.
  1.3550 +
  1.3551 +May note that the project network must be acyclic; otherwise, it would
  1.3552 +be impossible to satisfy to the precedence relation for any job that
  1.3553 +belongs to a cycle.
  1.3554 +
  1.3555 +\newpage
  1.3556 +
  1.3557 +\xymatrix
  1.3558 +{&&&C|3\ar[rd]&&I|5\ar[r]&K|4\ar[rd]&\\
  1.3559 +A|3\ar[r]&B|4\ar[rru]\ar[rd]&&E|8\ar[r]&H|8\ar[ru]\ar[rd]&&&M|4\\
  1.3560 +&&D|10\ar[ru]\ar[r]\ar[rd]&F|4\ar[ru]&&J|5\ar[r]&L|2\ar[ru]&\\
  1.3561 +&&&G|6\ar[ruu]&&&&\\
  1.3562 +}
  1.3563 +
  1.3564 +\bigskip
  1.3565 +
  1.3566 +\noindent\hfil
  1.3567 +Fig.~4. An example of the project network.
  1.3568 +
  1.3569 +\bigskip
  1.3570 +
  1.3571 +The critical path problem can be naturally formulated as the following
  1.3572 +LP problem:
  1.3573 +
  1.3574 +\medskip
  1.3575 +
  1.3576 +\noindent
  1.3577 +\hspace{.5in}minimize
  1.3578 +$$z\eqno(19)$$
  1.3579 +\hspace{.5in}subject to
  1.3580 +$$x_i+t_i\leq z\ \ \ \hbox{for all}\ i\in J\ \ \ \ \eqno(20)$$
  1.3581 +$$x_i+t_i\leq x_j\ \ \ \hbox{for all}\ (i,j)\in R\eqno(21)$$
  1.3582 +$$x_i\geq 0\ \ \ \ \ \ \ \hbox{for all}\ i\in J\ \ \eqno(22)$$
  1.3583 +
  1.3584 +The inequality constraints (21), which are active in the optimal
  1.3585 +solution, define so called {\it critical path} having the following
  1.3586 +property: the minimal project duration $z$ can be decreased only by
  1.3587 +decreasing the times $t_j$ for jobs on the critical path, and delaying
  1.3588 +any critical job delays the entire project.
  1.3589 +
  1.3590 +\subsection{glp\_cpp---solve critical path problem}
  1.3591 +
  1.3592 +\subsubsection{Synopsis}
  1.3593 +
  1.3594 +\begin{verbatim}
  1.3595 +double glp_cpp(glp_graph *G, int v_t, int v_es, int v_ls);
  1.3596 +\end{verbatim}
  1.3597 +
  1.3598 +\subsubsection{Description}
  1.3599 +
  1.3600 +The routine \verb|glp_cpp| solves the critical path problem represented
  1.3601 +in the form of the project network.
  1.3602 +
  1.3603 +The parameter \verb|G| is a pointer to the graph object, which
  1.3604 +specifies the project network. This graph must be acyclic. Multiple
  1.3605 +arcs are allowed being considered as single arcs.
  1.3606 +
  1.3607 +The parameter \verb|v_t| specifies an offset of the field of type
  1.3608 +\verb|double| in the vertex data block, which contains time $t_i\geq 0$
  1.3609 +needed to perform corresponding job $j\in J$. If \verb|v_t| $<0$, it is
  1.3610 +assumed that $t_i=1$ for all jobs.
  1.3611 +
  1.3612 +The parameter \verb|v_es| specifies an offset of the field of type
  1.3613 +\verb|double| in the vertex data block, to which the routine stores
  1.3614 +the {\it earliest start time} for corresponding job. If \verb|v_es|
  1.3615 +$<0$, this time is not stored.
  1.3616 +
  1.3617 +The parameter \verb|v_ls| specifies an offset of the field of type
  1.3618 +\verb|double| in the vertex data block, to which the routine stores
  1.3619 +the {\it latest start time} for corresponding job. If \verb|v_ls|
  1.3620 +$<0$, this time is not stored.
  1.3621 +
  1.3622 +The difference between the latest and earliest start times of some job
  1.3623 +is called its {\it time reserve}. Delaying a job within its time reserve
  1.3624 +does not affect the project duration, so if the time reserve is zero,
  1.3625 +the corresponding job is critical.
  1.3626 +
  1.3627 +\subsubsection{Returns}
  1.3628 +
  1.3629 +The routine \verb|glp_cpp| returns the minimal project duration, i.e.
  1.3630 +minimal time needed to perform all jobs in the project.
  1.3631 +
  1.3632 +\subsubsection{Example}
  1.3633 +
  1.3634 +The example program below solves the critical path problem shown on
  1.3635 +Fig.~4 by using the routine \verb|glp_cpp| and writes the solution found
  1.3636 +to the standard output.
  1.3637 +
  1.3638 +\begin{footnotesize}
  1.3639 +\begin{verbatim}
  1.3640 +#include <stddef.h>
  1.3641 +#include <stdio.h>
  1.3642 +#include <stdlib.h>
  1.3643 +#include <glpk.h>
  1.3644 +
  1.3645 +typedef struct { double t, es, ls; } v_data;
  1.3646 +
  1.3647 +#define node(v) ((v_data *)((v)->data))
  1.3648 +
  1.3649 +int main(void)
  1.3650 +{     glp_graph *G;
  1.3651 +      int i;
  1.3652 +      double t, es, ef, ls, lf, total;
  1.3653 +      G = glp_create_graph(sizeof(v_data), 0);
  1.3654 +      glp_add_vertices(G, 13);
  1.3655 +      node(G->v[1])->t = 3;   /* A: Excavate */
  1.3656 +      node(G->v[2])->t = 4;   /* B: Lay foundation */
  1.3657 +      node(G->v[3])->t = 3;   /* C: Rough plumbing */
  1.3658 +      node(G->v[4])->t = 10;  /* D: Frame */
  1.3659 +      node(G->v[5])->t = 8;   /* E: Finish exterior */
  1.3660 +      node(G->v[6])->t = 4;   /* F: Install HVAC */
  1.3661 +      node(G->v[7])->t = 6;   /* G: Rough elecrtic */
  1.3662 +      node(G->v[8])->t = 8;   /* H: Sheet rock */
  1.3663 +      node(G->v[9])->t = 5;   /* I: Install cabinets */
  1.3664 +      node(G->v[10])->t = 5;  /* J: Paint */
  1.3665 +      node(G->v[11])->t = 4;  /* K: Final plumbing */
  1.3666 +      node(G->v[12])->t = 2;  /* L: Final electric */
  1.3667 +      node(G->v[13])->t = 4;  /* M: Install flooring */
  1.3668 +      glp_add_arc(G, 1, 2);   /* A precedes B */
  1.3669 +      glp_add_arc(G, 2, 3);   /* B precedes C */
  1.3670 +      glp_add_arc(G, 2, 4);   /* B precedes D */
  1.3671 +      glp_add_arc(G, 4, 5);   /* D precedes E */
  1.3672 +      glp_add_arc(G, 4, 6);   /* D precedes F */
  1.3673 +      glp_add_arc(G, 4, 7);   /* D precedes G */
  1.3674 +      glp_add_arc(G, 3, 8);   /* C precedes H */
  1.3675 +      glp_add_arc(G, 5, 8);   /* E precedes H */
  1.3676 +      glp_add_arc(G, 6, 8);   /* F precedes H */
  1.3677 +      glp_add_arc(G, 7, 8);   /* G precedes H */
  1.3678 +      glp_add_arc(G, 8, 9);   /* H precedes I */
  1.3679 +      glp_add_arc(G, 8, 10);  /* H precedes J */
  1.3680 +      glp_add_arc(G, 9, 11);  /* I precedes K */
  1.3681 +      glp_add_arc(G, 10, 12); /* J precedes L */
  1.3682 +      glp_add_arc(G, 11, 13); /* K precedes M */
  1.3683 +      glp_add_arc(G, 12, 13); /* L precedes M */
  1.3684 +      total = glp_cpp(G, offsetof(v_data, t), offsetof(v_data, es),
  1.3685 +         offsetof(v_data, ls));
  1.3686 +      printf("Minimal project duration is %.2f\n\n", total);
  1.3687 +      printf("Job  Time      ES     EF     LS     LF\n");
  1.3688 +      printf("--- ------   ------ ------ ------ ------\n");
  1.3689 +      for (i = 1; i <= G->nv; i++)
  1.3690 +      {  t = node(G->v[i])->t;
  1.3691 +         es = node(G->v[i])->es;
  1.3692 +         ef = es + node(G->v[i])->t;
  1.3693 +         ls = node(G->v[i])->ls;
  1.3694 +         lf = ls + node(G->v[i])->t;
  1.3695 +         printf("%3d %6.2f %s %6.2f %6.2f %6.2f %6.2f\n",
  1.3696 +            i, t, ls - es < 0.001 ? "*" : " ", es, ef, ls, lf);
  1.3697 +      }
  1.3698 +      glp_delete_graph(G);
  1.3699 +      return 0;
  1.3700 +}
  1.3701 +\end{verbatim}
  1.3702 +\end{footnotesize}
  1.3703 +
  1.3704 +The output from the example program shown below includes job number,
  1.3705 +the time needed to perform a job, earliest start time (\verb|ES|),
  1.3706 +earliest finish time (\verb|EF|), latest start time (\verb|LS|), and
  1.3707 +latest finish time (\verb|LF|) for each job in the project. Critical
  1.3708 +jobs are marked by asterisks.
  1.3709 +
  1.3710 +\newpage
  1.3711 +
  1.3712 +\begin{footnotesize}
  1.3713 +\begin{verbatim}
  1.3714 +Minimal project duration is 46.00
  1.3715 +
  1.3716 +Job  Time      ES     EF     LS     LF
  1.3717 +--- ------   ------ ------ ------ ------
  1.3718 +  1   3.00 *   0.00   3.00   0.00   3.00
  1.3719 +  2   4.00 *   3.00   7.00   3.00   7.00
  1.3720 +  3   3.00     7.00  10.00  22.00  25.00
  1.3721 +  4  10.00 *   7.00  17.00   7.00  17.00
  1.3722 +  5   8.00 *  17.00  25.00  17.00  25.00
  1.3723 +  6   4.00    17.00  21.00  21.00  25.00
  1.3724 +  7   6.00    17.00  23.00  19.00  25.00
  1.3725 +  8   8.00 *  25.00  33.00  25.00  33.00
  1.3726 +  9   5.00 *  33.00  38.00  33.00  38.00
  1.3727 + 10   5.00    33.00  38.00  35.00  40.00
  1.3728 + 11   4.00 *  38.00  42.00  38.00  42.00
  1.3729 + 12   2.00    38.00  40.00  40.00  42.00
  1.3730 + 13   4.00 *  42.00  46.00  42.00  46.00
  1.3731 +\end{verbatim}
  1.3732 +\end{footnotesize}
  1.3733 +
  1.3734 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1.3735 +
  1.3736 +\chapter{Graph Optimization API Routines}
  1.3737 +
  1.3738 +\section{Maximum clique problem}
  1.3739 +
  1.3740 +\subsection{Background}
  1.3741 +
  1.3742 +The {\it maximum clique problem (MCP)} is a classic combinatorial
  1.3743 +optimization problem. Given an undirected graph $G=(V,E)$, where $V$ is
  1.3744 +a set of vertices, and $E$ is a set of edges, this problem is to find
  1.3745 +the largest {\it clique} $C\subseteq G$, i.e. the largest induced
  1.3746 +complete subgraph. A generalization of this problem is the {\it maximum
  1.3747 +weight clique problem (MWCP)}, which is to find a clique $C\subseteq G$
  1.3748 +of the largest weight $\displaystyle\sum_{v\in C}w(v)\rightarrow\max$,
  1.3749 +where $w(v)$ is a weight of vertex $v\in V$.
  1.3750 +
  1.3751 +An example of the maximum weight clique problem is shown on Fig.~5.
  1.3752 +
  1.3753 +\begin{figure}
  1.3754 +\noindent\hfil
  1.3755 +\begin{tabular}{c}
  1.3756 +{\xymatrix %@C=16pt
  1.3757 +{&&&{v_1}\ar@{-}[lllddd]\ar@{-}[llddddd]\ar@{-}[dddddd]
  1.3758 +\ar@{-}[rrrddd]&&&\\
  1.3759 +&{v_2}\ar@{-}[rrrr]\ar@{-}[rrrrdddd]\ar@{-}[rrddddd]\ar@{-}[dddd]&&&&
  1.3760 +{v_3}\ar@{-}[llllldd]\ar@{-}[lllldddd]\ar@{-}[dddd]&\\
  1.3761 +&&&&&&\\
  1.3762 +{v_4}\ar@{-}[rrrrrr]\ar@{-}[rrrddd]&&&&&&{v_5}\ar@{-}[lllddd]
  1.3763 +\ar@{-}[ldd]\\
  1.3764 +&&&&&&\\
  1.3765 +&{v_6}\ar@{-}[rrrr]&&&&{v_7}&\\
  1.3766 +&&&{v_8}&&&\\
  1.3767 +}}
  1.3768 +\end{tabular}
  1.3769 +\begin{tabular}{r@{\ }c@{\ }l}
  1.3770 +$w(v_1)$&=&3\\$w(v_2)$&=&4\\$w(v_3)$&=&8\\$w(v_4)$&=&1\\
  1.3771 +$w(v_5)$&=&5\\$w(v_6)$&=&2\\$w(v_7)$&=&1\\$w(v_8)$&=&3\\
  1.3772 +\end{tabular}
  1.3773 +
  1.3774 +\begin{center}
  1.3775 +Fig.~5. An example of the maximum weight clique problem.
  1.3776 +\end{center}
  1.3777 +\end{figure}
  1.3778 +
  1.3779 +\subsection{glp\_wclique\_exact---find maximum weight clique with exact
  1.3780 +algorithm}
  1.3781 +
  1.3782 +\subsubsection*{Synopsis}
  1.3783 +
  1.3784 +\begin{verbatim}
  1.3785 +int glp_wclique_exact(glp_graph *G, int v_wgt, double *sol,
  1.3786 +      int v_set);
  1.3787 +\end{verbatim}
  1.3788 +
  1.3789 +\subsection*{Description}
  1.3790 +
  1.3791 +The routine {\it glp\_wclique\_exact} finds a maximum weight clique in
  1.3792 +the specified undirected graph with the exact algorithm developed by
  1.3793 +Patric \"Osterg{\aa}rd.\footnote{P.~R.~J.~\"Osterg{\aa}rd, A new
  1.3794 +algorithm for the maximum-weight clique problem, Nordic J. of Computing,
  1.3795 +Vol.~8, No.~4, 2001, pp.~424--36.}
  1.3796 +
  1.3797 +The parameter $G$ is the program object, which specifies an undirected
  1.3798 +graph. Each arc $(x\rightarrow y)$ in $G$ is considered as edge
  1.3799 +$(x,y)$, self-loops are ignored, and multiple edges, if present, are
  1.3800 +replaced (internally) by simple edges.
  1.3801 +
  1.3802 +The parameter {\it v\_wgt} specifies an offset of the field of type
  1.3803 +{\bf double} in the vertex data block, which contains a weight of
  1.3804 +corresponding vertex. Vertex weights must be integer-valued in the
  1.3805 +range $[0,$ {\it INT\_MAX}$]$. If {\it v\_wgt} $<0$, it is assumed that
  1.3806 +all vertices of the graph have the weight 1.
  1.3807 +
  1.3808 +The parameter {\it sol} specifies a location, to which the routine
  1.3809 +stores the weight of the clique found (the clique weight is the sum
  1.3810 +of weights of all vertices included in the clique.) If {\it sol} is
  1.3811 +{\it NULL}, the solution is not stored.
  1.3812 +
  1.3813 +The parameter {\it v\_set} specifies an offset of the field of type
  1.3814 +{\bf int} in the vertex data block, to which the routines stores a
  1.3815 +vertex flag: 1 means that the corresponding vertex is included in the
  1.3816 +clique found, and 0 otherwise. If {\it v\_set} $<0$, vertex flags are
  1.3817 +not stored.
  1.3818 +
  1.3819 +\subsubsection*{Returns}
  1.3820 +
  1.3821 +\def\arraystretch{1}
  1.3822 +
  1.3823 +\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
  1.3824 +0 & Optimal solution found.\\
  1.3825 +\verb|GLP_EDATA| & Unable to start the search, because some vertex
  1.3826 +weights are either not integer-valued or out of range. This code is
  1.3827 +also returned if the sum of weights of all vertices exceeds
  1.3828 +{\it INT\_MAX}. \\
  1.3829 +\end{tabular}
  1.3830 +
  1.3831 +\subsubsection*{Notes}
  1.3832 +
  1.3833 +\noindent\indent
  1.3834 +1. The routine {\it glp\_wclique\_exact} finds exact solution. Since
  1.3835 +both MCP and MWCP problems are NP-complete, the algorithm may require
  1.3836 +exponential time in worst cases.
  1.3837 +
  1.3838 +2. Internally the specified graph is converted to an adjacency matrix
  1.3839 +in {\it dense} format. This requires about $|V|^2/16$ bytes of memory,
  1.3840 +where $|V|$ is the number of vertices in the graph.
  1.3841 +
  1.3842 +\subsubsection*{Example}
  1.3843 +
  1.3844 +The example program shown below reads a MWCP instance in DIMACS
  1.3845 +clique/coloring format from file `\verb|sample.clq|', finds the clique
  1.3846 +of largest weight, and writes the solution found to the standard output.
  1.3847 +
  1.3848 +\begin{footnotesize}
  1.3849 +\begin{verbatim}
  1.3850 +#include <stddef.h>
  1.3851 +#include <stdio.h>
  1.3852 +#include <stdlib.h>
  1.3853 +#include <glpk.h>
  1.3854 +
  1.3855 +typedef struct { double wgt; int set; } v_data;
  1.3856 +
  1.3857 +#define vertex(v) ((v_data *)((v)->data))
  1.3858 +
  1.3859 +int main(void)
  1.3860 +{     glp_graph *G;
  1.3861 +      glp_vertex *v;
  1.3862 +      int i, ret;
  1.3863 +      double sol;
  1.3864 +      G = glp_create_graph(sizeof(v_data), 0);
  1.3865 +      glp_read_ccdata(G, offsetof(v_data, wgt), "sample.clq");
  1.3866 +      ret = glp_wclique_exact(G, offsetof(v_data, wgt), &sol,
  1.3867 +         offsetof(v_data, set));
  1.3868 +      printf("ret = %d; sol = %g\n", ret, sol);
  1.3869 +      for (i = 1; i <= G->nv; i++)
  1.3870 +      {  v = G->v[i];
  1.3871 +         printf("vertex %d: weight = %g, flag = %d\n",
  1.3872 +            i, vertex(v)->wgt, vertex(v)->set);
  1.3873 +      }
  1.3874 +      glp_delete_graph(G);
  1.3875 +      return 0;
  1.3876 +}
  1.3877 +\end{verbatim}
  1.3878 +\end{footnotesize}
  1.3879 +
  1.3880 +\noindent
  1.3881 +For the example shown on Fig.~5 the data file may look like follows:
  1.3882 +
  1.3883 +\begin{footnotesize}
  1.3884 +\begin{verbatim}
  1.3885 +c sample.clq
  1.3886 +c
  1.3887 +c This is an example of the maximum weight clique
  1.3888 +c problem in DIMACS clique/coloring format.
  1.3889 +c
  1.3890 +p edge 8 16
  1.3891 +n 1 3
  1.3892 +n 2 4
  1.3893 +n 3 8
  1.3894 +n 5 5
  1.3895 +n 6 2
  1.3896 +n 8 3
  1.3897 +e 1 4
  1.3898 +e 1 5
  1.3899 +e 1 6
  1.3900 +e 1 8
  1.3901 +e 2 3
  1.3902 +e 2 6
  1.3903 +e 2 7
  1.3904 +e 2 8
  1.3905 +e 3 4
  1.3906 +e 3 6
  1.3907 +e 3 7
  1.3908 +e 4 5
  1.3909 +e 4 8
  1.3910 +e 5 7
  1.3911 +e 5 8
  1.3912 +e 6 7
  1.3913 +c
  1.3914 +c eof
  1.3915 +\end{verbatim}
  1.3916 +\end{footnotesize}
  1.3917 +
  1.3918 +\noindent
  1.3919 +The corresponding output from the example program is the following:
  1.3920 +
  1.3921 +\begin{footnotesize}
  1.3922 +\begin{verbatim}
  1.3923 +Reading graph from `sample.clq'...
  1.3924 +Graph has 8 vertices and 16 edges
  1.3925 +28 lines were read
  1.3926 +ret = 0; sol = 15
  1.3927 +vertex 1: weight = 3, flag = 0
  1.3928 +vertex 2: weight = 4, flag = 1
  1.3929 +vertex 3: weight = 8, flag = 1
  1.3930 +vertex 4: weight = 1, flag = 0
  1.3931 +vertex 5: weight = 5, flag = 0
  1.3932 +vertex 6: weight = 2, flag = 1
  1.3933 +vertex 7: weight = 1, flag = 1
  1.3934 +vertex 8: weight = 3, flag = 0
  1.3935 +\end{verbatim}
  1.3936 +\end{footnotesize}
  1.3937 +
  1.3938 +\end{document}