lemon-project-template-glpk: deps/glpk/doc/graphs.tex annotate

lemon-project-template-glpk

annotate deps/glpk/doc/graphs.tex @ 9:33de93886c88

Import GLPK 4.47

author	Alpar Juttner <alpar@cs.elte.hu>
date	Sun, 06 Nov 2011 20:59:10 +0100
parents
children

rev	line source
alpar@9	1 %* graphs.tex *%
alpar@9	2
alpar@9	3 %***********************************************************************
alpar@9	4 % This code is part of GLPK (GNU Linear Programming Kit).
alpar@9	5 %
alpar@9	6 % Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
alpar@9	7 % 2009, 2010 Andrew Makhorin, Department for Applied Informatics,
alpar@9	8 % Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@9	9 % E-mail: <mao@gnu.org>.
alpar@9	10 %
alpar@9	11 % GLPK is free software: you can redistribute it and/or modify it
alpar@9	12 % under the terms of the GNU General Public License as published by
alpar@9	13 % the Free Software Foundation, either version 3 of the License, or
alpar@9	14 % (at your option) any later version.
alpar@9	15 %
alpar@9	16 % GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@9	17 % ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@9	18 % or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@9	19 % License for more details.
alpar@9	20 %
alpar@9	21 % You should have received a copy of the GNU General Public License
alpar@9	22 % along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@9	23 %***********************************************************************
alpar@9	24
alpar@9	25 \documentclass[11pt]{report}
alpar@9	26 \usepackage{amssymb}
alpar@9	27 \usepackage[dvipdfm,linktocpage,colorlinks,linkcolor=blue,
alpar@9	28 urlcolor=blue]{hyperref}
alpar@9	29 \usepackage[all]{xy}
alpar@9	30
alpar@9	31 \renewcommand\contentsname{\sf\bfseries Contents}
alpar@9	32 \renewcommand\chaptername{\sf\bfseries Chapter}
alpar@9	33 \renewcommand\appendixname{\sf\bfseries Appendix}
alpar@9	34
alpar@9	35 \begin{document}
alpar@9	36
alpar@9	37 \thispagestyle{empty}
alpar@9	38
alpar@9	39 \begin{center}
alpar@9	40
alpar@9	41 \vspace*{1in}
alpar@9	42
alpar@9	43 \begin{huge}
alpar@9	44 \sf\bfseries GNU Linear Programming Kit
alpar@9	45 \end{huge}
alpar@9	46
alpar@9	47 \vspace{0.5in}
alpar@9	48
alpar@9	49 \begin{LARGE}
alpar@9	50 \sf Graph and Network Routines
alpar@9	51 \end{LARGE}
alpar@9	52
alpar@9	53 \vspace{0.5in}
alpar@9	54
alpar@9	55 \begin{LARGE}
alpar@9	56 \sf for GLPK Version 4.45
alpar@9	57 \end{LARGE}
alpar@9	58
alpar@9	59 \vspace{0.5in}
alpar@9	60 \begin{Large}
alpar@9	61 \sf (DRAFT, December 2010)
alpar@9	62 \end{Large}
alpar@9	63 \end{center}
alpar@9	64
alpar@9	65 \newpage
alpar@9	66
alpar@9	67 \vspace*{1in}
alpar@9	68
alpar@9	69 \vfill
alpar@9	70
alpar@9	71 \noindent
alpar@9	72 The GLPK package is part of the GNU Project released under the aegis of
alpar@9	73 GNU.
alpar@9	74
alpar@9	75 \medskip \noindent
alpar@9	76 Copyright \copyright{} 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
alpar@9	77 2008, 2009, 2010 Andrew Makhorin, Department for Applied Informatics,
alpar@9	78 Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@9	79
alpar@9	80 \medskip \noindent
alpar@9	81 Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
alpar@9	82 02110-1301, USA.
alpar@9	83
alpar@9	84 \medskip \noindent
alpar@9	85 Permission is granted to make and distribute verbatim copies of this
alpar@9	86 manual provided the copyright notice and this permission notice are
alpar@9	87 preserved on all copies.
alpar@9	88
alpar@9	89 \medskip \noindent
alpar@9	90 Permission is granted to copy and distribute modified versions of this
alpar@9	91 manual under the conditions for verbatim copying, provided also that the
alpar@9	92 entire resulting derived work is distributed under the terms of
alpar@9	93 a permission notice identical to this one.
alpar@9	94
alpar@9	95 \medskip \noindent
alpar@9	96 Permission is granted to copy and distribute translations of this manual
alpar@9	97 into another language, under the above conditions for modified versions.
alpar@9	98
alpar@9	99 \tableofcontents
alpar@9	100
alpar@9	101 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9	102
alpar@9	103 \chapter{Basic Graph API Routines}
alpar@9	104
alpar@9	105 \section{Graph program object}
alpar@9	106
alpar@9	107 In GLPK the base program object used to represent graphs and networks
alpar@9	108 is a directed graph (digraph).
alpar@9	109
alpar@9	110 Formally, {\it digraph} (or simply, {\it graph}) is a pair $G=(V,A)$,
alpar@9	111 where $V$ is a set of {\it vertices}, and $A$ is a set
alpar@9	112 {\it arcs}.\footnote{$A$ may be a multiset.} Each arc $a\in A$ is an
alpar@9	113 ordered pair of vertices $a=(x,y)$, where $x\in V$ is called {\it tail
alpar@9	114 vertex} of arc $a$, and $y\in V$ is called its {\it head vertex}.
alpar@9	115
alpar@9	116 Representation of a graph in the program includes three structs defined
alpar@9	117 by typedef in the header \verb\|glpk.h\|:
alpar@9	118
alpar@9	119 \medskip
alpar@9	120
alpar@9	121 $\bullet$ \verb\|glp_graph\|, which represents the graph in a whole,
alpar@9	122
alpar@9	123 $\bullet$ \verb\|glp_vertex\|, which represents a vertex of the graph, and
alpar@9	124
alpar@9	125 $\bullet$ \verb\|glp_arc\|, which represents an arc of the graph.
alpar@9	126
alpar@9	127 \medskip
alpar@9	128
alpar@9	129 All these three structs are ``semi-opaque'', i.e. the application
alpar@9	130 program can directly access their fields through pointers, however,
alpar@9	131 changing the fields directly is not allowed---all changes should be
alpar@9	132 performed only with appropriate GLPK API routines.
alpar@9	133
alpar@9	134 \newpage
alpar@9	135
alpar@9	136 \newenvironment{comment}
alpar@9	137 {\addtolength{\leftskip}{17pt}\noindent}
alpar@9	138 {\par\addtolength{\leftskip}{-17pt}}
alpar@9	139
alpar@9	140 \noindent
alpar@9	141 {\bf glp\_graph.} The struct \verb\|glp_graph\| has the following
alpar@9	142 fields available to the application program:
alpar@9	143
alpar@9	144 \medskip
alpar@9	145
alpar@9	146 \noindent
alpar@9	147 \verb\|char *name;\|
alpar@9	148
alpar@9	149 \begin{comment}Symbolic name assigned to the graph. It is a pointer to
alpar@9	150 a null terminated character string of length from 1 to 255 characters.
alpar@9	151 If no name is assigned to the graph, this field contains \verb\|NULL\|.
alpar@9	152 \end{comment}
alpar@9	153
alpar@9	154 \medskip
alpar@9	155
alpar@9	156 \noindent
alpar@9	157 \verb\|int nv;\|
alpar@9	158
alpar@9	159 \begin{comment}The number of vertices in the graph, $nv\geq 0$.
alpar@9	160 \end{comment}
alpar@9	161
alpar@9	162 \medskip
alpar@9	163
alpar@9	164 \noindent
alpar@9	165 \verb\|int na;\|
alpar@9	166
alpar@9	167 \begin{comment}The number of arcs in the graph, $na\geq 0$.
alpar@9	168 \end{comment}
alpar@9	169
alpar@9	170 \medskip
alpar@9	171
alpar@9	172 \noindent
alpar@9	173 \verb\|glp_vertex **v;\|
alpar@9	174
alpar@9	175 \begin{comment}Pointer to an array containing the list of vertices.
alpar@9	176 Element $v[0]$ is not used. Element $v[i]$, $1\leq i\leq nv$, is a
alpar@9	177 pointer to $i$-th vertex of the graph. Note that on adding new vertices
alpar@9	178 to the graph the field $v$ may be altered due to reallocation. However,
alpar@9	179 pointers $v[i]$ are not changed while corresponding vertices exist in
alpar@9	180 the graph.
alpar@9	181 \end{comment}
alpar@9	182
alpar@9	183 \medskip
alpar@9	184
alpar@9	185 \noindent
alpar@9	186 \verb\|int v_size;\|
alpar@9	187
alpar@9	188 \begin{comment}Size of vertex data blocks, in bytes,
alpar@9	189 $0\leq v\_size\leq 256$. (See also the field \verb\|data\| in the struct
alpar@9	190 \verb\|glp_vertex\|.)
alpar@9	191 \end{comment}
alpar@9	192
alpar@9	193 \medskip
alpar@9	194
alpar@9	195 \noindent
alpar@9	196 \verb\|int a_size;\|
alpar@9	197
alpar@9	198 \begin{comment}Size of arc data blocks, in bytes,
alpar@9	199 $0\leq v\_size\leq 256$. (See also the field \verb\|data\| in the struct
alpar@9	200 \verb\|glp_arc\|.)
alpar@9	201 \end{comment}
alpar@9	202
alpar@9	203 \bigskip
alpar@9	204
alpar@9	205 \noindent
alpar@9	206 {\bf glp\_vertex.} The struct \verb\|glp_vertex\| has the following
alpar@9	207 fields available to the application program:
alpar@9	208
alpar@9	209 \medskip
alpar@9	210
alpar@9	211 \noindent
alpar@9	212 \verb\|int i;\|
alpar@9	213
alpar@9	214 \begin{comment}Ordinal number of the vertex, $1\leq i\leq nv$. Note
alpar@9	215 that element $v[i]$ in the struct \verb\|glp_graph\| points to the vertex,
alpar@9	216 whose ordinal number is $i$.
alpar@9	217 \end{comment}
alpar@9	218
alpar@9	219 \medskip
alpar@9	220
alpar@9	221 \noindent
alpar@9	222 \verb\|char *name;\|
alpar@9	223
alpar@9	224 \begin{comment}Symbolic name assigned to the vertex. It is a pointer to
alpar@9	225 a null terminated character string of length from 1 to 255 characters.
alpar@9	226 If no name is assigned to the vertex, this field contains \verb\|NULL\|.
alpar@9	227 \end{comment}
alpar@9	228
alpar@9	229 \medskip
alpar@9	230
alpar@9	231 \noindent
alpar@9	232 \verb\|void *data;\|
alpar@9	233
alpar@9	234 \begin{comment}Pointer to a data block associated with the vertex. This
alpar@9	235 data block is automatically allocated on creating a new vertex and freed
alpar@9	236 on deleting the vertex. If $v\_size=0$, the block is not allocated, and
alpar@9	237 this field contains \verb\|NULL\|.
alpar@9	238 \end{comment}
alpar@9	239
alpar@9	240 \medskip
alpar@9	241
alpar@9	242 \noindent
alpar@9	243 \verb\|void *temp;\|
alpar@9	244
alpar@9	245 \begin{comment}Working pointer, which may be used freely for any
alpar@9	246 purposes. The application program can change this field directly.
alpar@9	247 \end{comment}
alpar@9	248
alpar@9	249 \medskip
alpar@9	250
alpar@9	251 \noindent
alpar@9	252 \verb\|glp_arc *in;\|
alpar@9	253
alpar@9	254 \begin{comment}Pointer to the (unordered) list of incoming arcs. If the
alpar@9	255 vertex has no incoming arcs, this field contains \verb\|NULL\|.
alpar@9	256 \end{comment}
alpar@9	257
alpar@9	258 \medskip
alpar@9	259
alpar@9	260 \noindent
alpar@9	261 \verb\|glp_arc *out;\|
alpar@9	262
alpar@9	263 \begin{comment}Pointer to the (unordered) list of outgoing arcs. If the
alpar@9	264 vertex has no outgoing arcs, this field contains \verb\|NULL\|.
alpar@9	265 \end{comment}
alpar@9	266
alpar@9	267 \bigskip
alpar@9	268
alpar@9	269 \noindent
alpar@9	270 {\bf glp\_arc.} The struct \verb\|glp_arc\| has the following fields
alpar@9	271 available to the application program:
alpar@9	272
alpar@9	273 \medskip
alpar@9	274
alpar@9	275 \noindent
alpar@9	276 \verb\|glp_vertex *tail;\|
alpar@9	277
alpar@9	278 \begin{comment}Pointer to a vertex, which is tail endpoint of the arc.
alpar@9	279 \end{comment}
alpar@9	280
alpar@9	281 \medskip
alpar@9	282
alpar@9	283 \noindent
alpar@9	284 \verb\|glp_vertex *head;\|
alpar@9	285
alpar@9	286 \begin{comment}Pointer to a vertex, which is head endpoint of the arc.
alpar@9	287 \end{comment}
alpar@9	288
alpar@9	289 \medskip
alpar@9	290
alpar@9	291 \noindent
alpar@9	292 \verb\|void *data;\|
alpar@9	293
alpar@9	294 \begin{comment}Pointer to a data block associated with the arc. This
alpar@9	295 data block is automatically allocated on creating a new arc and freed on
alpar@9	296 deleting the arc. If $v\_size=0$, the block is not allocated, and this
alpar@9	297 field contains \verb\|NULL\|.
alpar@9	298 \end{comment}
alpar@9	299
alpar@9	300 \medskip
alpar@9	301
alpar@9	302 \noindent
alpar@9	303 \verb\|void *temp;\|
alpar@9	304
alpar@9	305 \begin{comment}Working pointer, which may be used freely for any
alpar@9	306 purposes. The application program can change this field directly.
alpar@9	307 \end{comment}
alpar@9	308
alpar@9	309 \medskip
alpar@9	310
alpar@9	311 \noindent
alpar@9	312 \verb\|glp_arc *t_next;\|
alpar@9	313
alpar@9	314 \begin{comment}Pointer to another arc, which has the same tail endpoint
alpar@9	315 as this one. \verb\|NULL\| in this field indicates the end of the list of
alpar@9	316 outgoing arcs.
alpar@9	317 \end{comment}
alpar@9	318
alpar@9	319 \medskip
alpar@9	320
alpar@9	321 \noindent
alpar@9	322 \verb\|glp_arc *h_next;\|
alpar@9	323
alpar@9	324 \begin{comment}Pointer to another arc, which has the same head endpoint
alpar@9	325 as this one. \verb\|NULL\| in this field indicates the end of the list of
alpar@9	326 incoming arcs.
alpar@9	327 \end{comment}
alpar@9	328
alpar@9	329 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9	330
alpar@9	331 \newpage
alpar@9	332
alpar@9	333 \section{Graph creating and modifying routines}
alpar@9	334
alpar@9	335 \subsection{glp\_create\_graph---create graph}
alpar@9	336
alpar@9	337 \subsubsection*{Synopsis}
alpar@9	338
alpar@9	339 \begin{verbatim}
alpar@9	340 glp_graph *glp_create_graph(int v_size, int a_size);
alpar@9	341 \end{verbatim}
alpar@9	342
alpar@9	343 \subsubsection*{Description}
alpar@9	344
alpar@9	345 The routine \verb\|glp_create_graph\| creates a new graph, which
alpar@9	346 initially is\linebreak empty, i.e. has no vertices and arcs.
alpar@9	347
alpar@9	348 The parameter \verb\|v_size\| specifies the size of vertex data blocks,
alpar@9	349 in bytes, $0\leq v\_size\leq 256$.
alpar@9	350
alpar@9	351 The parameter \verb\|a_size\| specifies the size of arc data blocks, in
alpar@9	352 bytes, $0\leq a\_size\leq 256$.
alpar@9	353
alpar@9	354 \subsubsection*{Returns}
alpar@9	355
alpar@9	356 The routine returns a pointer to the graph created.
alpar@9	357
alpar@9	358 \subsection{glp\_set\_graph\_name---assign (change) graph name}
alpar@9	359
alpar@9	360 \subsubsection*{Synopsis}
alpar@9	361
alpar@9	362 \begin{verbatim}
alpar@9	363 void glp_set_graph_name(glp_graph G, const char name);
alpar@9	364 \end{verbatim}
alpar@9	365
alpar@9	366 \subsubsection*{Description}
alpar@9	367
alpar@9	368 The routine \verb\|glp_set_graph_name\| assigns a symbolic name specified
alpar@9	369 by the character string \verb\|name\| (1 to 255 chars) to the graph.
alpar@9	370
alpar@9	371 If the parameter \verb\|name\| is \verb\|NULL\| or an empty string, the
alpar@9	372 routine erases the existing symbolic name of the graph.
alpar@9	373
alpar@9	374 \newpage
alpar@9	375
alpar@9	376 \subsection{glp\_add\_vertices---add new vertices to graph}
alpar@9	377
alpar@9	378 \subsubsection*{Synopsis}
alpar@9	379
alpar@9	380 \begin{verbatim}
alpar@9	381 int glp_add_vertices(glp_graph *G, int nadd);
alpar@9	382 \end{verbatim}
alpar@9	383
alpar@9	384 \subsubsection*{Description}
alpar@9	385
alpar@9	386 The routine \verb\|glp_add_vertices\| adds \verb\|nadd\| vertices to the
alpar@9	387 specified graph. New vertices are always added to the end of the vertex
alpar@9	388 list, so ordinal numbers of existing vertices remain unchanged. Note
alpar@9	389 that this operation may change the field \verb\|v\| in the struct
alpar@9	390 \verb\|glp_graph\| (pointer to the vertex array) due to reallocation.
alpar@9	391
alpar@9	392 Being added each new vertex is isolated, i.e. has no incident arcs.
alpar@9	393
alpar@9	394 If the size of vertex data blocks specified on creating the graph is
alpar@9	395 non-zero, the routine also allocates a memory block of that size for
alpar@9	396 each new vertex added, fills it by binary zeros, and stores a pointer to
alpar@9	397 it in the field \verb\|data\| of the struct \verb\|glp_vertex\|. Otherwise,
alpar@9	398 if the block size is zero, the field \verb\|data\| is set to \verb\|NULL\|.
alpar@9	399
alpar@9	400 \subsubsection*{Returns}
alpar@9	401
alpar@9	402 The routine \verb\|glp_add_vertices\| returns the ordinal number of the
alpar@9	403 first new vertex added to the graph.
alpar@9	404
alpar@9	405 \subsection{glp\_set\_vertex\_name---assign (change) vertex name}
alpar@9	406
alpar@9	407 \subsubsection*{Synopsis}
alpar@9	408
alpar@9	409 \begin{verbatim}
alpar@9	410 void glp_set_vertex_name(glp_graph G, int i, const char name);
alpar@9	411 \end{verbatim}
alpar@9	412
alpar@9	413 \subsubsection*{Description}
alpar@9	414
alpar@9	415 The routine \verb\|glp_set_vertex_name\| assigns a given symbolic name
alpar@9	416 (1 up to 255 characters) to \verb\|i\|-th vertex of the specified graph.
alpar@9	417
alpar@9	418 If the parameter \verb\|name\| is \verb\|NULL\| or empty string, the
alpar@9	419 routine erases an existing name of \verb\|i\|-th vertex.
alpar@9	420
alpar@9	421 \newpage
alpar@9	422
alpar@9	423 \subsection{glp\_add\_arc---add new arc to graph}
alpar@9	424
alpar@9	425 \subsubsection*{Synopsis}
alpar@9	426
alpar@9	427 \begin{verbatim}
alpar@9	428 glp_arc glp_add_arc(glp_graph G, int i, int j);
alpar@9	429 \end{verbatim}
alpar@9	430
alpar@9	431 \subsubsection*{Description}
alpar@9	432
alpar@9	433 The routine \verb\|glp_add_arc\| adds one new arc to the specified graph.
alpar@9	434
alpar@9	435 The parameters \verb\|i\| and \verb\|j\| specify the ordinal numbers of,
alpar@9	436 resp., tail and head endpoints (vertices) of the arc. Note that
alpar@9	437 self-loops and multiple arcs are allowed.
alpar@9	438
alpar@9	439 If the size of arc data blocks specified on creating the graph is
alpar@9	440 non-zero, the routine also allocates a memory block of that size, fills
alpar@9	441 it by binary zeros, and stores a pointer to it in the field \verb\|data\|
alpar@9	442 of the struct \verb\|glp_arc\|. Otherwise, if the block size is zero, the
alpar@9	443 field \verb\|data\| is set to \verb\|NULL\|.
alpar@9	444
alpar@9	445 \subsection{glp\_del\_vertices---delete vertices from graph}
alpar@9	446
alpar@9	447 \subsubsection*{Synopsis}
alpar@9	448
alpar@9	449 \begin{verbatim}
alpar@9	450 void glp_del_vertices(glp_graph *G, int ndel, const int num[]);
alpar@9	451 \end{verbatim}
alpar@9	452
alpar@9	453 \subsubsection*{Description}
alpar@9	454
alpar@9	455 The routine \verb\|glp_del_vertices\| deletes vertices along with all
alpar@9	456 incident arcs from the specified graph. Ordinal numbers of vertices to
alpar@9	457 be deleted should be placed in locations \verb\|num[1]\|, \dots,
alpar@9	458 \verb\|num[ndel]\|, \verb\|ndel\| $>0$.
alpar@9	459
alpar@9	460 Note that deleting vertices involves changing ordinal numbers of other
alpar@9	461 vertices remaining in the graph. New ordinal numbers of the remaining
alpar@9	462 vertices are assigned under the assumption that the original order of
alpar@9	463 vertices is not changed.
alpar@9	464
alpar@9	465 \subsection{glp\_del\_arc---delete arc from graph}
alpar@9	466
alpar@9	467 \subsubsection*{Synopsis}
alpar@9	468
alpar@9	469 \begin{verbatim}
alpar@9	470 void glp_del_arc(glp_graph G, glp_arc a);
alpar@9	471 \end{verbatim}
alpar@9	472
alpar@9	473 \subsubsection*{Description}
alpar@9	474
alpar@9	475 The routine \verb\|glp_del_arc\| deletes an arc from the specified graph.
alpar@9	476 The arc to be deleted must exist.
alpar@9	477
alpar@9	478 \subsection{glp\_erase\_graph---erase graph content}
alpar@9	479
alpar@9	480 \subsubsection*{Synopsis}
alpar@9	481
alpar@9	482 \begin{verbatim}
alpar@9	483 void glp_erase_graph(glp_graph *G, int v_size, int a_size);
alpar@9	484 \end{verbatim}
alpar@9	485
alpar@9	486 \subsubsection*{Description}
alpar@9	487
alpar@9	488 The routine \verb\|glp_erase_graph\| erases the content of the specified
alpar@9	489 graph. The effect of this operation is the same as if the graph would be
alpar@9	490 deleted with the routine \verb\|glp_delete_graph\| and then created anew
alpar@9	491 with the routine \verb\|glp_create_graph\|, with exception that the handle
alpar@9	492 (pointer) to the graph remains valid.
alpar@9	493
alpar@9	494 The parameters \verb\|v_size\| and \verb\|a_size\| have the same meaning as
alpar@9	495 for the routine \verb\|glp_create_graph\|.
alpar@9	496
alpar@9	497 \subsection{glp\_delete\_graph---delete graph}
alpar@9	498
alpar@9	499 \subsubsection*{Synopsis}
alpar@9	500
alpar@9	501 \begin{verbatim}
alpar@9	502 void glp_delete_graph(glp_graph *G);
alpar@9	503 \end{verbatim}
alpar@9	504
alpar@9	505 \subsubsection*{Description}
alpar@9	506
alpar@9	507 The routine \verb\|glp_delete_graph\| deletes the specified graph and
alpar@9	508 frees all the memory allocated to this program object.
alpar@9	509
alpar@9	510 \newpage
alpar@9	511
alpar@9	512 \section{Graph searching routines}
alpar@9	513
alpar@9	514 \subsection{glp\_create\_v\_index---create vertex name index}
alpar@9	515
alpar@9	516 \subsubsection*{Synopsis}
alpar@9	517
alpar@9	518 \begin{verbatim}
alpar@9	519 void glp_create_v_index(glp_graph *G);
alpar@9	520 \end{verbatim}
alpar@9	521
alpar@9	522 \subsubsection*{Description}
alpar@9	523
alpar@9	524 The routine \verb\|glp_create_v_index\| creates the name index for the
alpar@9	525 specified graph. The name index is an auxiliary data structure, which
alpar@9	526 is intended to quickly (i.e. for logarithmic time) find vertices by
alpar@9	527 their names.
alpar@9	528
alpar@9	529 This routine can be called at any time. If the name index already
alpar@9	530 exists, the routine does nothing.
alpar@9	531
alpar@9	532 \subsection{glp\_find\_vertex---find vertex by its name}
alpar@9	533
alpar@9	534 \subsubsection*{Synopsis}
alpar@9	535
alpar@9	536 \begin{verbatim}
alpar@9	537 int glp_find_vertex(glp_graph G, const char name);
alpar@9	538 \end{verbatim}
alpar@9	539
alpar@9	540 \subsubsection*{Returns}
alpar@9	541
alpar@9	542 The routine \verb\|glp_find_vertex\| returns the ordinal number of
alpar@9	543 a vertex, which is assigned (by the routine \verb\|glp_set_vertex_name\|)
alpar@9	544 the specified symbolic \verb\|name\|. If no such vertex exists, the
alpar@9	545 routine returns 0.
alpar@9	546
alpar@9	547 \subsection{glp\_delete\_v\_index---delete vertex name index}
alpar@9	548
alpar@9	549 \subsubsection*{Synopsis}
alpar@9	550
alpar@9	551 \begin{verbatim}
alpar@9	552 void glp_delete_v_index(glp_graph *G);
alpar@9	553 \end{verbatim}
alpar@9	554
alpar@9	555 \subsubsection*{Description}
alpar@9	556
alpar@9	557 The routine \verb\|glp_delete_v_index\| deletes the name index previously
alpar@9	558 created by the routine \verb\|glp_create_v_index\| and frees the memory
alpar@9	559 allocated to this auxiliary data structure.
alpar@9	560
alpar@9	561 This routine can be called at any time. If the name index does not
alpar@9	562 exist, the routine does nothing.
alpar@9	563
alpar@9	564 \newpage
alpar@9	565
alpar@9	566 \section{Graph reading/writing routines}
alpar@9	567
alpar@9	568 \subsection{glp\_read\_graph---read graph from plain text file}
alpar@9	569
alpar@9	570 \subsubsection*{Synopsis}
alpar@9	571
alpar@9	572 \begin{verbatim}
alpar@9	573 int glp_read_graph(glp_graph G, const char fname);
alpar@9	574 \end{verbatim}
alpar@9	575
alpar@9	576 \subsubsection*{Description}
alpar@9	577
alpar@9	578 The routine \verb\|glp_read_graph\| reads a graph from a plain text file,
alpar@9	579 whose name is specified by the parameter \verb\|fname\|. Note that before
alpar@9	580 reading data the current content of the graph object is completely
alpar@9	581 erased with the routine \verb\|glp_erase_graph\|.
alpar@9	582
alpar@9	583 For the file format see description of the routine
alpar@9	584 \verb\|glp_write_graph\|.
alpar@9	585
alpar@9	586 \subsubsection*{Returns}
alpar@9	587
alpar@9	588 If the operation was successful, the routine returns zero. Otherwise
alpar@9	589 it prints an error message and returns non-zero.
alpar@9	590
alpar@9	591 \subsection{glp\_write\_graph---write graph to plain text file}
alpar@9	592
alpar@9	593 \subsubsection*{Synopsis}
alpar@9	594
alpar@9	595 \begin{verbatim}
alpar@9	596 int glp_write_graph(glp_graph G, const char fname);
alpar@9	597 \end{verbatim}
alpar@9	598
alpar@9	599 \subsubsection*{Description}
alpar@9	600
alpar@9	601 The routine \verb\|glp_write_graph\| writes the graph to a plain text
alpar@9	602 file, whose name is specified by the parameter \verb\|fname\|.
alpar@9	603
alpar@9	604 \subsubsection*{Returns}
alpar@9	605
alpar@9	606 If the operation was successful, the routine returns zero. Otherwise
alpar@9	607 it prints an error message and returns non-zero.
alpar@9	608
alpar@9	609 \subsubsection*{File format}
alpar@9	610
alpar@9	611 The file created by the routine \verb\|glp_write_graph\| is a plain text
alpar@9	612 file, which contains the following information:
alpar@9	613
alpar@9	614 \begin{verbatim}
alpar@9	615 nv na
alpar@9	616 i[1] j[1]
alpar@9	617 i[2] j[2]
alpar@9	618 . . .
alpar@9	619 i[na] j[na]
alpar@9	620 \end{verbatim}
alpar@9	621
alpar@9	622 \noindent
alpar@9	623 where:
alpar@9	624
alpar@9	625 \noindent
alpar@9	626 \verb\|nv\| is the number of vertices (nodes);
alpar@9	627
alpar@9	628 \noindent
alpar@9	629 \verb\|na\| is the number of arcs;
alpar@9	630
alpar@9	631 \noindent
alpar@9	632 \verb\|i[k]\|, $k=1,\dots,na$, is the index of tail vertex of arc $k$;
alpar@9	633
alpar@9	634 \noindent
alpar@9	635 \verb\|j[k]\|, $k=1,\dots,na$, is the index of head vertex of arc $k$.
alpar@9	636
alpar@9	637 \subsection{glp\_read\_ccdata---read graph from text file in DIMACS
alpar@9	638 clique/coloring format}
alpar@9	639
alpar@9	640 \subsubsection*{Synopsis}
alpar@9	641
alpar@9	642 \begin{verbatim}
alpar@9	643 int glp_read_ccdata(glp_graph *G, int v_wgt,
alpar@9	644 const char *fname);
alpar@9	645 \end{verbatim}
alpar@9	646
alpar@9	647 \subsubsection*{Description}
alpar@9	648
alpar@9	649 The routine {\it glp\_read\_ccdata} reads a graph from a text file in
alpar@9	650 DIMACS clique/coloring format. (Though this format is originally
alpar@9	651 designed to represent data for the minimal vertex coloring and maximal
alpar@9	652 clique problems, it may be used to represent general undirected and
alpar@9	653 directed graphs, because the routine allows reading self-loops and
alpar@9	654 multiple edges/arcs keeping the order of vertices specified for each
alpar@9	655 edge/arc of the graph.)
alpar@9	656
alpar@9	657 The parameter $G$ specifies the graph object to be read in. Note that
alpar@9	658 before reading data the current content of the graph object is
alpar@9	659 completely erased with the routine {\it glp\_erase\_graph}.
alpar@9	660
alpar@9	661 The parameter {\it v\_wgt} specifies an offset of the field of type
alpar@9	662 {\bf double} in the vertex data block, to which the routine stores the
alpar@9	663 vertex weight. If {\it v\_wgt} $<0$, the vertex weights are not stored.
alpar@9	664
alpar@9	665 The character string {\it fname} specifies the name of a text file to
alpar@9	666 be read in. (If the file name ends with the suffix `\verb\|.gz\|', the
alpar@9	667 file is assumed to be compressed, in which case the routine decompresses
alpar@9	668 it ``on the fly''.)
alpar@9	669
alpar@9	670 \subsubsection*{Returns}
alpar@9	671
alpar@9	672 If the operation was successful, the routine returns zero. Otherwise,
alpar@9	673 it prints an error message and returns non-zero.
alpar@9	674
alpar@9	675 \subsubsection*{DIMACS clique/coloring format\footnote{This material is
alpar@9	676 based on the paper ``Clique and Coloring Problems Graph Format'', which
alpar@9	677 is publically available at
alpar@9	678 {\tt http://dimacs.rutgers.edu/Challenges/}.}}
alpar@9	679
alpar@9	680 The DIMACS input file is a plain ASCII text file. It contains
alpar@9	681 {\it lines} of several types described below. A line is terminated with
alpar@9	682 an end-of-line character. Fields in each line are separated by at least
alpar@9	683 one blank space. Each line begins with a one-character designator to
alpar@9	684 identify the line type.
alpar@9	685
alpar@9	686 Note that DIMACS requires all numerical quantities to be integers in
alpar@9	687 the range $[-2^{31},2^{31}-1]$ while GLPK allows the quantities to be
alpar@9	688 floating-point numbers.
alpar@9	689
alpar@9	690 \paragraph{Comment lines.} Comment lines give human-readable information
alpar@9	691 about the file and are ignored by programs. Comment lines can appear
alpar@9	692 anywhere in the file. Each comment line begins with a lower-case
alpar@9	693 character \verb\|c\|.
alpar@9	694
alpar@9	695 \begin{verbatim}
alpar@9	696 c This is a comment line
alpar@9	697 \end{verbatim}
alpar@9	698
alpar@9	699 \paragraph{Problem line.} There is one problem line per data file. The
alpar@9	700 problem line must appear before any node or edge descriptor lines. It
alpar@9	701 has the following format:
alpar@9	702
alpar@9	703 \begin{verbatim}
alpar@9	704 p edge NODES EDGES
alpar@9	705 \end{verbatim}
alpar@9	706
alpar@9	707 \noindent
alpar@9	708 The lower-case letter \verb\|p\| signifies that this is a problem line.
alpar@9	709 The four-character problem designator \verb\|edge\| identifies the file
alpar@9	710 as containing data for the minimal vertex coloring or maximal clique
alpar@9	711 problem. The \verb\|NODES\| field contains an integer value specifying
alpar@9	712 the number of vertices in the graph. The \verb\|EDGES\| field contains an
alpar@9	713 integer value specifying the number of edges (arcs) in the graph.
alpar@9	714
alpar@9	715 \paragraph{Vertex descriptors.} These lines give the weight assigned to
alpar@9	716 a vertex of the graph. There is one vertex descriptor line for each
alpar@9	717 vertex, with the following format. Vertices without a descriptor take on
alpar@9	718 a default value of 1.
alpar@9	719
alpar@9	720 \begin{verbatim}
alpar@9	721 n ID VALUE
alpar@9	722 \end{verbatim}
alpar@9	723
alpar@9	724 \noindent
alpar@9	725 The lower-case character \verb\|n\| signifies that this is a vertex
alpar@9	726 descriptor line. The \verb\|ID\| field gives a vertex identification
alpar@9	727 number, an integer between 1 and $n$, where $n$ is the number of
alpar@9	728 vertices in the graph. The \verb\|VALUE\| field gives a vertex weight,
alpar@9	729 which can either positive or negative (or zero).
alpar@9	730
alpar@9	731 \paragraph{Edge descriptors.} There is one edge descriptor line for
alpar@9	732 each edge (arc) of the graph, each with the following format:
alpar@9	733
alpar@9	734 \begin{verbatim}
alpar@9	735 e I J
alpar@9	736 \end{verbatim}
alpar@9	737
alpar@9	738 \noindent
alpar@9	739 The lower-case character \verb\|e\| signifies that this is an edge
alpar@9	740 descriptor line. For an edge (arc) $(i,j)$ the fields \verb\|I\| and
alpar@9	741 \verb\|J\| specify its endpoints.
alpar@9	742
alpar@9	743 \paragraph{Example.} The following example of an undirected graph:
alpar@9	744
alpar@9	745 \bigskip
alpar@9	746
alpar@9	747 \noindent\hfil
alpar@9	748 \xymatrix %@C=32pt
alpar@9	749 {&{v_1}\ar@{-}[ldd]\ar@{-}[dd]\ar@{-}[rd]\ar@{-}[rr]&&{v_2}\ar@{-}[ld]
alpar@9	750 \ar@{-}[dd]\ar@{-}[rdd]&\\
alpar@9	751 &&{v_7}\ar@{-}[ld]\ar@{-}[rd]&&\\
alpar@9	752 {v_6}\ar@{-}[r]\ar@{-}[rdd]&{v_{10}}\ar@{-}[rr]\ar@{-}[rd]\ar@{-}[dd]&&
alpar@9	753 {v_8}\ar@{-}[ld]\ar@{-}[dd]\ar@{-}[r]&{v_3}\ar@{-}[ldd]\\
alpar@9	754 &&{v_9}\ar@{-}[ld]\ar@{-}[rd]&&\\
alpar@9	755 &{v_5}\ar@{-}[rr]&&{v_4}&\\
alpar@9	756 }
alpar@9	757
alpar@9	758 \bigskip
alpar@9	759
alpar@9	760 \noindent
alpar@9	761 might be coded in DIMACS clique/coloring format as follows:
alpar@9	762
alpar@9	763 \begin{footnotesize}
alpar@9	764 \begin{verbatim}
alpar@9	765 c sample.col
alpar@9	766 c
alpar@9	767 c This is an example of the vertex coloring problem data
alpar@9	768 c in DIMACS format.
alpar@9	769 c
alpar@9	770 p edge 10 21
alpar@9	771 c
alpar@9	772 e 1 2
alpar@9	773 e 1 6
alpar@9	774 e 1 7
alpar@9	775 e 1 10
alpar@9	776 e 2 3
alpar@9	777 e 2 7
alpar@9	778 e 2 8
alpar@9	779 e 3 4
alpar@9	780 e 3 8
alpar@9	781 e 4 5
alpar@9	782 e 4 8
alpar@9	783 e 4 9
alpar@9	784 e 5 6
alpar@9	785 e 5 9
alpar@9	786 e 5 10
alpar@9	787 e 6 10
alpar@9	788 e 7 8
alpar@9	789 e 7 10
alpar@9	790 e 8 9
alpar@9	791 e 8 10
alpar@9	792 e 9 10
alpar@9	793 c
alpar@9	794 c eof
alpar@9	795 \end{verbatim}
alpar@9	796 \end{footnotesize}
alpar@9	797
alpar@9	798 \subsection{glp\_write\_ccdata---write graph to text file in DIMACS
alpar@9	799 clique/coloring format}
alpar@9	800
alpar@9	801 \subsubsection*{Synopsis}
alpar@9	802
alpar@9	803 \begin{verbatim}
alpar@9	804 int glp_write_ccdata(glp_graph *G, int v_wgt,
alpar@9	805 const char *fname);
alpar@9	806 \end{verbatim}
alpar@9	807
alpar@9	808 \subsection*{Description}
alpar@9	809
alpar@9	810 The routine {\it glp\_write\_ccdata} writes the graph object specified
alpar@9	811 by the parameter $G$ to a text file in DIMACS clique/coloring format.
alpar@9	812 (Though this format is originally designed to represent data for the
alpar@9	813 minimal vertex coloring and maximal clique problems, it may be used to
alpar@9	814 represent general undirected and directed graphs, because the routine
alpar@9	815 allows writing self-loops and multiple edges/arcs keeping the order of
alpar@9	816 vertices specified for each edge/arc of the graph.)
alpar@9	817
alpar@9	818 The parameter {\it v\_wgt} specifies an offset of the field of type
alpar@9	819 {\bf double} in the vertex data block, which contains the vertex weight.
alpar@9	820 If {\it v\_wgt} $<0$, it is assumed that the weight of each vertex is 1.
alpar@9	821
alpar@9	822 The character string {\it fname} specifies a name of the text file to be
alpar@9	823 written out. (If the file name ends with suffix `\verb\|.gz\|', the file
alpar@9	824 is assumed to be compressed, in which case the routine performs
alpar@9	825 automatic compression on writing it.)
alpar@9	826
alpar@9	827 \subsubsection*{Returns}
alpar@9	828
alpar@9	829 If the operation was successful, the routine returns zero. Otherwise,
alpar@9	830 it prints an error message and returns non-zero.
alpar@9	831
alpar@9	832 \newpage
alpar@9	833
alpar@9	834 \section{Graph analysis routines}
alpar@9	835
alpar@9	836 \subsection{glp\_weak\_comp---find all weakly connected components of
alpar@9	837 graph}
alpar@9	838
alpar@9	839 \subsubsection*{Synopsis}
alpar@9	840
alpar@9	841 \begin{verbatim}
alpar@9	842 int glp_weak_comp(glp_graph *G, int v_num);
alpar@9	843 \end{verbatim}
alpar@9	844
alpar@9	845 \subsubsection*{Description}
alpar@9	846
alpar@9	847 The routine \verb\|glp_weak_comp\| finds all weakly connected components
alpar@9	848 of the specified graph.
alpar@9	849
alpar@9	850 The parameter \verb\|v_num\| specifies an offset of the field of type
alpar@9	851 \verb\|int\| in the vertex data block, to which the routine stores the
alpar@9	852 number of a weakly connected component containing that vertex. If
alpar@9	853 \verb\|v_num\| $<0$, no component numbers are stored.
alpar@9	854
alpar@9	855 The components are numbered in arbitrary order from 1 to \verb\|nc\|,
alpar@9	856 where \verb\|nc\| is the total number of components found,
alpar@9	857 $0\leq$ \verb\|nc\| $\leq\|V\|$.
alpar@9	858
alpar@9	859 \subsubsection*{Returns}
alpar@9	860
alpar@9	861 The routine returns \verb\|nc\|, the total number of components found.
alpar@9	862
alpar@9	863 \subsection{glp\_strong\_comp---find all strongly connected components
alpar@9	864 of graph}
alpar@9	865
alpar@9	866 \subsubsection*{Synopsis}
alpar@9	867
alpar@9	868 \begin{verbatim}
alpar@9	869 int glp_strong_comp(glp_graph *G, int v_num);
alpar@9	870 \end{verbatim}
alpar@9	871
alpar@9	872 \subsubsection*{Description}
alpar@9	873
alpar@9	874 The routine \verb\|glp_strong_comp\| finds all strongly connected
alpar@9	875 components of the specified graph.
alpar@9	876
alpar@9	877 The parameter \verb\|v_num\| specifies an offset of the field of type
alpar@9	878 \verb\|int\| in the vertex data block, to which the routine stores the
alpar@9	879 number of a strongly connected component containing that vertex. If
alpar@9	880 \verb\|v_num\| $<0$, no component numbers are stored.
alpar@9	881
alpar@9	882 The components are numbered in arbitrary order from 1 to \verb\|nc\|,
alpar@9	883 where \verb\|nc\| is the total number of components found,
alpar@9	884 $0\leq$ \verb\|nc\| $\leq\|V\|$. However, the component numbering has the
alpar@9	885 property that for every arc $(i\rightarrow j)$ in the graph the
alpar@9	886 condition $num(i)\geq num(j)$ holds.
alpar@9	887
alpar@9	888 \subsubsection*{Returns}
alpar@9	889
alpar@9	890 The routine returns \verb\|nc\|, the total number of components found.
alpar@9	891
alpar@9	892 \subsubsection*{References}
alpar@9	893
alpar@9	894 I.~S.~Duff, J.~K.~Reid, Algorithm 529: Permutations to block triangular
alpar@9	895 form, ACM Trans. on Math. Softw. 4 (1978), 189-92.
alpar@9	896
alpar@9	897 \subsubsection*{Example}
alpar@9	898
alpar@9	899 The following program reads a graph from a plain text file
alpar@9	900 `\verb\|graph.txt\|' and finds all its strongly connected components.
alpar@9	901
alpar@9	902 \begin{footnotesize}
alpar@9	903 \begin{verbatim}
alpar@9	904 #include <stddef.h>
alpar@9	905 #include <stdio.h>
alpar@9	906 #include <stdlib.h>
alpar@9	907 #include <glpk.h>
alpar@9	908
alpar@9	909 typedef struct { int num; } v_data;
alpar@9	910
alpar@9	911 #define vertex(v) ((v_data *)((v)->data))
alpar@9	912
alpar@9	913 int main(void)
alpar@9	914 { glp_graph *G;
alpar@9	915 int i, nc;
alpar@9	916 G = glp_create_graph(sizeof(v_data), 0);
alpar@9	917 glp_read_graph(G, "graph.txt");
alpar@9	918 nc = glp_strong_comp(G, offsetof(v_data, num));
alpar@9	919 printf("nc = %d\n", nc);
alpar@9	920 for (i = 1; i <= G->nv; i++)
alpar@9	921 printf("num[%d] = %d\n", i, vertex(G->v[i])->num);
alpar@9	922 glp_delete_graph(G);
alpar@9	923 return 0;
alpar@9	924 }
alpar@9	925 \end{verbatim}
alpar@9	926 \end{footnotesize}
alpar@9	927
alpar@9	928 \noindent
alpar@9	929 If the file `\verb\|graph.txt\|' contains the graph shown below:
alpar@9	930
alpar@9	931 \bigskip
alpar@9	932
alpar@9	933 \noindent\hfil
alpar@9	934 \xymatrix
alpar@9	935 {1\ar[r]&2\ar[r]&3\ar[r]\ar[dd]&4\ar[dd]\\
alpar@9	936 5\ar[u]&6\ar[l]\\
alpar@9	937 7\ar[u]&&8\ar[lu]\ar[ll]\ar[r]&9\ar[r]&10\ar[r]\ar[d]&11\ar[d]\\
alpar@9	938 12\ar[u]\ar[rru]\ar@/_/[rr]&&13\ar[ll]\ar[u]\ar[rr]&&14\ar[lu]&15\ar[l]
alpar@9	939 \\
alpar@9	940 }
alpar@9	941
alpar@9	942 \bigskip\bigskip
alpar@9	943
alpar@9	944 \noindent
alpar@9	945 the program output may look like follows:
alpar@9	946
alpar@9	947 \begin{footnotesize}
alpar@9	948 \begin{verbatim}
alpar@9	949 Reading graph from `graph.txt'...
alpar@9	950 Graph has 15 vertices and 30 arcs
alpar@9	951 31 lines were read
alpar@9	952 nc = 4
alpar@9	953 num[1] = 3
alpar@9	954 num[2] = 3
alpar@9	955 num[3] = 3
alpar@9	956 num[4] = 2
alpar@9	957 num[5] = 3
alpar@9	958 num[6] = 3
alpar@9	959 num[7] = 3
alpar@9	960 num[8] = 3
alpar@9	961 num[9] = 1
alpar@9	962 num[10] = 1
alpar@9	963 num[11] = 1
alpar@9	964 num[12] = 4
alpar@9	965 num[13] = 4
alpar@9	966 num[14] = 1
alpar@9	967 num[15] = 1
alpar@9	968 \end{verbatim}
alpar@9	969 \end{footnotesize}
alpar@9	970
alpar@9	971 \subsection{glp\_top\_sort---topological sorting of acyclic digraph}
alpar@9	972
alpar@9	973 \subsubsection*{Synopsis}
alpar@9	974
alpar@9	975 \begin{verbatim}
alpar@9	976 int glp_top_sort(glp_graph *G, int v_num);
alpar@9	977 \end{verbatim}
alpar@9	978
alpar@9	979 \subsubsection*{Description}
alpar@9	980
alpar@9	981 The routine \verb\|glp_top_sort\| performs topological sorting of
alpar@9	982 vertices of the specified acyclic digraph.
alpar@9	983
alpar@9	984 The parameter \verb\|v_num\| specifies an offset of the field of type
alpar@9	985 \verb\|int\| in the vertex data block, to which the routine stores the
alpar@9	986 vertex number assigned. If \verb\|v_num\| $<0$, vertex numbers are not
alpar@9	987 stored.
alpar@9	988
alpar@9	989 The vertices are numbered from 1 to $n$, where $n$ is the total number
alpar@9	990 of vertices in the graph. The vertex numbering has the property that
alpar@9	991 for every arc $(i\rightarrow j)$ in the graph the condition
alpar@9	992 $num(i)<num(j)$ holds. Special case $num(i)=0$ means that vertex $i$ is
alpar@9	993 not assigned a number, because the graph is {\it not} acyclic.
alpar@9	994
alpar@9	995 \subsubsection*{Returns}
alpar@9	996
alpar@9	997 If the graph is acyclic and therefore all the vertices have been
alpar@9	998 assigned numbers, the routine \verb\|glp_top_sort\| returns zero.
alpar@9	999 Otherwise, if the graph is not acyclic, the routine returns the number
alpar@9	1000 of vertices which have not been numbered, i.e. for which $num(i)=0$.
alpar@9	1001
alpar@9	1002 \subsubsection*{Example}
alpar@9	1003
alpar@9	1004 The following program reads a digraph from a plain text file
alpar@9	1005 `\verb\|graph.txt\|' and performs topological sorting of its vertices.
alpar@9	1006
alpar@9	1007 \begin{footnotesize}
alpar@9	1008 \begin{verbatim}
alpar@9	1009 #include <stddef.h>
alpar@9	1010 #include <stdio.h>
alpar@9	1011 #include <stdlib.h>
alpar@9	1012 #include <glpk.h>
alpar@9	1013
alpar@9	1014 typedef struct { int num; } v_data;
alpar@9	1015
alpar@9	1016 #define vertex(v) ((v_data *)((v)->data))
alpar@9	1017
alpar@9	1018 int main(void)
alpar@9	1019 { glp_graph *G;
alpar@9	1020 int i, cnt;
alpar@9	1021 G = glp_create_graph(sizeof(v_data), 0);
alpar@9	1022 glp_read_graph(G, "graph.txt");
alpar@9	1023 cnt = glp_top_sort(G, offsetof(v_data, num));
alpar@9	1024 printf("cnt = %d\n", cnt);
alpar@9	1025 for (i = 1; i <= G->nv; i++)
alpar@9	1026 printf("num[%d] = %d\n", i, vertex(G->v[i])->num);
alpar@9	1027 glp_delete_graph(G);
alpar@9	1028 return 0;
alpar@9	1029 }
alpar@9	1030 \end{verbatim}
alpar@9	1031 \end{footnotesize}
alpar@9	1032
alpar@9	1033 \noindent
alpar@9	1034 If the file `\verb\|graph.txt\|' contains the graph shown below:
alpar@9	1035
alpar@9	1036 \bigskip
alpar@9	1037
alpar@9	1038 \noindent\hfil
alpar@9	1039 \xymatrix @=20pt
alpar@9	1040 {
alpar@9	1041 1\ar[rrr]&&&2\ar[r]\ar[rddd]&3\ar[rd]&&&&\\
alpar@9	1042 &&&4\ar[ru]&&5\ar[r]&6\ar[rd]\ar[dd]&&\\
alpar@9	1043 7\ar[r]&8\ar[r]&9\ar[ruu]\ar[ru]\ar[r]\ar[rd]&10\ar[rr]\ar[rru]&&
alpar@9	1044 11\ar[ru]&&12\ar[r]&13\\
alpar@9	1045 &&&14\ar[r]&15\ar[rrru]\ar[rr]&&16\ar[rru]\ar[rr]&&17\\
alpar@9	1046 }
alpar@9	1047
alpar@9	1048 \bigskip\bigskip
alpar@9	1049
alpar@9	1050 \noindent
alpar@9	1051 the program output may look like follows:
alpar@9	1052
alpar@9	1053 \begin{footnotesize}
alpar@9	1054 \begin{verbatim}
alpar@9	1055 Reading graph from `graph.txt'...
alpar@9	1056 Graph has 17 vertices and 23 arcs
alpar@9	1057 24 lines were read
alpar@9	1058 cnt = 0
alpar@9	1059 num[1] = 8
alpar@9	1060 num[2] = 9
alpar@9	1061 num[3] = 10
alpar@9	1062 num[4] = 4
alpar@9	1063 num[5] = 11
alpar@9	1064 num[6] = 12
alpar@9	1065 num[7] = 1
alpar@9	1066 num[8] = 2
alpar@9	1067 num[9] = 3
alpar@9	1068 num[10] = 5
alpar@9	1069 num[11] = 6
alpar@9	1070 num[12] = 14
alpar@9	1071 num[13] = 16
alpar@9	1072 num[14] = 7
alpar@9	1073 num[15] = 13
alpar@9	1074 num[16] = 15
alpar@9	1075 num[17] = 17
alpar@9	1076 \end{verbatim}
alpar@9	1077 \end{footnotesize}
alpar@9	1078
alpar@9	1079 \noindent
alpar@9	1080 The output corresponds to the following vertex numbering:
alpar@9	1081
alpar@9	1082 \bigskip
alpar@9	1083
alpar@9	1084 \noindent\hfil
alpar@9	1085 \xymatrix @=20pt
alpar@9	1086 {
alpar@9	1087 8\ar[rrr]&&&9\ar[r]\ar[rddd]&10\ar[rd]&&&&\\
alpar@9	1088 &&&4\ar[ru]&&11\ar[r]&12\ar[rd]\ar[dd]&&\\
alpar@9	1089 1\ar[r]&2\ar[r]&3\ar[ruu]\ar[ru]\ar[r]\ar[rd]&5\ar[rr]\ar[rru]&&
alpar@9	1090 6\ar[ru]&&14\ar[r]&16\\
alpar@9	1091 &&&7\ar[r]&13\ar[rrru]\ar[rr]&&15\ar[rru]\ar[rr]&&17\\
alpar@9	1092 }
alpar@9	1093
alpar@9	1094 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9	1095
alpar@9	1096 \chapter{Network optimization API routines}
alpar@9	1097
alpar@9	1098 \section{Minimum cost flow problem}
alpar@9	1099
alpar@9	1100 \subsection{Background}
alpar@9	1101
alpar@9	1102 The {\it minimum cost flow problem} (MCFP) is stated as follows. Let
alpar@9	1103 there be given a directed graph (flow network) $G=(V,A)$, where $V$ is
alpar@9	1104 a set of vertices (nodes), and $A\subseteq V\times V$ is a set of arcs.
alpar@9	1105 Let for each node $i\in V$ there be given a quantity $b_i$ having the
alpar@9	1106 following meaning:
alpar@9	1107
alpar@9	1108 if $b_i>0$, then $\|b_i\|$ is a {\it supply} at node $i$, which shows
alpar@9	1109 how many flow units are {\it generated} at node $i$ (or, equivalently,
alpar@9	1110 entering the network through node $i$ from the outside);
alpar@9	1111
alpar@9	1112 if $b_i<0$, then $\|b_i\|$ is a {\it demand} at node $i$, which shows how
alpar@9	1113 many flow units are {\it lost} at node $i$ (or, equivalently, leaving
alpar@9	1114 the network through node $i$ to the outside);
alpar@9	1115
alpar@9	1116 if $b_i=0$, then $i$ is a {\it transshipment} node, at which the flow
alpar@9	1117 is conserved, i.e. neither generated nor lost.
alpar@9	1118
alpar@9	1119 Let also for each arc $a=(i,j)\in A$ there be given the following three
alpar@9	1120 quantities:
alpar@9	1121
alpar@9	1122 $l_{ij}$, a (non-negative) lower bound to the flow through arc $(i,j)$;
alpar@9	1123
alpar@9	1124 $u_{ij}$, an upper bound to the flow through arc $(i,j)$, which is the
alpar@9	1125 {\it arc capacity};
alpar@9	1126
alpar@9	1127 $c_{ij}$, a per-unit cost of the flow through arc $(i,j)$.
alpar@9	1128
alpar@9	1129 The problem is to find flows $x_{ij}$ through every arc of the network,
alpar@9	1130 which satisfy the specified bounds and the conservation constraints at
alpar@9	1131 all nodes, and minimize the total flow cost. Here the conservation
alpar@9	1132 constraint at a node means that the total flow entering this node
alpar@9	1133 through its incoming arcs plus the supply at this node must be equal to
alpar@9	1134 the total flow leaving this node through its outgoing arcs plus the
alpar@9	1135 demand at this node.
alpar@9	1136
alpar@9	1137 An example of the minimum cost flow problem is shown on Fig.~1.
alpar@9	1138
alpar@9	1139 \bigskip
alpar@9	1140
alpar@9	1141 \noindent\hfil
alpar@9	1142 \xymatrix @C=48pt
alpar@9	1143 {_{20}\ar@{~>}[d]&
alpar@9	1144 v_2\ar[r]\|{_{0,10,\$2}}\ar[dd]\|{_{0,9,\$3}}&
alpar@9	1145 v_3\ar[dd]\|{_{2,12,\$1}}\ar[r]\|{_{0,18,\$0}}&
alpar@9	1146 v_8\ar[rd]\|{_{0,20,\$9}}&\\
alpar@9	1147 v_1\ar[ru]\|{_{0,14,\$0}}\ar[rd]\|{_{0,23,\$0}}&&&
alpar@9	1148 v_6\ar[d]\|{_{0,7,\$0}}\ar[u]\|{_{4,8,\$0}}&
alpar@9	1149 v_9\ar@{~>}[d]\\
alpar@9	1150 &v_4\ar[r]\|{_{0,26,\$0}}&
alpar@9	1151 v_5\ar[luu]\|{_{0,11,\$1}}\ar[ru]\|{_{0,25,\$5}}\ar[r]\|{_{0,4,\$7}}&
alpar@9	1152 v_7\ar[ru]\|{_{0,15,\$3}}&_{20}\\
alpar@9	1153 }
alpar@9	1154
alpar@9	1155 \medskip
alpar@9	1156
alpar@9	1157 \noindent\hfil
alpar@9	1158 \begin{tabular}{ccc}
alpar@9	1159 \xymatrix @C=48pt{v_i\ar[r]\|{\ l,u,\$c\ }&v_j\\}&
alpar@9	1160 \xymatrix{\hbox{\footnotesize supply}\ar@{~>}[r]&v_i\\}&
alpar@9	1161 \xymatrix{v_i\ar@{~>}[r]&\hbox{\footnotesize demand}\\}\\
alpar@9	1162 \end{tabular}
alpar@9	1163
alpar@9	1164 \bigskip
alpar@9	1165
alpar@9	1166 \noindent\hfil
alpar@9	1167 Fig.~1. An example of the minimum cost flow problem.
alpar@9	1168
alpar@9	1169 \bigskip
alpar@9	1170
alpar@9	1171 The minimum cost flow problem can be naturally formulated as the
alpar@9	1172 following LP problem:
alpar@9	1173
alpar@9	1174 \medskip
alpar@9	1175
alpar@9	1176 \noindent
alpar@9	1177 \hspace{.5in}minimize
alpar@9	1178 $$z=\sum_{(i,j)\in A}c_{ij}x_{ij}\eqno(1)$$
alpar@9	1179 \hspace{.5in}subject to
alpar@9	1180 $$\sum_{(i,j)\in A}x_{ij}-\sum_{(j,i)\in A}x_{ji}=b_i\ \ \ \hbox
alpar@9	1181 {for all}\ i\in V\eqno(2)$$
alpar@9	1182 $$l_{ij}\leq x_{ij}\leq u_{ij}\ \ \ \hbox{for all}\ (i,j)\in A
alpar@9	1183 \eqno(3)$$
alpar@9	1184
alpar@9	1185 \newpage
alpar@9	1186
alpar@9	1187 \subsection{glp\_read\_mincost---read minimum cost flow problem\\data
alpar@9	1188 in DIMACS format}
alpar@9	1189
alpar@9	1190 \subsubsection*{Synopsis}
alpar@9	1191
alpar@9	1192 \begin{verbatim}
alpar@9	1193 int glp_read_mincost(glp_graph *G, int v_rhs, int a_low,
alpar@9	1194 int a_cap, int a_cost, const char *fname);
alpar@9	1195 \end{verbatim}
alpar@9	1196
alpar@9	1197 \subsubsection*{Description}
alpar@9	1198
alpar@9	1199 The routine \verb\|glp_read_mincost\| reads the minimum cost flow problem
alpar@9	1200 data from a text file in DIMACS format.
alpar@9	1201
alpar@9	1202 The parameter \verb\|G\| specifies the graph object, to which the problem
alpar@9	1203 data have to be stored. Note that before reading data the current
alpar@9	1204 content of the graph object is completely erased with the routine
alpar@9	1205 \verb\|glp_erase_graph\|.
alpar@9	1206
alpar@9	1207 The parameter \verb\|v_rhs\| specifies an offset of the field of type
alpar@9	1208 \verb\|double\| in the vertex data block, to which the routine stores
alpar@9	1209 $b_i$, the supply/demand value. If \verb\|v_rhs\| $<0$, the value is not
alpar@9	1210 stored.
alpar@9	1211
alpar@9	1212 The parameter \verb\|a_low\| specifies an offset of the field of type
alpar@9	1213 \verb\|double\| in the arc data block, to which the routine stores
alpar@9	1214 $l_{ij}$, the lower bound to the arc flow. If \verb\|a_low\| $<0$, the
alpar@9	1215 lower bound is not stored.
alpar@9	1216
alpar@9	1217 The parameter \verb\|a_cap\| specifies an offset of the field of type
alpar@9	1218 \verb\|double\| in the arc data block, to which the routine stores
alpar@9	1219 $u_{ij}$, the upper bound to the arc flow (the arc capacity). If
alpar@9	1220 \verb\|a_cap\| $<0$, the upper bound is not stored.
alpar@9	1221
alpar@9	1222 The parameter \verb\|a_cost\| specifies an offset of the field of type
alpar@9	1223 \verb\|double\| in the arc data block, to which the routine stores
alpar@9	1224 $c_{ij}$, the per-unit cost of the arc flow. If \verb\|a_cost\| $<0$, the
alpar@9	1225 cost is not stored.
alpar@9	1226
alpar@9	1227 The character string \verb\|fname\| specifies the name of a text file to
alpar@9	1228 be read in. (If the file name name ends with the suffix `\verb\|.gz\|',
alpar@9	1229 the file is assumed to be compressed, in which case the routine
alpar@9	1230 decompresses it ``on the fly''.)
alpar@9	1231
alpar@9	1232 \subsubsection*{Returns}
alpar@9	1233
alpar@9	1234 If the operation was successful, the routine returns zero. Otherwise,
alpar@9	1235 it prints an error message and returns non-zero.
alpar@9	1236
alpar@9	1237 \newpage
alpar@9	1238
alpar@9	1239 \subsubsection*{Example}
alpar@9	1240
alpar@9	1241 \begin{footnotesize}
alpar@9	1242 \begin{verbatim}
alpar@9	1243 typedef struct
alpar@9	1244 { /* vertex data block */
alpar@9	1245 ...
alpar@9	1246 double rhs;
alpar@9	1247 ...
alpar@9	1248 } v_data;
alpar@9	1249
alpar@9	1250 typedef struct
alpar@9	1251 { /* arc data block */
alpar@9	1252 ...
alpar@9	1253 double low, cap, cost;
alpar@9	1254 ...
alpar@9	1255 } a_data;
alpar@9	1256
alpar@9	1257 int main(void)
alpar@9	1258 { glp_graph *G;
alpar@9	1259 int ret;
alpar@9	1260 G = glp_create_graph(sizeof(v_data), sizeof(a_data));
alpar@9	1261 ret = glp_read_mincost(G, offsetof(v_data, rhs),
alpar@9	1262 offsetof(a_data, low), offsetof(a_data, cap),
alpar@9	1263 offsetof(a_data, cost), "sample.min");
alpar@9	1264 if (ret != 0) goto ...
alpar@9	1265 ...
alpar@9	1266 }
alpar@9	1267 \end{verbatim}
alpar@9	1268 \end{footnotesize}
alpar@9	1269
alpar@9	1270 \subsubsection*{DIMACS minimum cost flow problem format\footnote{This
alpar@9	1271 material is based on the paper ``The First DIMACS International
alpar@9	1272 Algorithm Implementation Challenge: Problem Definitions and
alpar@9	1273 Specifications'', which is publically available at
alpar@9	1274 {\tt http://dimacs.rutgers.edu/Challenges/}.}}
alpar@9	1275 \label{subsecmincost}
alpar@9	1276
alpar@9	1277 The DIMACS input file is a plain ASCII text file. It contains
alpar@9	1278 {\it lines} of several types described below. A line is terminated with
alpar@9	1279 an end-of-line character. Fields in each line are separated by at least
alpar@9	1280 one blank space. Each line begins with a one-character designator to
alpar@9	1281 identify the line type.
alpar@9	1282
alpar@9	1283 Note that DIMACS requires all numerical quantities to be integers in
alpar@9	1284 the range $[-2^{31},\ 2^{31}-1]$ while GLPK allows the quantities to be
alpar@9	1285 floating-point numbers.
alpar@9	1286
alpar@9	1287 \newpage
alpar@9	1288
alpar@9	1289 \paragraph{Comment lines.} Comment lines give human-readable information
alpar@9	1290 about the file and are ignored by programs. Comment lines can appear
alpar@9	1291 anywhere in the file. Each comment line begins with a lower-case
alpar@9	1292 character \verb\|c\|.
alpar@9	1293
alpar@9	1294 \begin{verbatim}
alpar@9	1295 c This is a comment line
alpar@9	1296 \end{verbatim}
alpar@9	1297
alpar@9	1298 \paragraph{Problem line.} There is one problem line per data file. The
alpar@9	1299 problem line must appear before any node or arc descriptor lines. It has
alpar@9	1300 the following format:
alpar@9	1301
alpar@9	1302 \begin{verbatim}
alpar@9	1303 p min NODES ARCS
alpar@9	1304 \end{verbatim}
alpar@9	1305
alpar@9	1306 \noindent
alpar@9	1307 The lower-case character \verb\|p\| signifies that this is a problem line.
alpar@9	1308 The three-character problem designator \verb\|min\| identifies the file as
alpar@9	1309 containing specification information for the minimum cost flow problem.
alpar@9	1310 The \verb\|NODES\| field contains an integer value specifying the number
alpar@9	1311 of nodes in the network. The \verb\|ARCS\| field contains an integer value
alpar@9	1312 specifying the number of arcs in the network.
alpar@9	1313
alpar@9	1314 \paragraph{Node descriptors.} All node descriptor lines must appear
alpar@9	1315 before all arc descriptor lines. The node descriptor lines describe
alpar@9	1316 supply and demand nodes, but not transshipment nodes. That is, only
alpar@9	1317 nodes with non-zero node supply/demand values appear. There is one node
alpar@9	1318 descriptor line for each such node, with the following format:
alpar@9	1319
alpar@9	1320 \begin{verbatim}
alpar@9	1321 n ID FLOW
alpar@9	1322 \end{verbatim}
alpar@9	1323
alpar@9	1324 \noindent
alpar@9	1325 The lower-case character \verb\|n\| signifies that this is a node
alpar@9	1326 descriptor line. The \verb\|ID\| field gives a node identification number,
alpar@9	1327 an integer between 1 and \verb\|NODES\|. The \verb\|FLOW\| field gives the
alpar@9	1328 amount of supply (if positive) or demand (if negative) at node
alpar@9	1329 \verb\|ID\|.
alpar@9	1330
alpar@9	1331 \paragraph{Arc descriptors.} There is one arc descriptor line for each
alpar@9	1332 arc in the network. Arc descriptor lines are of the following format:
alpar@9	1333
alpar@9	1334 \begin{verbatim}
alpar@9	1335 a SRC DST LOW CAP COST
alpar@9	1336 \end{verbatim}
alpar@9	1337
alpar@9	1338 \noindent
alpar@9	1339 The lower-case character \verb\|a\| signifies that this is an arc
alpar@9	1340 descriptor line. For a directed arc $(i,j)$ the \verb\|SRC\| field gives
alpar@9	1341 the identification number $i$ for the tail endpoint, and the \verb\|DST\|
alpar@9	1342 field gives the identification number $j$ for the head endpoint.
alpar@9	1343 Identification numbers are integers between 1 and \verb\|NODES\|. The
alpar@9	1344 \verb\|LOW\| field specifies the minimum amount of flow that can be sent
alpar@9	1345 along arc $(i,j)$, and the \verb\|CAP\| field gives the maximum amount of
alpar@9	1346 flow that can be sent along arc $(i,j)$ in a feasible flow. The
alpar@9	1347 \verb\|COST\| field contains the per-unit cost of flow sent along arc
alpar@9	1348 $(i,j)$.
alpar@9	1349
alpar@9	1350 \paragraph{Example.} Below here is an example of the data file in
alpar@9	1351 DIMACS format corresponding to the minimum cost flow problem shown on
alpar@9	1352 Fig~1.
alpar@9	1353
alpar@9	1354 \begin{footnotesize}
alpar@9	1355 \begin{verbatim}
alpar@9	1356 c sample.min
alpar@9	1357 c
alpar@9	1358 c This is an example of the minimum cost flow problem data
alpar@9	1359 c in DIMACS format.
alpar@9	1360 c
alpar@9	1361 p min 9 14
alpar@9	1362 c
alpar@9	1363 n 1 20
alpar@9	1364 n 9 -20
alpar@9	1365 c
alpar@9	1366 a 1 2 0 14 0
alpar@9	1367 a 1 4 0 23 0
alpar@9	1368 a 2 3 0 10 2
alpar@9	1369 a 2 4 0 9 3
alpar@9	1370 a 3 5 2 12 1
alpar@9	1371 a 3 8 0 18 0
alpar@9	1372 a 4 5 0 26 0
alpar@9	1373 a 5 2 0 11 1
alpar@9	1374 a 5 6 0 25 5
alpar@9	1375 a 5 7 0 4 7
alpar@9	1376 a 6 7 0 7 0
alpar@9	1377 a 6 8 4 8 0
alpar@9	1378 a 7 9 0 15 3
alpar@9	1379 a 8 9 0 20 9
alpar@9	1380 c
alpar@9	1381 c eof
alpar@9	1382 \end{verbatim}
alpar@9	1383 \end{footnotesize}
alpar@9	1384
alpar@9	1385 \newpage
alpar@9	1386
alpar@9	1387 \subsection{glp\_write\_mincost---write minimum cost flow problem\\data
alpar@9	1388 in DIMACS format}
alpar@9	1389
alpar@9	1390 \subsubsection*{Synopsis}
alpar@9	1391
alpar@9	1392 \begin{verbatim}
alpar@9	1393 int glp_write_mincost(glp_graph *G, int v_rhs, int a_low,
alpar@9	1394 int a_cap, int a_cost, const char *fname);
alpar@9	1395 \end{verbatim}
alpar@9	1396
alpar@9	1397 \subsubsection*{Description}
alpar@9	1398
alpar@9	1399 The routine \verb\|glp_write_mincost\| writes the minimum cost flow
alpar@9	1400 problem data to a text file in DIMACS format.
alpar@9	1401
alpar@9	1402 The parameter \verb\|G\| is the graph (network) program object, which
alpar@9	1403 specifies the minimum cost flow problem instance.
alpar@9	1404
alpar@9	1405 The parameter \verb\|v_rhs\| specifies an offset of the field of type
alpar@9	1406 \verb\|double\| in the vertex data block, which contains $b_i$, the
alpar@9	1407 supply/demand value. If \verb\|v_rhs\| $<0$, it is assumed that $b_i=0$
alpar@9	1408 for all nodes.
alpar@9	1409
alpar@9	1410 The parameter \verb\|a_low\| specifies an offset of the field of type
alpar@9	1411 \verb\|double\| in the arc data block, which contains $l_{ij}$, the lower
alpar@9	1412 bound to the arc flow. If \verb\|a_low\| $<0$, it is assumed that
alpar@9	1413 $l_{ij}=0$ for all arcs.
alpar@9	1414
alpar@9	1415 The parameter \verb\|a_cap\| specifies an offset of the field of type
alpar@9	1416 \verb\|double\| in the arc data block, which contains $u_{ij}$, the upper
alpar@9	1417 bound to the arc flow (the arc capacity). If the upper bound is
alpar@9	1418 specified as \verb\|DBL_MAX\|, it is assumed that $u_{ij}=\infty$, i.e.
alpar@9	1419 the arc is uncapacitated. If \verb\|a_cap\| $<0$, it is assumed that
alpar@9	1420 $u_{ij}=1$ for all arcs.
alpar@9	1421
alpar@9	1422 The parameter \verb\|a_cost\| specifies an offset of the field of type
alpar@9	1423 \verb\|double\| in the arc data block, which contains $c_{ij}$, the
alpar@9	1424 per-unit cost of the arc flow. If \verb\|a_cost\| $<0$, it is assumed that
alpar@9	1425 $c_{ij}=0$ for all arcs.
alpar@9	1426
alpar@9	1427 The character string \verb\|fname\| specifies a name of the text file to
alpar@9	1428 be written out. (If the file name ends with suffix `\verb\|.gz\|', the
alpar@9	1429 file is assumed to be compressed, in which case the routine performs
alpar@9	1430 automatic compression on writing it.)
alpar@9	1431
alpar@9	1432 \subsubsection*{Returns}
alpar@9	1433
alpar@9	1434 If the operation was successful, the routine returns zero. Otherwise,
alpar@9	1435 it prints an error message and returns non-zero.
alpar@9	1436
alpar@9	1437 \newpage
alpar@9	1438
alpar@9	1439 \subsection{glp\_mincost\_lp---convert minimum cost flow problem\\to LP}
alpar@9	1440
alpar@9	1441 \subsubsection*{Synopsis}
alpar@9	1442
alpar@9	1443 \begin{verbatim}
alpar@9	1444 void glp_mincost_lp(glp_prob lp, glp_graph G, int names,
alpar@9	1445 int v_rhs, int a_low, int a_cap, int a_cost);
alpar@9	1446 \end{verbatim}
alpar@9	1447
alpar@9	1448 \subsubsection*{Description}
alpar@9	1449
alpar@9	1450 The routine \verb\|glp_mincost_lp\| builds LP problem (1)---(3), which
alpar@9	1451 corresponds to the specified minimum cost flow problem.
alpar@9	1452
alpar@9	1453 The parameter \verb\|lp\| is the resultant LP problem object to be built.
alpar@9	1454 Note that on entry its current content is erased with the routine
alpar@9	1455 \verb\|glp_erase_prob\|.
alpar@9	1456
alpar@9	1457 The parameter \verb\|G\| is the graph (network) program object, which
alpar@9	1458 specifies the minimum cost flow problem instance.
alpar@9	1459
alpar@9	1460 The parameter \verb\|names\| is a flag. If it is \verb\|GLP_ON\|, the
alpar@9	1461 routine uses symbolic names of the graph object components to assign
alpar@9	1462 symbolic names to the LP problem object components. If the flag is
alpar@9	1463 \verb\|GLP_OFF\|, no symbolic names are assigned.
alpar@9	1464
alpar@9	1465 The parameter \verb\|v_rhs\| specifies an offset of the field of type
alpar@9	1466 \verb\|double\| in the vertex data block, which contains $b_i$, the
alpar@9	1467 supply/demand value. If \verb\|v_rhs\| $<0$, it is assumed that $b_i=0$
alpar@9	1468 for all nodes.
alpar@9	1469
alpar@9	1470 The parameter \verb\|a_low\| specifies an offset of the field of type
alpar@9	1471 \verb\|double\| in the arc data block, which contains $l_{ij}$, the lower
alpar@9	1472 bound to the arc flow. If \verb\|a_low\| $<0$, it is assumed that
alpar@9	1473 $l_{ij}=0$ for all arcs.
alpar@9	1474
alpar@9	1475 The parameter \verb\|a_cap\| specifies an offset of the field of type
alpar@9	1476 \verb\|double\| in the arc data block, which contains $u_{ij}$, the upper
alpar@9	1477 bound to the arc flow (the arc capacity). If the upper bound is
alpar@9	1478 specified as \verb\|DBL_MAX\|, it is assumed that $u_{ij}=\infty$, i.e.
alpar@9	1479 the arc is uncapacitated. If \verb\|a_cap\| $<0$, it is assumed that
alpar@9	1480 $u_{ij}=1$ for all arcs.
alpar@9	1481
alpar@9	1482 The parameter \verb\|a_cost\| specifies an offset of the field of type
alpar@9	1483 \verb\|double\| in the arc data block, which contains $c_{ij}$, the
alpar@9	1484 per-unit cost of the arc flow. If \verb\|a_cost\| $<0$, it is assumed that
alpar@9	1485 $c_{ij}=0$ for all arcs.
alpar@9	1486
alpar@9	1487 \subsubsection*{Example}
alpar@9	1488
alpar@9	1489 The example program below reads the minimum cost problem instance in
alpar@9	1490 DIMACS format from file `\verb\|sample.min\|', converts the instance to
alpar@9	1491 LP, and then writes the resultant LP in CPLEX format to file
alpar@9	1492 `\verb\|mincost.lp\|'.
alpar@9	1493
alpar@9	1494 \newpage
alpar@9	1495
alpar@9	1496 \begin{footnotesize}
alpar@9	1497 \begin{verbatim}
alpar@9	1498 #include <stddef.h>
alpar@9	1499 #include <glpk.h>
alpar@9	1500
alpar@9	1501 typedef struct { double rhs; } v_data;
alpar@9	1502 typedef struct { double low, cap, cost; } a_data;
alpar@9	1503
alpar@9	1504 int main(void)
alpar@9	1505 { glp_graph *G;
alpar@9	1506 glp_prob *lp;
alpar@9	1507 G = glp_create_graph(sizeof(v_data), sizeof(a_data));
alpar@9	1508 glp_read_mincost(G, offsetof(v_data, rhs),
alpar@9	1509 offsetof(a_data, low), offsetof(a_data, cap),
alpar@9	1510 offsetof(a_data, cost), "sample.min");
alpar@9	1511 lp = glp_create_prob();
alpar@9	1512 glp_mincost_lp(lp, G, GLP_ON, offsetof(v_data, rhs),
alpar@9	1513 offsetof(a_data, low), offsetof(a_data, cap),
alpar@9	1514 offsetof(a_data, cost));
alpar@9	1515 glp_delete_graph(G);
alpar@9	1516 glp_write_lp(lp, NULL, "mincost.lp");
alpar@9	1517 glp_delete_prob(lp);
alpar@9	1518 return 0;
alpar@9	1519 }
alpar@9	1520 \end{verbatim}
alpar@9	1521 \end{footnotesize}
alpar@9	1522
alpar@9	1523 If `\verb\|sample.min\|' is the example data file from the subsection
alpar@9	1524 describing the routine \verb\|glp_read_mincost\|, file `\verb\|mincost.lp\|'
alpar@9	1525 may look like follows:
alpar@9	1526
alpar@9	1527 \begin{footnotesize}
alpar@9	1528 \begin{verbatim}
alpar@9	1529 Minimize
alpar@9	1530 obj: + 3 x(2,4) + 2 x(2,3) + x(3,5) + 7 x(5,7) + 5 x(5,6)
alpar@9	1531 + x(5,2) + 3 x(7,9) + 9 x(8,9)
alpar@9	1532
alpar@9	1533 Subject To
alpar@9	1534 r_1: + x(1,2) + x(1,4) = 20
alpar@9	1535 r_2: - x(5,2) + x(2,3) + x(2,4) - x(1,2) = 0
alpar@9	1536 r_3: + x(3,5) + x(3,8) - x(2,3) = 0
alpar@9	1537 r_4: + x(4,5) - x(2,4) - x(1,4) = 0
alpar@9	1538 r_5: + x(5,2) + x(5,6) + x(5,7) - x(4,5) - x(3,5) = 0
alpar@9	1539 r_6: + x(6,7) + x(6,8) - x(5,6) = 0
alpar@9	1540 r_7: + x(7,9) - x(6,7) - x(5,7) = 0
alpar@9	1541 r_8: + x(8,9) - x(6,8) - x(3,8) = 0
alpar@9	1542 r_9: - x(8,9) - x(7,9) = -20
alpar@9	1543
alpar@9	1544 Bounds
alpar@9	1545 0 <= x(1,4) <= 23
alpar@9	1546 0 <= x(1,2) <= 14
alpar@9	1547 0 <= x(2,4) <= 9
alpar@9	1548 0 <= x(2,3) <= 10
alpar@9	1549 0 <= x(3,8) <= 18
alpar@9	1550 2 <= x(3,5) <= 12
alpar@9	1551 0 <= x(4,5) <= 26
alpar@9	1552 0 <= x(5,7) <= 4
alpar@9	1553 0 <= x(5,6) <= 25
alpar@9	1554 0 <= x(5,2) <= 11
alpar@9	1555 4 <= x(6,8) <= 8
alpar@9	1556 0 <= x(6,7) <= 7
alpar@9	1557 0 <= x(7,9) <= 15
alpar@9	1558 0 <= x(8,9) <= 20
alpar@9	1559
alpar@9	1560 End
alpar@9	1561 \end{verbatim}
alpar@9	1562 \end{footnotesize}
alpar@9	1563
alpar@9	1564 \subsection{glp\_mincost\_okalg---solve minimum cost flow problem with
alpar@9	1565 out-of-kilter algorithm}
alpar@9	1566
alpar@9	1567 \subsubsection*{Synopsis}
alpar@9	1568
alpar@9	1569 \begin{verbatim}
alpar@9	1570 int glp_mincost_okalg(glp_graph *G, int v_rhs, int a_low,
alpar@9	1571 int a_cap, int a_cost, double *sol, int a_x, int v_pi);
alpar@9	1572 \end{verbatim}
alpar@9	1573
alpar@9	1574 \subsubsection*{Description}
alpar@9	1575
alpar@9	1576 The routine \verb\|glp_mincost_okalg\| finds optimal solution to the
alpar@9	1577 minimum cost flow problem with the out-of-kilter
alpar@9	1578 algorithm.\footnote{GLPK implementation of the out-of-kilter algorithm
alpar@9	1579 is based on the following book: L.~R.~Ford,~Jr., and D.~R.~Fulkerson,
alpar@9	1580 ``Flows in Networks,'' The RAND Corp., Report R-375-PR (August 1962),
alpar@9	1581 Chap. III ``Minimal Cost Flow Problems,'' pp.~113-26.} Note that this
alpar@9	1582 routine requires all the problem data to be integer-valued.
alpar@9	1583
alpar@9	1584 The parameter \verb\|G\| is a graph (network) program object which
alpar@9	1585 specifies the minimum cost flow problem instance to be solved.
alpar@9	1586
alpar@9	1587 The parameter \verb\|v_rhs\| specifies an offset of the field of type
alpar@9	1588 \verb\|double\| in the vertex data block, which contains $b_i$, the
alpar@9	1589 supply/demand value. This value must be integer in the range
alpar@9	1590 [$-$\verb\|INT_MAX\|, $+$\verb\|INT_MAX\|]. If \verb\|v_rhs\| $<0$, it is
alpar@9	1591 assumed that $b_i=0$ for all nodes.
alpar@9	1592
alpar@9	1593 The parameter \verb\|a_low\| specifies an offset of the field of type
alpar@9	1594 \verb\|double\| in the arc data block, which contains $l_{ij}$, the lower
alpar@9	1595 bound to the arc flow. This bound must be integer in the range
alpar@9	1596 [$0$, \verb\|INT_MAX\|]. If \verb\|a_low\| $<0$, it is assumed that
alpar@9	1597 $l_{ij}=0$ for all arcs.
alpar@9	1598
alpar@9	1599 The parameter \verb\|a_cap\| specifies an offset of the field of type
alpar@9	1600 \verb\|double\| in the arc data block, which contains $u_{ij}$, the upper
alpar@9	1601 bound to the arc flow (the arc capacity). This bound must be integer in
alpar@9	1602 the range [$l_{ij}$, \verb\|INT_MAX\|]. If \verb\|a_cap\| $<0$, it is
alpar@9	1603 assumed that $u_{ij}=1$ for all arcs.
alpar@9	1604
alpar@9	1605 The parameter \verb\|a_cost\| specifies an offset of the field of type
alpar@9	1606 \verb\|double\| in the arc data block, which contains $c_{ij}$, the
alpar@9	1607 per-unit cost of the arc flow. This value must be integer in the range
alpar@9	1608 [$-$\verb\|INT_MAX\|, $+$\verb\|INT_MAX\|]. If \verb\|a_cost\| $<0$, it is
alpar@9	1609 assumed that $c_{ij}=0$ for all arcs.
alpar@9	1610
alpar@9	1611 The parameter \verb\|sol\| specifies a location, to which the routine
alpar@9	1612 stores the objective value (that is, the total cost) found. If
alpar@9	1613 \verb\|sol\| is NULL, the objective value is not stored.
alpar@9	1614
alpar@9	1615 The parameter \verb\|a_x\| specifies an offset of the field of type
alpar@9	1616 \verb\|double\| in the arc data block, to which the routine stores
alpar@9	1617 $x_{ij}$, the arc flow found. If \verb\|a_x\| $<0$, the arc flow value is
alpar@9	1618 not stored.
alpar@9	1619
alpar@9	1620 The parameter \verb\|v_pi\| specifies an offset of the field of type
alpar@9	1621 \verb\|double\| in the vertex data block, to which the routine stores
alpar@9	1622 $\pi_i$, the node potential, which is the Lagrange multiplier for the
alpar@9	1623 corresponding flow conservation equality constraint (see (2) in
alpar@9	1624 Subsection ``Background''). If necessary, the application program may
alpar@9	1625 use the node potentials to compute $\lambda_{ij}$, reduced costs of the
alpar@9	1626 arc flows $x_{ij}$, which are the Lagrange multipliers for the arc flow
alpar@9	1627 bound constraints (see (3) ibid.), using the following formula:
alpar@9	1628 $$\lambda_{ij}=c_{ij}-(\pi_i-\pi_j),$$
alpar@9	1629 where $c_{ij}$ is the per-unit cost for arc $(i,j)$.
alpar@9	1630
alpar@9	1631 Note that all solution components (the objective value, arc flows, and
alpar@9	1632 node potentials) computed by the routine are always integer-valued.
alpar@9	1633
alpar@9	1634 \subsubsection*{Returns}
alpar@9	1635
alpar@9	1636 \def\arraystretch{1}
alpar@9	1637
alpar@9	1638 \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
alpar@9	1639 0 & Optimal solution found.\\
alpar@9	1640 \verb\|GLP_ENOPFS\| & No (primal) feasible solution exists.\\
alpar@9	1641 \verb\|GLP_EDATA\| & Unable to start the search, because some problem
alpar@9	1642 data are either not integer-valued or out of range. This code is also
alpar@9	1643 returned if the total supply, which is the sum of $b_i$ over all source
alpar@9	1644 nodes (nodes with $b_i>0$), exceeds \verb\|INT_MAX\|.\\
alpar@9	1645 \end{tabular}
alpar@9	1646
alpar@9	1647 \noindent
alpar@9	1648 \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
alpar@9	1649 \verb\|GLP_ERANGE\| & The search was prematurely terminated because of
alpar@9	1650 integer overflow.\\
alpar@9	1651 \verb\|GLP_EFAIL\| & An error has been detected in the program logic.
alpar@9	1652 (If this code is returned for your problem instance, please report to
alpar@9	1653 \verb\|<bug-glpk@gnu.org>\|.)\\
alpar@9	1654 \end{tabular}
alpar@9	1655
alpar@9	1656 \subsubsection*{Comments}
alpar@9	1657
alpar@9	1658 By design the out-of-kilter algorithm is applicable only to networks,
alpar@9	1659 where $b_i=0$ for {\it all} nodes, i.e. actually this algorithm finds a
alpar@9	1660 minimal cost {\it circulation}. Due to this requirement the routine
alpar@9	1661 \verb\|glp_mincost_okalg\| converts the original network to a network
alpar@9	1662 suitable for the out-of-kilter algorithm in the following
alpar@9	1663 way:\footnote{The conversion is performed internally and does not change
alpar@9	1664 the original network program object passed to the routine.}
alpar@9	1665
alpar@9	1666 1) it adds two auxiliary nodes $s$ and $t$;
alpar@9	1667
alpar@9	1668 2) for each original node $i$ with $b_i>0$ the routine adds auxiliary
alpar@9	1669 supply arc $(s\rightarrow i)$, flow $x_{si}$ through which is costless
alpar@9	1670 ($c_{si}=0$) and fixed to $+b_i$ ($l_{si}=u_{si}=+b_i$);
alpar@9	1671
alpar@9	1672 3) for each original node $i$ with $b_i<0$ the routine adds auxiliary
alpar@9	1673 demand arc $(i\rightarrow t)$, flow $x_{it}$ through which is costless
alpar@9	1674 ($c_{it}=0$) and fixed to $-b_i$ ($l_{it}=u_{it}=-b_i$);
alpar@9	1675
alpar@9	1676 4) finally, the routine adds auxiliary feedback arc $(t\rightarrow s)$,
alpar@9	1677 flow $x_{ts}$ through which is also costless ($c_{ts}=0$) and fixed to
alpar@9	1678 $F$ ($l_{ts}=u_{ts}=F$), where $\displaystyle F=\sum_{b_i>0}b_i$ is the
alpar@9	1679 total supply.
alpar@9	1680
alpar@9	1681 \subsubsection*{Example}
alpar@9	1682
alpar@9	1683 The example program below reads the minimum cost problem instance in
alpar@9	1684 DIMACS format from file `\verb\|sample.min\|', solves it by using the
alpar@9	1685 routine \verb\|glp_mincost_okalg\|, and writes the solution found to the
alpar@9	1686 standard output.
alpar@9	1687
alpar@9	1688 \begin{footnotesize}
alpar@9	1689 \begin{verbatim}
alpar@9	1690 #include <stddef.h>
alpar@9	1691 #include <stdio.h>
alpar@9	1692 #include <stdlib.h>
alpar@9	1693 #include <glpk.h>
alpar@9	1694
alpar@9	1695 typedef struct { double rhs, pi; } v_data;
alpar@9	1696 typedef struct { double low, cap, cost, x; } a_data;
alpar@9	1697
alpar@9	1698 #define node(v) ((v_data *)((v)->data))
alpar@9	1699 #define arc(a) ((a_data *)((a)->data))
alpar@9	1700
alpar@9	1701 int main(void)
alpar@9	1702 { glp_graph *G;
alpar@9	1703 glp_vertex v, w;
alpar@9	1704 glp_arc *a;
alpar@9	1705 int i, ret;
alpar@9	1706 double sol;
alpar@9	1707 G = glp_create_graph(sizeof(v_data), sizeof(a_data));
alpar@9	1708 glp_read_mincost(G, offsetof(v_data, rhs),
alpar@9	1709 offsetof(a_data, low), offsetof(a_data, cap),
alpar@9	1710 offsetof(a_data, cost), "sample.min");
alpar@9	1711 ret = glp_mincost_okalg(G, offsetof(v_data, rhs),
alpar@9	1712 offsetof(a_data, low), offsetof(a_data, cap),
alpar@9	1713 offsetof(a_data, cost), &sol, offsetof(a_data, x),
alpar@9	1714 offsetof(v_data, pi));
alpar@9	1715 printf("ret = %d; sol = %5g\n", ret, sol);
alpar@9	1716 for (i = 1; i <= G->nv; i++)
alpar@9	1717 { v = G->v[i];
alpar@9	1718 printf("node %d: pi = %5g\n", i, node(v)->pi);
alpar@9	1719 for (a = v->out; a != NULL; a = a->t_next)
alpar@9	1720 { w = a->head;
alpar@9	1721 printf("arc %d->%d: x = %5g; lambda = %5g\n",
alpar@9	1722 v->i, w->i, arc(a)->x,
alpar@9	1723 arc(a)->cost - (node(v)->pi - node(w)->pi));
alpar@9	1724 }
alpar@9	1725 }
alpar@9	1726 glp_delete_graph(G);
alpar@9	1727 return 0;
alpar@9	1728 }
alpar@9	1729 \end{verbatim}
alpar@9	1730 \end{footnotesize}
alpar@9	1731
alpar@9	1732 If `\verb\|sample.min\|' is the example data file from the subsection
alpar@9	1733 describing the routine \verb\|glp_read_mincost\|, the output may look like
alpar@9	1734 follows:
alpar@9	1735
alpar@9	1736 \begin{footnotesize}
alpar@9	1737 \begin{verbatim}
alpar@9	1738 Reading min-cost flow problem data from `sample.min'...
alpar@9	1739 Flow network has 9 nodes and 14 arcs
alpar@9	1740 24 lines were read
alpar@9	1741 ret = 0; sol = 213
alpar@9	1742 node 1: pi = -12
alpar@9	1743 arc 1->4: x = 13; lambda = 0
alpar@9	1744 arc 1->2: x = 7; lambda = 0
alpar@9	1745 node 2: pi = -12
alpar@9	1746 arc 2->4: x = 0; lambda = 3
alpar@9	1747 arc 2->3: x = 7; lambda = 0
alpar@9	1748 node 3: pi = -14
alpar@9	1749 arc 3->8: x = 5; lambda = 0
alpar@9	1750 arc 3->5: x = 2; lambda = 3
alpar@9	1751 node 4: pi = -12
alpar@9	1752 arc 4->5: x = 13; lambda = 0
alpar@9	1753 node 5: pi = -12
alpar@9	1754 arc 5->7: x = 4; lambda = -1
alpar@9	1755 arc 5->6: x = 11; lambda = 0
alpar@9	1756 arc 5->2: x = 0; lambda = 1
alpar@9	1757 node 6: pi = -17
alpar@9	1758 arc 6->8: x = 4; lambda = 3
alpar@9	1759 arc 6->7: x = 7; lambda = -3
alpar@9	1760 node 7: pi = -20
alpar@9	1761 arc 7->9: x = 11; lambda = 0
alpar@9	1762 node 8: pi = -14
alpar@9	1763 arc 8->9: x = 9; lambda = 0
alpar@9	1764 node 9: pi = -23
alpar@9	1765 \end{verbatim}
alpar@9	1766 \end{footnotesize}
alpar@9	1767
alpar@9	1768 \subsection{glp\_netgen---Klingman's network problem generator}
alpar@9	1769
alpar@9	1770 \subsubsection*{Synopsis}
alpar@9	1771
alpar@9	1772 \begin{verbatim}
alpar@9	1773 int glp_netgen(glp_graph *G, int v_rhs, int a_cap, int a_cost,
alpar@9	1774 const int parm[1+15]);
alpar@9	1775 \end{verbatim}
alpar@9	1776
alpar@9	1777 \subsubsection*{Description}
alpar@9	1778
alpar@9	1779 The routine \verb\|glp_netgen\| is a GLPK version of the network problem
alpar@9	1780 generator developed by Dr.~Darwin~Klingman.\footnote{D.~Klingman,
alpar@9	1781 A.~Napier, and J.~Stutz. NETGEN: A program for generating large scale
alpar@9	1782 capacitated assignment, transportation, and minimum cost flow networks.
alpar@9	1783 Management Science 20 (1974), 814-20.} It can create capacitated and
alpar@9	1784 uncapacitated minimum cost flow (or transshipment), transportation, and
alpar@9	1785 assignment problems.
alpar@9	1786
alpar@9	1787 The parameter \verb\|G\| specifies the graph object, to which the
alpar@9	1788 generated problem data have to be stored. Note that on entry the graph
alpar@9	1789 object is erased with the routine \verb\|glp_erase_graph\|.
alpar@9	1790
alpar@9	1791 The parameter \verb\|v_rhs\| specifies an offset of the field of type
alpar@9	1792 \verb\|double\| in the vertex data block, to which the routine stores the
alpar@9	1793 supply or demand value. If \verb\|v_rhs\| $<0$, the value is not stored.
alpar@9	1794
alpar@9	1795 The parameter \verb\|a_cap\| specifies an offset of the field of type
alpar@9	1796 \verb\|double\| in the arc data block, to which the routine stores the
alpar@9	1797 arc capacity. If \verb\|a_cap\| $<0$, the capacity is not stored.
alpar@9	1798
alpar@9	1799 The parameter \verb\|a_cost\| specifies an offset of the field of type
alpar@9	1800 \verb\|double\| in the arc data block, to which the routine stores the
alpar@9	1801 per-unit cost if the arc flow. If \verb\|a_cost\| $<0$, the cost is not
alpar@9	1802 stored.
alpar@9	1803
alpar@9	1804 The array \verb\|parm\| contains description of the network to be
alpar@9	1805 generated:
alpar@9	1806
alpar@9	1807 \begin{tabular}{@{}lll@{}}
alpar@9	1808 \verb\|parm[0] \|& &not used\\
alpar@9	1809 \verb\|parm[1] \|&\verb\|iseed \|&8-digit positive random number seed\\
alpar@9	1810 \verb\|parm[2] \|&\verb\|nprob \|&8-digit problem id number\\
alpar@9	1811 \verb\|parm[3] \|&\verb\|nodes \|&total number of nodes\\
alpar@9	1812 \verb\|parm[4] \|&\verb\|nsorc \|&total number of source nodes\\
alpar@9	1813 &&(including transshipment nodes)\\
alpar@9	1814 \verb\|parm[5] \|&\verb\|nsink \|&total number of sink nodes\\
alpar@9	1815 &&(including transshipment nodes)\\
alpar@9	1816 \verb\|parm[6] \|&\verb\|iarcs \|&number of arc\\
alpar@9	1817 \verb\|parm[7] \|&\verb\|mincst\|&minimum cost for arcs\\
alpar@9	1818 \verb\|parm[8] \|&\verb\|maxcst\|&maximum cost for arcs\\
alpar@9	1819 \verb\|parm[9] \|&\verb\|itsup \|&total supply\\
alpar@9	1820 \end{tabular}
alpar@9	1821
alpar@9	1822 \begin{tabular}{@{}lll@{}}
alpar@9	1823 \verb\|parm[10]\|&\verb\|ntsorc\|&number of transshipment source nodes\\
alpar@9	1824 \verb\|parm[11]\|&\verb\|ntsink\|&number of transshipment sink nodes\\
alpar@9	1825 \verb\|parm[12]\|&\verb\|iphic \|&percentage of skeleton arcs to be given
alpar@9	1826 the maxi-\\&&mum cost\\
alpar@9	1827 \verb\|parm[13]\|&\verb\|ipcap \|&percentage of arcs to be capacitated\\
alpar@9	1828 \verb\|parm[14]\|&\verb\|mincap\|&minimum upper bound for capacitated arcs\\
alpar@9	1829 \verb\|parm[15]\|&\verb\|maxcap\|&maximum upper bound for capacitated arcs\\
alpar@9	1830 \end{tabular}
alpar@9	1831
alpar@9	1832 \subsubsection*{Notes}
alpar@9	1833
alpar@9	1834 \noindent\indent
alpar@9	1835 1. The routine generates a transportation problem if:
alpar@9	1836 $${\tt nsorc}+{\tt nsink}={\tt nodes},
alpar@9	1837 \ {\tt ntsorc}=0,\ \mbox{and}\ {\tt ntsink}=0.$$
alpar@9	1838
alpar@9	1839 2. The routine generates an assignment problem if the requirements for
alpar@9	1840 a transportation problem are met and:
alpar@9	1841 $${\tt nsorc}={\tt nsink}\ \mbox{and}\ {\tt itsup}={\tt nsorc}.$$
alpar@9	1842
alpar@9	1843 3. The routine always generates connected graphs. So, if the number of
alpar@9	1844 requested arcs has been reached and the generated instance is not fully
alpar@9	1845 connected, the routine generates a few remaining arcs to ensure
alpar@9	1846 connectedness. Thus, the actual number of arcs generated by the routine
alpar@9	1847 may be greater than the requested number of arcs.
alpar@9	1848
alpar@9	1849 \subsubsection*{Returns}
alpar@9	1850
alpar@9	1851 If the instance was successfully generated, the routine
alpar@9	1852 \verb\|glp_netgen\| returns zero; otherwise, if specified parameters are
alpar@9	1853 inconsistent, the routine returns a non-zero error code.
alpar@9	1854
alpar@9	1855 \subsection{glp\_gridgen---grid-like network problem generator}
alpar@9	1856
alpar@9	1857 \subsubsection*{Synopsis}
alpar@9	1858
alpar@9	1859 \begin{verbatim}
alpar@9	1860 int glp_gridgen(glp_graph *G, int v_rhs, int a_cap, int a_cost,
alpar@9	1861 const int parm[1+14]);
alpar@9	1862 \end{verbatim}
alpar@9	1863
alpar@9	1864 \subsubsection*{Description}
alpar@9	1865
alpar@9	1866 The routine \verb\|glp_gridgen\| is a GLPK version of the grid-like
alpar@9	1867 network problem generator developed by Yusin Lee and Jim
alpar@9	1868 Orlin.\footnote{Y.~Lee and J.~Orlin. GRIDGEN generator., 1991. The
alpar@9	1869 original code is publically available from
alpar@9	1870 {\tt<ftp://dimacs.rutgers.edu/pub/netflow/generators/network/gridgen>}.}
alpar@9	1871
alpar@9	1872 The parameter \verb\|G\| specifies the graph object, to which the
alpar@9	1873 generated problem data have to be stored. Note that on entry the graph
alpar@9	1874 object is erased with the routine \verb\|glp_erase_graph\|.
alpar@9	1875
alpar@9	1876 The parameter \verb\|v_rhs\| specifies an offset of the field of type
alpar@9	1877 \verb\|double\| in the vertex data block, to which the routine stores the
alpar@9	1878 supply or demand value. If \verb\|v_rhs\| $<0$, the value is not stored.
alpar@9	1879
alpar@9	1880 The parameter \verb\|a_cap\| specifies an offset of the field of type
alpar@9	1881 \verb\|double\| in the arc data block, to which the routine stores the
alpar@9	1882 arc capacity. If \verb\|a_cap\| $<0$, the capacity is not stored.
alpar@9	1883
alpar@9	1884 The parameter \verb\|a_cost\| specifies an offset of the field of type
alpar@9	1885 \verb\|double\| in the arc data block, to which the routine stores the
alpar@9	1886 per-unit cost if the arc flow. If \verb\|a_cost\| $<0$, the cost is not
alpar@9	1887 stored.
alpar@9	1888
alpar@9	1889 The array \verb\|parm\| contains parameters of the network to be
alpar@9	1890 generated:
alpar@9	1891
alpar@9	1892 \begin{tabular}{@{}ll@{}}
alpar@9	1893 \verb\|parm[0] \|&not used\\
alpar@9	1894 \verb\|parm[1] \|&two-ways arcs indicator:\\
alpar@9	1895 &1 --- if links in both direction should be generated\\
alpar@9	1896 &0 --- otherwise\\
alpar@9	1897 \verb\|parm[2] \|&random number seed (a positive integer)\\
alpar@9	1898 \verb\|parm[3] \|&number of nodes (the number of nodes generated might
alpar@9	1899 be\\&slightly different to make the network a grid)\\
alpar@9	1900 \verb\|parm[4] \|&grid width\\
alpar@9	1901 \verb\|parm[5] \|&number of sources\\
alpar@9	1902 \verb\|parm[6] \|&number of sinks\\
alpar@9	1903 \verb\|parm[7] \|&average degree\\
alpar@9	1904 \verb\|parm[8] \|&total flow\\
alpar@9	1905 \verb\|parm[9] \|&distribution of arc costs:\\
alpar@9	1906 &1 --- uniform\\
alpar@9	1907 &2 --- exponential\\
alpar@9	1908 \verb\|parm[10]\|&lower bound for arc cost (uniform)\\
alpar@9	1909 &$100\lambda$ (exponential)\\
alpar@9	1910 \verb\|parm[11]\|&upper bound for arc cost (uniform)\\
alpar@9	1911 &not used (exponential)\\
alpar@9	1912 \verb\|parm[12]\|&distribution of arc capacities:\\
alpar@9	1913 &1 --- uniform\\
alpar@9	1914 &2 --- exponential\\
alpar@9	1915 \verb\|parm[13]\|&lower bound for arc capacity (uniform)\\
alpar@9	1916 &$100\lambda$ (exponential)\\
alpar@9	1917 \verb\|parm[14]\|&upper bound for arc capacity (uniform)\\
alpar@9	1918 &not used (exponential)\\
alpar@9	1919 \end{tabular}
alpar@9	1920
alpar@9	1921 \subsubsection*{Returns}
alpar@9	1922
alpar@9	1923 If the instance was successfully generated, the routine
alpar@9	1924 \verb\|glp_gridgen\| returns zero; otherwise, if specified parameters are
alpar@9	1925 inconsistent, the routine returns a non-zero error code.
alpar@9	1926
alpar@9	1927 \subsubsection*{Comments\footnote{This material is based on comments
alpar@9	1928 to the original version of GRIDGEN.}}
alpar@9	1929
alpar@9	1930 This network generator generates a grid-like network plus a super node.
alpar@9	1931 In additional to the arcs connecting the nodes in the grid, there is an
alpar@9	1932 arc from each supply node to the super node and from the super node to
alpar@9	1933 each demand node to guarantee feasiblity. These arcs have very high
alpar@9	1934 costs and very big capacities.
alpar@9	1935
alpar@9	1936 The idea of this network generator is as follows: First, a grid of
alpar@9	1937 $n_1\times n_2$ is generated. For example, $5\times 3$. The nodes are
alpar@9	1938 numbered as 1 to 15, and the supernode is numbered as $n_1\times n_2+1$.
alpar@9	1939 Then arcs between adjacent nodes are generated. For these arcs, the user
alpar@9	1940 is allowed to specify either to generate two-way arcs or one-way arcs.
alpar@9	1941 If two-way arcs are to be generated, two arcs, one in each direction,
alpar@9	1942 will be generated between each adjacent node pairs. Otherwise, only one
alpar@9	1943 arc will be generated. If this is the case, the arcs will be generated
alpar@9	1944 in alterntive directions as shown below.
alpar@9	1945
alpar@9	1946 \bigskip
alpar@9	1947
alpar@9	1948 \noindent\hfil
alpar@9	1949 \xymatrix
alpar@9	1950 {1\ar[r]\ar[d]&2\ar[r]&3\ar[r]\ar[d]&4\ar[r]&5\ar[d]\\
alpar@9	1951 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	1952 11\ar[r]&12\ar[r]\ar[u]&13\ar[r]&14\ar[r]\ar[u]&15\\
alpar@9	1953 }
alpar@9	1954
alpar@9	1955 \bigskip
alpar@9	1956
alpar@9	1957 Then the arcs between the super node and the source/sink nodes are added
alpar@9	1958 as mentioned before. If the number of arcs still doesn't reach the
alpar@9	1959 requirement, additional arcs will be added by uniformly picking random
alpar@9	1960 node pairs. There is no checking to prevent multiple arcs between any
alpar@9	1961 pair of nodes. However, there will be no self-arcs (arcs that poins back
alpar@9	1962 to its tail node) in the network.
alpar@9	1963
alpar@9	1964 The source and sink nodes are selected uniformly in the network, and
alpar@9	1965 the imbalances of each source/sink node are also assigned by uniform
alpar@9	1966 distribution.
alpar@9	1967
alpar@9	1968 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9	1969
alpar@9	1970 \newpage
alpar@9	1971
alpar@9	1972 \section{Maximum flow problem}
alpar@9	1973
alpar@9	1974 \subsection{Background}
alpar@9	1975
alpar@9	1976 The {\it maximum flow problem} (MAXFLOW) is stated as follows. Let
alpar@9	1977 there be given a directed graph (flow network) $G=(V,A)$, where $V$ is
alpar@9	1978 a set of vertices (nodes), and $A\subseteq V\times V$ is a set of arcs.
alpar@9	1979 Let also for each arc $a=(i,j)\in A$ there be given its capacity
alpar@9	1980 $u_{ij}$. The problem is, for given {\it source} node $s\in V$ and
alpar@9	1981 {\it sink} node $t\in V$, to find flows $x_{ij}$ through every arc of
alpar@9	1982 the network, which satisfy the specified arc capacities and the
alpar@9	1983 conservation constraints at all nodes, and maximize the total flow $F$
alpar@9	1984 through the network from $s$ to $t$. Here the conservation constraint
alpar@9	1985 at a node means that the total flow entering this node through its
alpar@9	1986 incoming arcs (plus $F$, if it is the source node) must be equal to the
alpar@9	1987 total flow leaving this node through its outgoing arcs (plus $F$, if it
alpar@9	1988 is the sink node).
alpar@9	1989
alpar@9	1990 An example of the maximum flow problem, where $s=v_1$ and $t=v_9$, is
alpar@9	1991 shown on Fig.~2.
alpar@9	1992
alpar@9	1993 \bigskip
alpar@9	1994
alpar@9	1995 \noindent\hfil
alpar@9	1996 \xymatrix @C=48pt
alpar@9	1997 {_{F}\ar@{~>}[d]&
alpar@9	1998 v_2\ar[r]\|{_{10}}\ar[dd]\|{_{9}}&
alpar@9	1999 v_3\ar[dd]\|{_{12}}\ar[r]\|{_{18}}&
alpar@9	2000 v_8\ar[rd]\|{_{20}}&\\
alpar@9	2001 v_1\ar[ru]\|{_{14}}\ar[rd]\|{_{23}}&&&
alpar@9	2002 v_6\ar[d]\|{_{7}}\ar[u]\|{_{8}}&
alpar@9	2003 v_9\ar@{~>}[d]\\
alpar@9	2004 &v_4\ar[r]\|{_{26}}&
alpar@9	2005 v_5\ar[luu]\|{_{11}}\ar[ru]\|{_{25}}\ar[r]\|{_{4}}&
alpar@9	2006 v_7\ar[ru]\|{_{15}}&_{F}\\
alpar@9	2007 }
alpar@9	2008
alpar@9	2009 \bigskip
alpar@9	2010
alpar@9	2011 \noindent\hfil
alpar@9	2012 Fig.~2. An example of the maximum flow problem.
alpar@9	2013
alpar@9	2014 \bigskip
alpar@9	2015
alpar@9	2016 The maximum flow problem can be naturally formulated as the following
alpar@9	2017 LP problem:
alpar@9	2018
alpar@9	2019 \medskip
alpar@9	2020
alpar@9	2021 \noindent
alpar@9	2022 \hspace{.5in}maximize
alpar@9	2023 $$F\eqno(4)$$
alpar@9	2024 \hspace{.5in}subject to
alpar@9	2025 $$\sum_{(i,j)\in A}x_{ij}-\sum_{(j,i)\in A}x_{ji}=\left\{
alpar@9	2026 \begin{array}{@{\ }rl}
alpar@9	2027 +F,&\hbox{for}\ i=s\\
alpar@9	2028 0,&\hbox{for all}\ i\in V\backslash\{s,t\}\\
alpar@9	2029 -F,&\hbox{for}\ i=t\\
alpar@9	2030 \end{array}
alpar@9	2031 \right.\eqno(5)
alpar@9	2032 $$
alpar@9	2033 $$0\leq x_{ij}\leq u_{ij}\ \ \ \hbox{for all}\ (i,j)\in A
alpar@9	2034 \eqno(6)$$
alpar@9	2035
alpar@9	2036 \medskip
alpar@9	2037
alpar@9	2038 \noindent
alpar@9	2039 where $F\geq 0$ is an additional variable playing the role of the
alpar@9	2040 objective.
alpar@9	2041
alpar@9	2042 \newpage
alpar@9	2043
alpar@9	2044 Another LP formulation of the maximum flow problem, which does not
alpar@9	2045 include the variable $F$, is the following:
alpar@9	2046
alpar@9	2047 \medskip
alpar@9	2048
alpar@9	2049 \noindent
alpar@9	2050 \hspace{.5in}maximize
alpar@9	2051 $$z=\sum_{(s,j)\in A}x_{sj}-\sum_{(j,s)\in A}x_{js}\ (=F)\eqno(7)$$
alpar@9	2052 \hspace{.5in}subject to
alpar@9	2053 $$\sum_{(i,j)\in A}x_{ij}-\sum_{(j,i)\in A}x_{ji}\left\{
alpar@9	2054 \begin{array}{@{\ }rl}
alpar@9	2055 \geq 0,&\hbox{for}\ i=s\\
alpar@9	2056 =0,&\hbox{for all}\ i\in V\backslash\{s,t\}\\
alpar@9	2057 \leq 0,&\hbox{for}\ i=t\\
alpar@9	2058 \end{array}
alpar@9	2059 \right.\eqno(8)
alpar@9	2060 $$
alpar@9	2061 $$0\leq x_{ij}\leq u_{ij}\ \ \ \hbox{for all}\ (i,j)\in A
alpar@9	2062 \eqno(9)$$
alpar@9	2063
alpar@9	2064 \subsection{glp\_read\_maxflow---read maximum flow problem data\\in
alpar@9	2065 DIMACS format}
alpar@9	2066
alpar@9	2067 \subsubsection*{Synopsis}
alpar@9	2068
alpar@9	2069 \begin{verbatim}
alpar@9	2070 int glp_read_maxflow(glp_graph G, int s, int *t, int a_cap,
alpar@9	2071 const char *fname);
alpar@9	2072 \end{verbatim}
alpar@9	2073
alpar@9	2074 \subsubsection*{Description}
alpar@9	2075
alpar@9	2076 The routine \verb\|glp_read_maxflow\| reads the maximum flow problem
alpar@9	2077 data from a text file in DIMACS format.
alpar@9	2078
alpar@9	2079 The parameter \verb\|G\| specifies the graph object, to which the problem
alpar@9	2080 data have to be stored. Note that before reading data the current
alpar@9	2081 content of the graph object is completely erased with the routine
alpar@9	2082 \verb\|glp_erase_graph\|.
alpar@9	2083
alpar@9	2084 The pointer \verb\|s\| specifies a location, to which the routine stores
alpar@9	2085 the ordinal number of the source node. If \verb\|s\| is \verb\|NULL\|, the
alpar@9	2086 source node number is not stored.
alpar@9	2087
alpar@9	2088 The pointer \verb\|t\| specifies a location, to which the routine stores
alpar@9	2089 the ordinal number of the sink node. If \verb\|t\| is \verb\|NULL\|, the
alpar@9	2090 sink node number is not stored.
alpar@9	2091
alpar@9	2092 The parameter \verb\|a_cap\| specifies an offset of the field of type
alpar@9	2093 \verb\|double\| in the arc data block, to which the routine stores
alpar@9	2094 $u_{ij}$, the arc capacity. If \verb\|a_cap\| $<0$, the arc capacity is
alpar@9	2095 not stored.
alpar@9	2096
alpar@9	2097 The character string \verb\|fname\| specifies the name of a text file to
alpar@9	2098 be read in. (If the file name name ends with the suffix `\verb\|.gz\|',
alpar@9	2099 the file is assumed to be compressed, in which case the routine
alpar@9	2100 decompresses it ``on the fly''.)
alpar@9	2101
alpar@9	2102 \subsubsection*{Returns}
alpar@9	2103
alpar@9	2104 If the operation was successful, the routine returns zero. Otherwise,
alpar@9	2105 it prints an error message and returns non-zero.
alpar@9	2106
alpar@9	2107 \subsubsection*{Example}
alpar@9	2108
alpar@9	2109 \begin{footnotesize}
alpar@9	2110 \begin{verbatim}
alpar@9	2111 typedef struct
alpar@9	2112 { /* arc data block */
alpar@9	2113 ...
alpar@9	2114 double cap;
alpar@9	2115 ...
alpar@9	2116 } a_data;
alpar@9	2117
alpar@9	2118 int main(void)
alpar@9	2119 { glp_graph *G;
alpar@9	2120 int s, t, ret;
alpar@9	2121 G = glp_create_graph(..., sizeof(a_data));
alpar@9	2122 ret = glp_read_maxflow(G, &s, &t, offsetof(a_data, cap),
alpar@9	2123 "sample.max");
alpar@9	2124 if (ret != 0) goto ...
alpar@9	2125 ...
alpar@9	2126 }
alpar@9	2127 \end{verbatim}
alpar@9	2128 \end{footnotesize}
alpar@9	2129
alpar@9	2130 \subsubsection*{DIMACS maximum flow problem format\footnote{This
alpar@9	2131 material is based on the paper ``The First DIMACS International
alpar@9	2132 Algorithm Implementation Challenge: Problem Definitions and
alpar@9	2133 Specifications'', which is publically available at
alpar@9	2134 {\tt http://dimacs.rutgers.edu/Challenges/}.}}
alpar@9	2135 \label{subsecmaxflow}
alpar@9	2136
alpar@9	2137 The DIMACS input file is a plain ASCII text file. It contains
alpar@9	2138 {\it lines} of several types described below. A line is terminated with
alpar@9	2139 an end-of-line character. Fields in each line are separated by at least
alpar@9	2140 one blank space. Each line begins with a one-character designator to
alpar@9	2141 identify the line type.
alpar@9	2142
alpar@9	2143 Note that DIMACS requires all numerical quantities to be integers in
alpar@9	2144 the range $[-2^{31},\ 2^{31}-1]$ while GLPK allows the quantities to be
alpar@9	2145 floating-point numbers.
alpar@9	2146
alpar@9	2147 \paragraph{Comment lines.} Comment lines give human-readable information
alpar@9	2148 about the file and are ignored by programs. Comment lines can appear
alpar@9	2149 anywhere in the file. Each comment line begins with a lower-case
alpar@9	2150 character \verb\|c\|.
alpar@9	2151
alpar@9	2152 \begin{verbatim}
alpar@9	2153 c This is a comment line
alpar@9	2154 \end{verbatim}
alpar@9	2155
alpar@9	2156 \newpage
alpar@9	2157
alpar@9	2158 \paragraph{Problem line.} There is one problem line per data file. The
alpar@9	2159 problem line must appear before any node or arc descriptor lines. It has
alpar@9	2160 the following format:
alpar@9	2161
alpar@9	2162 \begin{verbatim}
alpar@9	2163 p max NODES ARCS
alpar@9	2164 \end{verbatim}
alpar@9	2165
alpar@9	2166 \noindent
alpar@9	2167 The lower-case character \verb\|p\| signifies that this is a problem line.
alpar@9	2168 The three-character problem designator \verb\|max\| identifies the file as
alpar@9	2169 containing specification information for the maximum flow problem. The
alpar@9	2170 \verb\|NODES\| field contains an integer value specifying the number of
alpar@9	2171 nodes in the network. The \verb\|ARCS\| field contains an integer value
alpar@9	2172 specifying the number of arcs in the network.
alpar@9	2173
alpar@9	2174 \paragraph{Node descriptors.} Two node descriptor lines for the source
alpar@9	2175 and sink nodes must appear before all arc descriptor lines. They may
alpar@9	2176 appear in either order, each with the following format:
alpar@9	2177
alpar@9	2178 \begin{verbatim}
alpar@9	2179 n ID WHICH
alpar@9	2180 \end{verbatim}
alpar@9	2181
alpar@9	2182 \noindent
alpar@9	2183 The lower-case character \verb\|n\| signifies that this a node descriptor
alpar@9	2184 line. The \verb\|ID\| field gives a node identification number, an integer
alpar@9	2185 between 1 and \verb\|NODES\|. The \verb\|WHICH\| field gives either a
alpar@9	2186 lower-case \verb\|s\| or \verb\|t\|, designating the source and sink,
alpar@9	2187 respectively.
alpar@9	2188
alpar@9	2189 \paragraph{Arc descriptors.} There is one arc descriptor line for each
alpar@9	2190 arc in the network. Arc descriptor lines are of the following format:
alpar@9	2191
alpar@9	2192 \begin{verbatim}
alpar@9	2193 a SRC DST CAP
alpar@9	2194 \end{verbatim}
alpar@9	2195
alpar@9	2196 \noindent
alpar@9	2197 The lower-case character \verb\|a\| signifies that this is an arc
alpar@9	2198 descriptor line. For a directed arc $(i,j)$ the \verb\|SRC\| field gives
alpar@9	2199 the identification number $i$ for the tail endpoint, and the \verb\|DST\|
alpar@9	2200 field gives the identification number $j$ for the head endpoint.
alpar@9	2201 Identification numbers are integers between 1 and \verb\|NODES\|. The
alpar@9	2202 \verb\|CAP\| field gives the arc capacity, i.e. maximum amount of flow
alpar@9	2203 that can be sent along arc $(i,j)$ in a feasible flow.
alpar@9	2204
alpar@9	2205 \paragraph{Example.} Below here is an example of the data file in
alpar@9	2206 DIMACS format corresponding to the maximum flow problem shown on Fig~2.
alpar@9	2207
alpar@9	2208 \newpage
alpar@9	2209
alpar@9	2210 \begin{footnotesize}
alpar@9	2211 \begin{verbatim}
alpar@9	2212 c sample.max
alpar@9	2213 c
alpar@9	2214 c This is an example of the maximum flow problem data
alpar@9	2215 c in DIMACS format.
alpar@9	2216 c
alpar@9	2217 p max 9 14
alpar@9	2218 c
alpar@9	2219 n 1 s
alpar@9	2220 n 9 t
alpar@9	2221 c
alpar@9	2222 a 1 2 14
alpar@9	2223 a 1 4 23
alpar@9	2224 a 2 3 10
alpar@9	2225 a 2 4 9
alpar@9	2226 a 3 5 12
alpar@9	2227 a 3 8 18
alpar@9	2228 a 4 5 26
alpar@9	2229 a 5 2 11
alpar@9	2230 a 5 6 25
alpar@9	2231 a 5 7 4
alpar@9	2232 a 6 7 7
alpar@9	2233 a 6 8 8
alpar@9	2234 a 7 9 15
alpar@9	2235 a 8 9 20
alpar@9	2236 c
alpar@9	2237 c eof
alpar@9	2238 \end{verbatim}
alpar@9	2239 \end{footnotesize}
alpar@9	2240
alpar@9	2241 \subsection{glp\_write\_maxflow---write maximum flow problem data\\
alpar@9	2242 in DIMACS format}
alpar@9	2243
alpar@9	2244 \subsubsection*{Synopsis}
alpar@9	2245
alpar@9	2246 \begin{verbatim}
alpar@9	2247 int glp_write_maxflow(glp_graph *G, int s, int t, int a_cap,
alpar@9	2248 const char *fname);
alpar@9	2249 \end{verbatim}
alpar@9	2250
alpar@9	2251 \subsubsection*{Description}
alpar@9	2252
alpar@9	2253 The routine \verb\|glp_write_maxflow\| writes the maximum flow problem
alpar@9	2254 data to a text file in DIMACS format.
alpar@9	2255
alpar@9	2256 The parameter \verb\|G\| is the graph (network) program object, which
alpar@9	2257 specifies the maximum flow problem instance.
alpar@9	2258
alpar@9	2259 The parameter \verb\|s\| specifies the ordinal number of the source node.
alpar@9	2260
alpar@9	2261 The parameter \verb\|t\| specifies the ordinal number of the sink node.
alpar@9	2262
alpar@9	2263 The parameter \verb\|a_cap\| specifies an offset of the field of type
alpar@9	2264 \verb\|double\| in the arc data block, which contains $u_{ij}$, the upper
alpar@9	2265 bound to the arc flow (the arc capacity). If the upper bound is
alpar@9	2266 specified as \verb\|DBL_MAX\|, it is assumed that $u_{ij}=\infty$, i.e.
alpar@9	2267 the arc is uncapacitated. If \verb\|a_cap\| $<0$, it is assumed that
alpar@9	2268 $u_{ij}=1$ for all arcs.
alpar@9	2269
alpar@9	2270 The character string \verb\|fname\| specifies a name of the text file to
alpar@9	2271 be written out. (If the file name ends with suffix `\verb\|.gz\|', the
alpar@9	2272 file is assumed to be compressed, in which case the routine performs
alpar@9	2273 automatic compression on writing it.)
alpar@9	2274
alpar@9	2275 \subsubsection*{Returns}
alpar@9	2276
alpar@9	2277 If the operation was successful, the routine returns zero. Otherwise,
alpar@9	2278 it prints an error message and returns non-zero.
alpar@9	2279
alpar@9	2280 \subsection{glp\_maxflow\_lp---convert maximum flow problem to LP}
alpar@9	2281
alpar@9	2282 \subsubsection*{Synopsis}
alpar@9	2283
alpar@9	2284 \begin{verbatim}
alpar@9	2285 void glp_maxflow_lp(glp_prob lp, glp_graph G, int names,
alpar@9	2286 int s, int t, int a_cap);
alpar@9	2287 \end{verbatim}
alpar@9	2288
alpar@9	2289 \subsubsection*{Description}
alpar@9	2290
alpar@9	2291 The routine \verb\|glp_maxflow_lp\| builds LP problem (7)---(9), which
alpar@9	2292 corresponds to the specified maximum flow problem.
alpar@9	2293
alpar@9	2294 The parameter \verb\|lp\| is the resultant LP problem object to be built.
alpar@9	2295 Note that on entry its current content is erased with the routine
alpar@9	2296 \verb\|glp_erase_prob\|.
alpar@9	2297
alpar@9	2298 The parameter \verb\|G\| is the graph (network) program object, which
alpar@9	2299 specifies the maximum flow problem instance.
alpar@9	2300
alpar@9	2301 The parameter \verb\|names\| is a flag. If it is \verb\|GLP_ON\|, the
alpar@9	2302 routine uses symbolic names of the graph object components to assign
alpar@9	2303 symbolic names to the LP problem object components. If the flag is
alpar@9	2304 \verb\|GLP_OFF\|, no symbolic names are assigned.
alpar@9	2305
alpar@9	2306 The parameter \verb\|s\| specifies the ordinal number of the source node.
alpar@9	2307
alpar@9	2308 The parameter \verb\|t\| specifies the ordinal number of the sink node.
alpar@9	2309
alpar@9	2310 The parameter \verb\|a_cap\| specifies an offset of the field of type
alpar@9	2311 \verb\|double\| in the arc data block, which contains $u_{ij}$, the upper
alpar@9	2312 bound to the arc flow (the arc capacity). If the upper bound is
alpar@9	2313 specified as \verb\|DBL_MAX\|, it is assumed that $u_{ij}=\infty$, i.e.
alpar@9	2314 the arc is uncapacitated. If \verb\|a_cap\| $<0$, it is assumed that
alpar@9	2315 $u_{ij}=1$ for all arcs.
alpar@9	2316
alpar@9	2317 \subsubsection*{Example}
alpar@9	2318
alpar@9	2319 The example program below reads the maximum flow problem in DIMACS
alpar@9	2320 format from file `\verb\|sample.max\|', converts the instance to LP, and
alpar@9	2321 then writes the resultant LP in CPLEX format to file
alpar@9	2322 `\verb\|maxflow.lp\|'.
alpar@9	2323
alpar@9	2324 \begin{footnotesize}
alpar@9	2325 \begin{verbatim}
alpar@9	2326 #include <stddef.h>
alpar@9	2327 #include <glpk.h>
alpar@9	2328
alpar@9	2329 int main(void)
alpar@9	2330 { glp_graph *G;
alpar@9	2331 glp_prob *lp;
alpar@9	2332 int s, t;
alpar@9	2333 G = glp_create_graph(0, sizeof(double));
alpar@9	2334 glp_read_maxflow(G, &s, &t, 0, "sample.max");
alpar@9	2335 lp = glp_create_prob();
alpar@9	2336 glp_maxflow_lp(lp, G, GLP_ON, s, t, 0);
alpar@9	2337 glp_delete_graph(G);
alpar@9	2338 glp_write_lp(lp, NULL, "maxflow.lp");
alpar@9	2339 glp_delete_prob(lp);
alpar@9	2340 return 0;
alpar@9	2341 }
alpar@9	2342 \end{verbatim}
alpar@9	2343 \end{footnotesize}
alpar@9	2344
alpar@9	2345 If `\verb\|sample.max\|' is the example data file from the previous
alpar@9	2346 subsection, the output `\verb\|maxflow.lp\|' may look like follows:
alpar@9	2347
alpar@9	2348 \begin{footnotesize}
alpar@9	2349 \begin{verbatim}
alpar@9	2350 Maximize
alpar@9	2351 obj: + x(1,4) + x(1,2)
alpar@9	2352
alpar@9	2353 Subject To
alpar@9	2354 r_1: + x(1,2) + x(1,4) >= 0
alpar@9	2355 r_2: - x(5,2) + x(2,3) + x(2,4) - x(1,2) = 0
alpar@9	2356 r_3: + x(3,5) + x(3,8) - x(2,3) = 0
alpar@9	2357 r_4: + x(4,5) - x(2,4) - x(1,4) = 0
alpar@9	2358 r_5: + x(5,2) + x(5,6) + x(5,7) - x(4,5) - x(3,5) = 0
alpar@9	2359 r_6: + x(6,7) + x(6,8) - x(5,6) = 0
alpar@9	2360 r_7: + x(7,9) - x(6,7) - x(5,7) = 0
alpar@9	2361 r_8: + x(8,9) - x(6,8) - x(3,8) = 0
alpar@9	2362 r_9: - x(8,9) - x(7,9) <= 0
alpar@9	2363
alpar@9	2364 Bounds
alpar@9	2365 0 <= x(1,4) <= 23
alpar@9	2366 0 <= x(1,2) <= 14
alpar@9	2367 0 <= x(2,4) <= 9
alpar@9	2368 0 <= x(2,3) <= 10
alpar@9	2369 0 <= x(3,8) <= 18
alpar@9	2370 0 <= x(3,5) <= 12
alpar@9	2371 0 <= x(4,5) <= 26
alpar@9	2372 0 <= x(5,7) <= 4
alpar@9	2373 0 <= x(5,6) <= 25
alpar@9	2374 0 <= x(5,2) <= 11
alpar@9	2375 0 <= x(6,8) <= 8
alpar@9	2376 0 <= x(6,7) <= 7
alpar@9	2377 0 <= x(7,9) <= 15
alpar@9	2378 0 <= x(8,9) <= 20
alpar@9	2379
alpar@9	2380 End
alpar@9	2381 \end{verbatim}
alpar@9	2382 \end{footnotesize}
alpar@9	2383
alpar@9	2384 \subsection{glp\_maxflow\_ffalg---solve maximum flow problem with
alpar@9	2385 Ford-Fulkerson algorithm}
alpar@9	2386
alpar@9	2387 \subsubsection*{Synopsis}
alpar@9	2388
alpar@9	2389 \begin{verbatim}
alpar@9	2390 int glp_maxflow_ffalg(glp_graph *G, int s, int t, int a_cap,
alpar@9	2391 double *sol, int a_x, int v_cut);
alpar@9	2392 \end{verbatim}
alpar@9	2393
alpar@9	2394 \subsubsection*{Description}
alpar@9	2395
alpar@9	2396 The routine \verb\|glp_mincost_ffalg\| finds optimal solution to the
alpar@9	2397 maximum flow problem with the Ford-Fulkerson algorithm.\footnote{GLPK
alpar@9	2398 implementation of the Ford-Fulkerson algorithm is based on the following
alpar@9	2399 book: L.~R.~Ford,~Jr., and D.~R.~Fulkerson, ``Flows in Networks,'' The
alpar@9	2400 RAND Corp., Report\linebreak R-375-PR (August 1962), Chap. I
alpar@9	2401 ``Static Maximal Flow,'' pp.~30-33.} Note that this routine requires all
alpar@9	2402 the problem data to be integer-valued.
alpar@9	2403
alpar@9	2404 The parameter \verb\|G\| is a graph (network) program object which
alpar@9	2405 specifies the maximum flow problem instance to be solved.
alpar@9	2406
alpar@9	2407 The parameter $s$ specifies the ordinal number of the source node.
alpar@9	2408
alpar@9	2409 The parameter $t$ specifies the ordinal number of the sink node.
alpar@9	2410
alpar@9	2411 The parameter \verb\|a_cap\| specifies an offset of the field of type
alpar@9	2412 \verb\|double\| in the arc data block, which contains $u_{ij}$, the upper
alpar@9	2413 bound to the arc flow (the arc capacity). This bound must be integer in
alpar@9	2414 the range [0, \verb\|INT_MAX\|]. If \verb\|a_cap\| $<0$, it is assumed that
alpar@9	2415 $u_{ij}=1$ for all arcs.
alpar@9	2416
alpar@9	2417 The parameter \verb\|sol\| specifies a location, to which the routine
alpar@9	2418 stores the objective value (that is, the total flow from $s$ to $t$)
alpar@9	2419 found. If \verb\|sol\| is NULL, the objective value is not stored.
alpar@9	2420
alpar@9	2421 The parameter \verb\|a_x\| specifies an offset of the field of type
alpar@9	2422 \verb\|double\| in the arc data block, to which the routine stores
alpar@9	2423 $x_{ij}$, the arc flow found. If \verb\|a_x\| $<0$, the arc flow values
alpar@9	2424 are not stored.
alpar@9	2425
alpar@9	2426 The parameter \verb\|v_cut\| specifies an offset of the field of type
alpar@9	2427 \verb\|int\| in the vertex data block, to which the routine stores node
alpar@9	2428 flags corresponding to the optimal solution found: if the node flag is
alpar@9	2429 1, the node is labelled, and if the node flag is 0, the node is
alpar@9	2430 unlabelled. The calling program may use these node flags to determine
alpar@9	2431 the {\it minimal cut}, which is a subset of arcs whose one endpoint is
alpar@9	2432 labelled and other is not. If \verb\|v_cut\| $<0$, the node flags are not
alpar@9	2433 stored.
alpar@9	2434
alpar@9	2435 Note that all solution components (the objective value and arc flows)
alpar@9	2436 computed by the routine are always integer-valued.
alpar@9	2437
alpar@9	2438 \subsubsection*{Returns}
alpar@9	2439
alpar@9	2440 \def\arraystretch{1}
alpar@9	2441
alpar@9	2442 \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
alpar@9	2443 0 & Optimal solution found.\\
alpar@9	2444 \verb\|GLP_EDATA\| & Unable to start the search, because some problem
alpar@9	2445 data are either not integer-valued or out of range.\\
alpar@9	2446 \end{tabular}
alpar@9	2447
alpar@9	2448 \subsubsection*{Example}
alpar@9	2449
alpar@9	2450 The example program shown below reads the maximum flow problem instance
alpar@9	2451 in DIMACS format from file `\verb\|sample.max\|', solves it using the
alpar@9	2452 routine \verb\|glp_maxflow_ffalg\|, and write the solution found to the
alpar@9	2453 standard output.
alpar@9	2454
alpar@9	2455 \begin{footnotesize}
alpar@9	2456 \begin{verbatim}
alpar@9	2457 #include <stddef.h>
alpar@9	2458 #include <stdio.h>
alpar@9	2459 #include <stdlib.h>
alpar@9	2460 #include <glpk.h>
alpar@9	2461
alpar@9	2462 typedef struct { int cut; } v_data;
alpar@9	2463 typedef struct { double cap, x; } a_data;
alpar@9	2464
alpar@9	2465 #define node(v) ((v_data *)((v)->data))
alpar@9	2466 #define arc(a) ((a_data *)((a)->data))
alpar@9	2467
alpar@9	2468 int main(void)
alpar@9	2469 { glp_graph *G;
alpar@9	2470 glp_vertex v, w;
alpar@9	2471 glp_arc *a;
alpar@9	2472 int i, s, t, ret;
alpar@9	2473 double sol;
alpar@9	2474 G = glp_create_graph(sizeof(v_data), sizeof(a_data));
alpar@9	2475 glp_read_maxflow(G, &s, &t, offsetof(a_data, cap),
alpar@9	2476 "sample.max");
alpar@9	2477 ret = glp_maxflow_ffalg(G, s, t, offsetof(a_data, cap),
alpar@9	2478 &sol, offsetof(a_data, x), offsetof(v_data, cut));
alpar@9	2479 printf("ret = %d; sol = %5g\n", ret, sol);
alpar@9	2480 for (i = 1; i <= G->nv; i++)
alpar@9	2481 { v = G->v[i];
alpar@9	2482 for (a = v->out; a != NULL; a = a->t_next)
alpar@9	2483 { w = a->head;
alpar@9	2484 printf("x[%d->%d] = %5g (%d)\n", v->i, w->i,
alpar@9	2485 arc(a)->x, node(v)->cut ^ node(w)->cut);
alpar@9	2486 }
alpar@9	2487 }
alpar@9	2488 glp_delete_graph(G);
alpar@9	2489 return 0;
alpar@9	2490 }
alpar@9	2491 \end{verbatim}
alpar@9	2492 \end{footnotesize}
alpar@9	2493
alpar@9	2494 If `\verb\|sample.max\|' is the example data file from the subsection
alpar@9	2495 describing the routine \verb\|glp_read_maxflow\|, the output may look like
alpar@9	2496 follows:
alpar@9	2497
alpar@9	2498 \begin{footnotesize}
alpar@9	2499 \begin{verbatim}
alpar@9	2500 Reading maximum flow problem data from `sample.max'...
alpar@9	2501 Flow network has 9 nodes and 14 arcs
alpar@9	2502 24 lines were read
alpar@9	2503 ret = 0; sol = 29
alpar@9	2504 x[1->4] = 19 (0)
alpar@9	2505 x[1->2] = 10 (0)
alpar@9	2506 x[2->4] = 0 (0)
alpar@9	2507 x[2->3] = 10 (1)
alpar@9	2508 x[3->8] = 10 (0)
alpar@9	2509 x[3->5] = 0 (1)
alpar@9	2510 x[4->5] = 19 (0)
alpar@9	2511 x[5->7] = 4 (1)
alpar@9	2512 x[5->6] = 15 (0)
alpar@9	2513 x[5->2] = 0 (0)
alpar@9	2514 x[6->8] = 8 (1)
alpar@9	2515 x[6->7] = 7 (1)
alpar@9	2516 x[7->9] = 11 (0)
alpar@9	2517 x[8->9] = 18 (0)
alpar@9	2518 \end{verbatim}
alpar@9	2519 \end{footnotesize}
alpar@9	2520
alpar@9	2521 \newpage
alpar@9	2522
alpar@9	2523 \subsection{glp\_rmfgen---Goldfarb's maximum flow problem generator}
alpar@9	2524
alpar@9	2525 \subsubsection*{Synopsis}
alpar@9	2526
alpar@9	2527 \begin{verbatim}
alpar@9	2528 int glp_rmfgen(glp_graph G, int s, int *t, int a_cap,
alpar@9	2529 const int parm[1+5]);
alpar@9	2530 \end{verbatim}
alpar@9	2531
alpar@9	2532 \subsubsection*{Description}
alpar@9	2533
alpar@9	2534 The routine \verb\|glp_rmfgen\| is a GLPK version of the maximum flow
alpar@9	2535 problem generator developed by D.~Goldfarb and
alpar@9	2536 M.~Grigoriadis.\footnote{D.~Goldfarb and M.~D.~Grigoriadis,
alpar@9	2537 ``A computational comparison of the Dinic and network simplex methods
alpar@9	2538 for maximum flow.'' Annals of Op. Res. 13 (1988),
alpar@9	2539 pp.~83-123.}$^{,}$\footnote{U.~Derigs and W.~Meier, ``Implementing
alpar@9	2540 Goldberg's max-flow algorithm: A computational investigation.''
alpar@9	2541 Zeitschrift f\"ur Operations Research 33 (1989),
alpar@9	2542 pp.~383-403.}$^{,}$\footnote{The original code of RMFGEN implemented by
alpar@9	2543 Tamas Badics is publically available from
alpar@9	2544 {\tt <ftp://dimacs.rutgers.edu/pub/netflow/generators/network/genrmf>}.}
alpar@9	2545
alpar@9	2546 The parameter \verb\|G\| specifies the graph object, to which the
alpar@9	2547 generated problem data have to be stored. Note that on entry the graph
alpar@9	2548 object is erased with the routine \verb\|glp_erase_graph\|.
alpar@9	2549
alpar@9	2550 The pointers \verb\|s\| and \verb\|t\| specify locations, to which the
alpar@9	2551 routine stores the source and sink node numbers, respectively. If
alpar@9	2552 \verb\|s\| or \verb\|t\| is \verb\|NULL\|, corresponding node number is not
alpar@9	2553 stored.
alpar@9	2554
alpar@9	2555 The parameter \verb\|a_cap\| specifies an offset of the field of type
alpar@9	2556 \verb\|double\| in the arc data block, to which the routine stores the arc
alpar@9	2557 capacity. If \verb\|a_cap\| $<0$, the capacity is not stored.
alpar@9	2558
alpar@9	2559 The array \verb\|parm\| contains description of the network to be
alpar@9	2560 generated:
alpar@9	2561
alpar@9	2562 \begin{tabular}{@{}lll@{}}
alpar@9	2563 \verb\|parm[0]\|& &not used\\
alpar@9	2564 \verb\|parm[1]\|&\verb\|seed\|&random number seed (a positive integer)\\
alpar@9	2565 \verb\|parm[2]\|&\verb\|a \|&frame size\\
alpar@9	2566 \verb\|parm[3]\|&\verb\|b \|&depth\\
alpar@9	2567 \verb\|parm[4]\|&\verb\|c1 \|&minimal arc capacity\\
alpar@9	2568 \verb\|parm[5]\|&\verb\|c2 \|&maximal arc capacity\\
alpar@9	2569 \end{tabular}
alpar@9	2570
alpar@9	2571 \subsubsection*{Returns}
alpar@9	2572
alpar@9	2573 If the instance was successfully generated, the routine
alpar@9	2574 \verb\|glp_netgen\| returns zero; otherwise, if specified parameters are
alpar@9	2575 inconsistent, the routine returns a non-zero error code.
alpar@9	2576
alpar@9	2577 \newpage
alpar@9	2578
alpar@9	2579 \subsubsection*{Comments\footnote{This material is based on comments
alpar@9	2580 to the original version of RMFGEN.}}
alpar@9	2581
alpar@9	2582 The generated network is as follows. It has $b$ pieces of frames of
alpar@9	2583 size $a\times a$. (So alltogether the number of vertices is
alpar@9	2584 $a\times a\times b$.)
alpar@9	2585
alpar@9	2586 In each frame all the vertices are connected with their neighbours
alpar@9	2587 (forth and back). In addition the vertices of a frame are connected
alpar@9	2588 one to one with the vertices of next frame using a random permutation
alpar@9	2589 of those vertices.
alpar@9	2590
alpar@9	2591 The source is the lower left vertex of the first frame, the sink is
alpar@9	2592 the upper right vertex of the $b$-th frame.
alpar@9	2593
alpar@9	2594 \begin{verbatim}
alpar@9	2595 t
alpar@9	2596 +-------+
alpar@9	2597 \| .\|
alpar@9	2598 \| . \|
alpar@9	2599 / \| / \|
alpar@9	2600 +-------+/ -+ b
alpar@9	2601 \| \| \|/.
alpar@9	2602 a \| -v- \|/
alpar@9	2603 \| \| \|/
alpar@9	2604 +-------+ 1
alpar@9	2605 s a
alpar@9	2606 \end{verbatim}
alpar@9	2607
alpar@9	2608 The capacities are randomly chosen integers from the range of
alpar@9	2609 $[c_1,c_2]$ in the case of interconnecting edges, and $c_2\cdot a^2$
alpar@9	2610 for the in-frame edges.
alpar@9	2611
alpar@9	2612 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9	2613
alpar@9	2614 \newpage
alpar@9	2615
alpar@9	2616 \section{Assignment problem}
alpar@9	2617
alpar@9	2618 \subsection{Background}
alpar@9	2619
alpar@9	2620 Let there be given an undirected bipartite graph $G=(R\cup S,E)$, where
alpar@9	2621 $R$ and $S$ are disjoint sets of vertices (nodes), and
alpar@9	2622 $E\subseteq R\times S$ is a set of edges. Let also for each edge
alpar@9	2623 $e=(i,j)\in E$ there be given its cost $c_{ij}$. A {\it matching}
alpar@9	2624 (which in case of bipartite graph is also called {\it assignment})
alpar@9	2625 $M\subseteq E$ in $G$ is a set of pairwise non-adjacent edges, that is,
alpar@9	2626 no two edges in $M$ share a common vertex. A matching, which matches
alpar@9	2627 all vertices of the graph, is called a {\it perfect matching}.
alpar@9	2628 Obviously, a perfect matching in bipartite graph $G=(R\cup S,E)$
alpar@9	2629 defines some bijection $R\leftrightarrow S$.
alpar@9	2630
alpar@9	2631 The {\it assignment problem} has two different variants. In the first
alpar@9	2632 variant the problem is to find matching (assignment) $M$, which
alpar@9	2633 maximizes the sum:
alpar@9	2634 $$\sum_{(i,j)\in M}c_{ij}\eqno(10)$$
alpar@9	2635 (so this variant is also called the {\it maximum weighted bipartite
alpar@9	2636 matching problem} or, if all $c_{ij}=1$, the {\it maximum cardinality
alpar@9	2637 bipartite matching problem}). In the second, classic variant the
alpar@9	2638 problem is to find {\it perfect} matching (assignment) $M$, which
alpar@9	2639 minimizes or maximizes the sum (10).
alpar@9	2640
alpar@9	2641 An example of the assignment problem, which is the maximum weighted
alpar@9	2642 bipartite matching problem, is shown on Fig. 3.
alpar@9	2643
alpar@9	2644 The maximum weighted bipartite matching problem can be naturally
alpar@9	2645 formulated as the following LP problem:
alpar@9	2646
alpar@9	2647 \medskip
alpar@9	2648
alpar@9	2649 \noindent
alpar@9	2650 \hspace{.5in}maximize
alpar@9	2651 $$z=\sum_{(i,j)\in E}c_{ij}x_{ij}\eqno(11)$$
alpar@9	2652 \hspace{.5in}subject to
alpar@9	2653 $$\sum_{(i,j)\in E}x_{ij}\leq 1\ \ \ \hbox{for all}\ i\in R\eqno(12)$$
alpar@9	2654 $$\sum_{(i,j)\in E}x_{ij}\leq 1\ \ \ \hbox{for all}\ j\in S\eqno(13)$$
alpar@9	2655 $$\ \ \ \ \ \ \ \ 0\leq x_{ij}\leq 1\ \ \ \hbox{for all}\ (i,j)\in E
alpar@9	2656 \eqno(14)$$
alpar@9	2657
alpar@9	2658 \medskip
alpar@9	2659
alpar@9	2660 \noindent
alpar@9	2661 where $x_{ij}=1$ means that $(i,j)\in M$, and $x_{ij}=0$ means that
alpar@9	2662 $(i,j)\notin M$.\footnote{The constraint matrix of LP formulation
alpar@9	2663 (11)---(14) is totally unimodular, due to which $x_{ij}\in\{0,1\}$ for
alpar@9	2664 any basic solution.}
alpar@9	2665
alpar@9	2666 \newpage
alpar@9	2667
alpar@9	2668 \bigskip
alpar@9	2669
alpar@9	2670 \noindent\hfil
alpar@9	2671 \xymatrix @C=48pt
alpar@9	2672 {v_1\ar@{-}[rr]\|{_{13}}\ar@{-}[rrd]\|{_{21}}\ar@{-}[rrddd]\|(.2){_{20}}&&
alpar@9	2673 v_9\\
alpar@9	2674 v_2\ar@{-}[rr]\|{_{12}}\ar@{-}[rrdd]\|(.3){_{8}}
alpar@9	2675 \ar@{-}[rrddd]\|(.4){_{26}}&&v_{10}\\
alpar@9	2676 v_3\ar@{-}[rr]\|(.2){_{22}}\ar@{-}[rrdd]\|(.3){_{11}}&&v_{11}\\
alpar@9	2677 v_4\ar@{-}[rruuu]\|(.6){_{12}}\ar@{-}[rr]\|(.2){_{36}}
alpar@9	2678 \ar@{-}[rrdd]\|(.7){_{25}}&&v_{12}\\
alpar@9	2679 v_5\ar@{-}[rruu]\|(.42){_{41}}\ar@{-}[rru]\|(.4){_{40}}
alpar@9	2680 \ar@{-}[rr]\|(.75){_{11}}\ar@{-}[rrd]\|(.6){_{4}}\ar@{-}[rrdd]\|{_{8}}
alpar@9	2681 \ar@{-}[rrddd]\|{_{35}}\ar@{-}[rrdddd]\|{_{32}}&&v_{13}\\
alpar@9	2682 v_6\ar@{-}[rruuuuu]\|(.7){_{13}}&&v_{14}\\
alpar@9	2683 v_7\ar@{-}[rruuuuu]\|(.15){_{19}}&&v_{15}\\
alpar@9	2684 v_8\ar@{-}[rruuuuuu]\|(.25){_{39}}\ar@{-}[rruuuuu]\|(.65){_{15}}&&
alpar@9	2685 v_{16}\\
alpar@9	2686 &&v_{17}\\
alpar@9	2687 }
alpar@9	2688
alpar@9	2689 \bigskip
alpar@9	2690
alpar@9	2691 \noindent\hfil
alpar@9	2692 Fig.~3. An example of the assignment problem.
alpar@9	2693
alpar@9	2694 \bigskip
alpar@9	2695
alpar@9	2696 Similarly, the perfect assignment problem can be naturally formulated
alpar@9	2697 as the following LP problem:
alpar@9	2698
alpar@9	2699 \medskip
alpar@9	2700
alpar@9	2701 \noindent
alpar@9	2702 \hspace{.5in}minimize (or maximize)
alpar@9	2703 $$z=\sum_{(i,j)\in E}c_{ij}x_{ij}\eqno(15)$$
alpar@9	2704 \hspace{.5in}subject to
alpar@9	2705 $$\sum_{(i,j)\in E}x_{ij}=1\ \ \ \hbox{for all}\ i\in R\eqno(16)$$
alpar@9	2706 $$\sum_{(i,j)\in E}x_{ij}=1\ \ \ \hbox{for all}\ j\in S\eqno(17)$$
alpar@9	2707 $$\ \ \ \ \ \ \ \ 0\leq x_{ij}\leq 1\ \ \ \hbox{for all}\ (i,j)\in E
alpar@9	2708 \eqno(18)$$
alpar@9	2709
alpar@9	2710 \medskip
alpar@9	2711
alpar@9	2712 \noindent
alpar@9	2713 where variables $x_{ij}$ have the same meaning as for (11)---(14)
alpar@9	2714 above.
alpar@9	2715
alpar@9	2716 \newpage
alpar@9	2717
alpar@9	2718 In GLPK an undirected bipartite graph $G=(R\cup S,E)$ is represented as
alpar@9	2719 directed graph $\overline{G}=(V,A)$, where $V=R\cup S$ and
alpar@9	2720 $A=\{(i,j):(i,j)\in E\}$, i.e. every edge $(i,j)\in E$ in $G$
alpar@9	2721 corresponds to arc $(i\rightarrow j)\in A$ in $\overline{G}$.
alpar@9	2722
alpar@9	2723 \subsection{glp\_read\_asnprob---read assignment problem data in\\DIMACS
alpar@9	2724 format}
alpar@9	2725
alpar@9	2726 \subsubsection*{Synopsis}
alpar@9	2727
alpar@9	2728 \begin{verbatim}
alpar@9	2729 int glp_read_asnprob(glp_graph *G, int v_set, int a_cost,
alpar@9	2730 const char *fname);
alpar@9	2731 \end{verbatim}
alpar@9	2732
alpar@9	2733 \subsubsection*{Description}
alpar@9	2734
alpar@9	2735 The routine \verb\|glp_read_asnprob\| reads the assignment problem data
alpar@9	2736 from a text file in DIMACS format.
alpar@9	2737
alpar@9	2738 The parameter \verb\|G\| specifies the graph object, to which the problem
alpar@9	2739 data have to be stored. Note that before reading data the current
alpar@9	2740 content of the graph object is completely erased with the routine
alpar@9	2741 \verb\|glp_erase_graph\|.
alpar@9	2742
alpar@9	2743 The parameter \verb\|v_set\| specifies an offset of the field of type
alpar@9	2744 \verb\|int\| in the vertex data block, to which the routine stores the
alpar@9	2745 node set indicator:
alpar@9	2746
alpar@9	2747 0 --- the node is in set $R$;
alpar@9	2748
alpar@9	2749 1 --- the node is in set $S$.
alpar@9	2750
alpar@9	2751 \noindent
alpar@9	2752 If \verb\|v_set\| $<0$, the node set indicator is not stored.
alpar@9	2753
alpar@9	2754 The parameter \verb\|a_cost\| specifies an offset of the field of type
alpar@9	2755 \verb\|double\| in the arc data block, to which the routine stores the
alpar@9	2756 edge cost $c_{ij}$. If \verb\|a_cost\| $<0$, the edge cost is not stored.
alpar@9	2757
alpar@9	2758 The character string \verb\|fname\| specifies the name of a text file to
alpar@9	2759 be read in. (If the file name name ends with the suffix `\verb\|.gz\|',
alpar@9	2760 the file is assumed to be compressed, in which case the routine
alpar@9	2761 decompresses it ``on the fly''.)
alpar@9	2762
alpar@9	2763 \subsubsection*{Returns}
alpar@9	2764
alpar@9	2765 If the operation was successful, the routine returns zero. Otherwise,
alpar@9	2766 it prints an error message and returns non-zero.
alpar@9	2767
alpar@9	2768 \newpage
alpar@9	2769
alpar@9	2770 \subsubsection*{Example}
alpar@9	2771
alpar@9	2772 \begin{footnotesize}
alpar@9	2773 \begin{verbatim}
alpar@9	2774 typedef struct
alpar@9	2775 { /* vertex data block */
alpar@9	2776 ...
alpar@9	2777 int set;
alpar@9	2778 ...
alpar@9	2779 } v_data;
alpar@9	2780
alpar@9	2781 typedef struct
alpar@9	2782 { /* arc data block */
alpar@9	2783 ...
alpar@9	2784 double cost;
alpar@9	2785 ...
alpar@9	2786 } a_data;
alpar@9	2787
alpar@9	2788 int main(void)
alpar@9	2789 { glp_graph *G;
alpar@9	2790 int ret;
alpar@9	2791 G = glp_create_graph(sizeof(v_data), sizeof(a_data));
alpar@9	2792 ret = glp_read_asnprob(G, offsetof(v_data, set),
alpar@9	2793 offsetof(a_data, cost), "sample.asn");
alpar@9	2794 if (ret != 0) goto ...
alpar@9	2795 ...
alpar@9	2796 }
alpar@9	2797 \end{verbatim}
alpar@9	2798 \end{footnotesize}
alpar@9	2799
alpar@9	2800 \subsubsection*{DIMACS assignment problem format\footnote{This
alpar@9	2801 material is based on the paper ``The First DIMACS International
alpar@9	2802 Algorithm Implementation Challenge: Problem Definitions and
alpar@9	2803 Specifications'', which is publically available at
alpar@9	2804 {\tt http://dimacs.rutgers.edu/Challenges/}.}}
alpar@9	2805 \label{subsecasnprob}
alpar@9	2806
alpar@9	2807 The DIMACS input file is a plain ASCII text file. It contains
alpar@9	2808 {\it lines} of several types described below. A line is terminated with
alpar@9	2809 an end-of-line character. Fields in each line are separated by at least
alpar@9	2810 one blank space. Each line begins with a one-character designator to
alpar@9	2811 identify the line type.
alpar@9	2812
alpar@9	2813 Note that DIMACS requires all numerical quantities to be integers in
alpar@9	2814 the range $[-2^{31},\ 2^{31}-1]$ while GLPK allows the quantities to be
alpar@9	2815 floating-point numbers.
alpar@9	2816
alpar@9	2817 \paragraph{Comment lines.} Comment lines give human-readable information
alpar@9	2818 about the file and are ignored by programs. Comment lines can appear
alpar@9	2819 anywhere in the file. Each comment line begins with a lower-case
alpar@9	2820 character \verb\|c\|.
alpar@9	2821
alpar@9	2822 \begin{verbatim}
alpar@9	2823 c This is a comment line
alpar@9	2824 \end{verbatim}
alpar@9	2825
alpar@9	2826 \newpage
alpar@9	2827
alpar@9	2828 \paragraph{Problem line.} There is one problem line per data file. The
alpar@9	2829 problem line must appear before any node or arc descriptor lines. It has
alpar@9	2830 the following format:
alpar@9	2831
alpar@9	2832 \begin{verbatim}
alpar@9	2833 p asn NODES EDGES
alpar@9	2834 \end{verbatim}
alpar@9	2835
alpar@9	2836 \noindent
alpar@9	2837 The lower-case character \verb\|p\| signifies that this is a problem line.
alpar@9	2838 The three-character problem designator \verb\|asn\| identifies the file as
alpar@9	2839 containing specification information for the assignment problem.
alpar@9	2840 The \verb\|NODES\| field contains an integer value specifying the total
alpar@9	2841 number of nodes in the graph (i.e. in both sets $R$ and $S$). The
alpar@9	2842 \verb\|EDGES\| field contains an integer value specifying the number of
alpar@9	2843 edges in the graph.
alpar@9	2844
alpar@9	2845 \paragraph{Node descriptors.} All node descriptor lines must appear
alpar@9	2846 before all edge descriptor lines. The node descriptor lines lists the
alpar@9	2847 nodes in set $R$ only, and all other nodes are assumed to be in set
alpar@9	2848 $S$. There is one node descriptor line for each such node, with the
alpar@9	2849 following format:
alpar@9	2850
alpar@9	2851 \begin{verbatim}
alpar@9	2852 n ID
alpar@9	2853 \end{verbatim}
alpar@9	2854
alpar@9	2855 \noindent
alpar@9	2856 The lower-case character \verb\|n\| signifies that this is a node
alpar@9	2857 descriptor line. The \verb\|ID\| field gives a node identification number,
alpar@9	2858 an integer between 1 and \verb\|NODES\|.
alpar@9	2859
alpar@9	2860 \paragraph{Edge descriptors.} There is one edge descriptor line for
alpar@9	2861 each edge in the graph. Edge descriptor lines are of the following
alpar@9	2862 format:
alpar@9	2863
alpar@9	2864 \begin{verbatim}
alpar@9	2865 a SRC DST COST
alpar@9	2866 \end{verbatim}
alpar@9	2867
alpar@9	2868 \noindent
alpar@9	2869 The lower-case character \verb\|a\| signifies that this is an edge
alpar@9	2870 descriptor line. For each edge $(i,j)$, where $i\in R$ and $j\in S$,
alpar@9	2871 the \verb\|SRC\| field gives the identification number of vertex $i$, and
alpar@9	2872 the \verb\|DST\| field gives the identification number of vertex $j$.
alpar@9	2873 Identification numbers are integers between 1 and \verb\|NODES\|. The
alpar@9	2874 \verb\|COST\| field contains the cost of edge $(i,j)$.
alpar@9	2875
alpar@9	2876 \paragraph{Example.} Below here is an example of the data file in
alpar@9	2877 DIMACS format corresponding to the assignment problem shown on Fig~3.
alpar@9	2878
alpar@9	2879 \newpage
alpar@9	2880
alpar@9	2881 \begin{footnotesize}
alpar@9	2882 \begin{verbatim}
alpar@9	2883 c sample.asn
alpar@9	2884 c
alpar@9	2885 c This is an example of the assignment problem data
alpar@9	2886 c in DIMACS format.
alpar@9	2887 c
alpar@9	2888 p asn 17 22
alpar@9	2889 c
alpar@9	2890 n 1
alpar@9	2891 n 2
alpar@9	2892 n 3
alpar@9	2893 n 4
alpar@9	2894 n 5
alpar@9	2895 n 6
alpar@9	2896 n 7
alpar@9	2897 n 8
alpar@9	2898 c
alpar@9	2899 a 1 9 13
alpar@9	2900 a 1 10 21
alpar@9	2901 a 1 12 20
alpar@9	2902 a 2 10 12
alpar@9	2903 a 2 12 8
alpar@9	2904 a 2 13 26
alpar@9	2905 a 3 11 22
alpar@9	2906 a 3 13 11
alpar@9	2907 a 4 9 12
alpar@9	2908 a 4 12 36
alpar@9	2909 a 4 14 25
alpar@9	2910 a 5 11 41
alpar@9	2911 a 5 12 40
alpar@9	2912 a 5 13 11
alpar@9	2913 a 5 14 4
alpar@9	2914 a 5 15 8
alpar@9	2915 a 5 16 35
alpar@9	2916 a 5 17 32
alpar@9	2917 a 6 9 13
alpar@9	2918 a 7 10 19
alpar@9	2919 a 8 10 39
alpar@9	2920 a 8 11 15
alpar@9	2921 c
alpar@9	2922 c eof
alpar@9	2923 \end{verbatim}
alpar@9	2924 \end{footnotesize}
alpar@9	2925
alpar@9	2926 \newpage
alpar@9	2927
alpar@9	2928 \subsection{glp\_write\_asnprob---write assignment problem data in\\
alpar@9	2929 DIMACS format}
alpar@9	2930
alpar@9	2931 \subsubsection*{Synopsis}
alpar@9	2932
alpar@9	2933 \begin{verbatim}
alpar@9	2934 int glp_write_asnprob(glp_graph *G, int v_set, int a_cost,
alpar@9	2935 const char *fname);
alpar@9	2936 \end{verbatim}
alpar@9	2937
alpar@9	2938 \subsubsection*{Description}
alpar@9	2939
alpar@9	2940 The routine \verb\|glp_write_asnprob\| writes the assignment problem data
alpar@9	2941 to a text file in DIMACS format.
alpar@9	2942
alpar@9	2943 The parameter \verb\|G\| is the graph program object, which specifies the
alpar@9	2944 assignment problem instance.
alpar@9	2945
alpar@9	2946 The parameter \verb\|v_set\| specifies an offset of the field of type
alpar@9	2947 \verb\|int\| in the vertex data block, which contains the node set
alpar@9	2948 indicator:
alpar@9	2949
alpar@9	2950 0 --- the node is in set $R$;
alpar@9	2951
alpar@9	2952 1 --- the node is in set $S$.
alpar@9	2953
alpar@9	2954 \noindent
alpar@9	2955 If \verb\|v_set\| $<0$, it is assumed that a node having no incoming arcs
alpar@9	2956 is in set $R$, and a node having no outgoing arcs is in set $S$.
alpar@9	2957
alpar@9	2958 The parameter \verb\|a_cost\| specifies an offset of the field of type
alpar@9	2959 \verb\|double\| in the arc data block, which contains $c_{ij}$, the edge
alpar@9	2960 cost. If \verb\|a_cost\| $<0$, it is assumed that $c_{ij}=1$ for all
alpar@9	2961 edges.
alpar@9	2962
alpar@9	2963 The character string \verb\|fname\| specifies a name of the text file to
alpar@9	2964 be written out. (If the file name ends with suffix `\verb\|.gz\|', the
alpar@9	2965 file is assumed to be compressed, in which case the routine performs
alpar@9	2966 automatic compression on writing it.)
alpar@9	2967
alpar@9	2968 \subsubsection*{Note}
alpar@9	2969
alpar@9	2970 The routine \verb\|glp_write_asnprob\| does not check that the specified
alpar@9	2971 graph object correctly represents a bipartite graph. To make sure that
alpar@9	2972 the problem data are correct, use the routine \verb\|glp_check_asnprob\|.
alpar@9	2973
alpar@9	2974 \subsubsection*{Returns}
alpar@9	2975
alpar@9	2976 If the operation was successful, the routine returns zero. Otherwise,
alpar@9	2977 it prints an error message and returns non-zero.
alpar@9	2978
alpar@9	2979 \newpage
alpar@9	2980
alpar@9	2981 \subsection{glp\_check\_asnprob---check correctness of assignment
alpar@9	2982 problem data}
alpar@9	2983
alpar@9	2984 \subsubsection*{Synopsis}
alpar@9	2985
alpar@9	2986 \begin{verbatim}
alpar@9	2987 int glp_check_asnprob(glp_graph *G, int v_set);
alpar@9	2988 \end{verbatim}
alpar@9	2989
alpar@9	2990 \subsubsection*{Description}
alpar@9	2991
alpar@9	2992 The routine \verb\|glp_check_asnprob\| checks that the specified graph
alpar@9	2993 object \verb\|G\| correctly represents a bipartite graph.
alpar@9	2994
alpar@9	2995 The parameter \verb\|v_set\| specifies an offset of the field of type
alpar@9	2996 \verb\|int\| in the vertex data block, which contains the node set
alpar@9	2997 indicator:
alpar@9	2998
alpar@9	2999 0 --- the node is in set $R$;
alpar@9	3000
alpar@9	3001 1 --- the node is in set $S$.
alpar@9	3002
alpar@9	3003 \noindent
alpar@9	3004 If \verb\|v_set\| $<0$, it is assumed that a node having no incoming arcs
alpar@9	3005 is in set $R$, and a node having no outgoing arcs is in set $S$.
alpar@9	3006
alpar@9	3007 \subsubsection*{Returns}
alpar@9	3008
alpar@9	3009 The routine \verb\|glp_check_asnprob\| may return the following codes:
alpar@9	3010
alpar@9	3011 0 --- the data are correct;
alpar@9	3012
alpar@9	3013 1 --- the set indicator of some node is 0, however, that node has one
alpar@9	3014 or more incoming arcs;
alpar@9	3015
alpar@9	3016 2 --- the set indicator of some node is 1, however, that node has one
alpar@9	3017 or more outgoing arcs;
alpar@9	3018
alpar@9	3019 3 --- the set indicator of some node is invalid (neither 0 nor 1);
alpar@9	3020
alpar@9	3021 4 --- some node has both incoming and outgoing arcs.
alpar@9	3022
alpar@9	3023 \subsection{glp\_asnprob\_lp---convert assignment problem to LP}
alpar@9	3024
alpar@9	3025 \subsubsection*{Synopsis}
alpar@9	3026
alpar@9	3027 \begin{verbatim}
alpar@9	3028 int glp_asnprob_lp(glp_prob P, int form, glp_graph G,
alpar@9	3029 int names, int v_set, int a_cost);
alpar@9	3030 \end{verbatim}
alpar@9	3031
alpar@9	3032 \subsubsection*{Description}
alpar@9	3033
alpar@9	3034 The routine \verb\|glp_asnprob_lp\| builds LP problem, which corresponds
alpar@9	3035 to the specified assignment problem.
alpar@9	3036
alpar@9	3037 The parameter \verb\|lp\| is the resultant LP problem object to be built.
alpar@9	3038 Note that on entry its current content is erased with the routine
alpar@9	3039 \verb\|glp_erase_prob\|.
alpar@9	3040
alpar@9	3041 The parameter \verb\|form\| defines which LP formulation should be used:
alpar@9	3042
alpar@9	3043 \verb\|GLP_ASN_MIN\| --- perfect matching (15)---(18), minimization;
alpar@9	3044
alpar@9	3045 \verb\|GLP_ASN_MAX\| --- perfect matching (15)---(18), maximization;
alpar@9	3046
alpar@9	3047 \verb\|GLP_ASN_MMP\| --- maximum weighted matching (11)---(14).
alpar@9	3048
alpar@9	3049 The parameter \verb\|G\| is the graph program object, which specifies the
alpar@9	3050 assignment problem instance.
alpar@9	3051
alpar@9	3052 The parameter \verb\|names\| is a flag. If it is \verb\|GLP_ON\|, the
alpar@9	3053 routine uses symbolic names of the graph object components to assign
alpar@9	3054 symbolic names to the LP problem object components. If the \verb\|flag\|
alpar@9	3055 is \verb\|GLP_OFF\|, no symbolic names are assigned.
alpar@9	3056
alpar@9	3057 The parameter \verb\|v_set\| specifies an offset of the field of type
alpar@9	3058 \verb\|int\| in the vertex data block, which contains the node set
alpar@9	3059 indicator:
alpar@9	3060
alpar@9	3061 0 --- the node is in set $R$;
alpar@9	3062
alpar@9	3063 1 --- the node is in set $S$.
alpar@9	3064
alpar@9	3065 \noindent
alpar@9	3066 If \verb\|v_set\| $<0$, it is assumed that a node having no incoming arcs
alpar@9	3067 is in set $R$, and a node having no outgoing arcs is in set $S$.
alpar@9	3068
alpar@9	3069 The parameter \verb\|a_cost\| specifies an offset of the field of type
alpar@9	3070 \verb\|double\| in the arc data block, which contains $c_{ij}$, the edge
alpar@9	3071 cost. If \verb\|a_cost\| $<0$, it is assumed that $c_{ij}=1$ for all
alpar@9	3072 edges.
alpar@9	3073
alpar@9	3074 \subsubsection*{Returns}
alpar@9	3075
alpar@9	3076 If the LP problem has been successfully built, the routine
alpar@9	3077 \verb\|glp_asnprob_lp\| returns zero, otherwise, non-zero (see the
alpar@9	3078 routine \verb\|glp_check_asnprob\|).
alpar@9	3079
alpar@9	3080 \subsubsection*{Example}
alpar@9	3081
alpar@9	3082 The example program below reads the assignment problem instance in
alpar@9	3083 DIMACS format from file `\verb\|sample.asn\|', converts the instance to
alpar@9	3084 LP (11)---(14), and writes the resultant LP in CPLEX format to file
alpar@9	3085 `\verb\|matching.lp\|'.
alpar@9	3086
alpar@9	3087 \begin{footnotesize}
alpar@9	3088 \begin{verbatim}
alpar@9	3089 #include <stddef.h>
alpar@9	3090 #include <glpk.h>
alpar@9	3091
alpar@9	3092 typedef struct { int set; } v_data;
alpar@9	3093 typedef struct { double cost; } a_data;
alpar@9	3094
alpar@9	3095 int main(void)
alpar@9	3096 { glp_graph *G;
alpar@9	3097 glp_prob *P;
alpar@9	3098 G = glp_create_graph(sizeof(v_data), sizeof(a_data));
alpar@9	3099 glp_read_asnprob(G, offsetof(v_data, set),
alpar@9	3100 offsetof(a_data, cost), "sample.asn");
alpar@9	3101 P = glp_create_prob();
alpar@9	3102 glp_asnprob_lp(P, GLP_ASN_MMP, G, GLP_ON,
alpar@9	3103 offsetof(v_data, set), offsetof(a_data, cost));
alpar@9	3104 glp_delete_graph(G);
alpar@9	3105 glp_write_lp(P, NULL, "matching.lp");
alpar@9	3106 glp_delete_prob(P);
alpar@9	3107 return 0;
alpar@9	3108 }
alpar@9	3109 \end{verbatim}
alpar@9	3110 \end{footnotesize}
alpar@9	3111
alpar@9	3112 If `\verb\|sample.asn\|' is the example data file from the subsection
alpar@9	3113 describing the routine \verb\|glp_read_asnprob\|, file
alpar@9	3114 `\verb\|matching.lp\|' may look like follows:
alpar@9	3115
alpar@9	3116 \begin{footnotesize}
alpar@9	3117 \begin{verbatim}
alpar@9	3118 Maximize
alpar@9	3119 obj: + 20 x(1,12) + 21 x(1,10) + 13 x(1,9) + 26 x(2,13) + 8 x(2,12)
alpar@9	3120 + 12 x(2,10) + 11 x(3,13) + 22 x(3,11) + 25 x(4,14) + 36 x(4,12)
alpar@9	3121 + 12 x(4,9) + 32 x(5,17) + 35 x(5,16) + 8 x(5,15) + 4 x(5,14)
alpar@9	3122 + 11 x(5,13) + 40 x(5,12) + 41 x(5,11) + 13 x(6,9) + 19 x(7,10)
alpar@9	3123 + 15 x(8,11) + 39 x(8,10)
alpar@9	3124
alpar@9	3125 Subject To
alpar@9	3126 r_1: + x(1,9) + x(1,10) + x(1,12) <= 1
alpar@9	3127 r_2: + x(2,10) + x(2,12) + x(2,13) <= 1
alpar@9	3128 r_3: + x(3,11) + x(3,13) <= 1
alpar@9	3129 r_4: + x(4,9) + x(4,12) + x(4,14) <= 1
alpar@9	3130 r_5: + x(5,11) + x(5,12) + x(5,13) + x(5,14) + x(5,15) + x(5,16)
alpar@9	3131 + x(5,17) <= 1
alpar@9	3132 r_6: + x(6,9) <= 1
alpar@9	3133 r_7: + x(7,10) <= 1
alpar@9	3134 r_8: + x(8,10) + x(8,11) <= 1
alpar@9	3135 r_9: + x(6,9) + x(4,9) + x(1,9) <= 1
alpar@9	3136 r_10: + x(8,10) + x(7,10) + x(2,10) + x(1,10) <= 1
alpar@9	3137 r_11: + x(8,11) + x(5,11) + x(3,11) <= 1
alpar@9	3138 r_12: + x(5,12) + x(4,12) + x(2,12) + x(1,12) <= 1
alpar@9	3139 r_13: + x(5,13) + x(3,13) + x(2,13) <= 1
alpar@9	3140 r_14: + x(5,14) + x(4,14) <= 1
alpar@9	3141 r_15: + x(5,15) <= 1
alpar@9	3142 r_16: + x(5,16) <= 1
alpar@9	3143 r_17: + x(5,17) <= 1
alpar@9	3144
alpar@9	3145 Bounds
alpar@9	3146 0 <= x(1,12) <= 1
alpar@9	3147 0 <= x(1,10) <= 1
alpar@9	3148 0 <= x(1,9) <= 1
alpar@9	3149 0 <= x(2,13) <= 1
alpar@9	3150 0 <= x(2,12) <= 1
alpar@9	3151 0 <= x(2,10) <= 1
alpar@9	3152 0 <= x(3,13) <= 1
alpar@9	3153 0 <= x(3,11) <= 1
alpar@9	3154 0 <= x(4,14) <= 1
alpar@9	3155 0 <= x(4,12) <= 1
alpar@9	3156 0 <= x(4,9) <= 1
alpar@9	3157 0 <= x(5,17) <= 1
alpar@9	3158 0 <= x(5,16) <= 1
alpar@9	3159 0 <= x(5,15) <= 1
alpar@9	3160 0 <= x(5,14) <= 1
alpar@9	3161 0 <= x(5,13) <= 1
alpar@9	3162 0 <= x(5,12) <= 1
alpar@9	3163 0 <= x(5,11) <= 1
alpar@9	3164 0 <= x(6,9) <= 1
alpar@9	3165 0 <= x(7,10) <= 1
alpar@9	3166 0 <= x(8,11) <= 1
alpar@9	3167 0 <= x(8,10) <= 1
alpar@9	3168
alpar@9	3169 End
alpar@9	3170 \end{verbatim}
alpar@9	3171 \end{footnotesize}
alpar@9	3172
alpar@9	3173 \subsection{glp\_asnprob\_okalg---solve assignment problem with
alpar@9	3174 out-of-kilter algorithm}
alpar@9	3175
alpar@9	3176 \subsubsection*{Synopsis}
alpar@9	3177
alpar@9	3178 \begin{verbatim}
alpar@9	3179 int glp_asnprob_okalg(int form, glp_graph *G, int v_set,
alpar@9	3180 int a_cost, double *sol, int a_x);
alpar@9	3181 \end{verbatim}
alpar@9	3182
alpar@9	3183 \subsubsection*{Description}
alpar@9	3184
alpar@9	3185 The routine \verb\|glp_mincost_okalg\| finds optimal solution to the
alpar@9	3186 assignment problem with the out-of-kilter
alpar@9	3187 algorithm.\footnote{GLPK implementation of the out-of-kilter algorithm
alpar@9	3188 is based on the following book: L.~R.~Ford,~Jr., and D.~R.~Fulkerson,
alpar@9	3189 ``Flows in Networks,'' The RAND Corp., Report R-375-PR (August 1962),
alpar@9	3190 Chap. III ``Minimal Cost Flow Problems,'' pp.~113-26.} Note that this
alpar@9	3191 routine requires all the problem data to be integer-valued.
alpar@9	3192
alpar@9	3193 The parameter \verb\|form\| defines which LP formulation should be used:
alpar@9	3194
alpar@9	3195 \verb\|GLP_ASN_MIN\| --- perfect matching (15)---(18), minimization;
alpar@9	3196
alpar@9	3197 \verb\|GLP_ASN_MAX\| --- perfect matching (15)---(18), maximization;
alpar@9	3198
alpar@9	3199 \verb\|GLP_ASN_MMP\| --- maximum weighted matching (11)---(14).
alpar@9	3200
alpar@9	3201 The parameter \verb\|G\| is the graph program object, which specifies the
alpar@9	3202 assignment problem instance.
alpar@9	3203
alpar@9	3204 The parameter \verb\|v_set\| specifies an offset of the field of type
alpar@9	3205 \verb\|int\| in the vertex data block, which contains the node set
alpar@9	3206 indicator:
alpar@9	3207
alpar@9	3208 0 --- the node is in set $R$;
alpar@9	3209
alpar@9	3210 1 --- the node is in set $S$.
alpar@9	3211
alpar@9	3212 \newpage
alpar@9	3213
alpar@9	3214 \noindent
alpar@9	3215 If \verb\|v_set\| $<0$, it is assumed that a node having no incoming arcs
alpar@9	3216 is in set $R$, and a node having no outgoing arcs is in set $S$.
alpar@9	3217
alpar@9	3218 The parameter \verb\|a_cost\| specifies an offset of the field of type
alpar@9	3219 \verb\|double\| in the arc data block, which contains $c_{ij}$, the edge
alpar@9	3220 cost. This value must be integer in the range [\verb\|-INT_MAX\|,
alpar@9	3221 \verb\|+INT_MAX\|]. If \verb\|a_cost\| $<0$, it is assumed that $c_{ij}=1$
alpar@9	3222 for all edges.
alpar@9	3223
alpar@9	3224 The parameter \verb\|sol\| specifies a location, to which the routine
alpar@9	3225 stores the objective value (that is, the total cost) found.
alpar@9	3226 If \verb\|sol\| is \verb\|NULL\|, the objective value is not stored.
alpar@9	3227
alpar@9	3228 The parameter \verb\|a_x\| specifies an offset of the field of type
alpar@9	3229 \verb\|int\| in the arc data block, to which the routine stores $x_{ij}$.
alpar@9	3230 If \verb\|a_x\| $<0$, this value is not stored.
alpar@9	3231
alpar@9	3232 \subsubsection*{Returns}
alpar@9	3233
alpar@9	3234 \def\arraystretch{1}
alpar@9	3235
alpar@9	3236 \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
alpar@9	3237 0 & Optimal solution found.\\
alpar@9	3238 \verb\|GLP_ENOPFS\| & No (primal) feasible solution exists.\\
alpar@9	3239 \verb\|GLP_EDATA\| & Unable to start the search, because the assignment
alpar@9	3240 problem data are either incorrect (this error is detected by the
alpar@9	3241 routine \verb\|glp_check_asnprob\|), not integer-valued or out of range.\\
alpar@9	3242 \verb\|GLP_ERANGE\| & The search was prematurely terminated because of
alpar@9	3243 integer overflow.\\
alpar@9	3244 \verb\|GLP_EFAIL\| & An error has been detected in the program logic.
alpar@9	3245 (If this code is returned for your problem instance, please report to
alpar@9	3246 \verb\|<bug-glpk@gnu.org>\|.)\\
alpar@9	3247 \end{tabular}
alpar@9	3248
alpar@9	3249 \subsubsection*{Comments}
alpar@9	3250
alpar@9	3251 Since the out-of-kilter algorithm is designed to find a minimal cost
alpar@9	3252 circulation, the routine \verb\|glp_asnprob_okalg\| converts the original
alpar@9	3253 graph to a network suitable for this algorithm in the following
alpar@9	3254 way:\footnote{The conversion is performed internally and does not change
alpar@9	3255 the original graph program object passed to the routine.}
alpar@9	3256
alpar@9	3257 1) it replaces each edge $(i,j)$ by arc $(i\rightarrow j)$,
alpar@9	3258 flow $x_{ij}$ through which has zero lower bound ($l_{ij}=0$), unity
alpar@9	3259 upper bound ($u_{ij}=1$), and per-unit cost $+c_{ij}$ (in case of
alpar@9	3260 \verb\|GLP_ASN_MIN\|), or $-c_{ij}$ (in case of \verb\|GLP_ASN_MAX\| and
alpar@9	3261 \verb\|GLP_ASN_MMP\|);
alpar@9	3262
alpar@9	3263 2) then it adds one auxiliary feedback node $k$;
alpar@9	3264
alpar@9	3265 \newpage
alpar@9	3266
alpar@9	3267 3) for each original node $i\in R$ the routine adds auxiliary supply
alpar@9	3268 arc $(k\rightarrow i)$, flow $x_{ki}$ through which is costless
alpar@9	3269 ($c_{ki}=0$) and either fixed at 1 ($l_{ki}=u_{ki}=1$, in case of
alpar@9	3270 \verb\|GLP_ASN_MIN\| and \verb\|GLP_ASN_MAX\|) or has zero lower bound and
alpar@9	3271 unity upper bound ($l_{ij}=0$, $u_{ij}=1$, in case of
alpar@9	3272 \verb\|GLP_ASN_MMP\|);
alpar@9	3273
alpar@9	3274 4) similarly, for each original node $j\in S$ the routine adds
alpar@9	3275 auxiliary demand arc $(j\rightarrow k)$, flow $x_{jk}$ through which is
alpar@9	3276 costless ($c_{jk}=0$) and either fixed at 1 ($l_{jk}=u_{jk}=1$, in case
alpar@9	3277 of \verb\|GLP_ASN_MIN\| and \verb\|GLP_ASN_MAX\|) or has zero lower bound
alpar@9	3278 and unity upper bound ($l_{jk}=0$, $u_{jk}=1$, in case of
alpar@9	3279 \verb\|GLP_ASN_MMP\|).
alpar@9	3280
alpar@9	3281 \subsubsection*{Example}
alpar@9	3282
alpar@9	3283 The example program shown below reads the assignment problem instance
alpar@9	3284 in DIMACS format from file `\verb\|sample.asn\|', solves it by using the
alpar@9	3285 routine \verb\|glp_asnprob_okalg\|, and writes the solution found to the
alpar@9	3286 standard output.
alpar@9	3287
alpar@9	3288 \begin{footnotesize}
alpar@9	3289 \begin{verbatim}
alpar@9	3290 #include <stddef.h>
alpar@9	3291 #include <stdio.h>
alpar@9	3292 #include <stdlib.h>
alpar@9	3293 #include <glpk.h>
alpar@9	3294
alpar@9	3295 typedef struct { int set; } v_data;
alpar@9	3296 typedef struct { double cost; int x; } e_data;
alpar@9	3297
alpar@9	3298 #define node(v) ((v_data *)((v)->data))
alpar@9	3299 #define edge(e) ((e_data *)((e)->data))
alpar@9	3300
alpar@9	3301 int main(void)
alpar@9	3302 { glp_graph *G;
alpar@9	3303 glp_vertex *v;
alpar@9	3304 glp_arc *e;
alpar@9	3305 int i, ret;
alpar@9	3306 double sol;
alpar@9	3307 G = glp_create_graph(sizeof(v_data), sizeof(e_data));
alpar@9	3308 glp_read_asnprob(G, offsetof(v_data, set),
alpar@9	3309 offsetof(e_data, cost), "sample.asn");
alpar@9	3310 ret = glp_asnprob_okalg(GLP_ASN_MMP, G,
alpar@9	3311 offsetof(v_data, set), offsetof(e_data, cost), &sol,
alpar@9	3312 offsetof(e_data, x));
alpar@9	3313 printf("ret = %d; sol = %5g\n", ret, sol);
alpar@9	3314 for (i = 1; i <= G->nv; i++)
alpar@9	3315 { v = G->v[i];
alpar@9	3316 for (e = v->out; e != NULL; e = e->t_next)
alpar@9	3317 printf("edge %2d %2d: x = %d; c = %g\n",
alpar@9	3318 e->tail->i, e->head->i, edge(e)->x, edge(e)->cost);
alpar@9	3319 }
alpar@9	3320 glp_delete_graph(G);
alpar@9	3321 return 0;
alpar@9	3322 }
alpar@9	3323 \end{verbatim}
alpar@9	3324 \end{footnotesize}
alpar@9	3325
alpar@9	3326 If `\verb\|sample.asn\|' is the example data file from the subsection
alpar@9	3327 describing the routine \verb\|glp_read_asnprob\|, the output may look
alpar@9	3328 like follows:
alpar@9	3329
alpar@9	3330 \begin{footnotesize}
alpar@9	3331 \begin{verbatim}
alpar@9	3332 Reading assignment problem data from `sample.asn'...
alpar@9	3333 Assignment problem has 8 + 9 = 17 nodes and 22 arcs
alpar@9	3334 38 lines were read
alpar@9	3335 ret = 0; sol = 180
alpar@9	3336 edge 1 12: x = 1; c = 20
alpar@9	3337 edge 1 10: x = 0; c = 21
alpar@9	3338 edge 1 9: x = 0; c = 13
alpar@9	3339 edge 2 13: x = 1; c = 26
alpar@9	3340 edge 2 12: x = 0; c = 8
alpar@9	3341 edge 2 10: x = 0; c = 12
alpar@9	3342 edge 3 13: x = 0; c = 11
alpar@9	3343 edge 3 11: x = 1; c = 22
alpar@9	3344 edge 4 14: x = 1; c = 25
alpar@9	3345 edge 4 12: x = 0; c = 36
alpar@9	3346 edge 4 9: x = 0; c = 12
alpar@9	3347 edge 5 17: x = 0; c = 32
alpar@9	3348 edge 5 16: x = 1; c = 35
alpar@9	3349 edge 5 15: x = 0; c = 8
alpar@9	3350 edge 5 14: x = 0; c = 4
alpar@9	3351 edge 5 13: x = 0; c = 11
alpar@9	3352 edge 5 12: x = 0; c = 40
alpar@9	3353 edge 5 11: x = 0; c = 41
alpar@9	3354 edge 6 9: x = 1; c = 13
alpar@9	3355 edge 7 10: x = 0; c = 19
alpar@9	3356 edge 8 11: x = 0; c = 15
alpar@9	3357 edge 8 10: x = 1; c = 39
alpar@9	3358 \end{verbatim}
alpar@9	3359 \end{footnotesize}
alpar@9	3360
alpar@9	3361 \newpage
alpar@9	3362
alpar@9	3363 \subsection{glp\_asnprob\_hall---find bipartite matching of maximum
alpar@9	3364 cardinality}
alpar@9	3365
alpar@9	3366 \subsubsection*{Synopsis}
alpar@9	3367
alpar@9	3368 \begin{verbatim}
alpar@9	3369 int glp_asnprob_hall(glp_graph *G, int v_set, int a_x);
alpar@9	3370 \end{verbatim}
alpar@9	3371
alpar@9	3372 \subsubsection*{Description}
alpar@9	3373
alpar@9	3374 The routine \verb\|glp_asnprob_hall\| finds a matching of maximal
alpar@9	3375 cardinality in the specified bipartite graph. It uses a version of the
alpar@9	3376 Fortran routine \verb\|MC21A\| developed by
alpar@9	3377 I.~S.~Duff\footnote{I.~S.~Duff, Algorithm 575: Permutations for
alpar@9	3378 zero-free diagonal, ACM Trans. on Math. Softw. 7 (1981), pp.~387-390.},
alpar@9	3379 which implements Hall's algorithm.\footnote{M.~Hall, ``An Algorithm for
alpar@9	3380 Distinct Representatives,'' Am. Math. Monthly 63 (1956), pp.~716-717.}
alpar@9	3381
alpar@9	3382 The parameter \verb\|G\| is a pointer to the graph program object.
alpar@9	3383
alpar@9	3384 The parameter \verb\|v_set\| specifies an offset of the field of type
alpar@9	3385 \verb\|int\| in the vertex data block, which contains the node set
alpar@9	3386 indicator:
alpar@9	3387
alpar@9	3388 0 --- the node is in set $R$;
alpar@9	3389
alpar@9	3390 1 --- the node is in set $S$.
alpar@9	3391
alpar@9	3392 \noindent
alpar@9	3393 If \verb\|v_set\| $<0$, it is assumed that a node having no incoming arcs
alpar@9	3394 is in set $R$, and a node having no outgoing arcs is in set $S$.
alpar@9	3395
alpar@9	3396 The parameter \verb\|a_x\| specifies an offset of the field of type
alpar@9	3397 \verb\|int\| in the arc data block, to which the routine stores $x_{ij}$.
alpar@9	3398 If \verb\|a_x\| $<0$, this value is not stored.
alpar@9	3399
alpar@9	3400 \subsubsection*{Returns}
alpar@9	3401
alpar@9	3402 The routine \verb\|glp_asnprob_hall\| returns the cardinality of the
alpar@9	3403 matching found. However, if the specified graph is incorrect (as
alpar@9	3404 detected by the routine \verb\|glp_check_asnprob\|), this routine returns
alpar@9	3405 a negative value.
alpar@9	3406
alpar@9	3407 \subsubsection*{Comments}
alpar@9	3408
alpar@9	3409 The same solution may be obtained with the routine
alpar@9	3410 \verb\|glp_asnprob_okalg\| (for LP formulation \verb\|GLP_ASN_MMP\| and
alpar@9	3411 all edge costs equal to 1). However, the routine \verb\|glp_asnprob_hall\|
alpar@9	3412 is much faster.
alpar@9	3413
alpar@9	3414 \newpage
alpar@9	3415
alpar@9	3416 \subsubsection*{Example}
alpar@9	3417
alpar@9	3418 The example program shown below reads the assignment problem instance
alpar@9	3419 in DIMACS format from file `\verb\|sample.asn\|', finds a bipartite
alpar@9	3420 matching of maximal cardinality by using the routine
alpar@9	3421 \verb\|glp_asnprob_hall\|, and writes the solution found to the standard
alpar@9	3422 output.
alpar@9	3423
alpar@9	3424 \begin{footnotesize}
alpar@9	3425 \begin{verbatim}
alpar@9	3426 #include <stddef.h>
alpar@9	3427 #include <stdio.h>
alpar@9	3428 #include <stdlib.h>
alpar@9	3429 #include <glpk.h>
alpar@9	3430
alpar@9	3431 typedef struct { int set; } v_data;
alpar@9	3432 typedef struct { int x; } e_data;
alpar@9	3433
alpar@9	3434 #define node(v) ((v_data *)((v)->data))
alpar@9	3435 #define edge(e) ((e_data *)((e)->data))
alpar@9	3436
alpar@9	3437 int main(void)
alpar@9	3438 { glp_graph *G;
alpar@9	3439 glp_vertex *v;
alpar@9	3440 glp_arc *e;
alpar@9	3441 int i, card;
alpar@9	3442 G = glp_create_graph(sizeof(v_data), sizeof(e_data));
alpar@9	3443 glp_read_asnprob(G, offsetof(v_data, set), -1,
alpar@9	3444 "sample.asn");
alpar@9	3445 card = glp_asnprob_hall(G, offsetof(v_data, set),
alpar@9	3446 offsetof(e_data, x));
alpar@9	3447 printf("card = %d\n", card);
alpar@9	3448 for (i = 1; i <= G->nv; i++)
alpar@9	3449 { v = G->v[i];
alpar@9	3450 for (e = v->out; e != NULL; e = e->t_next)
alpar@9	3451 printf("edge %2d %2d: x = %d\n",
alpar@9	3452 e->tail->i, e->head->i, edge(e)->x);
alpar@9	3453 }
alpar@9	3454 glp_delete_graph(G);
alpar@9	3455 return 0;
alpar@9	3456 }
alpar@9	3457 \end{verbatim}
alpar@9	3458 \end{footnotesize}
alpar@9	3459
alpar@9	3460 If `\verb\|sample.asn\|' is the example data file from the subsection
alpar@9	3461 describing the routine \verb\|glp_read_asnprob\|, the output may look
alpar@9	3462 like follows:
alpar@9	3463
alpar@9	3464 \begin{footnotesize}
alpar@9	3465 \begin{verbatim}
alpar@9	3466 Reading assignment problem data from `sample.asn'...
alpar@9	3467 Assignment problem has 8 + 9 = 17 nodes and 22 arcs
alpar@9	3468 38 lines were read
alpar@9	3469 card = 7
alpar@9	3470 edge 1 12: x = 1
alpar@9	3471 edge 1 10: x = 0
alpar@9	3472 edge 1 9: x = 0
alpar@9	3473 edge 2 13: x = 1
alpar@9	3474 edge 2 12: x = 0
alpar@9	3475 edge 2 10: x = 0
alpar@9	3476 edge 3 13: x = 0
alpar@9	3477 edge 3 11: x = 1
alpar@9	3478 edge 4 14: x = 1
alpar@9	3479 edge 4 12: x = 0
alpar@9	3480 edge 4 9: x = 0
alpar@9	3481 edge 5 17: x = 1
alpar@9	3482 edge 5 16: x = 0
alpar@9	3483 edge 5 15: x = 0
alpar@9	3484 edge 5 14: x = 0
alpar@9	3485 edge 5 13: x = 0
alpar@9	3486 edge 5 12: x = 0
alpar@9	3487 edge 5 11: x = 0
alpar@9	3488 edge 6 9: x = 1
alpar@9	3489 edge 7 10: x = 1
alpar@9	3490 edge 8 11: x = 0
alpar@9	3491 edge 8 10: x = 0
alpar@9	3492 \end{verbatim}
alpar@9	3493 \end{footnotesize}
alpar@9	3494
alpar@9	3495 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9	3496
alpar@9	3497 \newpage
alpar@9	3498
alpar@9	3499 \section{Critical path problem}
alpar@9	3500
alpar@9	3501 \subsection{Background}
alpar@9	3502
alpar@9	3503 The {\it critical path problem} (CPP) is stated as follows. Let there
alpar@9	3504 be given a project $J$, which a set of jobs (tasks, activities, etc.).
alpar@9	3505 Performing each job $i\in J$ requires time $t_i\geq 0$. Besides, over
alpar@9	3506 the set $J$ there is given a precedence relation $R\subseteq J\times J$,
alpar@9	3507 where $(i,j)\in R$ means that job $i$ immediately precedes job $j$, i.e.
alpar@9	3508 performing job $j$ cannot start until job $i$ has been completely
alpar@9	3509 performed. The problem is to find starting times $x_i$ for each job
alpar@9	3510 $i\in J$, which satisfy to the precedence relation and minimize the
alpar@9	3511 total duration (makespan) of the project.
alpar@9	3512
alpar@9	3513 The following is an example of the critical path problem:
alpar@9	3514
alpar@9	3515 \begin{center}
alpar@9	3516 \begin{tabular}{\|c\|l\|c\|c\|}
alpar@9	3517 \hline
alpar@9	3518 Job&Desription&Time&Predecessors\\
alpar@9	3519 \hline
alpar@9	3520 A&Excavate&3&---\\
alpar@9	3521 B&Lay foundation&4&A\\
alpar@9	3522 C&Rough plumbing&3&B\\
alpar@9	3523 D&Frame&10&B\\
alpar@9	3524 E&Finish exterior&8&D\\
alpar@9	3525 F&Install HVAC&4&D\\
alpar@9	3526 G&Rough electric&6&D\\
alpar@9	3527 H&Sheet rock&8&C, E, F, G\\
alpar@9	3528 I&Install cabinets&5&H\\
alpar@9	3529 J&Paint&5&H\\
alpar@9	3530 K&Final plumbing&4&I\\
alpar@9	3531 L&Final electric&2&J\\
alpar@9	3532 M&Install flooring&4&K, L\\
alpar@9	3533 \hline
alpar@9	3534 \end{tabular}
alpar@9	3535 \end{center}
alpar@9	3536
alpar@9	3537 Obviously, the project along with the precedence relation can be
alpar@9	3538 represented as a directed graph $G=(J,R)$ called {\it project network},
alpar@9	3539 where each node $i\in J$ corresponds to a job, and arc
alpar@9	3540 $(i\rightarrow j)\in R$ means that job $i$ immediately precedes job
alpar@9	3541 $j$.\footnote{There exists another network representation of the
alpar@9	3542 critical path problem, where jobs correspond to arcs while nodes
alpar@9	3543 correspond to events introduced to express the precedence relation.
alpar@9	3544 That representation, however, is much less convenient than the one,
alpar@9	3545 where jobs are represented as nodes of the network.} The project network
alpar@9	3546 for the example above is shown on Fig.~4.
alpar@9	3547
alpar@9	3548 May note that the project network must be acyclic; otherwise, it would
alpar@9	3549 be impossible to satisfy to the precedence relation for any job that
alpar@9	3550 belongs to a cycle.
alpar@9	3551
alpar@9	3552 \newpage
alpar@9	3553
alpar@9	3554 \xymatrix
alpar@9	3555 {&&&C\|3\ar[rd]&&I\|5\ar[r]&K\|4\ar[rd]&\\
alpar@9	3556 A\|3\ar[r]&B\|4\ar[rru]\ar[rd]&&E\|8\ar[r]&H\|8\ar[ru]\ar[rd]&&&M\|4\\
alpar@9	3557 &&D\|10\ar[ru]\ar[r]\ar[rd]&F\|4\ar[ru]&&J\|5\ar[r]&L\|2\ar[ru]&\\
alpar@9	3558 &&&G\|6\ar[ruu]&&&&\\
alpar@9	3559 }
alpar@9	3560
alpar@9	3561 \bigskip
alpar@9	3562
alpar@9	3563 \noindent\hfil
alpar@9	3564 Fig.~4. An example of the project network.
alpar@9	3565
alpar@9	3566 \bigskip
alpar@9	3567
alpar@9	3568 The critical path problem can be naturally formulated as the following
alpar@9	3569 LP problem:
alpar@9	3570
alpar@9	3571 \medskip
alpar@9	3572
alpar@9	3573 \noindent
alpar@9	3574 \hspace{.5in}minimize
alpar@9	3575 $$z\eqno(19)$$
alpar@9	3576 \hspace{.5in}subject to
alpar@9	3577 $$x_i+t_i\leq z\ \ \ \hbox{for all}\ i\in J\ \ \ \ \eqno(20)$$
alpar@9	3578 $$x_i+t_i\leq x_j\ \ \ \hbox{for all}\ (i,j)\in R\eqno(21)$$
alpar@9	3579 $$x_i\geq 0\ \ \ \ \ \ \ \hbox{for all}\ i\in J\ \ \eqno(22)$$
alpar@9	3580
alpar@9	3581 The inequality constraints (21), which are active in the optimal
alpar@9	3582 solution, define so called {\it critical path} having the following
alpar@9	3583 property: the minimal project duration $z$ can be decreased only by
alpar@9	3584 decreasing the times $t_j$ for jobs on the critical path, and delaying
alpar@9	3585 any critical job delays the entire project.
alpar@9	3586
alpar@9	3587 \subsection{glp\_cpp---solve critical path problem}
alpar@9	3588
alpar@9	3589 \subsubsection{Synopsis}
alpar@9	3590
alpar@9	3591 \begin{verbatim}
alpar@9	3592 double glp_cpp(glp_graph *G, int v_t, int v_es, int v_ls);
alpar@9	3593 \end{verbatim}
alpar@9	3594
alpar@9	3595 \subsubsection{Description}
alpar@9	3596
alpar@9	3597 The routine \verb\|glp_cpp\| solves the critical path problem represented
alpar@9	3598 in the form of the project network.
alpar@9	3599
alpar@9	3600 The parameter \verb\|G\| is a pointer to the graph object, which
alpar@9	3601 specifies the project network. This graph must be acyclic. Multiple
alpar@9	3602 arcs are allowed being considered as single arcs.
alpar@9	3603
alpar@9	3604 The parameter \verb\|v_t\| specifies an offset of the field of type
alpar@9	3605 \verb\|double\| in the vertex data block, which contains time $t_i\geq 0$
alpar@9	3606 needed to perform corresponding job $j\in J$. If \verb\|v_t\| $<0$, it is
alpar@9	3607 assumed that $t_i=1$ for all jobs.
alpar@9	3608
alpar@9	3609 The parameter \verb\|v_es\| specifies an offset of the field of type
alpar@9	3610 \verb\|double\| in the vertex data block, to which the routine stores
alpar@9	3611 the {\it earliest start time} for corresponding job. If \verb\|v_es\|
alpar@9	3612 $<0$, this time is not stored.
alpar@9	3613
alpar@9	3614 The parameter \verb\|v_ls\| specifies an offset of the field of type
alpar@9	3615 \verb\|double\| in the vertex data block, to which the routine stores
alpar@9	3616 the {\it latest start time} for corresponding job. If \verb\|v_ls\|
alpar@9	3617 $<0$, this time is not stored.
alpar@9	3618
alpar@9	3619 The difference between the latest and earliest start times of some job
alpar@9	3620 is called its {\it time reserve}. Delaying a job within its time reserve
alpar@9	3621 does not affect the project duration, so if the time reserve is zero,
alpar@9	3622 the corresponding job is critical.
alpar@9	3623
alpar@9	3624 \subsubsection{Returns}
alpar@9	3625
alpar@9	3626 The routine \verb\|glp_cpp\| returns the minimal project duration, i.e.
alpar@9	3627 minimal time needed to perform all jobs in the project.
alpar@9	3628
alpar@9	3629 \subsubsection{Example}
alpar@9	3630
alpar@9	3631 The example program below solves the critical path problem shown on
alpar@9	3632 Fig.~4 by using the routine \verb\|glp_cpp\| and writes the solution found
alpar@9	3633 to the standard output.
alpar@9	3634
alpar@9	3635 \begin{footnotesize}
alpar@9	3636 \begin{verbatim}
alpar@9	3637 #include <stddef.h>
alpar@9	3638 #include <stdio.h>
alpar@9	3639 #include <stdlib.h>
alpar@9	3640 #include <glpk.h>
alpar@9	3641
alpar@9	3642 typedef struct { double t, es, ls; } v_data;
alpar@9	3643
alpar@9	3644 #define node(v) ((v_data *)((v)->data))
alpar@9	3645
alpar@9	3646 int main(void)
alpar@9	3647 { glp_graph *G;
alpar@9	3648 int i;
alpar@9	3649 double t, es, ef, ls, lf, total;
alpar@9	3650 G = glp_create_graph(sizeof(v_data), 0);
alpar@9	3651 glp_add_vertices(G, 13);
alpar@9	3652 node(G->v[1])->t = 3; /* A: Excavate */
alpar@9	3653 node(G->v[2])->t = 4; /* B: Lay foundation */
alpar@9	3654 node(G->v[3])->t = 3; /* C: Rough plumbing */
alpar@9	3655 node(G->v[4])->t = 10; /* D: Frame */
alpar@9	3656 node(G->v[5])->t = 8; /* E: Finish exterior */
alpar@9	3657 node(G->v[6])->t = 4; /* F: Install HVAC */
alpar@9	3658 node(G->v[7])->t = 6; /* G: Rough elecrtic */
alpar@9	3659 node(G->v[8])->t = 8; /* H: Sheet rock */
alpar@9	3660 node(G->v[9])->t = 5; /* I: Install cabinets */
alpar@9	3661 node(G->v[10])->t = 5; /* J: Paint */
alpar@9	3662 node(G->v[11])->t = 4; /* K: Final plumbing */
alpar@9	3663 node(G->v[12])->t = 2; /* L: Final electric */
alpar@9	3664 node(G->v[13])->t = 4; /* M: Install flooring */
alpar@9	3665 glp_add_arc(G, 1, 2); /* A precedes B */
alpar@9	3666 glp_add_arc(G, 2, 3); /* B precedes C */
alpar@9	3667 glp_add_arc(G, 2, 4); /* B precedes D */
alpar@9	3668 glp_add_arc(G, 4, 5); /* D precedes E */
alpar@9	3669 glp_add_arc(G, 4, 6); /* D precedes F */
alpar@9	3670 glp_add_arc(G, 4, 7); /* D precedes G */
alpar@9	3671 glp_add_arc(G, 3, 8); /* C precedes H */
alpar@9	3672 glp_add_arc(G, 5, 8); /* E precedes H */
alpar@9	3673 glp_add_arc(G, 6, 8); /* F precedes H */
alpar@9	3674 glp_add_arc(G, 7, 8); /* G precedes H */
alpar@9	3675 glp_add_arc(G, 8, 9); /* H precedes I */
alpar@9	3676 glp_add_arc(G, 8, 10); /* H precedes J */
alpar@9	3677 glp_add_arc(G, 9, 11); /* I precedes K */
alpar@9	3678 glp_add_arc(G, 10, 12); /* J precedes L */
alpar@9	3679 glp_add_arc(G, 11, 13); /* K precedes M */
alpar@9	3680 glp_add_arc(G, 12, 13); /* L precedes M */
alpar@9	3681 total = glp_cpp(G, offsetof(v_data, t), offsetof(v_data, es),
alpar@9	3682 offsetof(v_data, ls));
alpar@9	3683 printf("Minimal project duration is %.2f\n\n", total);
alpar@9	3684 printf("Job Time ES EF LS LF\n");
alpar@9	3685 printf("--- ------ ------ ------ ------ ------\n");
alpar@9	3686 for (i = 1; i <= G->nv; i++)
alpar@9	3687 { t = node(G->v[i])->t;
alpar@9	3688 es = node(G->v[i])->es;
alpar@9	3689 ef = es + node(G->v[i])->t;
alpar@9	3690 ls = node(G->v[i])->ls;
alpar@9	3691 lf = ls + node(G->v[i])->t;
alpar@9	3692 printf("%3d %6.2f %s %6.2f %6.2f %6.2f %6.2f\n",
alpar@9	3693 i, t, ls - es < 0.001 ? "*" : " ", es, ef, ls, lf);
alpar@9	3694 }
alpar@9	3695 glp_delete_graph(G);
alpar@9	3696 return 0;
alpar@9	3697 }
alpar@9	3698 \end{verbatim}
alpar@9	3699 \end{footnotesize}
alpar@9	3700
alpar@9	3701 The output from the example program shown below includes job number,
alpar@9	3702 the time needed to perform a job, earliest start time (\verb\|ES\|),
alpar@9	3703 earliest finish time (\verb\|EF\|), latest start time (\verb\|LS\|), and
alpar@9	3704 latest finish time (\verb\|LF\|) for each job in the project. Critical
alpar@9	3705 jobs are marked by asterisks.
alpar@9	3706
alpar@9	3707 \newpage
alpar@9	3708
alpar@9	3709 \begin{footnotesize}
alpar@9	3710 \begin{verbatim}
alpar@9	3711 Minimal project duration is 46.00
alpar@9	3712
alpar@9	3713 Job Time ES EF LS LF
alpar@9	3714 --- ------ ------ ------ ------ ------
alpar@9	3715 1 3.00 * 0.00 3.00 0.00 3.00
alpar@9	3716 2 4.00 * 3.00 7.00 3.00 7.00
alpar@9	3717 3 3.00 7.00 10.00 22.00 25.00
alpar@9	3718 4 10.00 * 7.00 17.00 7.00 17.00
alpar@9	3719 5 8.00 * 17.00 25.00 17.00 25.00
alpar@9	3720 6 4.00 17.00 21.00 21.00 25.00
alpar@9	3721 7 6.00 17.00 23.00 19.00 25.00
alpar@9	3722 8 8.00 * 25.00 33.00 25.00 33.00
alpar@9	3723 9 5.00 * 33.00 38.00 33.00 38.00
alpar@9	3724 10 5.00 33.00 38.00 35.00 40.00
alpar@9	3725 11 4.00 * 38.00 42.00 38.00 42.00
alpar@9	3726 12 2.00 38.00 40.00 40.00 42.00
alpar@9	3727 13 4.00 * 42.00 46.00 42.00 46.00
alpar@9	3728 \end{verbatim}
alpar@9	3729 \end{footnotesize}
alpar@9	3730
alpar@9	3731 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9	3732
alpar@9	3733 \chapter{Graph Optimization API Routines}
alpar@9	3734
alpar@9	3735 \section{Maximum clique problem}
alpar@9	3736
alpar@9	3737 \subsection{Background}
alpar@9	3738
alpar@9	3739 The {\it maximum clique problem (MCP)} is a classic combinatorial
alpar@9	3740 optimization problem. Given an undirected graph $G=(V,E)$, where $V$ is
alpar@9	3741 a set of vertices, and $E$ is a set of edges, this problem is to find
alpar@9	3742 the largest {\it clique} $C\subseteq G$, i.e. the largest induced
alpar@9	3743 complete subgraph. A generalization of this problem is the {\it maximum
alpar@9	3744 weight clique problem (MWCP)}, which is to find a clique $C\subseteq G$
alpar@9	3745 of the largest weight $\displaystyle\sum_{v\in C}w(v)\rightarrow\max$,
alpar@9	3746 where $w(v)$ is a weight of vertex $v\in V$.
alpar@9	3747
alpar@9	3748 An example of the maximum weight clique problem is shown on Fig.~5.
alpar@9	3749
alpar@9	3750 \begin{figure}
alpar@9	3751 \noindent\hfil
alpar@9	3752 \begin{tabular}{c}
alpar@9	3753 {\xymatrix %@C=16pt
alpar@9	3754 {&&&{v_1}\ar@{-}[lllddd]\ar@{-}[llddddd]\ar@{-}[dddddd]
alpar@9	3755 \ar@{-}[rrrddd]&&&\\
alpar@9	3756 &{v_2}\ar@{-}[rrrr]\ar@{-}[rrrrdddd]\ar@{-}[rrddddd]\ar@{-}[dddd]&&&&
alpar@9	3757 {v_3}\ar@{-}[llllldd]\ar@{-}[lllldddd]\ar@{-}[dddd]&\\
alpar@9	3758 &&&&&&\\
alpar@9	3759 {v_4}\ar@{-}[rrrrrr]\ar@{-}[rrrddd]&&&&&&{v_5}\ar@{-}[lllddd]
alpar@9	3760 \ar@{-}[ldd]\\
alpar@9	3761 &&&&&&\\
alpar@9	3762 &{v_6}\ar@{-}[rrrr]&&&&{v_7}&\\
alpar@9	3763 &&&{v_8}&&&\\
alpar@9	3764 }}
alpar@9	3765 \end{tabular}
alpar@9	3766 \begin{tabular}{r@{\ }c@{\ }l}
alpar@9	3767 $w(v_1)$&=&3\\$w(v_2)$&=&4\\$w(v_3)$&=&8\\$w(v_4)$&=&1\\
alpar@9	3768 $w(v_5)$&=&5\\$w(v_6)$&=&2\\$w(v_7)$&=&1\\$w(v_8)$&=&3\\
alpar@9	3769 \end{tabular}
alpar@9	3770
alpar@9	3771 \begin{center}
alpar@9	3772 Fig.~5. An example of the maximum weight clique problem.
alpar@9	3773 \end{center}
alpar@9	3774 \end{figure}
alpar@9	3775
alpar@9	3776 \subsection{glp\_wclique\_exact---find maximum weight clique with exact
alpar@9	3777 algorithm}
alpar@9	3778
alpar@9	3779 \subsubsection*{Synopsis}
alpar@9	3780
alpar@9	3781 \begin{verbatim}
alpar@9	3782 int glp_wclique_exact(glp_graph G, int v_wgt, double sol,
alpar@9	3783 int v_set);
alpar@9	3784 \end{verbatim}
alpar@9	3785
alpar@9	3786 \subsection*{Description}
alpar@9	3787
alpar@9	3788 The routine {\it glp\_wclique\_exact} finds a maximum weight clique in
alpar@9	3789 the specified undirected graph with the exact algorithm developed by
alpar@9	3790 Patric \"Osterg{\aa}rd.\footnote{P.~R.~J.~\"Osterg{\aa}rd, A new
alpar@9	3791 algorithm for the maximum-weight clique problem, Nordic J. of Computing,
alpar@9	3792 Vol.~8, No.~4, 2001, pp.~424--36.}
alpar@9	3793
alpar@9	3794 The parameter $G$ is the program object, which specifies an undirected
alpar@9	3795 graph. Each arc $(x\rightarrow y)$ in $G$ is considered as edge
alpar@9	3796 $(x,y)$, self-loops are ignored, and multiple edges, if present, are
alpar@9	3797 replaced (internally) by simple edges.
alpar@9	3798
alpar@9	3799 The parameter {\it v\_wgt} specifies an offset of the field of type
alpar@9	3800 {\bf double} in the vertex data block, which contains a weight of
alpar@9	3801 corresponding vertex. Vertex weights must be integer-valued in the
alpar@9	3802 range $[0,$ {\it INT\_MAX}$]$. If {\it v\_wgt} $<0$, it is assumed that
alpar@9	3803 all vertices of the graph have the weight 1.
alpar@9	3804
alpar@9	3805 The parameter {\it sol} specifies a location, to which the routine
alpar@9	3806 stores the weight of the clique found (the clique weight is the sum
alpar@9	3807 of weights of all vertices included in the clique.) If {\it sol} is
alpar@9	3808 {\it NULL}, the solution is not stored.
alpar@9	3809
alpar@9	3810 The parameter {\it v\_set} specifies an offset of the field of type
alpar@9	3811 {\bf int} in the vertex data block, to which the routines stores a
alpar@9	3812 vertex flag: 1 means that the corresponding vertex is included in the
alpar@9	3813 clique found, and 0 otherwise. If {\it v\_set} $<0$, vertex flags are
alpar@9	3814 not stored.
alpar@9	3815
alpar@9	3816 \subsubsection*{Returns}
alpar@9	3817
alpar@9	3818 \def\arraystretch{1}
alpar@9	3819
alpar@9	3820 \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
alpar@9	3821 0 & Optimal solution found.\\
alpar@9	3822 \verb\|GLP_EDATA\| & Unable to start the search, because some vertex
alpar@9	3823 weights are either not integer-valued or out of range. This code is
alpar@9	3824 also returned if the sum of weights of all vertices exceeds
alpar@9	3825 {\it INT\_MAX}. \\
alpar@9	3826 \end{tabular}
alpar@9	3827
alpar@9	3828 \subsubsection*{Notes}
alpar@9	3829
alpar@9	3830 \noindent\indent
alpar@9	3831 1. The routine {\it glp\_wclique\_exact} finds exact solution. Since
alpar@9	3832 both MCP and MWCP problems are NP-complete, the algorithm may require
alpar@9	3833 exponential time in worst cases.
alpar@9	3834
alpar@9	3835 2. Internally the specified graph is converted to an adjacency matrix
alpar@9	3836 in {\it dense} format. This requires about $\|V\|^2/16$ bytes of memory,
alpar@9	3837 where $\|V\|$ is the number of vertices in the graph.
alpar@9	3838
alpar@9	3839 \subsubsection*{Example}
alpar@9	3840
alpar@9	3841 The example program shown below reads a MWCP instance in DIMACS
alpar@9	3842 clique/coloring format from file `\verb\|sample.clq\|', finds the clique
alpar@9	3843 of largest weight, and writes the solution found to the standard output.
alpar@9	3844
alpar@9	3845 \begin{footnotesize}
alpar@9	3846 \begin{verbatim}
alpar@9	3847 #include <stddef.h>
alpar@9	3848 #include <stdio.h>
alpar@9	3849 #include <stdlib.h>
alpar@9	3850 #include <glpk.h>
alpar@9	3851
alpar@9	3852 typedef struct { double wgt; int set; } v_data;
alpar@9	3853
alpar@9	3854 #define vertex(v) ((v_data *)((v)->data))
alpar@9	3855
alpar@9	3856 int main(void)
alpar@9	3857 { glp_graph *G;
alpar@9	3858 glp_vertex *v;
alpar@9	3859 int i, ret;
alpar@9	3860 double sol;
alpar@9	3861 G = glp_create_graph(sizeof(v_data), 0);
alpar@9	3862 glp_read_ccdata(G, offsetof(v_data, wgt), "sample.clq");
alpar@9	3863 ret = glp_wclique_exact(G, offsetof(v_data, wgt), &sol,
alpar@9	3864 offsetof(v_data, set));
alpar@9	3865 printf("ret = %d; sol = %g\n", ret, sol);
alpar@9	3866 for (i = 1; i <= G->nv; i++)
alpar@9	3867 { v = G->v[i];
alpar@9	3868 printf("vertex %d: weight = %g, flag = %d\n",
alpar@9	3869 i, vertex(v)->wgt, vertex(v)->set);
alpar@9	3870 }
alpar@9	3871 glp_delete_graph(G);
alpar@9	3872 return 0;
alpar@9	3873 }
alpar@9	3874 \end{verbatim}
alpar@9	3875 \end{footnotesize}
alpar@9	3876
alpar@9	3877 \noindent
alpar@9	3878 For the example shown on Fig.~5 the data file may look like follows:
alpar@9	3879
alpar@9	3880 \begin{footnotesize}
alpar@9	3881 \begin{verbatim}
alpar@9	3882 c sample.clq
alpar@9	3883 c
alpar@9	3884 c This is an example of the maximum weight clique
alpar@9	3885 c problem in DIMACS clique/coloring format.
alpar@9	3886 c
alpar@9	3887 p edge 8 16
alpar@9	3888 n 1 3
alpar@9	3889 n 2 4
alpar@9	3890 n 3 8
alpar@9	3891 n 5 5
alpar@9	3892 n 6 2
alpar@9	3893 n 8 3
alpar@9	3894 e 1 4
alpar@9	3895 e 1 5
alpar@9	3896 e 1 6
alpar@9	3897 e 1 8
alpar@9	3898 e 2 3
alpar@9	3899 e 2 6
alpar@9	3900 e 2 7
alpar@9	3901 e 2 8
alpar@9	3902 e 3 4
alpar@9	3903 e 3 6
alpar@9	3904 e 3 7
alpar@9	3905 e 4 5
alpar@9	3906 e 4 8
alpar@9	3907 e 5 7
alpar@9	3908 e 5 8
alpar@9	3909 e 6 7
alpar@9	3910 c
alpar@9	3911 c eof
alpar@9	3912 \end{verbatim}
alpar@9	3913 \end{footnotesize}
alpar@9	3914
alpar@9	3915 \noindent
alpar@9	3916 The corresponding output from the example program is the following:
alpar@9	3917
alpar@9	3918 \begin{footnotesize}
alpar@9	3919 \begin{verbatim}
alpar@9	3920 Reading graph from `sample.clq'...
alpar@9	3921 Graph has 8 vertices and 16 edges
alpar@9	3922 28 lines were read
alpar@9	3923 ret = 0; sol = 15
alpar@9	3924 vertex 1: weight = 3, flag = 0
alpar@9	3925 vertex 2: weight = 4, flag = 1
alpar@9	3926 vertex 3: weight = 8, flag = 1
alpar@9	3927 vertex 4: weight = 1, flag = 0
alpar@9	3928 vertex 5: weight = 5, flag = 0
alpar@9	3929 vertex 6: weight = 2, flag = 1
alpar@9	3930 vertex 7: weight = 1, flag = 1
alpar@9	3931 vertex 8: weight = 3, flag = 0
alpar@9	3932 \end{verbatim}
alpar@9	3933 \end{footnotesize}
alpar@9	3934
alpar@9	3935 \end{document}