1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/doc/graphs.tex Mon Dec 06 13:09:21 2010 +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] |& ¬ 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] |¬ 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 + ¬ 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 + ¬ 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]|& ¬ 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}