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