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