COIN-OR::LEMON - Graph Library

source: glpk-cmake/doc/graphs.tex @ 1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 13 years ago

Import glpk-4.45

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