
alpar@9: %* graphs.tex *%
alpar@9: 
alpar@9: %***********************************************************************
alpar@9: %  This code is part of GLPK (GNU Linear Programming Kit).
alpar@9: %
alpar@9: %  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
alpar@9: %  2009, 2010 Andrew Makhorin, Department for Applied Informatics,
alpar@9: %  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@9: %  E-mail: <mao@gnu.org>.
alpar@9: %
alpar@9: %  GLPK is free software: you can redistribute it and/or modify it
alpar@9: %  under the terms of the GNU General Public License as published by
alpar@9: %  the Free Software Foundation, either version 3 of the License, or
alpar@9: %  (at your option) any later version.
alpar@9: %
alpar@9: %  GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@9: %  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@9: %  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@9: %  License for more details.
alpar@9: %
alpar@9: %  You should have received a copy of the GNU General Public License
alpar@9: %  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@9: %***********************************************************************
alpar@9: 
alpar@9: \documentclass[11pt]{report}
alpar@9: \usepackage{amssymb}
alpar@9: \usepackage[dvipdfm,linktocpage,colorlinks,linkcolor=blue,
alpar@9: urlcolor=blue]{hyperref}
alpar@9: \usepackage[all]{xy}
alpar@9: 
alpar@9: \renewcommand\contentsname{\sf\bfseries Contents}
alpar@9: \renewcommand\chaptername{\sf\bfseries Chapter}
alpar@9: \renewcommand\appendixname{\sf\bfseries Appendix}
alpar@9: 
alpar@9: \begin{document}
alpar@9: 
alpar@9: \thispagestyle{empty}
alpar@9: 
alpar@9: \begin{center}
alpar@9: 
alpar@9: \vspace*{1in}
alpar@9: 
alpar@9: \begin{huge}
alpar@9: \sf\bfseries GNU Linear Programming Kit
alpar@9: \end{huge}
alpar@9: 
alpar@9: \vspace{0.5in}
alpar@9: 
alpar@9: \begin{LARGE}
alpar@9: \sf Graph and Network Routines
alpar@9: \end{LARGE}
alpar@9: 
alpar@9: \vspace{0.5in}
alpar@9: 
alpar@9: \begin{LARGE}
alpar@9: \sf for GLPK Version 4.45
alpar@9: \end{LARGE}
alpar@9: 
alpar@9: \vspace{0.5in}
alpar@9: \begin{Large}
alpar@9: \sf (DRAFT, December 2010)
alpar@9: \end{Large}
alpar@9: \end{center}
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \vspace*{1in}
alpar@9: 
alpar@9: \vfill
alpar@9: 
alpar@9: \noindent
alpar@9: The GLPK package is part of the GNU Project released under the aegis of
alpar@9: GNU.
alpar@9: 
alpar@9: \medskip \noindent
alpar@9: Copyright \copyright{} 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
alpar@9: 2008, 2009, 2010 Andrew Makhorin, Department for Applied Informatics,
alpar@9: Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@9: 
alpar@9: \medskip \noindent
alpar@9: Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
alpar@9: 02110-1301, USA.
alpar@9: 
alpar@9: \medskip \noindent
alpar@9: Permission is granted to make and distribute verbatim copies of this
alpar@9: manual provided the copyright notice and this permission notice are
alpar@9: preserved on all copies.
alpar@9: 
alpar@9: \medskip \noindent
alpar@9: Permission is granted to copy and distribute modified versions of this
alpar@9: manual under the conditions for verbatim copying, provided also that the
alpar@9: entire resulting derived work is distributed under the terms of
alpar@9: a permission notice identical to this one.
alpar@9: 
alpar@9: \medskip \noindent
alpar@9: Permission is granted to copy and distribute translations of this manual
alpar@9: into another language, under the above conditions for modified versions.
alpar@9: 
alpar@9: \tableofcontents
alpar@9: 
alpar@9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9: 
alpar@9: \chapter{Basic Graph API Routines}
alpar@9: 
alpar@9: \section{Graph program object}
alpar@9: 
alpar@9: In GLPK the base program object used to represent graphs and networks
alpar@9: is a directed graph (digraph).
alpar@9: 
alpar@9: Formally, {\it digraph} (or simply, {\it graph}) is a pair $G=(V,A)$,
alpar@9: where $V$ is a set of {\it vertices}, and $A$ is a set
alpar@9: {\it arcs}.\footnote{$A$ may be a multiset.} Each arc $a\in A$ is an
alpar@9: ordered pair of vertices $a=(x,y)$, where $x\in V$ is called {\it tail
alpar@9: vertex} of arc $a$, and $y\in V$ is called its {\it head vertex}.
alpar@9: 
alpar@9: Representation of a graph in the program includes three structs defined
alpar@9: by typedef in the header \verb|glpk.h|:
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: $\bullet$ \verb|glp_graph|, which represents the graph in a whole,
alpar@9: 
alpar@9: $\bullet$ \verb|glp_vertex|, which represents a vertex of the graph, and
alpar@9: 
alpar@9: $\bullet$ \verb|glp_arc|, which represents an arc of the graph.
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: All these three structs are ``semi-opaque'', i.e. the application
alpar@9: program can directly access their fields through pointers, however,
alpar@9: changing the fields directly is not allowed---all changes should be
alpar@9: performed only with appropriate GLPK API routines.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \newenvironment{comment}
alpar@9: {\addtolength{\leftskip}{17pt}\noindent}
alpar@9: {\par\addtolength{\leftskip}{-17pt}}
alpar@9: 
alpar@9: \noindent
alpar@9: {\bf glp\_graph.} The struct \verb|glp_graph| has the following
alpar@9: fields available to the application program:
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|char *name;|
alpar@9: 
alpar@9: \begin{comment}Symbolic name assigned to the graph. It is a pointer to
alpar@9: a null terminated character string of length from 1 to 255 characters.
alpar@9: If no name is assigned to the graph, this field contains \verb|NULL|.
alpar@9: \end{comment}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|int nv;|
alpar@9: 
alpar@9: \begin{comment}The number of vertices in the graph, $nv\geq 0$.
alpar@9: \end{comment}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|int na;|
alpar@9: 
alpar@9: \begin{comment}The number of arcs in the graph, $na\geq 0$.
alpar@9: \end{comment}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|glp_vertex **v;|
alpar@9: 
alpar@9: \begin{comment}Pointer to an array containing the list of vertices.
alpar@9: Element $v[0]$ is not used. Element $v[i]$, $1\leq i\leq nv$, is a
alpar@9: pointer to $i$-th vertex of the graph. Note that on adding new vertices
alpar@9: to the graph the field $v$ may be altered due to reallocation. However,
alpar@9: pointers $v[i]$ are not changed while corresponding vertices exist in
alpar@9: the graph.
alpar@9: \end{comment}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|int v_size;|
alpar@9: 
alpar@9: \begin{comment}Size of vertex data blocks, in bytes,
alpar@9: $0\leq v\_size\leq 256$. (See also the field \verb|data| in the struct
alpar@9: \verb|glp_vertex|.)
alpar@9: \end{comment}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|int a_size;|
alpar@9: 
alpar@9: \begin{comment}Size of arc data blocks, in bytes,
alpar@9: $0\leq v\_size\leq 256$. (See also the field \verb|data| in the struct
alpar@9: \verb|glp_arc|.)
alpar@9: \end{comment}
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: \noindent
alpar@9: {\bf glp\_vertex.} The struct \verb|glp_vertex| has the following
alpar@9: fields available to the application program:
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|int i;|
alpar@9: 
alpar@9: \begin{comment}Ordinal number of the vertex, $1\leq i\leq nv$. Note
alpar@9: that element $v[i]$ in the struct \verb|glp_graph| points to the vertex,
alpar@9: whose ordinal number is $i$.
alpar@9: \end{comment}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|char *name;|
alpar@9: 
alpar@9: \begin{comment}Symbolic name assigned to the vertex. It is a pointer to
alpar@9: a null terminated character string of length from 1 to 255 characters.
alpar@9: If no name is assigned to the vertex, this field contains \verb|NULL|.
alpar@9: \end{comment}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|void *data;|
alpar@9: 
alpar@9: \begin{comment}Pointer to a data block associated with the vertex. This
alpar@9: data block is automatically allocated on creating a new vertex and freed
alpar@9: on deleting the vertex. If $v\_size=0$, the block is not allocated, and
alpar@9: this field contains \verb|NULL|.
alpar@9: \end{comment}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|void *temp;|
alpar@9: 
alpar@9: \begin{comment}Working pointer, which may be used freely for any
alpar@9: purposes. The application program can change this field directly.
alpar@9: \end{comment}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|glp_arc *in;|
alpar@9: 
alpar@9: \begin{comment}Pointer to the (unordered) list of incoming arcs. If the
alpar@9: vertex has no incoming arcs, this field contains \verb|NULL|.
alpar@9: \end{comment}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|glp_arc *out;|
alpar@9: 
alpar@9: \begin{comment}Pointer to the (unordered) list of outgoing arcs. If the
alpar@9: vertex has no outgoing arcs, this field contains \verb|NULL|.
alpar@9: \end{comment}
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: \noindent
alpar@9: {\bf glp\_arc.} The struct \verb|glp_arc| has the following fields
alpar@9: available to the application program:
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|glp_vertex *tail;|
alpar@9: 
alpar@9: \begin{comment}Pointer to a vertex, which is tail endpoint of the arc.
alpar@9: \end{comment}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|glp_vertex *head;|
alpar@9: 
alpar@9: \begin{comment}Pointer to a vertex, which is head endpoint of the arc.
alpar@9: \end{comment}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|void *data;|
alpar@9: 
alpar@9: \begin{comment}Pointer to a data block associated with the arc. This
alpar@9: data block is automatically allocated on creating a new arc and freed on
alpar@9: deleting the arc. If $v\_size=0$, the block is not allocated, and this
alpar@9: field contains \verb|NULL|.
alpar@9: \end{comment}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|void *temp;|
alpar@9: 
alpar@9: \begin{comment}Working pointer, which may be used freely for any
alpar@9: purposes. The application program can change this field directly.
alpar@9: \end{comment}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|glp_arc *t_next;|
alpar@9: 
alpar@9: \begin{comment}Pointer to another arc, which has the same tail endpoint
alpar@9: as this one. \verb|NULL| in this field indicates the end of the list of
alpar@9: outgoing arcs.
alpar@9: \end{comment}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|glp_arc *h_next;|
alpar@9: 
alpar@9: \begin{comment}Pointer to another arc, which has the same head endpoint
alpar@9: as this one. \verb|NULL| in this field indicates the end of the list of
alpar@9: incoming arcs.
alpar@9: \end{comment}
alpar@9: 
alpar@9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \section{Graph creating and modifying routines}
alpar@9: 
alpar@9: \subsection{glp\_create\_graph---create graph}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: glp_graph *glp_create_graph(int v_size, int a_size);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_create_graph| creates a new graph, which
alpar@9: initially is\linebreak empty, i.e. has no vertices and arcs.
alpar@9: 
alpar@9: The parameter \verb|v_size| specifies the size of vertex data blocks,
alpar@9: in bytes, $0\leq v\_size\leq 256$.
alpar@9: 
alpar@9: The parameter \verb|a_size| specifies the size of arc data blocks, in
alpar@9: bytes, $0\leq a\_size\leq 256$.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine returns a pointer to the graph created.
alpar@9: 
alpar@9: \subsection{glp\_set\_graph\_name---assign (change) graph name}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_set_graph_name(glp_graph *G, const char *name);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_set_graph_name| assigns a symbolic name specified
alpar@9: by the character string \verb|name| (1 to 255 chars) to the graph.
alpar@9: 
alpar@9: If the parameter \verb|name| is \verb|NULL| or an empty string, the
alpar@9: routine erases the existing symbolic name of the graph.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_add\_vertices---add new vertices to graph}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_add_vertices(glp_graph *G, int nadd);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_add_vertices| adds \verb|nadd| vertices to the
alpar@9: specified graph. New vertices are always added to the end of the vertex
alpar@9: list, so ordinal numbers of existing vertices remain unchanged. Note
alpar@9: that this operation may change the field \verb|v| in the struct
alpar@9: \verb|glp_graph| (pointer to the vertex array) due to reallocation.
alpar@9: 
alpar@9: Being added each new vertex is isolated, i.e. has no incident arcs.
alpar@9: 
alpar@9: If the size of vertex data blocks specified on creating the graph is
alpar@9: non-zero, the routine also allocates a memory block of that size for
alpar@9: each new vertex added, fills it by binary zeros, and stores a pointer to
alpar@9: it in the field \verb|data| of the struct \verb|glp_vertex|. Otherwise,
alpar@9: if the block size is zero, the field \verb|data| is set to \verb|NULL|.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_add_vertices| returns the ordinal number of the
alpar@9: first new vertex added to the graph.
alpar@9: 
alpar@9: \subsection{glp\_set\_vertex\_name---assign (change) vertex name}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_set_vertex_name(glp_graph *G, int i, const char *name);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_set_vertex_name| assigns a given symbolic name
alpar@9: (1 up to 255 characters) to \verb|i|-th vertex of the specified graph.
alpar@9: 
alpar@9: If the parameter \verb|name| is \verb|NULL| or empty string, the
alpar@9: routine erases an existing name of \verb|i|-th vertex.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_add\_arc---add new arc to graph}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: glp_arc *glp_add_arc(glp_graph *G, int i, int j);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_add_arc| adds one new arc to the specified graph.
alpar@9: 
alpar@9: The parameters \verb|i| and \verb|j| specify the ordinal numbers of,
alpar@9: resp., tail and head endpoints (vertices) of the arc. Note that
alpar@9: self-loops and multiple arcs are allowed.
alpar@9: 
alpar@9: If the size of arc data blocks specified on creating the graph is
alpar@9: non-zero, the routine also allocates a memory block of that size, fills
alpar@9: it by binary zeros, and stores a pointer to it in the field \verb|data|
alpar@9: of the struct \verb|glp_arc|. Otherwise, if the block size is zero, the
alpar@9: field \verb|data| is set to \verb|NULL|.
alpar@9: 
alpar@9: \subsection{glp\_del\_vertices---delete vertices from graph}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_del_vertices(glp_graph *G, int ndel, const int num[]);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_del_vertices| deletes vertices along with all
alpar@9: incident arcs from the specified graph. Ordinal numbers of vertices to
alpar@9: be deleted should be placed in locations \verb|num[1]|, \dots,
alpar@9: \verb|num[ndel]|, \verb|ndel| $>0$.
alpar@9: 
alpar@9: Note that deleting vertices involves changing ordinal numbers of other
alpar@9: vertices remaining in the graph. New ordinal numbers of the remaining
alpar@9: vertices are assigned under the assumption that the original order of
alpar@9: vertices is not changed.
alpar@9: 
alpar@9: \subsection{glp\_del\_arc---delete arc from graph}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_del_arc(glp_graph *G, glp_arc *a);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_del_arc| deletes an arc from the specified graph.
alpar@9: The arc to be deleted must exist.
alpar@9: 
alpar@9: \subsection{glp\_erase\_graph---erase graph content}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_erase_graph(glp_graph *G, int v_size, int a_size);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_erase_graph| erases the content of the specified
alpar@9: graph. The effect of this operation is the same as if the graph would be
alpar@9: deleted with the routine \verb|glp_delete_graph| and then created anew
alpar@9: with the routine \verb|glp_create_graph|, with exception that the handle
alpar@9: (pointer) to the graph remains valid.
alpar@9: 
alpar@9: The parameters \verb|v_size| and \verb|a_size| have the same meaning as
alpar@9: for the routine \verb|glp_create_graph|.
alpar@9: 
alpar@9: \subsection{glp\_delete\_graph---delete graph}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_delete_graph(glp_graph *G);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_delete_graph| deletes the specified graph and
alpar@9: frees all the memory allocated to this program object.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \section{Graph searching routines}
alpar@9: 
alpar@9: \subsection{glp\_create\_v\_index---create vertex name index}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_create_v_index(glp_graph *G);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_create_v_index| creates the name index for the
alpar@9: specified graph. The name index is an auxiliary data structure, which
alpar@9: is intended to quickly (i.e. for logarithmic time) find vertices by
alpar@9: their names.
alpar@9: 
alpar@9: This routine can be called at any time. If the name index already
alpar@9: exists, the routine does nothing.
alpar@9: 
alpar@9: \subsection{glp\_find\_vertex---find vertex by its name}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_find_vertex(glp_graph *G, const char *name);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_find_vertex| returns the ordinal number of
alpar@9: a vertex, which is assigned (by the routine \verb|glp_set_vertex_name|)
alpar@9: the specified symbolic \verb|name|. If no such vertex exists, the
alpar@9: routine returns 0.
alpar@9: 
alpar@9: \subsection{glp\_delete\_v\_index---delete vertex name index}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_delete_v_index(glp_graph *G);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_delete_v_index| deletes the name index previously
alpar@9: created by the routine \verb|glp_create_v_index| and frees the memory
alpar@9: allocated to this auxiliary data structure.
alpar@9: 
alpar@9: This routine can be called at any time. If the name index does not
alpar@9: exist, the routine does nothing.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \section{Graph reading/writing routines}
alpar@9: 
alpar@9: \subsection{glp\_read\_graph---read graph from plain text file}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_read_graph(glp_graph *G, const char *fname);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_read_graph| reads a graph from a plain text file,
alpar@9: whose name is specified by the parameter \verb|fname|. Note that before
alpar@9: reading data the current content of the graph object is completely
alpar@9: erased with the routine \verb|glp_erase_graph|.
alpar@9: 
alpar@9: For the file format see description of the routine
alpar@9: \verb|glp_write_graph|.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: If the operation was successful, the routine returns zero. Otherwise
alpar@9: it prints an error message and returns non-zero.
alpar@9: 
alpar@9: \subsection{glp\_write\_graph---write graph to plain text file}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_write_graph(glp_graph *G, const char *fname);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_write_graph| writes the graph to a plain text
alpar@9: file, whose name is specified by the parameter \verb|fname|.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: If the operation was successful, the routine returns zero. Otherwise
alpar@9: it prints an error message and returns non-zero.
alpar@9: 
alpar@9: \subsubsection*{File format}
alpar@9: 
alpar@9: The file created by the routine \verb|glp_write_graph| is a plain text
alpar@9: file, which contains the following information:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    nv na
alpar@9:    i[1] j[1]
alpar@9:    i[2] j[2]
alpar@9:    . . .
alpar@9:    i[na] j[na]
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: where:
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|nv| is the number of vertices (nodes);
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|na| is the number of arcs;
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|i[k]|, $k=1,\dots,na$, is the index of tail vertex of arc $k$;
alpar@9: 
alpar@9: \noindent
alpar@9: \verb|j[k]|, $k=1,\dots,na$, is the index of head vertex of arc $k$.
alpar@9: 
alpar@9: \subsection{glp\_read\_ccdata---read graph from text file in DIMACS
alpar@9: clique/coloring format}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_read_ccdata(glp_graph *G, int v_wgt,
alpar@9:       const char *fname);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine {\it glp\_read\_ccdata} reads a graph from a text file in
alpar@9: DIMACS clique/coloring format. (Though this format is originally
alpar@9: designed to represent data for the minimal vertex coloring and maximal
alpar@9: clique problems, it may be used to represent general undirected and
alpar@9: directed graphs, because the routine allows reading self-loops and
alpar@9: multiple edges/arcs keeping the order of vertices specified for each
alpar@9: edge/arc of the graph.)
alpar@9: 
alpar@9: The parameter $G$ specifies the graph object to be read in. Note that
alpar@9: before reading data the current content of the graph object is
alpar@9: completely erased with the routine {\it glp\_erase\_graph}.
alpar@9: 
alpar@9: The parameter {\it v\_wgt} specifies an offset of the field of type
alpar@9: {\bf double} in the vertex data block, to which the routine stores the
alpar@9: vertex weight. If {\it v\_wgt} $<0$, the vertex weights are not stored.
alpar@9: 
alpar@9: The character string {\it fname} specifies the name of a text file to
alpar@9: be read in. (If the file name ends with the suffix `\verb|.gz|', the
alpar@9: file is assumed to be compressed, in which case the routine decompresses
alpar@9: it ``on the fly''.)
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: If the operation was successful, the routine returns zero. Otherwise,
alpar@9: it prints an error message and returns non-zero.
alpar@9: 
alpar@9: \subsubsection*{DIMACS clique/coloring format\footnote{This material is
alpar@9: based on the paper ``Clique and Coloring Problems Graph Format'', which
alpar@9: is publically available at
alpar@9: {\tt http://dimacs.rutgers.edu/Challenges/}.}}
alpar@9: 
alpar@9: The DIMACS input file is a plain ASCII text file. It contains
alpar@9: {\it lines} of several types described below. A line is terminated with
alpar@9: an end-of-line character. Fields in each line are separated by at least
alpar@9: one blank space. Each line begins with a one-character designator to
alpar@9: identify the line type.
alpar@9: 
alpar@9: Note that DIMACS requires all numerical quantities to be integers in
alpar@9: the range $[-2^{31},2^{31}-1]$ while GLPK allows the quantities to be
alpar@9: floating-point numbers.
alpar@9: 
alpar@9: \paragraph{Comment lines.} Comment lines give human-readable information
alpar@9: about the file and are ignored by programs. Comment lines can appear
alpar@9: anywhere in the file. Each comment line begins with a lower-case
alpar@9: character \verb|c|.
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    c This is a comment line
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \paragraph{Problem line.} There is one problem line per data file. The
alpar@9: problem line must appear before any node or edge descriptor lines. It
alpar@9: has the following format:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    p edge NODES EDGES
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: The lower-case letter \verb|p| signifies that this is a problem line.
alpar@9: The four-character problem designator \verb|edge| identifies the file
alpar@9: as containing data for the minimal vertex coloring or maximal clique
alpar@9: problem. The \verb|NODES| field contains an integer value specifying
alpar@9: the number of vertices in the graph. The \verb|EDGES| field contains an
alpar@9: integer value specifying the number of edges (arcs) in the graph.
alpar@9: 
alpar@9: \paragraph{Vertex descriptors.} These lines give the weight assigned to
alpar@9: a vertex of the graph. There is one vertex descriptor line for each
alpar@9: vertex, with the following format. Vertices without a descriptor take on
alpar@9: a default value of 1.
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    n ID VALUE
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: The lower-case character \verb|n| signifies that this is a vertex
alpar@9: descriptor line. The \verb|ID| field gives a vertex identification
alpar@9: number, an integer between 1 and $n$, where $n$ is the number of
alpar@9: vertices in the graph. The \verb|VALUE| field gives a vertex weight,
alpar@9: which can either positive or negative (or zero).
alpar@9: 
alpar@9: \paragraph{Edge descriptors.} There is one edge descriptor line for
alpar@9: each edge (arc) of the graph, each with the following format:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    e I J
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: The lower-case character \verb|e| signifies that this is an edge
alpar@9: descriptor line. For an edge (arc) $(i,j)$ the fields \verb|I| and
alpar@9: \verb|J| specify its endpoints.
alpar@9: 
alpar@9: \paragraph{Example.} The following example of an undirected graph:
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: \noindent\hfil
alpar@9: \xymatrix %@C=32pt
alpar@9: {&{v_1}\ar@{-}[ldd]\ar@{-}[dd]\ar@{-}[rd]\ar@{-}[rr]&&{v_2}\ar@{-}[ld]
alpar@9: \ar@{-}[dd]\ar@{-}[rdd]&\\
alpar@9: &&{v_7}\ar@{-}[ld]\ar@{-}[rd]&&\\
alpar@9: {v_6}\ar@{-}[r]\ar@{-}[rdd]&{v_{10}}\ar@{-}[rr]\ar@{-}[rd]\ar@{-}[dd]&&
alpar@9: {v_8}\ar@{-}[ld]\ar@{-}[dd]\ar@{-}[r]&{v_3}\ar@{-}[ldd]\\
alpar@9: &&{v_9}\ar@{-}[ld]\ar@{-}[rd]&&\\
alpar@9: &{v_5}\ar@{-}[rr]&&{v_4}&\\
alpar@9: }
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: \noindent
alpar@9: might be coded in DIMACS clique/coloring format as follows:
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: c sample.col
alpar@9: c
alpar@9: c This is an example of the vertex coloring problem data
alpar@9: c in DIMACS format.
alpar@9: c
alpar@9: p edge 10 21
alpar@9: c
alpar@9: e 1 2
alpar@9: e 1 6
alpar@9: e 1 7
alpar@9: e 1 10
alpar@9: e 2 3
alpar@9: e 2 7
alpar@9: e 2 8
alpar@9: e 3 4
alpar@9: e 3 8
alpar@9: e 4 5
alpar@9: e 4 8
alpar@9: e 4 9
alpar@9: e 5 6
alpar@9: e 5 9
alpar@9: e 5 10
alpar@9: e 6 10
alpar@9: e 7 8
alpar@9: e 7 10
alpar@9: e 8 9
alpar@9: e 8 10
alpar@9: e 9 10
alpar@9: c
alpar@9: c eof
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \subsection{glp\_write\_ccdata---write graph to text file in DIMACS
alpar@9: clique/coloring format}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_write_ccdata(glp_graph *G, int v_wgt,
alpar@9:       const char *fname);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsection*{Description}
alpar@9: 
alpar@9: The routine {\it glp\_write\_ccdata} writes the graph object specified
alpar@9: by the parameter $G$ to a text file in DIMACS clique/coloring format.
alpar@9: (Though this format is originally designed to represent data for the
alpar@9: minimal vertex coloring and maximal clique problems, it may be used to
alpar@9: represent general undirected and directed graphs, because the routine
alpar@9: allows writing self-loops and multiple edges/arcs keeping the order of
alpar@9: vertices specified for each edge/arc of the graph.)
alpar@9: 
alpar@9: The parameter {\it v\_wgt} specifies an offset of the field of type
alpar@9: {\bf double} in the vertex data block, which contains the vertex weight.
alpar@9: If {\it v\_wgt} $<0$, it is assumed that the weight of each vertex is 1.
alpar@9: 
alpar@9: The character string {\it fname} specifies a name of the text file to be
alpar@9: written out. (If the file name ends with suffix `\verb|.gz|', the file
alpar@9: is assumed to be compressed, in which case the routine performs
alpar@9: automatic compression on writing it.)
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: If the operation was successful, the routine returns zero. Otherwise,
alpar@9: it prints an error message and returns non-zero.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \section{Graph analysis routines}
alpar@9: 
alpar@9: \subsection{glp\_weak\_comp---find all weakly connected components of
alpar@9: graph}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_weak_comp(glp_graph *G, int v_num);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_weak_comp| finds all weakly connected components
alpar@9: of the specified graph.
alpar@9: 
alpar@9: The parameter \verb|v_num| specifies an offset of the field of type
alpar@9: \verb|int| in the vertex data block, to which the routine stores the
alpar@9: number of a weakly connected component containing that vertex. If
alpar@9: \verb|v_num| $<0$, no component numbers are stored.
alpar@9: 
alpar@9: The components are numbered in arbitrary order from 1 to \verb|nc|,
alpar@9: where \verb|nc| is the total number of components found,
alpar@9: $0\leq$ \verb|nc| $\leq|V|$.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine returns \verb|nc|, the total number of components found.
alpar@9: 
alpar@9: \subsection{glp\_strong\_comp---find all strongly connected components
alpar@9: of graph}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_strong_comp(glp_graph *G, int v_num);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_strong_comp| finds all strongly connected
alpar@9: components of the specified graph.
alpar@9: 
alpar@9: The parameter \verb|v_num| specifies an offset of the field of type
alpar@9: \verb|int| in the vertex data block, to which the routine stores the
alpar@9: number of a strongly connected component containing that vertex. If
alpar@9: \verb|v_num| $<0$, no component numbers are stored.
alpar@9: 
alpar@9: The components are numbered in arbitrary order from 1 to \verb|nc|,
alpar@9: where \verb|nc| is the total number of components found,
alpar@9: $0\leq$ \verb|nc| $\leq|V|$. However, the component numbering has the
alpar@9: property that for every arc $(i\rightarrow j)$ in the graph the
alpar@9: condition $num(i)\geq num(j)$ holds.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine returns \verb|nc|, the total number of components found.
alpar@9: 
alpar@9: \subsubsection*{References}
alpar@9: 
alpar@9: I.~S.~Duff, J.~K.~Reid, Algorithm 529: Permutations to block triangular
alpar@9: form, ACM Trans. on Math. Softw. 4 (1978), 189-92.
alpar@9: 
alpar@9: \subsubsection*{Example}
alpar@9: 
alpar@9: The following program reads a graph from a plain text file
alpar@9: `\verb|graph.txt|' and finds all its strongly connected components.
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: #include <stddef.h>
alpar@9: #include <stdio.h>
alpar@9: #include <stdlib.h>
alpar@9: #include <glpk.h>
alpar@9: 
alpar@9: typedef struct { int num; } v_data;
alpar@9: 
alpar@9: #define vertex(v) ((v_data *)((v)->data))
alpar@9: 
alpar@9: int main(void)
alpar@9: {     glp_graph *G;
alpar@9:       int i, nc;
alpar@9:       G = glp_create_graph(sizeof(v_data), 0);
alpar@9:       glp_read_graph(G, "graph.txt");
alpar@9:       nc = glp_strong_comp(G, offsetof(v_data, num));
alpar@9:       printf("nc = %d\n", nc);
alpar@9:       for (i = 1; i <= G->nv; i++)
alpar@9:          printf("num[%d] = %d\n", i, vertex(G->v[i])->num);
alpar@9:       glp_delete_graph(G);
alpar@9:       return 0;
alpar@9: }
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \noindent
alpar@9: If the file `\verb|graph.txt|' contains the graph shown below:
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: \noindent\hfil
alpar@9: \xymatrix
alpar@9: {1\ar[r]&2\ar[r]&3\ar[r]\ar[dd]&4\ar[dd]\\
alpar@9: 5\ar[u]&6\ar[l]\\
alpar@9: 7\ar[u]&&8\ar[lu]\ar[ll]\ar[r]&9\ar[r]&10\ar[r]\ar[d]&11\ar[d]\\
alpar@9: 12\ar[u]\ar[rru]\ar@/_/[rr]&&13\ar[ll]\ar[u]\ar[rr]&&14\ar[lu]&15\ar[l]
alpar@9: \\
alpar@9: }
alpar@9: 
alpar@9: \bigskip\bigskip
alpar@9: 
alpar@9: \noindent
alpar@9: the program output may look like follows:
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: Reading graph from `graph.txt'...
alpar@9: Graph has 15 vertices and 30 arcs
alpar@9: 31 lines were read
alpar@9: nc = 4
alpar@9: num[1] = 3
alpar@9: num[2] = 3
alpar@9: num[3] = 3
alpar@9: num[4] = 2
alpar@9: num[5] = 3
alpar@9: num[6] = 3
alpar@9: num[7] = 3
alpar@9: num[8] = 3
alpar@9: num[9] = 1
alpar@9: num[10] = 1
alpar@9: num[11] = 1
alpar@9: num[12] = 4
alpar@9: num[13] = 4
alpar@9: num[14] = 1
alpar@9: num[15] = 1
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \subsection{glp\_top\_sort---topological sorting of acyclic digraph}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_top_sort(glp_graph *G, int v_num);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_top_sort| performs topological sorting of
alpar@9: vertices of the specified acyclic digraph.
alpar@9: 
alpar@9: The parameter \verb|v_num| specifies an offset of the field of type
alpar@9: \verb|int| in the vertex data block, to which the routine stores the
alpar@9: vertex number assigned. If \verb|v_num| $<0$, vertex numbers are not
alpar@9: stored.
alpar@9: 
alpar@9: The vertices are numbered from 1 to $n$, where $n$ is the total number
alpar@9: of vertices in the graph. The vertex numbering has the property that
alpar@9: for every arc $(i\rightarrow j)$ in the graph the condition
alpar@9: $num(i)<num(j)$ holds. Special case $num(i)=0$ means that vertex $i$ is
alpar@9: not assigned a number, because the graph is {\it not} acyclic.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: If the graph is acyclic and therefore all the vertices have been
alpar@9: assigned numbers, the routine \verb|glp_top_sort| returns zero.
alpar@9: Otherwise, if the graph is not acyclic, the routine returns the number
alpar@9: of vertices which have not been numbered, i.e. for which $num(i)=0$.
alpar@9: 
alpar@9: \subsubsection*{Example}
alpar@9: 
alpar@9: The following program reads a digraph from a plain text file
alpar@9: `\verb|graph.txt|' and performs topological sorting of its vertices.
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: #include <stddef.h>
alpar@9: #include <stdio.h>
alpar@9: #include <stdlib.h>
alpar@9: #include <glpk.h>
alpar@9: 
alpar@9: typedef struct { int num; } v_data;
alpar@9: 
alpar@9: #define vertex(v) ((v_data *)((v)->data))
alpar@9: 
alpar@9: int main(void)
alpar@9: {     glp_graph *G;
alpar@9:       int i, cnt;
alpar@9:       G = glp_create_graph(sizeof(v_data), 0);
alpar@9:       glp_read_graph(G, "graph.txt");
alpar@9:       cnt = glp_top_sort(G, offsetof(v_data, num));
alpar@9:       printf("cnt = %d\n", cnt);
alpar@9:       for (i = 1; i <= G->nv; i++)
alpar@9:          printf("num[%d] = %d\n", i, vertex(G->v[i])->num);
alpar@9:       glp_delete_graph(G);
alpar@9:       return 0;
alpar@9: }
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \noindent
alpar@9: If the file `\verb|graph.txt|' contains the graph shown below:
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: \noindent\hfil
alpar@9: \xymatrix @=20pt
alpar@9: {
alpar@9: 1\ar[rrr]&&&2\ar[r]\ar[rddd]&3\ar[rd]&&&&\\
alpar@9: &&&4\ar[ru]&&5\ar[r]&6\ar[rd]\ar[dd]&&\\
alpar@9: 7\ar[r]&8\ar[r]&9\ar[ruu]\ar[ru]\ar[r]\ar[rd]&10\ar[rr]\ar[rru]&&
alpar@9: 11\ar[ru]&&12\ar[r]&13\\
alpar@9: &&&14\ar[r]&15\ar[rrru]\ar[rr]&&16\ar[rru]\ar[rr]&&17\\
alpar@9: }
alpar@9: 
alpar@9: \bigskip\bigskip
alpar@9: 
alpar@9: \noindent
alpar@9: the program output may look like follows:
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: Reading graph from `graph.txt'...
alpar@9: Graph has 17 vertices and 23 arcs
alpar@9: 24 lines were read
alpar@9: cnt = 0
alpar@9: num[1] = 8
alpar@9: num[2] = 9
alpar@9: num[3] = 10
alpar@9: num[4] = 4
alpar@9: num[5] = 11
alpar@9: num[6] = 12
alpar@9: num[7] = 1
alpar@9: num[8] = 2
alpar@9: num[9] = 3
alpar@9: num[10] = 5
alpar@9: num[11] = 6
alpar@9: num[12] = 14
alpar@9: num[13] = 16
alpar@9: num[14] = 7
alpar@9: num[15] = 13
alpar@9: num[16] = 15
alpar@9: num[17] = 17
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \noindent
alpar@9: The output corresponds to the following vertex numbering:
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: \noindent\hfil
alpar@9: \xymatrix @=20pt
alpar@9: {
alpar@9: 8\ar[rrr]&&&9\ar[r]\ar[rddd]&10\ar[rd]&&&&\\
alpar@9: &&&4\ar[ru]&&11\ar[r]&12\ar[rd]\ar[dd]&&\\
alpar@9: 1\ar[r]&2\ar[r]&3\ar[ruu]\ar[ru]\ar[r]\ar[rd]&5\ar[rr]\ar[rru]&&
alpar@9: 6\ar[ru]&&14\ar[r]&16\\
alpar@9: &&&7\ar[r]&13\ar[rrru]\ar[rr]&&15\ar[rru]\ar[rr]&&17\\
alpar@9: }
alpar@9: 
alpar@9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9: 
alpar@9: \chapter{Network optimization API routines}
alpar@9: 
alpar@9: \section{Minimum cost flow problem}
alpar@9: 
alpar@9: \subsection{Background}
alpar@9: 
alpar@9: The {\it minimum cost flow problem} (MCFP) is stated as follows. Let
alpar@9: there be given a directed graph (flow network) $G=(V,A)$, where $V$ is
alpar@9: a set of vertices (nodes), and $A\subseteq V\times V$ is a set of arcs.
alpar@9: Let for each node $i\in V$ there be given a quantity $b_i$ having the
alpar@9: following meaning:
alpar@9: 
alpar@9: if $b_i>0$, then $|b_i|$ is a {\it supply} at node $i$, which shows
alpar@9: how many flow units are {\it generated} at node $i$ (or, equivalently,
alpar@9: entering the network through node $i$ from the outside);
alpar@9: 
alpar@9: if $b_i<0$, then $|b_i|$ is a {\it demand} at node $i$, which shows how
alpar@9: many flow units are {\it lost} at node $i$ (or, equivalently, leaving
alpar@9: the network through node $i$ to the outside);
alpar@9: 
alpar@9: if $b_i=0$, then $i$ is a {\it transshipment} node, at which the flow
alpar@9: is conserved, i.e. neither generated nor lost.
alpar@9: 
alpar@9: Let also for each arc $a=(i,j)\in A$ there be given the following three
alpar@9: quantities:
alpar@9: 
alpar@9: $l_{ij}$, a (non-negative) lower bound to the flow through arc $(i,j)$;
alpar@9: 
alpar@9: $u_{ij}$, an upper bound to the flow through arc $(i,j)$, which is the
alpar@9: {\it arc capacity};
alpar@9: 
alpar@9: $c_{ij}$, a per-unit cost of the flow through arc $(i,j)$.
alpar@9: 
alpar@9: The problem is to find flows $x_{ij}$ through every arc of the network,
alpar@9: which satisfy the specified bounds and the conservation constraints at
alpar@9: all nodes, and minimize the total flow cost. Here the conservation
alpar@9: constraint at a node means that the total flow entering this node
alpar@9: through its incoming arcs plus the supply at this node must be equal to
alpar@9: the total flow leaving this node through its outgoing arcs plus the
alpar@9: demand at this node.
alpar@9: 
alpar@9: An example of the minimum cost flow problem is shown on Fig.~1.
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: \noindent\hfil
alpar@9: \xymatrix @C=48pt
alpar@9: {_{20}\ar@{~>}[d]&
alpar@9: v_2\ar[r]|{_{0,10,\$2}}\ar[dd]|{_{0,9,\$3}}&
alpar@9: v_3\ar[dd]|{_{2,12,\$1}}\ar[r]|{_{0,18,\$0}}&
alpar@9: v_8\ar[rd]|{_{0,20,\$9}}&\\
alpar@9: v_1\ar[ru]|{_{0,14,\$0}}\ar[rd]|{_{0,23,\$0}}&&&
alpar@9: v_6\ar[d]|{_{0,7,\$0}}\ar[u]|{_{4,8,\$0}}&
alpar@9: v_9\ar@{~>}[d]\\
alpar@9: &v_4\ar[r]|{_{0,26,\$0}}&
alpar@9: v_5\ar[luu]|{_{0,11,\$1}}\ar[ru]|{_{0,25,\$5}}\ar[r]|{_{0,4,\$7}}&
alpar@9: v_7\ar[ru]|{_{0,15,\$3}}&_{20}\\
alpar@9: }
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\hfil
alpar@9: \begin{tabular}{ccc}
alpar@9: \xymatrix @C=48pt{v_i\ar[r]|{\ l,u,\$c\ }&v_j\\}&
alpar@9: \xymatrix{\hbox{\footnotesize supply}\ar@{~>}[r]&v_i\\}&
alpar@9: \xymatrix{v_i\ar@{~>}[r]&\hbox{\footnotesize demand}\\}\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: \noindent\hfil
alpar@9: Fig.~1. An example of the minimum cost flow problem.
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: The minimum cost flow problem can be naturally formulated as the
alpar@9: following LP problem:
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \hspace{.5in}minimize
alpar@9: $$z=\sum_{(i,j)\in A}c_{ij}x_{ij}\eqno(1)$$
alpar@9: \hspace{.5in}subject to
alpar@9: $$\sum_{(i,j)\in A}x_{ij}-\sum_{(j,i)\in A}x_{ji}=b_i\ \ \ \hbox
alpar@9: {for all}\ i\in V\eqno(2)$$
alpar@9: $$l_{ij}\leq x_{ij}\leq u_{ij}\ \ \ \hbox{for all}\ (i,j)\in A
alpar@9: \eqno(3)$$
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_read\_mincost---read minimum cost flow problem\\data
alpar@9: in DIMACS format}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_read_mincost(glp_graph *G, int v_rhs, int a_low,
alpar@9:       int a_cap, int a_cost, const char *fname);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_read_mincost| reads the minimum cost flow problem
alpar@9: data from a text file in DIMACS format.
alpar@9: 
alpar@9: The parameter \verb|G| specifies the graph object, to which the problem
alpar@9: data have to be stored. Note that before reading data the current
alpar@9: content of the graph object is completely erased with the routine
alpar@9: \verb|glp_erase_graph|.
alpar@9: 
alpar@9: The parameter \verb|v_rhs| specifies an offset of the field of type
alpar@9: \verb|double| in the vertex data block, to which the routine stores
alpar@9: $b_i$, the supply/demand value. If \verb|v_rhs| $<0$, the value is not
alpar@9: stored.
alpar@9: 
alpar@9: The parameter \verb|a_low| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, to which the routine stores
alpar@9: $l_{ij}$, the lower bound to the arc flow. If \verb|a_low| $<0$, the
alpar@9: lower bound is not stored.
alpar@9: 
alpar@9: The parameter \verb|a_cap| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, to which the routine stores
alpar@9: $u_{ij}$, the upper bound to the arc flow (the arc capacity). If
alpar@9: \verb|a_cap| $<0$, the upper bound is not stored.
alpar@9: 
alpar@9: The parameter \verb|a_cost| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, to which the routine stores
alpar@9: $c_{ij}$, the per-unit cost of the arc flow. If \verb|a_cost| $<0$, the
alpar@9: cost is not stored.
alpar@9: 
alpar@9: The character string \verb|fname| specifies the name of a text file to
alpar@9: be read in. (If the file name name ends with the suffix `\verb|.gz|',
alpar@9: the file is assumed to be compressed, in which case the routine
alpar@9: decompresses it ``on the fly''.)
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: If the operation was successful, the routine returns zero. Otherwise,
alpar@9: it prints an error message and returns non-zero.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsubsection*{Example}
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: typedef struct
alpar@9: {     /* vertex data block */
alpar@9:       ...
alpar@9:       double rhs;
alpar@9:       ...
alpar@9: } v_data;
alpar@9: 
alpar@9: typedef struct
alpar@9: {     /* arc data block */
alpar@9:       ...
alpar@9:       double low, cap, cost;
alpar@9:       ...
alpar@9: } a_data;
alpar@9: 
alpar@9: int main(void)
alpar@9: {     glp_graph *G;
alpar@9:       int ret;
alpar@9:       G = glp_create_graph(sizeof(v_data), sizeof(a_data));
alpar@9:       ret = glp_read_mincost(G, offsetof(v_data, rhs),
alpar@9:          offsetof(a_data, low), offsetof(a_data, cap),
alpar@9:          offsetof(a_data, cost), "sample.min");
alpar@9:       if (ret != 0) goto ...
alpar@9:       ...
alpar@9: }
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \subsubsection*{DIMACS minimum cost flow problem format\footnote{This
alpar@9: material is based on the paper ``The First DIMACS International
alpar@9: Algorithm Implementation Challenge: Problem Definitions and
alpar@9: Specifications'', which is publically available at
alpar@9: {\tt http://dimacs.rutgers.edu/Challenges/}.}}
alpar@9: \label{subsecmincost}
alpar@9: 
alpar@9: The DIMACS input file is a plain ASCII text file. It contains
alpar@9: {\it lines} of several types described below. A line is terminated with
alpar@9: an end-of-line character. Fields in each line are separated by at least
alpar@9: one blank space. Each line begins with a one-character designator to
alpar@9: identify the line type.
alpar@9: 
alpar@9: Note that DIMACS requires all numerical quantities to be integers in
alpar@9: the range $[-2^{31},\ 2^{31}-1]$ while GLPK allows the quantities to be
alpar@9: floating-point numbers.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \paragraph{Comment lines.} Comment lines give human-readable information
alpar@9: about the file and are ignored by programs. Comment lines can appear
alpar@9: anywhere in the file. Each comment line begins with a lower-case
alpar@9: character \verb|c|.
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    c This is a comment line
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \paragraph{Problem line.} There is one problem line per data file. The
alpar@9: problem line must appear before any node or arc descriptor lines. It has
alpar@9: the following format:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    p min NODES ARCS
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: The lower-case character \verb|p| signifies that this is a problem line.
alpar@9: The three-character problem designator \verb|min| identifies the file as
alpar@9: containing specification information for the minimum cost flow problem.
alpar@9: The \verb|NODES| field contains an integer value specifying the number
alpar@9: of nodes in the network. The \verb|ARCS| field contains an integer value
alpar@9: specifying the number of arcs in the network.
alpar@9: 
alpar@9: \paragraph{Node descriptors.} All node descriptor lines must appear
alpar@9: before all arc descriptor lines. The node descriptor lines describe
alpar@9: supply and demand nodes, but not transshipment nodes. That is, only
alpar@9: nodes with non-zero node supply/demand values appear. There is one node
alpar@9: descriptor line for each such node, with the following format:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    n ID FLOW
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: The lower-case character \verb|n| signifies that this is a node
alpar@9: descriptor line. The \verb|ID| field gives a node identification number,
alpar@9: an integer between 1 and \verb|NODES|. The \verb|FLOW| field gives the
alpar@9: amount of supply (if positive) or demand (if negative) at node
alpar@9: \verb|ID|.
alpar@9: 
alpar@9: \paragraph{Arc descriptors.} There is one arc descriptor line for each
alpar@9: arc in the network. Arc descriptor lines are of the following format:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    a SRC DST LOW CAP COST
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: The lower-case character \verb|a| signifies that this is an arc
alpar@9: descriptor line. For a directed arc $(i,j)$ the \verb|SRC| field gives
alpar@9: the identification number $i$ for the tail endpoint, and the \verb|DST|
alpar@9: field gives the identification number $j$ for the head endpoint.
alpar@9: Identification numbers are integers between 1 and \verb|NODES|. The
alpar@9: \verb|LOW| field specifies the minimum amount of flow that can be sent
alpar@9: along arc $(i,j)$, and the \verb|CAP| field gives the maximum amount of
alpar@9: flow that can be sent along arc $(i,j)$ in a feasible flow. The
alpar@9: \verb|COST| field contains the per-unit cost of flow sent along arc
alpar@9: $(i,j)$.
alpar@9: 
alpar@9: \paragraph{Example.} Below here is an example of the data file in
alpar@9: DIMACS format corresponding to the minimum cost flow problem shown on
alpar@9: Fig~1.
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: c sample.min
alpar@9: c
alpar@9: c This is an example of the minimum cost flow problem data
alpar@9: c in DIMACS format.
alpar@9: c
alpar@9: p min 9 14
alpar@9: c
alpar@9: n 1 20
alpar@9: n 9 -20
alpar@9: c
alpar@9: a 1 2 0 14 0
alpar@9: a 1 4 0 23 0
alpar@9: a 2 3 0 10 2
alpar@9: a 2 4 0  9 3
alpar@9: a 3 5 2 12 1
alpar@9: a 3 8 0 18 0
alpar@9: a 4 5 0 26 0
alpar@9: a 5 2 0 11 1
alpar@9: a 5 6 0 25 5
alpar@9: a 5 7 0  4 7
alpar@9: a 6 7 0  7 0
alpar@9: a 6 8 4  8 0
alpar@9: a 7 9 0 15 3
alpar@9: a 8 9 0 20 9
alpar@9: c
alpar@9: c eof
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_write\_mincost---write minimum cost flow problem\\data
alpar@9: in DIMACS format}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_write_mincost(glp_graph *G, int v_rhs, int a_low,
alpar@9:       int a_cap, int a_cost, const char *fname);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_write_mincost| writes the minimum cost flow
alpar@9: problem data to a text file in DIMACS format.
alpar@9: 
alpar@9: The parameter \verb|G| is the graph (network) program object, which
alpar@9: specifies the minimum cost flow problem instance.
alpar@9: 
alpar@9: The parameter \verb|v_rhs| specifies an offset of the field of type
alpar@9: \verb|double| in the vertex data block, which contains $b_i$, the
alpar@9: supply/demand value. If \verb|v_rhs| $<0$, it is assumed that $b_i=0$
alpar@9: for all nodes.
alpar@9: 
alpar@9: The parameter \verb|a_low| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, which contains $l_{ij}$, the lower
alpar@9: bound to the arc flow. If \verb|a_low| $<0$, it is assumed that
alpar@9: $l_{ij}=0$ for all arcs.
alpar@9: 
alpar@9: The parameter \verb|a_cap| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, which contains $u_{ij}$, the upper
alpar@9: bound to the arc flow (the arc capacity). If the upper bound is
alpar@9: specified as \verb|DBL_MAX|, it is assumed that $u_{ij}=\infty$, i.e.
alpar@9: the arc is uncapacitated. If \verb|a_cap| $<0$, it is assumed that
alpar@9: $u_{ij}=1$ for all arcs.
alpar@9: 
alpar@9: The parameter \verb|a_cost| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, which contains $c_{ij}$, the
alpar@9: per-unit cost of the arc flow. If \verb|a_cost| $<0$, it is assumed that
alpar@9: $c_{ij}=0$ for all arcs.
alpar@9: 
alpar@9: The character string \verb|fname| specifies a name of the text file to
alpar@9: be written out. (If the file name ends with suffix `\verb|.gz|', the
alpar@9: file is assumed to be compressed, in which case the routine performs
alpar@9: automatic compression on writing it.)
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: If the operation was successful, the routine returns zero. Otherwise,
alpar@9: it prints an error message and returns non-zero.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_mincost\_lp---convert minimum cost flow problem\\to LP}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_mincost_lp(glp_prob *lp, glp_graph *G, int names,
alpar@9:       int v_rhs, int a_low, int a_cap, int a_cost);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_mincost_lp| builds LP problem (1)---(3), which
alpar@9: corresponds to the specified minimum cost flow problem.
alpar@9: 
alpar@9: The parameter \verb|lp| is the resultant LP problem object to be built.
alpar@9: Note that on entry its current content is erased with the routine
alpar@9: \verb|glp_erase_prob|.
alpar@9: 
alpar@9: The parameter \verb|G| is the graph (network) program object, which
alpar@9: specifies the minimum cost flow problem instance.
alpar@9: 
alpar@9: The parameter \verb|names| is a flag. If it is \verb|GLP_ON|, the
alpar@9: routine uses symbolic names of the graph object components to assign
alpar@9: symbolic names to the LP problem object components. If the flag is
alpar@9: \verb|GLP_OFF|, no symbolic names are assigned.
alpar@9: 
alpar@9: The parameter \verb|v_rhs| specifies an offset of the field of type
alpar@9: \verb|double| in the vertex data block, which contains $b_i$, the
alpar@9: supply/demand value. If \verb|v_rhs| $<0$, it is assumed that $b_i=0$
alpar@9: for all nodes.
alpar@9: 
alpar@9: The parameter \verb|a_low| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, which contains $l_{ij}$, the lower
alpar@9: bound to the arc flow. If \verb|a_low| $<0$, it is assumed that
alpar@9: $l_{ij}=0$ for all arcs.
alpar@9: 
alpar@9: The parameter \verb|a_cap| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, which contains $u_{ij}$, the upper
alpar@9: bound to the arc flow (the arc capacity). If the upper bound is
alpar@9: specified as \verb|DBL_MAX|, it is assumed that $u_{ij}=\infty$, i.e.
alpar@9: the arc is uncapacitated. If \verb|a_cap| $<0$, it is assumed that
alpar@9: $u_{ij}=1$ for all arcs.
alpar@9: 
alpar@9: The parameter \verb|a_cost| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, which contains $c_{ij}$, the
alpar@9: per-unit cost of the arc flow. If \verb|a_cost| $<0$, it is assumed that
alpar@9: $c_{ij}=0$ for all arcs.
alpar@9: 
alpar@9: \subsubsection*{Example}
alpar@9: 
alpar@9: The example program below reads the minimum cost problem instance in
alpar@9: DIMACS format from file `\verb|sample.min|', converts the instance to
alpar@9: LP, and then writes the resultant LP in CPLEX format to file
alpar@9: `\verb|mincost.lp|'.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: #include <stddef.h>
alpar@9: #include <glpk.h>
alpar@9: 
alpar@9: typedef struct { double rhs; } v_data;
alpar@9: typedef struct { double low, cap, cost; } a_data;
alpar@9: 
alpar@9: int main(void)
alpar@9: {     glp_graph *G;
alpar@9:       glp_prob *lp;
alpar@9:       G = glp_create_graph(sizeof(v_data), sizeof(a_data));
alpar@9:       glp_read_mincost(G, offsetof(v_data, rhs),
alpar@9:          offsetof(a_data, low), offsetof(a_data, cap),
alpar@9:          offsetof(a_data, cost), "sample.min");
alpar@9:       lp = glp_create_prob();
alpar@9:       glp_mincost_lp(lp, G, GLP_ON, offsetof(v_data, rhs),
alpar@9:          offsetof(a_data, low), offsetof(a_data, cap),
alpar@9:          offsetof(a_data, cost));
alpar@9:       glp_delete_graph(G);
alpar@9:       glp_write_lp(lp, NULL, "mincost.lp");
alpar@9:       glp_delete_prob(lp);
alpar@9:       return 0;
alpar@9: }
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: If `\verb|sample.min|' is the example data file from the subsection
alpar@9: describing the routine \verb|glp_read_mincost|, file `\verb|mincost.lp|'
alpar@9: may look like follows:
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: Minimize
alpar@9:  obj: + 3 x(2,4) + 2 x(2,3) + x(3,5) + 7 x(5,7) + 5 x(5,6)
alpar@9:  + x(5,2) + 3 x(7,9) + 9 x(8,9)
alpar@9: 
alpar@9: Subject To
alpar@9:  r_1: + x(1,2) + x(1,4) = 20
alpar@9:  r_2: - x(5,2) + x(2,3) + x(2,4) - x(1,2) = 0
alpar@9:  r_3: + x(3,5) + x(3,8) - x(2,3) = 0
alpar@9:  r_4: + x(4,5) - x(2,4) - x(1,4) = 0
alpar@9:  r_5: + x(5,2) + x(5,6) + x(5,7) - x(4,5) - x(3,5) = 0
alpar@9:  r_6: + x(6,7) + x(6,8) - x(5,6) = 0
alpar@9:  r_7: + x(7,9) - x(6,7) - x(5,7) = 0
alpar@9:  r_8: + x(8,9) - x(6,8) - x(3,8) = 0
alpar@9:  r_9: - x(8,9) - x(7,9) = -20
alpar@9: 
alpar@9: Bounds
alpar@9:  0 <= x(1,4) <= 23
alpar@9:  0 <= x(1,2) <= 14
alpar@9:  0 <= x(2,4) <= 9
alpar@9:  0 <= x(2,3) <= 10
alpar@9:  0 <= x(3,8) <= 18
alpar@9:  2 <= x(3,5) <= 12
alpar@9:  0 <= x(4,5) <= 26
alpar@9:  0 <= x(5,7) <= 4
alpar@9:  0 <= x(5,6) <= 25
alpar@9:  0 <= x(5,2) <= 11
alpar@9:  4 <= x(6,8) <= 8
alpar@9:  0 <= x(6,7) <= 7
alpar@9:  0 <= x(7,9) <= 15
alpar@9:  0 <= x(8,9) <= 20
alpar@9: 
alpar@9: End
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \subsection{glp\_mincost\_okalg---solve minimum cost flow problem with
alpar@9: out-of-kilter algorithm}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_mincost_okalg(glp_graph *G, int v_rhs, int a_low,
alpar@9:       int a_cap, int a_cost, double *sol, int a_x, int v_pi);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_mincost_okalg| finds optimal solution to the
alpar@9: minimum cost flow problem with the out-of-kilter
alpar@9: algorithm.\footnote{GLPK implementation of the out-of-kilter algorithm
alpar@9: is based on the following book: L.~R.~Ford,~Jr., and D.~R.~Fulkerson,
alpar@9: ``Flows in Networks,'' The RAND Corp., Report R-375-PR (August 1962),
alpar@9: Chap. III ``Minimal Cost Flow Problems,'' pp.~113-26.} Note that this
alpar@9: routine requires all the problem data to be integer-valued.
alpar@9: 
alpar@9: The parameter \verb|G| is a graph (network) program object which
alpar@9: specifies the minimum cost flow problem instance to be solved.
alpar@9: 
alpar@9: The parameter \verb|v_rhs| specifies an offset of the field of type
alpar@9: \verb|double| in the vertex data block, which contains $b_i$, the
alpar@9: supply/demand value. This value must be integer in the range
alpar@9: [$-$\verb|INT_MAX|, $+$\verb|INT_MAX|]. If \verb|v_rhs| $<0$, it is
alpar@9: assumed that $b_i=0$ for all nodes.
alpar@9: 
alpar@9: The parameter \verb|a_low| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, which contains $l_{ij}$, the lower
alpar@9: bound to the arc flow. This bound must be integer in the range
alpar@9: [$0$, \verb|INT_MAX|]. If \verb|a_low| $<0$, it is assumed that
alpar@9: $l_{ij}=0$ for all arcs.
alpar@9: 
alpar@9: The parameter \verb|a_cap| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, which contains $u_{ij}$, the upper
alpar@9: bound to the arc flow (the arc capacity). This bound must be integer in
alpar@9: the range [$l_{ij}$, \verb|INT_MAX|]. If \verb|a_cap| $<0$, it is
alpar@9: assumed that $u_{ij}=1$ for all arcs.
alpar@9: 
alpar@9: The parameter \verb|a_cost| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, which contains $c_{ij}$, the
alpar@9: per-unit cost of the arc flow. This value must be integer in the range
alpar@9: [$-$\verb|INT_MAX|, $+$\verb|INT_MAX|]. If \verb|a_cost| $<0$, it is
alpar@9: assumed that $c_{ij}=0$ for all arcs.
alpar@9: 
alpar@9: The parameter \verb|sol| specifies a location, to which the routine
alpar@9: stores the objective value (that is, the total cost) found. If
alpar@9: \verb|sol| is NULL, the objective value is not stored.
alpar@9: 
alpar@9: The parameter \verb|a_x| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, to which the routine stores
alpar@9: $x_{ij}$, the arc flow found. If \verb|a_x| $<0$, the arc flow value is
alpar@9: not stored.
alpar@9: 
alpar@9: The parameter \verb|v_pi| specifies an offset of the field of type
alpar@9: \verb|double| in the vertex data block, to which the routine stores
alpar@9: $\pi_i$, the node potential, which is the Lagrange multiplier for the
alpar@9: corresponding flow conservation equality constraint (see (2) in
alpar@9: Subsection ``Background''). If necessary, the application program may
alpar@9: use the node potentials to compute $\lambda_{ij}$, reduced costs of the
alpar@9: arc flows $x_{ij}$, which are the Lagrange multipliers for the arc flow
alpar@9: bound constraints (see (3) ibid.), using the following formula:
alpar@9: $$\lambda_{ij}=c_{ij}-(\pi_i-\pi_j),$$
alpar@9: where $c_{ij}$ is the per-unit cost for arc $(i,j)$.
alpar@9: 
alpar@9: Note that all solution components (the objective value, arc flows, and
alpar@9: node potentials) computed by the routine are always integer-valued.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: \def\arraystretch{1}
alpar@9: 
alpar@9: \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
alpar@9: 0 & Optimal solution found.\\
alpar@9: \verb|GLP_ENOPFS| & No (primal) feasible solution exists.\\
alpar@9: \verb|GLP_EDATA| & Unable to start the search, because some problem
alpar@9: data are either not integer-valued or out of range. This code is also
alpar@9: returned if the total supply, which is the sum of $b_i$ over all source
alpar@9: nodes (nodes with $b_i>0$), exceeds \verb|INT_MAX|.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \noindent
alpar@9: \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
alpar@9: \verb|GLP_ERANGE| & The search was prematurely terminated because of
alpar@9: integer overflow.\\
alpar@9: \verb|GLP_EFAIL| & An error has been detected in the program logic.
alpar@9: (If this code is returned for your problem instance, please report to
alpar@9: \verb|<bug-glpk@gnu.org>|.)\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsubsection*{Comments}
alpar@9: 
alpar@9: By design the out-of-kilter algorithm is applicable only to networks,
alpar@9: where $b_i=0$ for {\it all} nodes, i.e. actually this algorithm finds a
alpar@9: minimal cost {\it circulation}. Due to this requirement the routine
alpar@9: \verb|glp_mincost_okalg| converts the original network to a network
alpar@9: suitable for the out-of-kilter algorithm in the following
alpar@9: way:\footnote{The conversion is performed internally and does not change
alpar@9: the original network program object passed to the routine.}
alpar@9: 
alpar@9: 1) it adds two auxiliary nodes $s$ and $t$;
alpar@9: 
alpar@9: 2) for each original node $i$ with $b_i>0$ the routine adds auxiliary
alpar@9: supply arc $(s\rightarrow i)$, flow $x_{si}$ through which is costless
alpar@9: ($c_{si}=0$) and fixed to $+b_i$ ($l_{si}=u_{si}=+b_i$);
alpar@9: 
alpar@9: 3) for each original node $i$ with $b_i<0$ the routine adds auxiliary
alpar@9: demand arc $(i\rightarrow t)$, flow $x_{it}$ through which is costless
alpar@9: ($c_{it}=0$) and fixed to $-b_i$ ($l_{it}=u_{it}=-b_i$);
alpar@9: 
alpar@9: 4) finally, the routine adds auxiliary feedback arc $(t\rightarrow s)$,
alpar@9: flow $x_{ts}$ through which is also costless ($c_{ts}=0$) and fixed to
alpar@9: $F$ ($l_{ts}=u_{ts}=F$), where $\displaystyle F=\sum_{b_i>0}b_i$ is the
alpar@9: total supply.
alpar@9: 
alpar@9: \subsubsection*{Example}
alpar@9: 
alpar@9: The example program below reads the minimum cost problem instance in
alpar@9: DIMACS format from file `\verb|sample.min|', solves it by using the
alpar@9: routine \verb|glp_mincost_okalg|, and writes the solution found to the
alpar@9: standard output.
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: #include <stddef.h>
alpar@9: #include <stdio.h>
alpar@9: #include <stdlib.h>
alpar@9: #include <glpk.h>
alpar@9: 
alpar@9: typedef struct { double rhs, pi; } v_data;
alpar@9: typedef struct { double low, cap, cost, x; } a_data;
alpar@9: 
alpar@9: #define node(v) ((v_data *)((v)->data))
alpar@9: #define arc(a)  ((a_data *)((a)->data))
alpar@9: 
alpar@9: int main(void)
alpar@9: {     glp_graph *G;
alpar@9:       glp_vertex *v, *w;
alpar@9:       glp_arc *a;
alpar@9:       int i, ret;
alpar@9:       double sol;
alpar@9:       G = glp_create_graph(sizeof(v_data), sizeof(a_data));
alpar@9:       glp_read_mincost(G, offsetof(v_data, rhs),
alpar@9:          offsetof(a_data, low), offsetof(a_data, cap),
alpar@9:          offsetof(a_data, cost), "sample.min");
alpar@9:       ret = glp_mincost_okalg(G, offsetof(v_data, rhs),
alpar@9:          offsetof(a_data, low), offsetof(a_data, cap),
alpar@9:          offsetof(a_data, cost), &sol, offsetof(a_data, x),
alpar@9:          offsetof(v_data, pi));
alpar@9:       printf("ret = %d; sol = %5g\n", ret, sol);
alpar@9:       for (i = 1; i <= G->nv; i++)
alpar@9:       {  v = G->v[i];
alpar@9:          printf("node %d:    pi = %5g\n", i, node(v)->pi);
alpar@9:          for (a = v->out; a != NULL; a = a->t_next)
alpar@9:          {  w = a->head;
alpar@9:             printf("arc  %d->%d: x  = %5g; lambda = %5g\n",
alpar@9:                v->i, w->i, arc(a)->x,
alpar@9:                arc(a)->cost - (node(v)->pi - node(w)->pi));
alpar@9:          }
alpar@9:       }
alpar@9:       glp_delete_graph(G);
alpar@9:       return 0;
alpar@9: }
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: If `\verb|sample.min|' is the example data file from the subsection
alpar@9: describing the routine \verb|glp_read_mincost|, the output may look like
alpar@9: follows:
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: Reading min-cost flow problem data from `sample.min'...
alpar@9: Flow network has 9 nodes and 14 arcs
alpar@9: 24 lines were read
alpar@9: ret = 0; sol =   213
alpar@9: node 1:    pi =   -12
alpar@9: arc  1->4: x  =    13; lambda =     0
alpar@9: arc  1->2: x  =     7; lambda =     0
alpar@9: node 2:    pi =   -12
alpar@9: arc  2->4: x  =     0; lambda =     3
alpar@9: arc  2->3: x  =     7; lambda =     0
alpar@9: node 3:    pi =   -14
alpar@9: arc  3->8: x  =     5; lambda =     0
alpar@9: arc  3->5: x  =     2; lambda =     3
alpar@9: node 4:    pi =   -12
alpar@9: arc  4->5: x  =    13; lambda =     0
alpar@9: node 5:    pi =   -12
alpar@9: arc  5->7: x  =     4; lambda =    -1
alpar@9: arc  5->6: x  =    11; lambda =     0
alpar@9: arc  5->2: x  =     0; lambda =     1
alpar@9: node 6:    pi =   -17
alpar@9: arc  6->8: x  =     4; lambda =     3
alpar@9: arc  6->7: x  =     7; lambda =    -3
alpar@9: node 7:    pi =   -20
alpar@9: arc  7->9: x  =    11; lambda =     0
alpar@9: node 8:    pi =   -14
alpar@9: arc  8->9: x  =     9; lambda =     0
alpar@9: node 9:    pi =   -23
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \subsection{glp\_netgen---Klingman's network problem generator}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_netgen(glp_graph *G, int v_rhs, int a_cap, int a_cost,
alpar@9:       const int parm[1+15]);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_netgen| is a GLPK version of the network problem
alpar@9: generator developed by Dr.~Darwin~Klingman.\footnote{D.~Klingman,
alpar@9: A.~Napier, and J.~Stutz. NETGEN: A program for generating large scale
alpar@9: capacitated assignment, transportation, and minimum cost flow networks.
alpar@9: Management Science 20 (1974), 814-20.} It can create capacitated and
alpar@9: uncapacitated minimum cost flow (or transshipment), transportation, and
alpar@9: assignment problems.
alpar@9: 
alpar@9: The parameter \verb|G| specifies the graph object, to which the
alpar@9: generated  problem data have to be stored. Note that on entry the graph
alpar@9: object  is erased with the routine \verb|glp_erase_graph|.
alpar@9: 
alpar@9: The parameter \verb|v_rhs| specifies an offset of the field of type
alpar@9: \verb|double| in the vertex data block, to which the routine stores the
alpar@9: supply or  demand value. If \verb|v_rhs| $<0$, the value is not stored.
alpar@9: 
alpar@9: The parameter \verb|a_cap| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, to which the routine stores the
alpar@9: arc capacity. If \verb|a_cap| $<0$, the capacity is not stored.
alpar@9: 
alpar@9: The parameter \verb|a_cost| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, to which the routine stores the
alpar@9: per-unit cost if the arc flow. If \verb|a_cost| $<0$, the cost is not
alpar@9: stored.
alpar@9: 
alpar@9: The array \verb|parm| contains description of the network to be
alpar@9: generated:
alpar@9: 
alpar@9: \begin{tabular}{@{}lll@{}}
alpar@9: \verb|parm[0] |&             &not used\\
alpar@9: \verb|parm[1] |&\verb|iseed |&8-digit positive random number seed\\
alpar@9: \verb|parm[2] |&\verb|nprob |&8-digit problem id number\\
alpar@9: \verb|parm[3] |&\verb|nodes |&total number of nodes\\
alpar@9: \verb|parm[4] |&\verb|nsorc |&total number of source nodes\\
alpar@9: &&(including transshipment nodes)\\
alpar@9: \verb|parm[5] |&\verb|nsink |&total number of sink nodes\\
alpar@9: &&(including transshipment nodes)\\
alpar@9: \verb|parm[6] |&\verb|iarcs |&number of arc\\
alpar@9: \verb|parm[7] |&\verb|mincst|&minimum cost for arcs\\
alpar@9: \verb|parm[8] |&\verb|maxcst|&maximum cost for arcs\\
alpar@9: \verb|parm[9] |&\verb|itsup |&total supply\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \begin{tabular}{@{}lll@{}}
alpar@9: \verb|parm[10]|&\verb|ntsorc|&number of transshipment source nodes\\
alpar@9: \verb|parm[11]|&\verb|ntsink|&number of transshipment sink nodes\\
alpar@9: \verb|parm[12]|&\verb|iphic |&percentage of skeleton arcs to be given
alpar@9: the maxi-\\&&mum cost\\
alpar@9: \verb|parm[13]|&\verb|ipcap |&percentage of arcs to be capacitated\\
alpar@9: \verb|parm[14]|&\verb|mincap|&minimum upper bound for capacitated arcs\\
alpar@9: \verb|parm[15]|&\verb|maxcap|&maximum upper bound for capacitated arcs\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsubsection*{Notes}
alpar@9: 
alpar@9: \noindent\indent
alpar@9: 1. The routine generates a transportation problem if:
alpar@9: $${\tt nsorc}+{\tt nsink}={\tt nodes},
alpar@9: \  {\tt ntsorc}=0,\ \mbox{and}\ {\tt ntsink}=0.$$
alpar@9: 
alpar@9: 2. The routine generates an assignment problem if the requirements for
alpar@9: a transportation problem are met and:
alpar@9: $${\tt nsorc}={\tt nsink}\ \mbox{and}\ {\tt itsup}={\tt nsorc}.$$
alpar@9: 
alpar@9: 3. The routine always generates connected graphs. So, if the number of
alpar@9: requested arcs has been reached and the generated instance is not fully
alpar@9: connected, the routine generates a few remaining arcs to ensure
alpar@9: connectedness. Thus, the actual number of arcs generated by the routine
alpar@9: may be greater than the requested number of arcs.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: If the instance was successfully generated, the routine
alpar@9: \verb|glp_netgen| returns zero; otherwise, if specified parameters are
alpar@9: inconsistent, the routine returns a non-zero error code.
alpar@9: 
alpar@9: \subsection{glp\_gridgen---grid-like network problem generator}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_gridgen(glp_graph *G, int v_rhs, int a_cap, int a_cost,
alpar@9:       const int parm[1+14]);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_gridgen| is a GLPK version of the grid-like
alpar@9: network problem generator developed by Yusin Lee and Jim
alpar@9: Orlin.\footnote{Y.~Lee and J.~Orlin. GRIDGEN generator., 1991. The
alpar@9: original code is publically available from
alpar@9: {\tt<ftp://dimacs.rutgers.edu/pub/netflow/generators/network/gridgen>}.}
alpar@9: 
alpar@9: The parameter \verb|G| specifies the graph object, to which the
alpar@9: generated  problem data have to be stored. Note that on entry the graph
alpar@9: object  is erased with the routine \verb|glp_erase_graph|.
alpar@9: 
alpar@9: The parameter \verb|v_rhs| specifies an offset of the field of type
alpar@9: \verb|double| in the vertex data block, to which the routine stores the
alpar@9: supply or  demand value. If \verb|v_rhs| $<0$, the value is not stored.
alpar@9: 
alpar@9: The parameter \verb|a_cap| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, to which the routine stores the
alpar@9: arc capacity. If \verb|a_cap| $<0$, the capacity is not stored.
alpar@9: 
alpar@9: The parameter \verb|a_cost| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, to which the routine stores the
alpar@9: per-unit cost if the arc flow. If \verb|a_cost| $<0$, the cost is not
alpar@9: stored.
alpar@9: 
alpar@9: The array \verb|parm| contains parameters of the network to be
alpar@9: generated:
alpar@9: 
alpar@9: \begin{tabular}{@{}ll@{}}
alpar@9: \verb|parm[0] |&not used\\
alpar@9: \verb|parm[1] |&two-ways arcs indicator:\\
alpar@9:                &1 --- if links in both direction should be generated\\
alpar@9:                &0 --- otherwise\\
alpar@9: \verb|parm[2] |&random number seed (a positive integer)\\
alpar@9: \verb|parm[3] |&number of nodes (the number of nodes generated might
alpar@9: be\\&slightly different to make the network a grid)\\
alpar@9: \verb|parm[4] |&grid width\\
alpar@9: \verb|parm[5] |&number of sources\\
alpar@9: \verb|parm[6] |&number of sinks\\
alpar@9: \verb|parm[7] |&average degree\\
alpar@9: \verb|parm[8] |&total flow\\
alpar@9: \verb|parm[9] |&distribution of arc costs:\\
alpar@9:                &1 --- uniform\\
alpar@9:                &2 --- exponential\\
alpar@9: \verb|parm[10]|&lower bound for arc cost (uniform)\\
alpar@9:                &$100\lambda$ (exponential)\\
alpar@9: \verb|parm[11]|&upper bound for arc cost (uniform)\\
alpar@9:                &not used (exponential)\\
alpar@9: \verb|parm[12]|&distribution of arc capacities:\\
alpar@9:                &1 --- uniform\\
alpar@9:                &2 --- exponential\\
alpar@9: \verb|parm[13]|&lower bound for arc capacity (uniform)\\
alpar@9:                &$100\lambda$ (exponential)\\
alpar@9: \verb|parm[14]|&upper bound for arc capacity (uniform)\\
alpar@9:                &not used (exponential)\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: If the instance was successfully generated, the routine
alpar@9: \verb|glp_gridgen| returns zero; otherwise, if specified parameters are
alpar@9: inconsistent, the routine returns a non-zero error code.
alpar@9: 
alpar@9: \subsubsection*{Comments\footnote{This material is based on comments
alpar@9: to the original version of GRIDGEN.}}
alpar@9: 
alpar@9: This network generator generates a grid-like network plus a super node.
alpar@9: In additional to the arcs connecting the nodes in the grid, there is an
alpar@9: arc from each supply node to the super node and from the super node to
alpar@9: each demand node to guarantee feasiblity. These arcs have very high
alpar@9: costs and very big capacities.
alpar@9: 
alpar@9: The idea of this network generator is as follows: First, a grid of
alpar@9: $n_1\times n_2$ is generated. For example, $5\times 3$. The nodes are
alpar@9: numbered as 1 to 15, and the supernode is numbered as $n_1\times n_2+1$.
alpar@9: Then arcs between adjacent nodes are generated. For these arcs, the user
alpar@9: is allowed to specify either to generate two-way arcs or one-way arcs.
alpar@9: If two-way arcs are to be generated, two arcs, one in each direction,
alpar@9: will be generated between each adjacent node pairs. Otherwise, only one
alpar@9: arc will be generated. If this is the case, the arcs will be generated
alpar@9: in alterntive directions as shown below.
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: \noindent\hfil
alpar@9: \xymatrix
alpar@9: {1\ar[r]\ar[d]&2\ar[r]&3\ar[r]\ar[d]&4\ar[r]&5\ar[d]\\
alpar@9: 6\ar[d]&7\ar[l]\ar[u]&8\ar[l]\ar[d]&9\ar[l]\ar[u]&10\ar[l]\ar[d]\\
alpar@9: 11\ar[r]&12\ar[r]\ar[u]&13\ar[r]&14\ar[r]\ar[u]&15\\
alpar@9: }
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: Then the arcs between the super node and the source/sink nodes are added
alpar@9: as mentioned before. If the number of arcs still doesn't reach the
alpar@9: requirement, additional arcs will be added by uniformly picking random
alpar@9: node pairs. There is no checking to prevent multiple arcs between any
alpar@9: pair of nodes. However, there will be no self-arcs (arcs that poins back
alpar@9: to its tail node) in the network.
alpar@9: 
alpar@9: The source and sink nodes are selected uniformly in the network, and
alpar@9: the imbalances of each source/sink node are also assigned by uniform
alpar@9: distribution.
alpar@9: 
alpar@9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \section{Maximum flow problem}
alpar@9: 
alpar@9: \subsection{Background}
alpar@9: 
alpar@9: The {\it maximum flow problem} (MAXFLOW) is stated as follows. Let
alpar@9: there be given a directed graph (flow network) $G=(V,A)$, where $V$ is
alpar@9: a set of vertices (nodes), and $A\subseteq V\times V$ is a set of arcs.
alpar@9: Let also for each arc $a=(i,j)\in A$ there be given its capacity
alpar@9: $u_{ij}$. The problem is, for given {\it source} node $s\in V$ and
alpar@9: {\it sink} node $t\in V$, to find flows $x_{ij}$ through every arc of
alpar@9: the network, which satisfy the specified arc capacities and the
alpar@9: conservation constraints at all nodes, and maximize the total flow $F$
alpar@9: through the network from $s$ to $t$. Here the conservation constraint
alpar@9: at a node means that the total flow entering this node through its
alpar@9: incoming arcs (plus $F$, if it is the source node) must be equal to the
alpar@9: total flow leaving this node through its outgoing arcs (plus $F$, if it
alpar@9: is the sink node).
alpar@9: 
alpar@9: An example of the maximum flow problem, where $s=v_1$ and $t=v_9$, is
alpar@9: shown on Fig.~2.
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: \noindent\hfil
alpar@9: \xymatrix @C=48pt
alpar@9: {_{F}\ar@{~>}[d]&
alpar@9: v_2\ar[r]|{_{10}}\ar[dd]|{_{9}}&
alpar@9: v_3\ar[dd]|{_{12}}\ar[r]|{_{18}}&
alpar@9: v_8\ar[rd]|{_{20}}&\\
alpar@9: v_1\ar[ru]|{_{14}}\ar[rd]|{_{23}}&&&
alpar@9: v_6\ar[d]|{_{7}}\ar[u]|{_{8}}&
alpar@9: v_9\ar@{~>}[d]\\
alpar@9: &v_4\ar[r]|{_{26}}&
alpar@9: v_5\ar[luu]|{_{11}}\ar[ru]|{_{25}}\ar[r]|{_{4}}&
alpar@9: v_7\ar[ru]|{_{15}}&_{F}\\
alpar@9: }
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: \noindent\hfil
alpar@9: Fig.~2. An example of the maximum flow problem.
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: The maximum flow problem can be naturally formulated as the following
alpar@9: LP problem:
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \hspace{.5in}maximize
alpar@9: $$F\eqno(4)$$
alpar@9: \hspace{.5in}subject to
alpar@9: $$\sum_{(i,j)\in A}x_{ij}-\sum_{(j,i)\in A}x_{ji}=\left\{
alpar@9: \begin{array}{@{\ }rl}
alpar@9: +F,&\hbox{for}\ i=s\\
alpar@9:  0,&\hbox{for all}\ i\in V\backslash\{s,t\}\\
alpar@9: -F,&\hbox{for}\ i=t\\
alpar@9: \end{array}
alpar@9: \right.\eqno(5)
alpar@9: $$
alpar@9: $$0\leq x_{ij}\leq u_{ij}\ \ \ \hbox{for all}\ (i,j)\in A
alpar@9: \eqno(6)$$
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: where $F\geq 0$ is an additional variable playing the role of the
alpar@9: objective.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: Another LP formulation of the maximum flow problem, which does not
alpar@9: include the variable $F$, is the following:
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \hspace{.5in}maximize
alpar@9: $$z=\sum_{(s,j)\in A}x_{sj}-\sum_{(j,s)\in A}x_{js}\ (=F)\eqno(7)$$
alpar@9: \hspace{.5in}subject to
alpar@9: $$\sum_{(i,j)\in A}x_{ij}-\sum_{(j,i)\in A}x_{ji}\left\{
alpar@9: \begin{array}{@{\ }rl}
alpar@9: \geq 0,&\hbox{for}\ i=s\\
alpar@9: =0,&\hbox{for all}\ i\in V\backslash\{s,t\}\\
alpar@9: \leq 0,&\hbox{for}\ i=t\\
alpar@9: \end{array}
alpar@9: \right.\eqno(8)
alpar@9: $$
alpar@9: $$0\leq x_{ij}\leq u_{ij}\ \ \ \hbox{for all}\ (i,j)\in A
alpar@9: \eqno(9)$$
alpar@9: 
alpar@9: \subsection{glp\_read\_maxflow---read maximum flow problem data\\in
alpar@9: DIMACS format}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_read_maxflow(glp_graph *G, int *s, int *t, int a_cap,
alpar@9:       const char *fname);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_read_maxflow| reads the maximum flow problem
alpar@9: data from a text file in DIMACS format.
alpar@9: 
alpar@9: The parameter \verb|G| specifies the graph object, to which the problem
alpar@9: data have to be stored. Note that before reading data the current
alpar@9: content of the graph object is completely erased with the routine
alpar@9: \verb|glp_erase_graph|.
alpar@9: 
alpar@9: The pointer \verb|s| specifies a location, to which the routine stores
alpar@9: the ordinal number of the source node. If \verb|s| is \verb|NULL|, the
alpar@9: source node number is not stored.
alpar@9: 
alpar@9: The pointer \verb|t| specifies a location, to which the routine stores
alpar@9: the ordinal number of the sink node. If \verb|t| is \verb|NULL|, the
alpar@9: sink node number is not stored.
alpar@9: 
alpar@9: The parameter \verb|a_cap| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, to which the routine stores
alpar@9: $u_{ij}$, the arc capacity. If \verb|a_cap| $<0$, the arc capacity is
alpar@9: not stored.
alpar@9: 
alpar@9: The character string \verb|fname| specifies the name of a text file to
alpar@9: be read in. (If the file name name ends with the suffix `\verb|.gz|',
alpar@9: the file is assumed to be compressed, in which case the routine
alpar@9: decompresses it ``on the fly''.)
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: If the operation was successful, the routine returns zero. Otherwise,
alpar@9: it prints an error message and returns non-zero.
alpar@9: 
alpar@9: \subsubsection*{Example}
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: typedef struct
alpar@9: {     /* arc data block */
alpar@9:       ...
alpar@9:       double cap;
alpar@9:       ...
alpar@9: } a_data;
alpar@9: 
alpar@9: int main(void)
alpar@9: {     glp_graph *G;
alpar@9:       int s, t, ret;
alpar@9:       G = glp_create_graph(..., sizeof(a_data));
alpar@9:       ret = glp_read_maxflow(G, &s, &t, offsetof(a_data, cap),
alpar@9:          "sample.max");
alpar@9:       if (ret != 0) goto ...
alpar@9:       ...
alpar@9: }
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \subsubsection*{DIMACS maximum flow problem format\footnote{This
alpar@9: material is based on the paper ``The First DIMACS International
alpar@9: Algorithm Implementation Challenge: Problem Definitions and
alpar@9: Specifications'', which is publically available at
alpar@9: {\tt http://dimacs.rutgers.edu/Challenges/}.}}
alpar@9: \label{subsecmaxflow}
alpar@9: 
alpar@9: The DIMACS input file is a plain ASCII text file. It contains
alpar@9: {\it lines} of several types described below. A line is terminated with
alpar@9: an end-of-line character. Fields in each line are separated by at least
alpar@9: one blank space. Each line begins with a one-character designator to
alpar@9: identify the line type.
alpar@9: 
alpar@9: Note that DIMACS requires all numerical quantities to be integers in
alpar@9: the range $[-2^{31},\ 2^{31}-1]$ while GLPK allows the quantities to be
alpar@9: floating-point numbers.
alpar@9: 
alpar@9: \paragraph{Comment lines.} Comment lines give human-readable information
alpar@9: about the file and are ignored by programs. Comment lines can appear
alpar@9: anywhere in the file. Each comment line begins with a lower-case
alpar@9: character \verb|c|.
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    c This is a comment line
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \paragraph{Problem line.} There is one problem line per data file. The
alpar@9: problem line must appear before any node or arc descriptor lines. It has
alpar@9: the following format:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    p max NODES ARCS
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: The lower-case character \verb|p| signifies that this is a problem line.
alpar@9: The three-character problem designator \verb|max| identifies the file as
alpar@9: containing specification information for the maximum flow problem. The
alpar@9: \verb|NODES| field contains an integer value specifying the number of
alpar@9: nodes in the network. The \verb|ARCS| field contains an integer value
alpar@9: specifying the number of arcs in the network.
alpar@9: 
alpar@9: \paragraph{Node descriptors.} Two node descriptor lines for the source
alpar@9: and sink nodes must appear before all arc descriptor lines. They may
alpar@9: appear in either order, each with the following format:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    n ID WHICH
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: The lower-case character \verb|n| signifies that this a node descriptor
alpar@9: line. The \verb|ID| field gives a node identification number, an integer
alpar@9: between 1 and \verb|NODES|. The \verb|WHICH| field gives either a
alpar@9: lower-case \verb|s| or \verb|t|, designating the source and sink,
alpar@9: respectively.
alpar@9: 
alpar@9: \paragraph{Arc descriptors.} There is one arc descriptor line for each
alpar@9: arc in the network. Arc descriptor lines are of the following format:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    a SRC DST CAP
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: The lower-case character \verb|a| signifies that this is an arc
alpar@9: descriptor line. For a directed arc $(i,j)$ the \verb|SRC| field gives
alpar@9: the identification number $i$ for the tail endpoint, and the \verb|DST|
alpar@9: field gives the identification number $j$ for the head endpoint.
alpar@9: Identification numbers are integers between 1 and \verb|NODES|. The
alpar@9: \verb|CAP| field gives the arc capacity, i.e. maximum amount of flow
alpar@9: that can be sent along arc $(i,j)$ in a feasible flow.
alpar@9: 
alpar@9: \paragraph{Example.} Below here is an example of the data file in
alpar@9: DIMACS format corresponding to the maximum flow problem shown on Fig~2.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: c sample.max
alpar@9: c
alpar@9: c This is an example of the maximum flow problem data
alpar@9: c in DIMACS format.
alpar@9: c
alpar@9: p max 9 14
alpar@9: c
alpar@9: n 1 s
alpar@9: n 9 t
alpar@9: c
alpar@9: a 1 2 14
alpar@9: a 1 4 23
alpar@9: a 2 3 10
alpar@9: a 2 4  9
alpar@9: a 3 5 12
alpar@9: a 3 8 18
alpar@9: a 4 5 26
alpar@9: a 5 2 11
alpar@9: a 5 6 25
alpar@9: a 5 7  4
alpar@9: a 6 7  7
alpar@9: a 6 8  8
alpar@9: a 7 9 15
alpar@9: a 8 9 20
alpar@9: c
alpar@9: c eof
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \subsection{glp\_write\_maxflow---write maximum flow problem data\\
alpar@9: in DIMACS format}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_write_maxflow(glp_graph *G, int s, int t, int a_cap,
alpar@9:       const char *fname);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_write_maxflow| writes the maximum flow problem
alpar@9: data to a text file in DIMACS format.
alpar@9: 
alpar@9: The parameter \verb|G| is the graph (network) program object, which
alpar@9: specifies the maximum flow problem instance.
alpar@9: 
alpar@9: The parameter \verb|s| specifies the ordinal number of the source node.
alpar@9: 
alpar@9: The parameter \verb|t| specifies the ordinal number of the sink node.
alpar@9: 
alpar@9: The parameter \verb|a_cap| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, which contains $u_{ij}$, the upper
alpar@9: bound to the arc flow (the arc capacity). If the upper bound is
alpar@9: specified as \verb|DBL_MAX|, it is assumed that $u_{ij}=\infty$, i.e.
alpar@9: the arc is uncapacitated. If \verb|a_cap| $<0$, it is assumed that
alpar@9: $u_{ij}=1$ for all arcs.
alpar@9: 
alpar@9: The character string \verb|fname| specifies a name of the text file to
alpar@9: be written out. (If the file name ends with suffix `\verb|.gz|', the
alpar@9: file is assumed to be compressed, in which case the routine performs
alpar@9: automatic compression on writing it.)
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: If the operation was successful, the routine returns zero. Otherwise,
alpar@9: it prints an error message and returns non-zero.
alpar@9: 
alpar@9: \subsection{glp\_maxflow\_lp---convert maximum flow problem to LP}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_maxflow_lp(glp_prob *lp, glp_graph *G, int names,
alpar@9:       int s, int t, int a_cap);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_maxflow_lp| builds LP problem (7)---(9), which
alpar@9: corresponds to the specified maximum flow problem.
alpar@9: 
alpar@9: The parameter \verb|lp| is the resultant LP problem object to be built.
alpar@9: Note that on entry its current content is erased with the routine
alpar@9: \verb|glp_erase_prob|.
alpar@9: 
alpar@9: The parameter \verb|G| is the graph (network) program object, which
alpar@9: specifies the maximum flow problem instance.
alpar@9: 
alpar@9: The parameter \verb|names| is a flag. If it is \verb|GLP_ON|, the
alpar@9: routine uses symbolic names of the graph object components to assign
alpar@9: symbolic names to the LP problem object components. If the flag is
alpar@9: \verb|GLP_OFF|, no symbolic names are assigned.
alpar@9: 
alpar@9: The parameter \verb|s| specifies the ordinal number of the source node.
alpar@9: 
alpar@9: The parameter \verb|t| specifies the ordinal number of the sink node.
alpar@9: 
alpar@9: The parameter \verb|a_cap| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, which contains $u_{ij}$, the upper
alpar@9: bound to the arc flow (the arc capacity). If the upper bound is
alpar@9: specified as \verb|DBL_MAX|, it is assumed that $u_{ij}=\infty$, i.e.
alpar@9: the arc is uncapacitated. If \verb|a_cap| $<0$, it is assumed that
alpar@9: $u_{ij}=1$ for all arcs.
alpar@9: 
alpar@9: \subsubsection*{Example}
alpar@9: 
alpar@9: The example program below reads the maximum flow problem in DIMACS
alpar@9: format from file `\verb|sample.max|', converts the instance to LP, and
alpar@9: then writes the resultant LP in CPLEX format to file
alpar@9: `\verb|maxflow.lp|'.
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: #include <stddef.h>
alpar@9: #include <glpk.h>
alpar@9: 
alpar@9: int main(void)
alpar@9: {     glp_graph *G;
alpar@9:       glp_prob *lp;
alpar@9:       int s, t;
alpar@9:       G = glp_create_graph(0, sizeof(double));
alpar@9:       glp_read_maxflow(G, &s, &t, 0, "sample.max");
alpar@9:       lp = glp_create_prob();
alpar@9:       glp_maxflow_lp(lp, G, GLP_ON, s, t, 0);
alpar@9:       glp_delete_graph(G);
alpar@9:       glp_write_lp(lp, NULL, "maxflow.lp");
alpar@9:       glp_delete_prob(lp);
alpar@9:       return 0;
alpar@9: }
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: If `\verb|sample.max|' is the example data file from the previous
alpar@9: subsection, the output `\verb|maxflow.lp|' may look like follows:
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: Maximize
alpar@9:  obj: + x(1,4) + x(1,2)
alpar@9: 
alpar@9: Subject To
alpar@9:  r_1: + x(1,2) + x(1,4) >= 0
alpar@9:  r_2: - x(5,2) + x(2,3) + x(2,4) - x(1,2) = 0
alpar@9:  r_3: + x(3,5) + x(3,8) - x(2,3) = 0
alpar@9:  r_4: + x(4,5) - x(2,4) - x(1,4) = 0
alpar@9:  r_5: + x(5,2) + x(5,6) + x(5,7) - x(4,5) - x(3,5) = 0
alpar@9:  r_6: + x(6,7) + x(6,8) - x(5,6) = 0
alpar@9:  r_7: + x(7,9) - x(6,7) - x(5,7) = 0
alpar@9:  r_8: + x(8,9) - x(6,8) - x(3,8) = 0
alpar@9:  r_9: - x(8,9) - x(7,9) <= 0
alpar@9: 
alpar@9: Bounds
alpar@9:  0 <= x(1,4) <= 23
alpar@9:  0 <= x(1,2) <= 14
alpar@9:  0 <= x(2,4) <= 9
alpar@9:  0 <= x(2,3) <= 10
alpar@9:  0 <= x(3,8) <= 18
alpar@9:  0 <= x(3,5) <= 12
alpar@9:  0 <= x(4,5) <= 26
alpar@9:  0 <= x(5,7) <= 4
alpar@9:  0 <= x(5,6) <= 25
alpar@9:  0 <= x(5,2) <= 11
alpar@9:  0 <= x(6,8) <= 8
alpar@9:  0 <= x(6,7) <= 7
alpar@9:  0 <= x(7,9) <= 15
alpar@9:  0 <= x(8,9) <= 20
alpar@9: 
alpar@9: End
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \subsection{glp\_maxflow\_ffalg---solve maximum flow problem with
alpar@9: Ford-Fulkerson algorithm}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_maxflow_ffalg(glp_graph *G, int s, int t, int a_cap,
alpar@9:       double *sol, int a_x, int v_cut);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_mincost_ffalg| finds optimal solution to the
alpar@9: maximum flow problem with the Ford-Fulkerson algorithm.\footnote{GLPK
alpar@9: implementation of the Ford-Fulkerson algorithm is based on the following
alpar@9: book: L.~R.~Ford,~Jr., and D.~R.~Fulkerson, ``Flows in Networks,'' The
alpar@9: RAND Corp., Report\linebreak R-375-PR (August 1962), Chap. I
alpar@9: ``Static Maximal Flow,'' pp.~30-33.} Note that this routine requires all
alpar@9: the problem data to be integer-valued.
alpar@9: 
alpar@9: The parameter \verb|G| is a graph (network) program object which
alpar@9: specifies the maximum flow problem instance to be solved.
alpar@9: 
alpar@9: The parameter $s$ specifies the ordinal number of the source node.
alpar@9: 
alpar@9: The parameter $t$ specifies the ordinal number of the sink node.
alpar@9: 
alpar@9: The parameter \verb|a_cap| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, which contains $u_{ij}$, the upper
alpar@9: bound to the arc flow (the arc capacity). This bound must be integer in
alpar@9: the range [0, \verb|INT_MAX|]. If \verb|a_cap| $<0$, it is assumed that
alpar@9: $u_{ij}=1$ for all arcs.
alpar@9: 
alpar@9: The parameter \verb|sol| specifies a location, to which the routine
alpar@9: stores the objective value (that is, the total flow from $s$ to $t$)
alpar@9: found. If \verb|sol| is NULL, the objective value is not stored.
alpar@9: 
alpar@9: The parameter \verb|a_x| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, to which the routine stores
alpar@9: $x_{ij}$, the arc flow found. If \verb|a_x| $<0$, the arc flow values
alpar@9: are not stored.
alpar@9: 
alpar@9: The parameter \verb|v_cut| specifies an offset of the field of type
alpar@9: \verb|int| in the vertex data block, to which the routine stores node
alpar@9: flags corresponding to the optimal solution found: if the node flag is
alpar@9: 1, the node is labelled, and if the node flag is 0, the node is
alpar@9: unlabelled. The calling program may use these node flags to determine
alpar@9: the {\it minimal cut}, which is a subset of arcs whose one endpoint is
alpar@9: labelled and other is not. If \verb|v_cut| $<0$, the node flags are not
alpar@9: stored.
alpar@9: 
alpar@9: Note that all solution components (the objective value and arc flows)
alpar@9: computed by the routine are always integer-valued.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: \def\arraystretch{1}
alpar@9: 
alpar@9: \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
alpar@9: 0 & Optimal solution found.\\
alpar@9: \verb|GLP_EDATA| & Unable to start the search, because some problem
alpar@9: data are either not integer-valued or out of range.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsubsection*{Example}
alpar@9: 
alpar@9: The example program shown below reads the maximum flow problem instance
alpar@9: in DIMACS format from file `\verb|sample.max|', solves it using the
alpar@9: routine \verb|glp_maxflow_ffalg|, and write the solution found to the
alpar@9: standard output.
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: #include <stddef.h>
alpar@9: #include <stdio.h>
alpar@9: #include <stdlib.h>
alpar@9: #include <glpk.h>
alpar@9: 
alpar@9: typedef struct { int cut; } v_data;
alpar@9: typedef struct { double cap, x; } a_data;
alpar@9: 
alpar@9: #define node(v) ((v_data *)((v)->data))
alpar@9: #define arc(a)  ((a_data *)((a)->data))
alpar@9: 
alpar@9: int main(void)
alpar@9: {     glp_graph *G;
alpar@9:       glp_vertex *v, *w;
alpar@9:       glp_arc *a;
alpar@9:       int i, s, t, ret;
alpar@9:       double sol;
alpar@9:       G = glp_create_graph(sizeof(v_data), sizeof(a_data));
alpar@9:       glp_read_maxflow(G, &s, &t, offsetof(a_data, cap),
alpar@9:          "sample.max");
alpar@9:       ret = glp_maxflow_ffalg(G, s, t, offsetof(a_data, cap),
alpar@9:          &sol, offsetof(a_data, x), offsetof(v_data, cut));
alpar@9:       printf("ret = %d; sol = %5g\n", ret, sol);
alpar@9:       for (i = 1; i <= G->nv; i++)
alpar@9:       {  v = G->v[i];
alpar@9:          for (a = v->out; a != NULL; a = a->t_next)
alpar@9:          {  w = a->head;
alpar@9:             printf("x[%d->%d] = %5g (%d)\n", v->i, w->i,
alpar@9:                arc(a)->x, node(v)->cut ^ node(w)->cut);
alpar@9:          }
alpar@9:       }
alpar@9:       glp_delete_graph(G);
alpar@9:       return 0;
alpar@9: }
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: If `\verb|sample.max|' is the example data file from the subsection
alpar@9: describing the routine \verb|glp_read_maxflow|, the output may look like
alpar@9: follows:
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: Reading maximum flow problem data from `sample.max'...
alpar@9: Flow network has 9 nodes and 14 arcs
alpar@9: 24 lines were read
alpar@9: ret = 0; sol =    29
alpar@9: x[1->4] =    19 (0)
alpar@9: x[1->2] =    10 (0)
alpar@9: x[2->4] =     0 (0)
alpar@9: x[2->3] =    10 (1)
alpar@9: x[3->8] =    10 (0)
alpar@9: x[3->5] =     0 (1)
alpar@9: x[4->5] =    19 (0)
alpar@9: x[5->7] =     4 (1)
alpar@9: x[5->6] =    15 (0)
alpar@9: x[5->2] =     0 (0)
alpar@9: x[6->8] =     8 (1)
alpar@9: x[6->7] =     7 (1)
alpar@9: x[7->9] =    11 (0)
alpar@9: x[8->9] =    18 (0)
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_rmfgen---Goldfarb's maximum flow problem generator}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_rmfgen(glp_graph *G, int *s, int *t, int a_cap,
alpar@9:       const int parm[1+5]);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_rmfgen| is a GLPK version of the maximum flow
alpar@9: problem generator developed by D.~Goldfarb and
alpar@9: M.~Grigoriadis.\footnote{D.~Goldfarb and M.~D.~Grigoriadis,
alpar@9: ``A computational comparison of the Dinic and network simplex methods
alpar@9: for maximum flow.'' Annals of Op. Res. 13 (1988),
alpar@9: pp.~83-123.}$^{,}$\footnote{U.~Derigs and W.~Meier, ``Implementing
alpar@9: Goldberg's max-flow algorithm: A computational investigation.''
alpar@9: Zeitschrift f\"ur Operations Research 33 (1989),
alpar@9: pp.~383-403.}$^{,}$\footnote{The original code of RMFGEN implemented by
alpar@9: Tamas Badics is publically available from
alpar@9: {\tt <ftp://dimacs.rutgers.edu/pub/netflow/generators/network/genrmf>}.}
alpar@9: 
alpar@9: The parameter \verb|G| specifies the graph object, to which the
alpar@9: generated problem data have to be stored. Note that on entry the graph
alpar@9: object is erased with the routine \verb|glp_erase_graph|.
alpar@9: 
alpar@9: The pointers \verb|s| and \verb|t| specify locations, to which the
alpar@9: routine stores the source and sink node numbers, respectively. If
alpar@9: \verb|s| or \verb|t| is \verb|NULL|, corresponding node number is not
alpar@9: stored.
alpar@9: 
alpar@9: The parameter \verb|a_cap| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, to which the routine stores the arc
alpar@9: capacity. If \verb|a_cap| $<0$, the capacity is not stored.
alpar@9: 
alpar@9: The array \verb|parm| contains description of the network to be
alpar@9: generated:
alpar@9: 
alpar@9: \begin{tabular}{@{}lll@{}}
alpar@9: \verb|parm[0]|&           &not used\\
alpar@9: \verb|parm[1]|&\verb|seed|&random number seed (a positive integer)\\
alpar@9: \verb|parm[2]|&\verb|a   |&frame size\\
alpar@9: \verb|parm[3]|&\verb|b   |&depth\\
alpar@9: \verb|parm[4]|&\verb|c1  |&minimal arc capacity\\
alpar@9: \verb|parm[5]|&\verb|c2  |&maximal arc capacity\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: If the instance was successfully generated, the routine
alpar@9: \verb|glp_netgen| returns zero; otherwise, if specified parameters are
alpar@9: inconsistent, the routine returns a non-zero error code.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsubsection*{Comments\footnote{This material is based on comments
alpar@9: to the original version of RMFGEN.}}
alpar@9: 
alpar@9: The generated network is as follows. It has $b$ pieces of frames of
alpar@9: size $a\times a$. (So alltogether the number of vertices is
alpar@9: $a\times a\times b$.)
alpar@9: 
alpar@9: In each frame all the vertices are connected with their neighbours
alpar@9: (forth and back). In addition the vertices of a frame are connected
alpar@9: one to one with the vertices of next frame using a random permutation
alpar@9: of those vertices.
alpar@9: 
alpar@9: The source is the lower left vertex of the first frame, the sink is
alpar@9: the upper right vertex of the $b$-th frame.
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:                               t
alpar@9:                      +-------+
alpar@9:                      |      .|
alpar@9:                      |     . |
alpar@9:                   /  |    /  |
alpar@9:                  +-------+/ -+ b
alpar@9:                  |    |  |/.
alpar@9:                a |   -v- |/
alpar@9:                  |    |  |/
alpar@9:                  +-------+ 1
alpar@9:                 s    a
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: The capacities are randomly chosen integers from the range of
alpar@9: $[c_1,c_2]$  in the case of interconnecting edges, and $c_2\cdot a^2$
alpar@9: for the in-frame edges.
alpar@9: 
alpar@9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \section{Assignment problem}
alpar@9: 
alpar@9: \subsection{Background}
alpar@9: 
alpar@9: Let there be given an undirected bipartite graph $G=(R\cup S,E)$, where
alpar@9: $R$ and $S$ are disjoint sets of vertices (nodes), and
alpar@9: $E\subseteq R\times S$ is a set of edges. Let also for each edge
alpar@9: $e=(i,j)\in E$ there be given its cost $c_{ij}$. A {\it matching}
alpar@9: (which in case of bipartite graph is also called {\it assignment})
alpar@9: $M\subseteq E$ in $G$ is a set of pairwise non-adjacent edges, that is,
alpar@9: no two edges in $M$ share a common vertex. A matching, which matches
alpar@9: all vertices of the graph, is called a {\it perfect matching}.
alpar@9: Obviously, a perfect matching in bipartite graph $G=(R\cup S,E)$
alpar@9: defines some bijection $R\leftrightarrow S$.
alpar@9: 
alpar@9: The {\it assignment problem} has two different variants. In the first
alpar@9: variant the problem is to find matching (assignment) $M$, which
alpar@9: maximizes the sum:
alpar@9: $$\sum_{(i,j)\in M}c_{ij}\eqno(10)$$
alpar@9: (so this variant is also called the {\it maximum weighted bipartite
alpar@9: matching problem} or, if all $c_{ij}=1$, the {\it maximum cardinality
alpar@9: bipartite matching problem}). In the second, classic variant the
alpar@9: problem is to find {\it perfect} matching (assignment) $M$, which
alpar@9: minimizes or maximizes the sum (10).
alpar@9: 
alpar@9: An example of the assignment problem, which is the maximum weighted
alpar@9: bipartite matching problem, is shown on Fig. 3.
alpar@9: 
alpar@9: The maximum weighted bipartite matching problem can be naturally
alpar@9: formulated as the following LP problem:
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \hspace{.5in}maximize
alpar@9: $$z=\sum_{(i,j)\in E}c_{ij}x_{ij}\eqno(11)$$
alpar@9: \hspace{.5in}subject to
alpar@9: $$\sum_{(i,j)\in E}x_{ij}\leq 1\ \ \ \hbox{for all}\ i\in R\eqno(12)$$
alpar@9: $$\sum_{(i,j)\in E}x_{ij}\leq 1\ \ \ \hbox{for all}\ j\in S\eqno(13)$$
alpar@9: $$\ \ \ \ \ \ \ \ 0\leq x_{ij}\leq 1\ \ \ \hbox{for all}\ (i,j)\in E
alpar@9: \eqno(14)$$
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: where $x_{ij}=1$ means that $(i,j)\in M$, and $x_{ij}=0$ means that
alpar@9: $(i,j)\notin M$.\footnote{The constraint matrix of LP formulation
alpar@9: (11)---(14) is totally unimodular, due to which $x_{ij}\in\{0,1\}$ for
alpar@9: any basic solution.}
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: \noindent\hfil
alpar@9: \xymatrix @C=48pt
alpar@9: {v_1\ar@{-}[rr]|{_{13}}\ar@{-}[rrd]|{_{21}}\ar@{-}[rrddd]|(.2){_{20}}&&
alpar@9: v_9\\
alpar@9: v_2\ar@{-}[rr]|{_{12}}\ar@{-}[rrdd]|(.3){_{8}}
alpar@9: \ar@{-}[rrddd]|(.4){_{26}}&&v_{10}\\
alpar@9: v_3\ar@{-}[rr]|(.2){_{22}}\ar@{-}[rrdd]|(.3){_{11}}&&v_{11}\\
alpar@9: v_4\ar@{-}[rruuu]|(.6){_{12}}\ar@{-}[rr]|(.2){_{36}}
alpar@9: \ar@{-}[rrdd]|(.7){_{25}}&&v_{12}\\
alpar@9: v_5\ar@{-}[rruu]|(.42){_{41}}\ar@{-}[rru]|(.4){_{40}}
alpar@9: \ar@{-}[rr]|(.75){_{11}}\ar@{-}[rrd]|(.6){_{4}}\ar@{-}[rrdd]|{_{8}}
alpar@9: \ar@{-}[rrddd]|{_{35}}\ar@{-}[rrdddd]|{_{32}}&&v_{13}\\
alpar@9: v_6\ar@{-}[rruuuuu]|(.7){_{13}}&&v_{14}\\
alpar@9: v_7\ar@{-}[rruuuuu]|(.15){_{19}}&&v_{15}\\
alpar@9: v_8\ar@{-}[rruuuuuu]|(.25){_{39}}\ar@{-}[rruuuuu]|(.65){_{15}}&&
alpar@9: v_{16}\\
alpar@9: &&v_{17}\\
alpar@9: }
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: \noindent\hfil
alpar@9: Fig.~3. An example of the assignment problem.
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: Similarly, the perfect assignment problem can be naturally formulated
alpar@9: as the following LP problem:
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \hspace{.5in}minimize (or maximize)
alpar@9: $$z=\sum_{(i,j)\in E}c_{ij}x_{ij}\eqno(15)$$
alpar@9: \hspace{.5in}subject to
alpar@9: $$\sum_{(i,j)\in E}x_{ij}=1\ \ \ \hbox{for all}\ i\in R\eqno(16)$$
alpar@9: $$\sum_{(i,j)\in E}x_{ij}=1\ \ \ \hbox{for all}\ j\in S\eqno(17)$$
alpar@9: $$\ \ \ \ \ \ \ \ 0\leq x_{ij}\leq 1\ \ \ \hbox{for all}\ (i,j)\in E
alpar@9: \eqno(18)$$
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: where variables $x_{ij}$ have the same meaning as for (11)---(14)
alpar@9: above.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: In GLPK an undirected bipartite graph $G=(R\cup S,E)$ is represented as
alpar@9: directed graph $\overline{G}=(V,A)$, where $V=R\cup S$ and
alpar@9: $A=\{(i,j):(i,j)\in E\}$, i.e. every edge $(i,j)\in E$ in $G$
alpar@9: corresponds to arc $(i\rightarrow j)\in A$ in $\overline{G}$.
alpar@9: 
alpar@9: \subsection{glp\_read\_asnprob---read assignment problem data in\\DIMACS
alpar@9: format}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_read_asnprob(glp_graph *G, int v_set, int a_cost,
alpar@9:       const char *fname);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_read_asnprob| reads the assignment problem data
alpar@9: from a text file in DIMACS format.
alpar@9: 
alpar@9: The parameter \verb|G| specifies the graph object, to which the problem
alpar@9: data have to be stored. Note that before reading data the current
alpar@9: content of the graph object is completely erased with the routine
alpar@9: \verb|glp_erase_graph|.
alpar@9: 
alpar@9: The parameter \verb|v_set| specifies an offset of the field of type
alpar@9: \verb|int| in the vertex data block, to which the routine stores the
alpar@9: node set indicator:
alpar@9: 
alpar@9: 0 --- the node is in set $R$;
alpar@9: 
alpar@9: 1 --- the node is in set $S$.
alpar@9: 
alpar@9: \noindent
alpar@9: If \verb|v_set| $<0$, the node set indicator is not stored.
alpar@9: 
alpar@9: The parameter \verb|a_cost| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, to which the routine stores the
alpar@9: edge cost $c_{ij}$. If \verb|a_cost| $<0$, the edge cost is not stored.
alpar@9: 
alpar@9: The character string \verb|fname| specifies the name of a text file to
alpar@9: be read in. (If the file name name ends with the suffix `\verb|.gz|',
alpar@9: the file is assumed to be compressed, in which case the routine
alpar@9: decompresses it ``on the fly''.)
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: If the operation was successful, the routine returns zero. Otherwise,
alpar@9: it prints an error message and returns non-zero.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsubsection*{Example}
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: typedef struct
alpar@9: {     /* vertex data block */
alpar@9:       ...
alpar@9:       int set;
alpar@9:       ...
alpar@9: } v_data;
alpar@9: 
alpar@9: typedef struct
alpar@9: {     /* arc data block */
alpar@9:       ...
alpar@9:       double cost;
alpar@9:       ...
alpar@9: } a_data;
alpar@9: 
alpar@9: int main(void)
alpar@9: {     glp_graph *G;
alpar@9:       int ret;
alpar@9:       G = glp_create_graph(sizeof(v_data), sizeof(a_data));
alpar@9:       ret = glp_read_asnprob(G, offsetof(v_data, set),
alpar@9:          offsetof(a_data, cost), "sample.asn");
alpar@9:       if (ret != 0) goto ...
alpar@9:       ...
alpar@9: }
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \subsubsection*{DIMACS assignment problem format\footnote{This
alpar@9: material is based on the paper ``The First DIMACS International
alpar@9: Algorithm Implementation Challenge: Problem Definitions and
alpar@9: Specifications'', which is publically available at
alpar@9: {\tt http://dimacs.rutgers.edu/Challenges/}.}}
alpar@9: \label{subsecasnprob}
alpar@9: 
alpar@9: The DIMACS input file is a plain ASCII text file. It contains
alpar@9: {\it lines} of several types described below. A line is terminated with
alpar@9: an end-of-line character. Fields in each line are separated by at least
alpar@9: one blank space. Each line begins with a one-character designator to
alpar@9: identify the line type.
alpar@9: 
alpar@9: Note that DIMACS requires all numerical quantities to be integers in
alpar@9: the range $[-2^{31},\ 2^{31}-1]$ while GLPK allows the quantities to be
alpar@9: floating-point numbers.
alpar@9: 
alpar@9: \paragraph{Comment lines.} Comment lines give human-readable information
alpar@9: about the file and are ignored by programs. Comment lines can appear
alpar@9: anywhere in the file. Each comment line begins with a lower-case
alpar@9: character \verb|c|.
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    c This is a comment line
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \paragraph{Problem line.} There is one problem line per data file. The
alpar@9: problem line must appear before any node or arc descriptor lines. It has
alpar@9: the following format:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    p asn NODES EDGES
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: The lower-case character \verb|p| signifies that this is a problem line.
alpar@9: The three-character problem designator \verb|asn| identifies the file as
alpar@9: containing specification information for the assignment problem.
alpar@9: The \verb|NODES| field contains an integer value specifying the total
alpar@9: number of nodes in the graph (i.e. in both sets $R$ and $S$). The
alpar@9: \verb|EDGES| field contains an integer value specifying the number of
alpar@9: edges in the graph.
alpar@9: 
alpar@9: \paragraph{Node descriptors.} All node descriptor lines must appear
alpar@9: before all edge descriptor lines. The node descriptor lines lists the
alpar@9: nodes in set $R$ only, and all other nodes are assumed to be in set
alpar@9: $S$. There is one node descriptor line for each such node, with the
alpar@9: following format:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    n ID
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: The lower-case character \verb|n| signifies that this is a node
alpar@9: descriptor line. The \verb|ID| field gives a node identification number,
alpar@9: an integer between 1 and \verb|NODES|.
alpar@9: 
alpar@9: \paragraph{Edge descriptors.} There is one edge descriptor line for
alpar@9: each edge in the graph. Edge descriptor lines are of the following
alpar@9: format:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    a SRC DST COST
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: The lower-case character \verb|a| signifies that this is an edge
alpar@9: descriptor line. For each edge $(i,j)$, where $i\in R$ and $j\in S$,
alpar@9: the \verb|SRC| field gives the identification number of vertex $i$, and
alpar@9: the \verb|DST| field gives the identification number of vertex $j$.
alpar@9: Identification numbers are integers between 1 and \verb|NODES|. The
alpar@9: \verb|COST| field contains the cost of edge $(i,j)$.
alpar@9: 
alpar@9: \paragraph{Example.} Below here is an example of the data file in
alpar@9: DIMACS format corresponding to the assignment problem shown on Fig~3.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: c sample.asn
alpar@9: c
alpar@9: c This is an example of the assignment problem data
alpar@9: c in DIMACS format.
alpar@9: c
alpar@9: p asn 17 22
alpar@9: c
alpar@9: n 1
alpar@9: n 2
alpar@9: n 3
alpar@9: n 4
alpar@9: n 5
alpar@9: n 6
alpar@9: n 7
alpar@9: n 8
alpar@9: c
alpar@9: a 1  9 13
alpar@9: a 1 10 21
alpar@9: a 1 12 20
alpar@9: a 2 10 12
alpar@9: a 2 12  8
alpar@9: a 2 13 26
alpar@9: a 3 11 22
alpar@9: a 3 13 11
alpar@9: a 4  9 12
alpar@9: a 4 12 36
alpar@9: a 4 14 25
alpar@9: a 5 11 41
alpar@9: a 5 12 40
alpar@9: a 5 13 11
alpar@9: a 5 14  4
alpar@9: a 5 15  8
alpar@9: a 5 16 35
alpar@9: a 5 17 32
alpar@9: a 6  9 13
alpar@9: a 7 10 19
alpar@9: a 8 10 39
alpar@9: a 8 11 15
alpar@9: c
alpar@9: c eof
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_write\_asnprob---write assignment problem data in\\
alpar@9: DIMACS format}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_write_asnprob(glp_graph *G, int v_set, int a_cost,
alpar@9:       const char *fname);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_write_asnprob| writes the assignment problem data
alpar@9: to a text file in DIMACS format.
alpar@9: 
alpar@9: The parameter \verb|G| is the graph program object, which specifies the
alpar@9: assignment problem instance.
alpar@9: 
alpar@9: The parameter \verb|v_set| specifies an offset of the field of type
alpar@9: \verb|int| in the vertex data block, which contains the node set
alpar@9: indicator:
alpar@9: 
alpar@9: 0 --- the node is in set $R$;
alpar@9: 
alpar@9: 1 --- the node is in set $S$.
alpar@9: 
alpar@9: \noindent
alpar@9: If \verb|v_set| $<0$, it is assumed that a node having no incoming arcs
alpar@9: is in set $R$, and a node having no outgoing arcs is in set $S$.
alpar@9: 
alpar@9: The parameter \verb|a_cost| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, which contains $c_{ij}$, the edge
alpar@9: cost. If \verb|a_cost| $<0$, it is assumed that $c_{ij}=1$ for all
alpar@9: edges.
alpar@9: 
alpar@9: The character string \verb|fname| specifies a name of the text file to
alpar@9: be written out. (If the file name ends with suffix `\verb|.gz|', the
alpar@9: file is assumed to be compressed, in which case the routine performs
alpar@9: automatic compression on writing it.)
alpar@9: 
alpar@9: \subsubsection*{Note}
alpar@9: 
alpar@9: The routine \verb|glp_write_asnprob| does not check that the specified
alpar@9: graph object correctly represents a bipartite graph. To make sure that
alpar@9: the problem data are correct, use the routine \verb|glp_check_asnprob|.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: If the operation was successful, the routine returns zero. Otherwise,
alpar@9: it prints an error message and returns non-zero.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_check\_asnprob---check correctness of assignment
alpar@9: problem data}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_check_asnprob(glp_graph *G, int v_set);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_check_asnprob| checks that the specified graph
alpar@9: object \verb|G| correctly represents a bipartite graph.
alpar@9: 
alpar@9: The parameter \verb|v_set| specifies an offset of the field of type
alpar@9: \verb|int| in the vertex data block, which contains the node set
alpar@9: indicator:
alpar@9: 
alpar@9: 0 --- the node is in set $R$;
alpar@9: 
alpar@9: 1 --- the node is in set $S$.
alpar@9: 
alpar@9: \noindent
alpar@9: If \verb|v_set| $<0$, it is assumed that a node having no incoming arcs
alpar@9: is in set $R$, and a node having no outgoing arcs is in set $S$.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_check_asnprob| may return the following codes:
alpar@9: 
alpar@9: 0 --- the data are correct;
alpar@9: 
alpar@9: 1 --- the set indicator of some node is 0, however, that node has one
alpar@9: or more incoming arcs;
alpar@9: 
alpar@9: 2 --- the set indicator of some node is 1, however, that node has one
alpar@9: or more outgoing arcs;
alpar@9: 
alpar@9: 3 --- the set indicator of some node is invalid (neither 0 nor 1);
alpar@9: 
alpar@9: 4 --- some node has both incoming and outgoing arcs.
alpar@9: 
alpar@9: \subsection{glp\_asnprob\_lp---convert assignment problem to LP}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_asnprob_lp(glp_prob *P, int form, glp_graph *G,
alpar@9:       int names, int v_set, int a_cost);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_asnprob_lp| builds LP problem, which corresponds
alpar@9: to the specified assignment problem.
alpar@9: 
alpar@9: The parameter \verb|lp| is the resultant LP problem object to be built.
alpar@9: Note that on entry its current content is erased with the routine
alpar@9: \verb|glp_erase_prob|.
alpar@9: 
alpar@9: The parameter \verb|form| defines which LP formulation should be used:
alpar@9: 
alpar@9: \verb|GLP_ASN_MIN| --- perfect matching (15)---(18), minimization;
alpar@9: 
alpar@9: \verb|GLP_ASN_MAX| --- perfect matching (15)---(18), maximization;
alpar@9: 
alpar@9: \verb|GLP_ASN_MMP| --- maximum weighted matching (11)---(14).
alpar@9: 
alpar@9: The parameter \verb|G| is the graph program object, which specifies the
alpar@9: assignment problem instance.
alpar@9: 
alpar@9: The parameter \verb|names| is a flag. If it is \verb|GLP_ON|, the
alpar@9: routine uses symbolic names of the graph object components to assign
alpar@9: symbolic names to the LP problem object components. If the \verb|flag|
alpar@9: is \verb|GLP_OFF|, no symbolic names are assigned.
alpar@9: 
alpar@9: The parameter \verb|v_set| specifies an offset of the field of type
alpar@9: \verb|int| in the vertex data block, which contains the node set
alpar@9: indicator:
alpar@9: 
alpar@9: 0 --- the node is in set $R$;
alpar@9: 
alpar@9: 1 --- the node is in set $S$.
alpar@9: 
alpar@9: \noindent
alpar@9: If \verb|v_set| $<0$, it is assumed that a node having no incoming arcs
alpar@9: is in set $R$, and a node having no outgoing arcs is in set $S$.
alpar@9: 
alpar@9: The parameter \verb|a_cost| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, which contains $c_{ij}$, the edge
alpar@9: cost. If \verb|a_cost| $<0$, it is assumed that $c_{ij}=1$ for all
alpar@9: edges.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: If the LP problem has been successfully built, the routine
alpar@9: \verb|glp_asnprob_lp| returns zero, otherwise, non-zero (see the
alpar@9: routine \verb|glp_check_asnprob|).
alpar@9: 
alpar@9: \subsubsection*{Example}
alpar@9: 
alpar@9: The example program below reads the assignment problem instance in
alpar@9: DIMACS format from file `\verb|sample.asn|', converts the instance to
alpar@9: LP (11)---(14), and writes the resultant LP in CPLEX format to file
alpar@9: `\verb|matching.lp|'.
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: #include <stddef.h>
alpar@9: #include <glpk.h>
alpar@9: 
alpar@9: typedef struct { int set; } v_data;
alpar@9: typedef struct { double cost; } a_data;
alpar@9: 
alpar@9: int main(void)
alpar@9: {     glp_graph *G;
alpar@9:       glp_prob *P;
alpar@9:       G = glp_create_graph(sizeof(v_data), sizeof(a_data));
alpar@9:       glp_read_asnprob(G, offsetof(v_data, set),
alpar@9:          offsetof(a_data, cost), "sample.asn");
alpar@9:       P = glp_create_prob();
alpar@9:       glp_asnprob_lp(P, GLP_ASN_MMP, G, GLP_ON,
alpar@9:          offsetof(v_data, set), offsetof(a_data, cost));
alpar@9:       glp_delete_graph(G);
alpar@9:       glp_write_lp(P, NULL, "matching.lp");
alpar@9:       glp_delete_prob(P);
alpar@9:       return 0;
alpar@9: }
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: If `\verb|sample.asn|' is the example data file from the subsection
alpar@9: describing the routine \verb|glp_read_asnprob|, file
alpar@9: `\verb|matching.lp|' may look like follows:
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: Maximize
alpar@9:  obj: + 20 x(1,12) + 21 x(1,10) + 13 x(1,9) + 26 x(2,13) + 8 x(2,12)
alpar@9:  + 12 x(2,10) + 11 x(3,13) + 22 x(3,11) + 25 x(4,14) + 36 x(4,12)
alpar@9:  + 12 x(4,9) + 32 x(5,17) + 35 x(5,16) + 8 x(5,15) + 4 x(5,14)
alpar@9:  + 11 x(5,13) + 40 x(5,12) + 41 x(5,11) + 13 x(6,9) + 19 x(7,10)
alpar@9:  + 15 x(8,11) + 39 x(8,10)
alpar@9: 
alpar@9: Subject To
alpar@9:  r_1: + x(1,9) + x(1,10) + x(1,12) <= 1
alpar@9:  r_2: + x(2,10) + x(2,12) + x(2,13) <= 1
alpar@9:  r_3: + x(3,11) + x(3,13) <= 1
alpar@9:  r_4: + x(4,9) + x(4,12) + x(4,14) <= 1
alpar@9:  r_5: + x(5,11) + x(5,12) + x(5,13) + x(5,14) + x(5,15) + x(5,16)
alpar@9:  + x(5,17) <= 1
alpar@9:  r_6: + x(6,9) <= 1
alpar@9:  r_7: + x(7,10) <= 1
alpar@9:  r_8: + x(8,10) + x(8,11) <= 1
alpar@9:  r_9: + x(6,9) + x(4,9) + x(1,9) <= 1
alpar@9:  r_10: + x(8,10) + x(7,10) + x(2,10) + x(1,10) <= 1
alpar@9:  r_11: + x(8,11) + x(5,11) + x(3,11) <= 1
alpar@9:  r_12: + x(5,12) + x(4,12) + x(2,12) + x(1,12) <= 1
alpar@9:  r_13: + x(5,13) + x(3,13) + x(2,13) <= 1
alpar@9:  r_14: + x(5,14) + x(4,14) <= 1
alpar@9:  r_15: + x(5,15) <= 1
alpar@9:  r_16: + x(5,16) <= 1
alpar@9:  r_17: + x(5,17) <= 1
alpar@9: 
alpar@9: Bounds
alpar@9:  0 <= x(1,12) <= 1
alpar@9:  0 <= x(1,10) <= 1
alpar@9:  0 <= x(1,9) <= 1
alpar@9:  0 <= x(2,13) <= 1
alpar@9:  0 <= x(2,12) <= 1
alpar@9:  0 <= x(2,10) <= 1
alpar@9:  0 <= x(3,13) <= 1
alpar@9:  0 <= x(3,11) <= 1
alpar@9:  0 <= x(4,14) <= 1
alpar@9:  0 <= x(4,12) <= 1
alpar@9:  0 <= x(4,9) <= 1
alpar@9:  0 <= x(5,17) <= 1
alpar@9:  0 <= x(5,16) <= 1
alpar@9:  0 <= x(5,15) <= 1
alpar@9:  0 <= x(5,14) <= 1
alpar@9:  0 <= x(5,13) <= 1
alpar@9:  0 <= x(5,12) <= 1
alpar@9:  0 <= x(5,11) <= 1
alpar@9:  0 <= x(6,9) <= 1
alpar@9:  0 <= x(7,10) <= 1
alpar@9:  0 <= x(8,11) <= 1
alpar@9:  0 <= x(8,10) <= 1
alpar@9: 
alpar@9: End
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \subsection{glp\_asnprob\_okalg---solve assignment problem with
alpar@9: out-of-kilter algorithm}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_asnprob_okalg(int form, glp_graph *G, int v_set,
alpar@9:       int a_cost, double *sol, int a_x);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_mincost_okalg| finds optimal solution to the
alpar@9: assignment problem with the out-of-kilter
alpar@9: algorithm.\footnote{GLPK implementation of the out-of-kilter algorithm
alpar@9: is based on the following book: L.~R.~Ford,~Jr., and D.~R.~Fulkerson,
alpar@9: ``Flows in Networks,'' The RAND Corp., Report R-375-PR (August 1962),
alpar@9: Chap. III ``Minimal Cost Flow Problems,'' pp.~113-26.} Note that this
alpar@9: routine requires all the problem data to be integer-valued.
alpar@9: 
alpar@9: The parameter \verb|form| defines which LP formulation should be used:
alpar@9: 
alpar@9: \verb|GLP_ASN_MIN| --- perfect matching (15)---(18), minimization;
alpar@9: 
alpar@9: \verb|GLP_ASN_MAX| --- perfect matching (15)---(18), maximization;
alpar@9: 
alpar@9: \verb|GLP_ASN_MMP| --- maximum weighted matching (11)---(14).
alpar@9: 
alpar@9: The parameter \verb|G| is the graph program object, which specifies the
alpar@9: assignment problem instance.
alpar@9: 
alpar@9: The parameter \verb|v_set| specifies an offset of the field of type
alpar@9: \verb|int| in the vertex data block, which contains the node set
alpar@9: indicator:
alpar@9: 
alpar@9: 0 --- the node is in set $R$;
alpar@9: 
alpar@9: 1 --- the node is in set $S$.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \noindent
alpar@9: If \verb|v_set| $<0$, it is assumed that a node having no incoming arcs
alpar@9: is in set $R$, and a node having no outgoing arcs is in set $S$.
alpar@9: 
alpar@9: The parameter \verb|a_cost| specifies an offset of the field of type
alpar@9: \verb|double| in the arc data block, which contains $c_{ij}$, the edge
alpar@9: cost. This value must be integer in the range [\verb|-INT_MAX|,
alpar@9: \verb|+INT_MAX|]. If \verb|a_cost| $<0$, it is assumed that $c_{ij}=1$
alpar@9: for all edges.
alpar@9: 
alpar@9: The parameter \verb|sol| specifies a location, to which the routine
alpar@9: stores the objective value (that is, the total cost) found.
alpar@9: If \verb|sol| is \verb|NULL|, the objective value is not stored.
alpar@9: 
alpar@9: The parameter \verb|a_x| specifies an offset of the field of type
alpar@9: \verb|int| in the arc data block, to which the routine stores $x_{ij}$.
alpar@9: If \verb|a_x| $<0$, this value is not stored.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: \def\arraystretch{1}
alpar@9: 
alpar@9: \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
alpar@9: 0 & Optimal solution found.\\
alpar@9: \verb|GLP_ENOPFS| & No (primal) feasible solution exists.\\
alpar@9: \verb|GLP_EDATA| & Unable to start the search, because the assignment
alpar@9: problem data are either incorrect (this error is detected by the
alpar@9: routine \verb|glp_check_asnprob|), not integer-valued or out of range.\\
alpar@9: \verb|GLP_ERANGE| & The search was prematurely terminated because of
alpar@9: integer overflow.\\
alpar@9: \verb|GLP_EFAIL| & An error has been detected in the program logic.
alpar@9: (If this code is returned for your problem instance, please report to
alpar@9: \verb|<bug-glpk@gnu.org>|.)\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsubsection*{Comments}
alpar@9: 
alpar@9: Since the out-of-kilter algorithm is designed to find a minimal cost
alpar@9: circulation, the routine \verb|glp_asnprob_okalg| converts the original
alpar@9: graph to a network suitable for this algorithm in the following
alpar@9: way:\footnote{The conversion is performed internally and does not change
alpar@9: the original graph program object passed to the routine.}
alpar@9: 
alpar@9: 1) it replaces each edge $(i,j)$ by arc $(i\rightarrow j)$,
alpar@9: flow $x_{ij}$ through which has zero lower bound ($l_{ij}=0$), unity
alpar@9: upper bound ($u_{ij}=1$), and per-unit cost $+c_{ij}$ (in case of
alpar@9: \verb|GLP_ASN_MIN|), or $-c_{ij}$ (in case of \verb|GLP_ASN_MAX| and
alpar@9: \verb|GLP_ASN_MMP|);
alpar@9: 
alpar@9: 2) then it adds one auxiliary feedback node $k$;
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: 3) for each original node $i\in R$ the routine adds auxiliary supply
alpar@9: arc $(k\rightarrow i)$, flow $x_{ki}$ through which is costless
alpar@9: ($c_{ki}=0$) and either fixed at 1 ($l_{ki}=u_{ki}=1$, in case of
alpar@9: \verb|GLP_ASN_MIN| and \verb|GLP_ASN_MAX|) or has zero lower bound and
alpar@9: unity upper bound ($l_{ij}=0$, $u_{ij}=1$, in case of
alpar@9: \verb|GLP_ASN_MMP|);
alpar@9: 
alpar@9: 4) similarly, for each original node $j\in S$ the routine adds
alpar@9: auxiliary demand arc $(j\rightarrow k)$, flow $x_{jk}$ through which is
alpar@9: costless ($c_{jk}=0$) and either fixed at 1 ($l_{jk}=u_{jk}=1$, in case
alpar@9: of \verb|GLP_ASN_MIN| and \verb|GLP_ASN_MAX|) or has zero lower bound
alpar@9: and unity upper bound ($l_{jk}=0$, $u_{jk}=1$, in case of
alpar@9: \verb|GLP_ASN_MMP|).
alpar@9: 
alpar@9: \subsubsection*{Example}
alpar@9: 
alpar@9: The example program shown below reads the assignment problem instance
alpar@9: in DIMACS format from file `\verb|sample.asn|', solves it by using the
alpar@9: routine \verb|glp_asnprob_okalg|, and writes the solution found to the
alpar@9: standard output.
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: #include <stddef.h>
alpar@9: #include <stdio.h>
alpar@9: #include <stdlib.h>
alpar@9: #include <glpk.h>
alpar@9: 
alpar@9: typedef struct { int set; } v_data;
alpar@9: typedef struct { double cost; int x; } e_data;
alpar@9: 
alpar@9: #define node(v) ((v_data *)((v)->data))
alpar@9: #define edge(e) ((e_data *)((e)->data))
alpar@9: 
alpar@9: int main(void)
alpar@9: {     glp_graph *G;
alpar@9:       glp_vertex *v;
alpar@9:       glp_arc *e;
alpar@9:       int i, ret;
alpar@9:       double sol;
alpar@9:       G = glp_create_graph(sizeof(v_data), sizeof(e_data));
alpar@9:       glp_read_asnprob(G, offsetof(v_data, set),
alpar@9:          offsetof(e_data, cost), "sample.asn");
alpar@9:       ret = glp_asnprob_okalg(GLP_ASN_MMP, G,
alpar@9:          offsetof(v_data, set), offsetof(e_data, cost), &sol,
alpar@9:          offsetof(e_data, x));
alpar@9:       printf("ret = %d; sol = %5g\n", ret, sol);
alpar@9:       for (i = 1; i <= G->nv; i++)
alpar@9:       {  v = G->v[i];
alpar@9:          for (e = v->out; e != NULL; e = e->t_next)
alpar@9:             printf("edge %2d %2d: x = %d; c = %g\n",
alpar@9:                e->tail->i, e->head->i, edge(e)->x, edge(e)->cost);
alpar@9:       }
alpar@9:       glp_delete_graph(G);
alpar@9:       return 0;
alpar@9: }
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: If `\verb|sample.asn|' is the example data file from the subsection
alpar@9: describing the routine \verb|glp_read_asnprob|, the output may look
alpar@9: like follows:
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: Reading assignment problem data from `sample.asn'...
alpar@9: Assignment problem has 8 + 9 = 17 nodes and 22 arcs
alpar@9: 38 lines were read
alpar@9: ret = 0; sol =   180
alpar@9: edge  1 12: x = 1; c = 20
alpar@9: edge  1 10: x = 0; c = 21
alpar@9: edge  1  9: x = 0; c = 13
alpar@9: edge  2 13: x = 1; c = 26
alpar@9: edge  2 12: x = 0; c = 8
alpar@9: edge  2 10: x = 0; c = 12
alpar@9: edge  3 13: x = 0; c = 11
alpar@9: edge  3 11: x = 1; c = 22
alpar@9: edge  4 14: x = 1; c = 25
alpar@9: edge  4 12: x = 0; c = 36
alpar@9: edge  4  9: x = 0; c = 12
alpar@9: edge  5 17: x = 0; c = 32
alpar@9: edge  5 16: x = 1; c = 35
alpar@9: edge  5 15: x = 0; c = 8
alpar@9: edge  5 14: x = 0; c = 4
alpar@9: edge  5 13: x = 0; c = 11
alpar@9: edge  5 12: x = 0; c = 40
alpar@9: edge  5 11: x = 0; c = 41
alpar@9: edge  6  9: x = 1; c = 13
alpar@9: edge  7 10: x = 0; c = 19
alpar@9: edge  8 11: x = 0; c = 15
alpar@9: edge  8 10: x = 1; c = 39
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_asnprob\_hall---find bipartite matching of maximum
alpar@9: cardinality}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_asnprob_hall(glp_graph *G, int v_set, int a_x);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_asnprob_hall| finds a matching of maximal
alpar@9: cardinality in the specified bipartite graph. It uses a version of the
alpar@9: Fortran routine \verb|MC21A| developed by
alpar@9: I.~S.~Duff\footnote{I.~S.~Duff, Algorithm 575: Permutations for
alpar@9: zero-free diagonal, ACM Trans. on Math. Softw. 7 (1981), pp.~387-390.},
alpar@9: which implements Hall's algorithm.\footnote{M.~Hall, ``An Algorithm for
alpar@9: Distinct Representatives,'' Am. Math. Monthly 63 (1956), pp.~716-717.}
alpar@9: 
alpar@9: The parameter \verb|G| is a pointer to the graph program object.
alpar@9: 
alpar@9: The parameter \verb|v_set| specifies an offset of the field of type
alpar@9: \verb|int| in the vertex data block, which contains the node set
alpar@9: indicator:
alpar@9: 
alpar@9: 0 --- the node is in set $R$;
alpar@9: 
alpar@9: 1 --- the node is in set $S$.
alpar@9: 
alpar@9: \noindent
alpar@9: If \verb|v_set| $<0$, it is assumed that a node having no incoming arcs
alpar@9: is in set $R$, and a node having no outgoing arcs is in set $S$.
alpar@9: 
alpar@9: The parameter \verb|a_x| specifies an offset of the field of type
alpar@9: \verb|int| in the arc data block, to which the routine stores $x_{ij}$.
alpar@9: If \verb|a_x| $<0$, this value is not stored.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_asnprob_hall| returns the cardinality of the
alpar@9: matching found. However, if the specified graph is incorrect (as
alpar@9: detected by the routine \verb|glp_check_asnprob|), this routine returns
alpar@9: a negative value.
alpar@9: 
alpar@9: \subsubsection*{Comments}
alpar@9: 
alpar@9: The same solution may be obtained with the routine
alpar@9: \verb|glp_asnprob_okalg| (for LP formulation \verb|GLP_ASN_MMP| and
alpar@9: all edge costs equal to 1). However, the routine \verb|glp_asnprob_hall|
alpar@9: is much faster.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsubsection*{Example}
alpar@9: 
alpar@9: The example program shown below reads the assignment problem instance
alpar@9: in DIMACS format from file `\verb|sample.asn|', finds a bipartite
alpar@9: matching of maximal cardinality by using the routine
alpar@9: \verb|glp_asnprob_hall|, and writes the solution found to the standard
alpar@9: output.
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: #include <stddef.h>
alpar@9: #include <stdio.h>
alpar@9: #include <stdlib.h>
alpar@9: #include <glpk.h>
alpar@9: 
alpar@9: typedef struct { int set; } v_data;
alpar@9: typedef struct { int x;   } e_data;
alpar@9: 
alpar@9: #define node(v) ((v_data *)((v)->data))
alpar@9: #define edge(e) ((e_data *)((e)->data))
alpar@9: 
alpar@9: int main(void)
alpar@9: {     glp_graph *G;
alpar@9:       glp_vertex *v;
alpar@9:       glp_arc *e;
alpar@9:       int i, card;
alpar@9:       G = glp_create_graph(sizeof(v_data), sizeof(e_data));
alpar@9:       glp_read_asnprob(G, offsetof(v_data, set), -1,
alpar@9:          "sample.asn");
alpar@9:       card = glp_asnprob_hall(G, offsetof(v_data, set),
alpar@9:          offsetof(e_data, x));
alpar@9:       printf("card = %d\n", card);
alpar@9:       for (i = 1; i <= G->nv; i++)
alpar@9:       {  v = G->v[i];
alpar@9:          for (e = v->out; e != NULL; e = e->t_next)
alpar@9:             printf("edge %2d %2d: x = %d\n",
alpar@9:                e->tail->i, e->head->i, edge(e)->x);
alpar@9:       }
alpar@9:       glp_delete_graph(G);
alpar@9:       return 0;
alpar@9: }
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: If `\verb|sample.asn|' is the example data file from the subsection
alpar@9: describing the routine \verb|glp_read_asnprob|, the output may look
alpar@9: like follows:
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: Reading assignment problem data from `sample.asn'...
alpar@9: Assignment problem has 8 + 9 = 17 nodes and 22 arcs
alpar@9: 38 lines were read
alpar@9: card = 7
alpar@9: edge  1 12: x = 1
alpar@9: edge  1 10: x = 0
alpar@9: edge  1  9: x = 0
alpar@9: edge  2 13: x = 1
alpar@9: edge  2 12: x = 0
alpar@9: edge  2 10: x = 0
alpar@9: edge  3 13: x = 0
alpar@9: edge  3 11: x = 1
alpar@9: edge  4 14: x = 1
alpar@9: edge  4 12: x = 0
alpar@9: edge  4  9: x = 0
alpar@9: edge  5 17: x = 1
alpar@9: edge  5 16: x = 0
alpar@9: edge  5 15: x = 0
alpar@9: edge  5 14: x = 0
alpar@9: edge  5 13: x = 0
alpar@9: edge  5 12: x = 0
alpar@9: edge  5 11: x = 0
alpar@9: edge  6  9: x = 1
alpar@9: edge  7 10: x = 1
alpar@9: edge  8 11: x = 0
alpar@9: edge  8 10: x = 0
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \section{Critical path problem}
alpar@9: 
alpar@9: \subsection{Background}
alpar@9: 
alpar@9: The {\it critical path problem} (CPP) is stated as follows. Let there
alpar@9: be given a project $J$, which a set of jobs (tasks, activities, etc.).
alpar@9: Performing each job $i\in J$ requires time $t_i\geq 0$. Besides, over
alpar@9: the set $J$ there is given a precedence relation $R\subseteq J\times J$,
alpar@9: where $(i,j)\in R$ means that job $i$ immediately precedes job $j$, i.e.
alpar@9: performing job $j$ cannot start until job $i$ has been completely
alpar@9: performed. The problem is to find starting times $x_i$ for each job
alpar@9: $i\in J$, which satisfy to the precedence relation and minimize the
alpar@9: total duration (makespan) of the project.
alpar@9: 
alpar@9: The following is an example of the critical path problem:
alpar@9: 
alpar@9: \begin{center}
alpar@9: \begin{tabular}{|c|l|c|c|}
alpar@9: \hline
alpar@9: Job&Desription&Time&Predecessors\\
alpar@9: \hline
alpar@9: A&Excavate&3&---\\
alpar@9: B&Lay foundation&4&A\\
alpar@9: C&Rough plumbing&3&B\\
alpar@9: D&Frame&10&B\\
alpar@9: E&Finish exterior&8&D\\
alpar@9: F&Install HVAC&4&D\\
alpar@9: G&Rough electric&6&D\\
alpar@9: H&Sheet rock&8&C, E, F, G\\
alpar@9: I&Install cabinets&5&H\\
alpar@9: J&Paint&5&H\\
alpar@9: K&Final plumbing&4&I\\
alpar@9: L&Final electric&2&J\\
alpar@9: M&Install flooring&4&K, L\\
alpar@9: \hline
alpar@9: \end{tabular}
alpar@9: \end{center}
alpar@9: 
alpar@9: Obviously, the project along with the precedence relation can be
alpar@9: represented as a directed graph $G=(J,R)$ called {\it project network},
alpar@9: where each node $i\in J$ corresponds to a job, and arc
alpar@9: $(i\rightarrow j)\in R$ means that job $i$ immediately precedes job
alpar@9: $j$.\footnote{There exists another network representation of the
alpar@9: critical path problem, where jobs correspond to arcs while nodes
alpar@9: correspond to events introduced to express the precedence relation.
alpar@9: That representation, however, is much less convenient than the one,
alpar@9: where jobs are represented as nodes of the network.} The project network
alpar@9: for the example above is shown on Fig.~4.
alpar@9: 
alpar@9: May note that the project network must be acyclic; otherwise, it would
alpar@9: be impossible to satisfy to the precedence relation for any job that
alpar@9: belongs to a cycle.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \xymatrix
alpar@9: {&&&C|3\ar[rd]&&I|5\ar[r]&K|4\ar[rd]&\\
alpar@9: A|3\ar[r]&B|4\ar[rru]\ar[rd]&&E|8\ar[r]&H|8\ar[ru]\ar[rd]&&&M|4\\
alpar@9: &&D|10\ar[ru]\ar[r]\ar[rd]&F|4\ar[ru]&&J|5\ar[r]&L|2\ar[ru]&\\
alpar@9: &&&G|6\ar[ruu]&&&&\\
alpar@9: }
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: \noindent\hfil
alpar@9: Fig.~4. An example of the project network.
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: The critical path problem can be naturally formulated as the following
alpar@9: LP problem:
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \hspace{.5in}minimize
alpar@9: $$z\eqno(19)$$
alpar@9: \hspace{.5in}subject to
alpar@9: $$x_i+t_i\leq z\ \ \ \hbox{for all}\ i\in J\ \ \ \ \eqno(20)$$
alpar@9: $$x_i+t_i\leq x_j\ \ \ \hbox{for all}\ (i,j)\in R\eqno(21)$$
alpar@9: $$x_i\geq 0\ \ \ \ \ \ \ \hbox{for all}\ i\in J\ \ \eqno(22)$$
alpar@9: 
alpar@9: The inequality constraints (21), which are active in the optimal
alpar@9: solution, define so called {\it critical path} having the following
alpar@9: property: the minimal project duration $z$ can be decreased only by
alpar@9: decreasing the times $t_j$ for jobs on the critical path, and delaying
alpar@9: any critical job delays the entire project.
alpar@9: 
alpar@9: \subsection{glp\_cpp---solve critical path problem}
alpar@9: 
alpar@9: \subsubsection{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_cpp(glp_graph *G, int v_t, int v_es, int v_ls);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection{Description}
alpar@9: 
alpar@9: The routine \verb|glp_cpp| solves the critical path problem represented
alpar@9: in the form of the project network.
alpar@9: 
alpar@9: The parameter \verb|G| is a pointer to the graph object, which
alpar@9: specifies the project network. This graph must be acyclic. Multiple
alpar@9: arcs are allowed being considered as single arcs.
alpar@9: 
alpar@9: The parameter \verb|v_t| specifies an offset of the field of type
alpar@9: \verb|double| in the vertex data block, which contains time $t_i\geq 0$
alpar@9: needed to perform corresponding job $j\in J$. If \verb|v_t| $<0$, it is
alpar@9: assumed that $t_i=1$ for all jobs.
alpar@9: 
alpar@9: The parameter \verb|v_es| specifies an offset of the field of type
alpar@9: \verb|double| in the vertex data block, to which the routine stores
alpar@9: the {\it earliest start time} for corresponding job. If \verb|v_es|
alpar@9: $<0$, this time is not stored.
alpar@9: 
alpar@9: The parameter \verb|v_ls| specifies an offset of the field of type
alpar@9: \verb|double| in the vertex data block, to which the routine stores
alpar@9: the {\it latest start time} for corresponding job. If \verb|v_ls|
alpar@9: $<0$, this time is not stored.
alpar@9: 
alpar@9: The difference between the latest and earliest start times of some job
alpar@9: is called its {\it time reserve}. Delaying a job within its time reserve
alpar@9: does not affect the project duration, so if the time reserve is zero,
alpar@9: the corresponding job is critical.
alpar@9: 
alpar@9: \subsubsection{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_cpp| returns the minimal project duration, i.e.
alpar@9: minimal time needed to perform all jobs in the project.
alpar@9: 
alpar@9: \subsubsection{Example}
alpar@9: 
alpar@9: The example program below solves the critical path problem shown on
alpar@9: Fig.~4 by using the routine \verb|glp_cpp| and writes the solution found
alpar@9: to the standard output.
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: #include <stddef.h>
alpar@9: #include <stdio.h>
alpar@9: #include <stdlib.h>
alpar@9: #include <glpk.h>
alpar@9: 
alpar@9: typedef struct { double t, es, ls; } v_data;
alpar@9: 
alpar@9: #define node(v) ((v_data *)((v)->data))
alpar@9: 
alpar@9: int main(void)
alpar@9: {     glp_graph *G;
alpar@9:       int i;
alpar@9:       double t, es, ef, ls, lf, total;
alpar@9:       G = glp_create_graph(sizeof(v_data), 0);
alpar@9:       glp_add_vertices(G, 13);
alpar@9:       node(G->v[1])->t = 3;   /* A: Excavate */
alpar@9:       node(G->v[2])->t = 4;   /* B: Lay foundation */
alpar@9:       node(G->v[3])->t = 3;   /* C: Rough plumbing */
alpar@9:       node(G->v[4])->t = 10;  /* D: Frame */
alpar@9:       node(G->v[5])->t = 8;   /* E: Finish exterior */
alpar@9:       node(G->v[6])->t = 4;   /* F: Install HVAC */
alpar@9:       node(G->v[7])->t = 6;   /* G: Rough elecrtic */
alpar@9:       node(G->v[8])->t = 8;   /* H: Sheet rock */
alpar@9:       node(G->v[9])->t = 5;   /* I: Install cabinets */
alpar@9:       node(G->v[10])->t = 5;  /* J: Paint */
alpar@9:       node(G->v[11])->t = 4;  /* K: Final plumbing */
alpar@9:       node(G->v[12])->t = 2;  /* L: Final electric */
alpar@9:       node(G->v[13])->t = 4;  /* M: Install flooring */
alpar@9:       glp_add_arc(G, 1, 2);   /* A precedes B */
alpar@9:       glp_add_arc(G, 2, 3);   /* B precedes C */
alpar@9:       glp_add_arc(G, 2, 4);   /* B precedes D */
alpar@9:       glp_add_arc(G, 4, 5);   /* D precedes E */
alpar@9:       glp_add_arc(G, 4, 6);   /* D precedes F */
alpar@9:       glp_add_arc(G, 4, 7);   /* D precedes G */
alpar@9:       glp_add_arc(G, 3, 8);   /* C precedes H */
alpar@9:       glp_add_arc(G, 5, 8);   /* E precedes H */
alpar@9:       glp_add_arc(G, 6, 8);   /* F precedes H */
alpar@9:       glp_add_arc(G, 7, 8);   /* G precedes H */
alpar@9:       glp_add_arc(G, 8, 9);   /* H precedes I */
alpar@9:       glp_add_arc(G, 8, 10);  /* H precedes J */
alpar@9:       glp_add_arc(G, 9, 11);  /* I precedes K */
alpar@9:       glp_add_arc(G, 10, 12); /* J precedes L */
alpar@9:       glp_add_arc(G, 11, 13); /* K precedes M */
alpar@9:       glp_add_arc(G, 12, 13); /* L precedes M */
alpar@9:       total = glp_cpp(G, offsetof(v_data, t), offsetof(v_data, es),
alpar@9:          offsetof(v_data, ls));
alpar@9:       printf("Minimal project duration is %.2f\n\n", total);
alpar@9:       printf("Job  Time      ES     EF     LS     LF\n");
alpar@9:       printf("--- ------   ------ ------ ------ ------\n");
alpar@9:       for (i = 1; i <= G->nv; i++)
alpar@9:       {  t = node(G->v[i])->t;
alpar@9:          es = node(G->v[i])->es;
alpar@9:          ef = es + node(G->v[i])->t;
alpar@9:          ls = node(G->v[i])->ls;
alpar@9:          lf = ls + node(G->v[i])->t;
alpar@9:          printf("%3d %6.2f %s %6.2f %6.2f %6.2f %6.2f\n",
alpar@9:             i, t, ls - es < 0.001 ? "*" : " ", es, ef, ls, lf);
alpar@9:       }
alpar@9:       glp_delete_graph(G);
alpar@9:       return 0;
alpar@9: }
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: The output from the example program shown below includes job number,
alpar@9: the time needed to perform a job, earliest start time (\verb|ES|),
alpar@9: earliest finish time (\verb|EF|), latest start time (\verb|LS|), and
alpar@9: latest finish time (\verb|LF|) for each job in the project. Critical
alpar@9: jobs are marked by asterisks.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: Minimal project duration is 46.00
alpar@9: 
alpar@9: Job  Time      ES     EF     LS     LF
alpar@9: --- ------   ------ ------ ------ ------
alpar@9:   1   3.00 *   0.00   3.00   0.00   3.00
alpar@9:   2   4.00 *   3.00   7.00   3.00   7.00
alpar@9:   3   3.00     7.00  10.00  22.00  25.00
alpar@9:   4  10.00 *   7.00  17.00   7.00  17.00
alpar@9:   5   8.00 *  17.00  25.00  17.00  25.00
alpar@9:   6   4.00    17.00  21.00  21.00  25.00
alpar@9:   7   6.00    17.00  23.00  19.00  25.00
alpar@9:   8   8.00 *  25.00  33.00  25.00  33.00
alpar@9:   9   5.00 *  33.00  38.00  33.00  38.00
alpar@9:  10   5.00    33.00  38.00  35.00  40.00
alpar@9:  11   4.00 *  38.00  42.00  38.00  42.00
alpar@9:  12   2.00    38.00  40.00  40.00  42.00
alpar@9:  13   4.00 *  42.00  46.00  42.00  46.00
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9: 
alpar@9: \chapter{Graph Optimization API Routines}
alpar@9: 
alpar@9: \section{Maximum clique problem}
alpar@9: 
alpar@9: \subsection{Background}
alpar@9: 
alpar@9: The {\it maximum clique problem (MCP)} is a classic combinatorial
alpar@9: optimization problem. Given an undirected graph $G=(V,E)$, where $V$ is
alpar@9: a set of vertices, and $E$ is a set of edges, this problem is to find
alpar@9: the largest {\it clique} $C\subseteq G$, i.e. the largest induced
alpar@9: complete subgraph. A generalization of this problem is the {\it maximum
alpar@9: weight clique problem (MWCP)}, which is to find a clique $C\subseteq G$
alpar@9: of the largest weight $\displaystyle\sum_{v\in C}w(v)\rightarrow\max$,
alpar@9: where $w(v)$ is a weight of vertex $v\in V$.
alpar@9: 
alpar@9: An example of the maximum weight clique problem is shown on Fig.~5.
alpar@9: 
alpar@9: \begin{figure}
alpar@9: \noindent\hfil
alpar@9: \begin{tabular}{c}
alpar@9: {\xymatrix %@C=16pt
alpar@9: {&&&{v_1}\ar@{-}[lllddd]\ar@{-}[llddddd]\ar@{-}[dddddd]
alpar@9: \ar@{-}[rrrddd]&&&\\
alpar@9: &{v_2}\ar@{-}[rrrr]\ar@{-}[rrrrdddd]\ar@{-}[rrddddd]\ar@{-}[dddd]&&&&
alpar@9: {v_3}\ar@{-}[llllldd]\ar@{-}[lllldddd]\ar@{-}[dddd]&\\
alpar@9: &&&&&&\\
alpar@9: {v_4}\ar@{-}[rrrrrr]\ar@{-}[rrrddd]&&&&&&{v_5}\ar@{-}[lllddd]
alpar@9: \ar@{-}[ldd]\\
alpar@9: &&&&&&\\
alpar@9: &{v_6}\ar@{-}[rrrr]&&&&{v_7}&\\
alpar@9: &&&{v_8}&&&\\
alpar@9: }}
alpar@9: \end{tabular}
alpar@9: \begin{tabular}{r@{\ }c@{\ }l}
alpar@9: $w(v_1)$&=&3\\$w(v_2)$&=&4\\$w(v_3)$&=&8\\$w(v_4)$&=&1\\
alpar@9: $w(v_5)$&=&5\\$w(v_6)$&=&2\\$w(v_7)$&=&1\\$w(v_8)$&=&3\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \begin{center}
alpar@9: Fig.~5. An example of the maximum weight clique problem.
alpar@9: \end{center}
alpar@9: \end{figure}
alpar@9: 
alpar@9: \subsection{glp\_wclique\_exact---find maximum weight clique with exact
alpar@9: algorithm}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_wclique_exact(glp_graph *G, int v_wgt, double *sol,
alpar@9:       int v_set);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsection*{Description}
alpar@9: 
alpar@9: The routine {\it glp\_wclique\_exact} finds a maximum weight clique in
alpar@9: the specified undirected graph with the exact algorithm developed by
alpar@9: Patric \"Osterg{\aa}rd.\footnote{P.~R.~J.~\"Osterg{\aa}rd, A new
alpar@9: algorithm for the maximum-weight clique problem, Nordic J. of Computing,
alpar@9: Vol.~8, No.~4, 2001, pp.~424--36.}
alpar@9: 
alpar@9: The parameter $G$ is the program object, which specifies an undirected
alpar@9: graph. Each arc $(x\rightarrow y)$ in $G$ is considered as edge
alpar@9: $(x,y)$, self-loops are ignored, and multiple edges, if present, are
alpar@9: replaced (internally) by simple edges.
alpar@9: 
alpar@9: The parameter {\it v\_wgt} specifies an offset of the field of type
alpar@9: {\bf double} in the vertex data block, which contains a weight of
alpar@9: corresponding vertex. Vertex weights must be integer-valued in the
alpar@9: range $[0,$ {\it INT\_MAX}$]$. If {\it v\_wgt} $<0$, it is assumed that
alpar@9: all vertices of the graph have the weight 1.
alpar@9: 
alpar@9: The parameter {\it sol} specifies a location, to which the routine
alpar@9: stores the weight of the clique found (the clique weight is the sum
alpar@9: of weights of all vertices included in the clique.) If {\it sol} is
alpar@9: {\it NULL}, the solution is not stored.
alpar@9: 
alpar@9: The parameter {\it v\_set} specifies an offset of the field of type
alpar@9: {\bf int} in the vertex data block, to which the routines stores a
alpar@9: vertex flag: 1 means that the corresponding vertex is included in the
alpar@9: clique found, and 0 otherwise. If {\it v\_set} $<0$, vertex flags are
alpar@9: not stored.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: \def\arraystretch{1}
alpar@9: 
alpar@9: \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
alpar@9: 0 & Optimal solution found.\\
alpar@9: \verb|GLP_EDATA| & Unable to start the search, because some vertex
alpar@9: weights are either not integer-valued or out of range. This code is
alpar@9: also returned if the sum of weights of all vertices exceeds
alpar@9: {\it INT\_MAX}. \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsubsection*{Notes}
alpar@9: 
alpar@9: \noindent\indent
alpar@9: 1. The routine {\it glp\_wclique\_exact} finds exact solution. Since
alpar@9: both MCP and MWCP problems are NP-complete, the algorithm may require
alpar@9: exponential time in worst cases.
alpar@9: 
alpar@9: 2. Internally the specified graph is converted to an adjacency matrix
alpar@9: in {\it dense} format. This requires about $|V|^2/16$ bytes of memory,
alpar@9: where $|V|$ is the number of vertices in the graph.
alpar@9: 
alpar@9: \subsubsection*{Example}
alpar@9: 
alpar@9: The example program shown below reads a MWCP instance in DIMACS
alpar@9: clique/coloring format from file `\verb|sample.clq|', finds the clique
alpar@9: of largest weight, and writes the solution found to the standard output.
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: #include <stddef.h>
alpar@9: #include <stdio.h>
alpar@9: #include <stdlib.h>
alpar@9: #include <glpk.h>
alpar@9: 
alpar@9: typedef struct { double wgt; int set; } v_data;
alpar@9: 
alpar@9: #define vertex(v) ((v_data *)((v)->data))
alpar@9: 
alpar@9: int main(void)
alpar@9: {     glp_graph *G;
alpar@9:       glp_vertex *v;
alpar@9:       int i, ret;
alpar@9:       double sol;
alpar@9:       G = glp_create_graph(sizeof(v_data), 0);
alpar@9:       glp_read_ccdata(G, offsetof(v_data, wgt), "sample.clq");
alpar@9:       ret = glp_wclique_exact(G, offsetof(v_data, wgt), &sol,
alpar@9:          offsetof(v_data, set));
alpar@9:       printf("ret = %d; sol = %g\n", ret, sol);
alpar@9:       for (i = 1; i <= G->nv; i++)
alpar@9:       {  v = G->v[i];
alpar@9:          printf("vertex %d: weight = %g, flag = %d\n",
alpar@9:             i, vertex(v)->wgt, vertex(v)->set);
alpar@9:       }
alpar@9:       glp_delete_graph(G);
alpar@9:       return 0;
alpar@9: }
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \noindent
alpar@9: For the example shown on Fig.~5 the data file may look like follows:
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: c sample.clq
alpar@9: c
alpar@9: c This is an example of the maximum weight clique
alpar@9: c problem in DIMACS clique/coloring format.
alpar@9: c
alpar@9: p edge 8 16
alpar@9: n 1 3
alpar@9: n 2 4
alpar@9: n 3 8
alpar@9: n 5 5
alpar@9: n 6 2
alpar@9: n 8 3
alpar@9: e 1 4
alpar@9: e 1 5
alpar@9: e 1 6
alpar@9: e 1 8
alpar@9: e 2 3
alpar@9: e 2 6
alpar@9: e 2 7
alpar@9: e 2 8
alpar@9: e 3 4
alpar@9: e 3 6
alpar@9: e 3 7
alpar@9: e 4 5
alpar@9: e 4 8
alpar@9: e 5 7
alpar@9: e 5 8
alpar@9: e 6 7
alpar@9: c
alpar@9: c eof
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \noindent
alpar@9: The corresponding output from the example program is the following:
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: Reading graph from `sample.clq'...
alpar@9: Graph has 8 vertices and 16 edges
alpar@9: 28 lines were read
alpar@9: ret = 0; sol = 15
alpar@9: vertex 1: weight = 3, flag = 0
alpar@9: vertex 2: weight = 4, flag = 1
alpar@9: vertex 3: weight = 8, flag = 1
alpar@9: vertex 4: weight = 1, flag = 0
alpar@9: vertex 5: weight = 5, flag = 0
alpar@9: vertex 6: weight = 2, flag = 1
alpar@9: vertex 7: weight = 1, flag = 1
alpar@9: vertex 8: weight = 3, flag = 0
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \end{document}




