glpk06.tex

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

%* glpk06.tex *%

\chapter{Graph and Network API Routines}

\section{Introduction}

\subsection{Graph program object}

In GLPK the base program object used to represent graphs and networks
is a directed graph (digraph).

Formally, {\it digraph} (or simply, {\it graph}) is a pair $G=(V,A)$,
where $V$ is a set of {\it vertices}, and $A$ is a set
{\it arcs}.\footnote{$A$ may be a multiset.} Each arc $a\in A$ is an
ordered pair of vertices $a=(x,y)$, where $x\in V$ is called {\it tail
vertex} of arc $a$, and $y\in V$ is called its {\it head vertex}.

Representation of a graph in the program includes three structs defined
by typedef in the header \verb|glpk.h|:

\medskip

$\bullet$ \verb|glp_graph|, which represents the graph in a whole,

$\bullet$ \verb|glp_vertex|, which represents a vertex of the graph, and

$\bullet$ \verb|glp_arc|, which represents an arc of the graph.

\medskip

All these three structs are ``semi-opaque'', i.e. the application
program can directly access their fields through pointers, however,
changing the fields directly is not allowed---all changes should be
performed only with appropriate GLPK API routines.

\newpage

\newenvironment{comment}
{\addtolength{\leftskip}{17pt}\noindent}
{\par\addtolength{\leftskip}{-17pt}}

\noindent
{\bf glp\_graph.} The struct \verb|glp_graph| has the following
fields available to the application program:

\medskip

\noindent
\verb|char *name;|

\begin{comment}Symbolic name assigned to the graph. It is a pointer to
a null terminated character string of length from 1 to 255 characters.
If no name is assigned to the graph, this field contains \verb|NULL|.
\end{comment}

\medskip

\noindent
\verb|int nv;|

\begin{comment}The number of vertices in the graph, $nv\geq 0$.
\end{comment}

\medskip

\noindent
\verb|int na;|

\begin{comment}The number of arcs in the graph, $na\geq 0$.
\end{comment}

\medskip

\noindent
\verb|glp_vertex **v;|

\begin{comment}Pointer to an array containing the list of vertices.
Element $v[0]$ is not used. Element $v[i]$, $1\leq i\leq nv$, is a
pointer to $i$-th vertex of the graph. Note that on adding new vertices
to the graph the field $v$ may be altered due to reallocation. However,
pointers $v[i]$ are not changed while corresponding vertices exist in
the graph.
\end{comment}

\medskip

\noindent
\verb|int v_size;|

\begin{comment}Size of vertex data blocks, in bytes,
$0\leq v\_size\leq 256$. (See also the field \verb|data| in the struct
\verb|glp_vertex|.)
\end{comment}

\medskip

\noindent
\verb|int a_size;|

\begin{comment}Size of arc data blocks, in bytes,
$0\leq v\_size\leq 256$. (See also the field \verb|data| in the struct
\verb|glp_arc|.)
\end{comment}

\bigskip

\noindent
{\bf glp\_vertex.} The struct \verb|glp_vertex| has the following
fields available to the application program:

\medskip

\noindent
\verb|int i;|

\begin{comment}Ordinal number of the vertex, $1\leq i\leq nv$. Note
that element $v[i]$ in the struct \verb|glp_graph| points to the vertex,
whose ordinal number is $i$.
\end{comment}

\medskip

\noindent
\verb|char *name;|

\begin{comment}Symbolic name assigned to the vertex. It is a pointer to
a null terminated character string of length from 1 to 255 characters.
If no name is assigned to the vertex, this field contains \verb|NULL|.
\end{comment}

\medskip

\noindent
\verb|void *data;|

\begin{comment}Pointer to a data block associated with the vertex. This
data block is automatically allocated on creating a new vertex and freed
on deleting the vertex. If $v\_size=0$, the block is not allocated, and
this field contains \verb|NULL|.
\end{comment}

\medskip

\noindent
\verb|void *temp;|

\begin{comment}Working pointer, which may be used freely for any
purposes. The application program can change this field directly.
\end{comment}

\medskip

\noindent
\verb|glp_arc *in;|

\begin{comment}Pointer to the (unordered) list of incoming arcs. If the
vertex has no incoming arcs, this field contains \verb|NULL|.
\end{comment}

\medskip

\noindent
\verb|glp_arc *out;|

\begin{comment}Pointer to the (unordered) list of outgoing arcs. If the
vertex has no outgoing arcs, this field contains \verb|NULL|.
\end{comment}

\bigskip

\noindent
{\bf glp\_arc.} The struct \verb|glp_arc| has the following fields
available to the application program:

\medskip

\noindent
\verb|glp_vertex *tail;|

\begin{comment}Pointer to a vertex, which is tail endpoint of the arc.
\end{comment}

\medskip

\noindent
\verb|glp_vertex *head;|

\begin{comment}Pointer to a vertex, which is head endpoint of the arc.
\end{comment}

\medskip

\noindent
\verb|void *data;|

\begin{comment}Pointer to a data block associated with the arc. This
data block is automatically allocated on creating a new arc and freed on
deleting the arc. If $v\_size=0$, the block is not allocated, and this
field contains \verb|NULL|.
\end{comment}

\medskip

\noindent
\verb|void *temp;|

\begin{comment}Working pointer, which may be used freely for any
purposes. The application program can change this field directly.
\end{comment}

\medskip

\noindent
\verb|glp_arc *t_next;|

\begin{comment}Pointer to another arc, which has the same tail endpoint
as this one. \verb|NULL| in this field indicates the end of the list of
outgoing arcs.
\end{comment}

\medskip

\noindent
\verb|glp_arc *h_next;|

\begin{comment}Pointer to another arc, which has the same head endpoint
as this one. \verb|NULL| in this field indicates the end of the list of
incoming arcs.
\end{comment}

\newpage

\section{Graph creating and modifying routines}

\subsection{glp\_create\_graph---create graph}

\subsubsection*{Synopsis}

\begin{verbatim}
glp_graph *glp_create_graph(int v_size, int a_size);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_create_graph| creates a new graph, which
initially is\linebreak empty, i.e. has no vertices and arcs.

The parameter \verb|v_size| specifies the size of vertex data blocks,
in bytes, $0\leq v\_size\leq 256$.

The parameter \verb|a_size| specifies the size of arc data blocks, in
bytes, $0\leq a\_size\leq 256$.

\subsubsection*{Returns}

The routine returns a pointer to the graph created.

\subsection{glp\_set\_graph\_name---assign (change) graph name}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_graph_name(glp_graph *G, const char *name);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_graph_name| assigns a symbolic name specified
by the character string \verb|name| (1 to 255 chars) to the graph.

If the parameter \verb|name| is \verb|NULL| or an empty string, the
routine erases the existing symbolic name of the graph.

\newpage

\subsection{glp\_add\_vertices---add new vertices to graph}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_add_vertices(glp_graph *G, int nadd);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_add_vertices| adds \verb|nadd| vertices to the
specified graph. New vertices are always added to the end of the vertex
list, so ordinal numbers of existing vertices remain unchanged. Note
that this operation may change the field \verb|v| in the struct
\verb|glp_graph| (pointer to the vertex array) due to reallocation.

Being added each new vertex is isolated, i.e. has no incident arcs.

If the size of vertex data blocks specified on creating the graph is
non-zero, the routine also allocates a memory block of that size for
each new vertex added, fills it by binary zeros, and stores a pointer to
it in the field \verb|data| of the struct \verb|glp_vertex|. Otherwise,
if the block size is zero, the field \verb|data| is set to \verb|NULL|.

\subsubsection*{Returns}

The routine \verb|glp_add_vertices| returns the ordinal number of the
first new vertex added to the graph.

\subsection{glp\_set\_vertex\_name---assign (change) vertex name}

[This routine is not implemented yet.]

\subsection{glp\_add\_arc---add new arc to graph}

\subsubsection*{Synopsis}

\begin{verbatim}
glp_arc *glp_add_arc(glp_graph *G, int i, int j);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_add_arc| adds one new arc to the specified graph.

The parameters \verb|i| and \verb|j| specify the ordinal numbers of,
resp., tail and head endpoints (vertices) of the arc. Note that
self-loops and multiple arcs are allowed.

If the size of arc data blocks specified on creating the graph is
non-zero, the routine also allocates a memory block of that size, fills
it by binary zeros, and stores a pointer to it in the field \verb|data|
of the struct \verb|glp_arc|. Otherwise, if the block size is zero, the
field \verb|data| is set to \verb|NULL|.

\subsection{glp\_remove\_vertices---remove vertices from graph}

[This routine is not implemented yet.]

\subsection{glp\_remove\_arc---remove arc from graph}

[This routine is not implemented yet.]

\subsection{glp\_erase\_graph---erase graph content}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_erase_graph(glp_graph *G, int v_size, int a_size);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_erase_graph| erases the content of the specified
graph. The effect of this operation is the same as if the graph would be
deleted with the routine \verb|glp_delete_graph| and then created anew
with the routine \verb|glp_create_graph|, with exception that the handle
(pointer) to the graph remains valid.

The parameters \verb|v_size| and \verb|a_size| have the same meaning as
for the routine \verb|glp_create_graph|.

\subsection{glp\_delete\_graph---delete graph}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_delete_graph(glp_graph *G);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_delete_graph| deletes the specified graph and
frees all the memory allocated to this program object.

\newpage

\section{Minimum cost flow problem}

\subsection{Background}

The {\it minimum cost flow problem} (MCFP) is stated as follows. Let
there be given a directed graph (flow network) $G=(V,A)$, where $V$ is
a set of vertices (nodes), and $A\subseteq V\times V$ is a set of arcs.
Let for each node $i\in V$ there be given a quantity $b_i$ having the
following meaning:

if $b_i>0$, then $|b_i|$ is a {\it supply} at node $i$, which shows
how many flow units are {\it generated} at node $i$ (or, equivalently,
entering the network through node $i$ from the outside);

if $b_i<0$, then $|b_i|$ is a {\it demand} at node $i$, which shows how
many flow units are {\it lost} at node $i$ (or, equivalently, leaving
the network through node $i$ to the outside);

if $b_i=0$, then $i$ is a {\it transshipment} node, at which the flow
is conserved, i.e. neither generated nor lost.

Let also for each arc $a=(i,j)\in A$ there be given the following three
quantities:

$l_{ij}$, a (non-negative) lower bound to the flow through arc $(i,j)$;

$u_{ij}$, an upper bound to the flow through arc $(i,j)$, which is the
{\it arc capacity};

$c_{ij}$, a per-unit cost of the flow through arc $(i,j)$.

The problem is to find flows $x_{ij}$ through every arc of the network,
which satisfy the specified bounds and the conservation constraints at
all nodes, and minimize the total flow cost. Here the conservation
constraint at a node means that the total flow entering this node
through its incoming arcs plus the supply at this node must be equal to
the total flow leaving this node through its outgoing arcs plus the
demand at this node.

An example of the minimum cost flow problem is shown on Fig.~1.

\bigskip

\noindent\hfil
\xymatrix @C=48pt
{_{20}\ar@{~>}[d]&
v_2\ar[r]|{_{0,10,\$2}}\ar[dd]|{_{0,9,\$3}}&
v_3\ar[dd]|{_{2,12,\$1}}\ar[r]|{_{0,18,\$0}}&
v_8\ar[rd]|{_{0,20,\$9}}&\\
v_1\ar[ru]|{_{0,14,\$0}}\ar[rd]|{_{0,23,\$0}}&&&
v_6\ar[d]|{_{0,7,\$0}}\ar[u]|{_{4,8,\$0}}&
v_9\ar@{~>}[d]\\
&v_4\ar[r]|{_{0,26,\$0}}&
v_5\ar[luu]|{_{0,11,\$1}}\ar[ru]|{_{0,25,\$5}}\ar[r]|{_{0,4,\$7}}&
v_7\ar[ru]|{_{0,15,\$3}}&_{20}\\
}

\medskip

\noindent\hfil
\begin{tabular}{ccc}
\xymatrix @C=48pt{v_i\ar[r]|{\ l,u,\$c\ }&v_j\\}&
\xymatrix{\hbox{\footnotesize supply}\ar@{~>}[r]&v_i\\}&
\xymatrix{v_i\ar@{~>}[r]&\hbox{\footnotesize demand}\\}\\
\end{tabular}

\bigskip

\noindent\hfil
Fig.~1. An example of the minimum cost flow problem.

\newpage

The minimum cost flow problem can be naturally formulated as the
following LP problem:

\medskip

\noindent
\hspace{.5in}minimize
$$z=\sum_{(i,j)\in A}c_{ij}x_{ij}\eqno(1)$$
\hspace{.5in}subject to
$$\sum_{(i,j)\in A}x_{ij}-\sum_{(j,i)\in A}x_{ji}=b_i\ \ \ \hbox
{for all}\ i\in V\eqno(2)$$
$$l_{ij}\leq x_{ij}\leq u_{ij}\ \ \ \hbox{for all}\ (i,j)\in A
\eqno(3)$$

\subsection{glp\_read\_mincost---read minimum cost flow problem\\data
in DIMACS format}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_read_mincost(glp_graph *G, int v_rhs, int a_low,
      int a_cap, int a_cost, const char *fname);