glpk06.tex

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

4) finally, the routine adds auxiliary feedback arc $(t\rightarrow s)$,
flow $x_{ts}$ through which is also costless ($c_{ts}=0$) and fixed to
$F$ ($l_{ts}=u_{ts}=F$), where $\displaystyle F=\sum_{b_i>0}b_i$ is the
total supply.

\subsubsection*{Example}

The example program below reads the minimum cost problem instance in
DIMACS format from file `\verb|sample.min|', solves it by using the
routine \verb|glp_mincost_okalg|, and writes the solution found to the
standard output.

\newpage

\begin{verbatim}
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <glpk.h>

typedef struct { double rhs, pi; } v_data;
typedef struct { double low, cap, cost, x; } a_data;

#define node(v) ((v_data *)((v)->data))
#define arc(a)  ((a_data *)((a)->data))

int main(void)
{     glp_graph *G;
      glp_vertex *v, *w;
      glp_arc *a;
      int i, ret;
      double sol;
      G = glp_create_graph(sizeof(v_data), sizeof(a_data));
      glp_read_mincost(G, offsetof(v_data, rhs),
         offsetof(a_data, low), offsetof(a_data, cap),
         offsetof(a_data, cost), "sample.min");
      ret = glp_mincost_okalg(G, offsetof(v_data, rhs),
         offsetof(a_data, low), offsetof(a_data, cap),
         offsetof(a_data, cost), &sol, offsetof(a_data, x),
         offsetof(v_data, pi));
      printf("ret = %d; sol = %5g\n", ret, sol);
      for (i = 1; i <= G->nv; i++)
      {  v = G->v[i];
         printf("node %d:    pi = %5g\n", i, node(v)->pi);
         for (a = v->out; a != NULL; a = a->t_next)
         {  w = a->head;
            printf("arc  %d->%d: x  = %5g; lambda = %5g\n",
               v->i, w->i, arc(a)->x,
               arc(a)->cost - (node(v)->pi - node(w)->pi));
         }
      }
      glp_delete_graph(G);
      return 0;
}
\end{verbatim}

\newpage

If `\verb|sample.min|' is the example data file from the subsection
describing the routine \verb|glp_read_mincost|, the output may look like
follows:

\begin{verbatim}
Reading min-cost flow problem data from `sample.min'...
Flow network has 9 nodes and 14 arcs
24 lines were read
ret = 0; sol =   213
node 1:    pi =   -12
arc  1->4: x  =    13; lambda =     0
arc  1->2: x  =     7; lambda =     0
node 2:    pi =   -12
arc  2->4: x  =     0; lambda =     3
arc  2->3: x  =     7; lambda =     0
node 3:    pi =   -14
arc  3->8: x  =     5; lambda =     0
arc  3->5: x  =     2; lambda =     3
node 4:    pi =   -12
arc  4->5: x  =    13; lambda =     0
node 5:    pi =   -12
arc  5->7: x  =     4; lambda =    -1
arc  5->6: x  =    11; lambda =     0
arc  5->2: x  =     0; lambda =     1
node 6:    pi =   -17
arc  6->8: x  =     4; lambda =     3
arc  6->7: x  =     7; lambda =    -3
node 7:    pi =   -20
arc  7->9: x  =    11; lambda =     0
node 8:    pi =   -14
arc  8->9: x  =     9; lambda =     0
node 9:    pi =   -23
\end{verbatim}

\newpage

\subsection{glp\_netgen---Klingman's network problem generator}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_netgen(glp_graph *G, int v_rhs, int a_cap, int a_cost,
      const int parm[1+15]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_netgen| is a GLPK version of the network problem
generator developed by Dr.~Darwin~Klingman.\footnote{D.~Klingman,
A.~Napier, and J.~Stutz. NETGEN: A program for generating large scale
capacitated assignment, transportation, and minimum cost flow networks.
Management Science 20 (1974), 814-20.} It can create capacitated and
uncapacitated minimum cost flow (or transshipment), transportation, and
assignment problems.

The parameter \verb|G| specifies the graph object, to which the
generated  problem data have to be stored. Note that on entry the graph
object  is erased with the routine \verb|glp_erase_graph|.

The parameter \verb|v_rhs| specifies an offset of the field of type
\verb|double| in the vertex data block, to which the routine stores the
supply or  demand value. If \verb|v_rhs| $<0$, the value is not stored.

The parameter \verb|a_cap| specifies an offset of the field of type
\verb|double| in the arc data block, to which the routine stores the
arc capacity. If \verb|a_cap| $<0$, the capacity is not stored.

The parameter \verb|a_cost| specifies an offset of the field of type
\verb|double| in the arc data block, to which the routine stores the
per-unit cost if the arc flow. If \verb|a_cost| $<0$, the cost is not
stored.

The array \verb|parm| contains description of the network to be
generated:

\begin{tabular}{@{}lll@{}}
\verb|parm[0] |&             &not used\\
\verb|parm[1] |&\verb|iseed |&8-digit positive random number seed\\
\verb|parm[2] |&\verb|nprob |&8-digit problem id number\\
\verb|parm[3] |&\verb|nodes |&total number of nodes\\
\verb|parm[4] |&\verb|nsorc |&total number of source nodes\\
&&(including transshipment nodes)\\
\verb|parm[5] |&\verb|nsink |&total number of sink nodes\\
&&(including transshipment nodes)\\
\verb|parm[6] |&\verb|iarcs |&number of arc\\
\verb|parm[7] |&\verb|mincst|&minimum cost for arcs\\
\verb|parm[8] |&\verb|maxcst|&maximum cost for arcs\\
\verb|parm[9] |&\verb|itsup |&total supply\\
\end{tabular}

\begin{tabular}{@{}lll@{}}
\verb|parm[10]|&\verb|ntsorc|&number of transshipment source nodes\\
\verb|parm[11]|&\verb|ntsink|&number of transshipment sink nodes\\
\verb|parm[12]|&\verb|iphic |&percentage of skeleton arcs to be given
the maxi-\\&&mum cost\\
\verb|parm[13]|&\verb|ipcap |&percentage of arcs to be capacitated\\
\verb|parm[14]|&\verb|mincap|&minimum upper bound for capacitated arcs\\
\verb|parm[15]|&\verb|maxcap|&maximum upper bound for capacitated arcs\\
\end{tabular}

\subsubsection*{Notes}

\noindent\indent
1. The routine generates a transportation problem if:
$${\tt nsorc}+{\tt nsink}={\tt nodes},
\  {\tt ntsorc}=0,\ \mbox{and}\ {\tt ntsink}=0.$$

2. The routine generates an assignment problem if the requirements for
a transportation problem are met and:
$${\tt nsorc}={\tt nsink}\ \mbox{and}\ {\tt itsup}={\tt nsorc}.$$

3. The routine always generates connected graphs. So, if the number of
requested arcs has been reached and the generated instance is not fully
connected, the routine generates a few remaining arcs to ensure
connectedness. Thus, the actual number of arcs generated by the routine
may be greater than the requested number of arcs.

\subsubsection*{Returns}

If the instance was successfully generated, the routine
\verb|glp_netgen| returns zero; otherwise, if specified parameters are
inconsistent, the routine returns a non-zero error code.

\subsection{glp\_gridgen---grid-like network problem generator}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_gridgen(glp_graph *G, int v_rhs, int a_cap, int a_cost,
      const int parm[1+14]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_gridgen| is a GLPK version of the grid-like
network problem generator developed by Yusin Lee and Jim
Orlin.\footnote{Y.~Lee and J.~Orlin. GRIDGEN generator., 1991. The
original code is publically available from
{\tt<ftp://dimacs.rutgers.edu/pub/netflow/generators/network/gridgen>}.}

The parameter \verb|G| specifies the graph object, to which the
generated  problem data have to be stored. Note that on entry the graph
object  is erased with the routine \verb|glp_erase_graph|.

The parameter \verb|v_rhs| specifies an offset of the field of type
\verb|double| in the vertex data block, to which the routine stores the
supply or  demand value. If \verb|v_rhs| $<0$, the value is not stored.

The parameter \verb|a_cap| specifies an offset of the field of type
\verb|double| in the arc data block, to which the routine stores the
arc capacity. If \verb|a_cap| $<0$, the capacity is not stored.

The parameter \verb|a_cost| specifies an offset of the field of type
\verb|double| in the arc data block, to which the routine stores the
per-unit cost if the arc flow. If \verb|a_cost| $<0$, the cost is not
stored.

The array \verb|parm| contains parameters of the network to be
generated:

\begin{tabular}{@{}ll@{}}
\verb|parm[0] |&not used\\
\verb|parm[1] |&two-ways arcs indicator:\\
               &1 --- if links in both direction should be generated\\
               &0 --- otherwise\\
\verb|parm[2] |&random number seed (a positive integer)\\
\verb|parm[3] |&number of nodes (the number of nodes generated might
be\\&slightly different to make the network a grid)\\
\verb|parm[4] |&grid width\\
\verb|parm[5] |&number of sources\\
\verb|parm[6] |&number of sinks\\
\verb|parm[7] |&average degree\\
\verb|parm[8] |&total flow\\
\verb|parm[9] |&distribution of arc costs:\\
               &1 --- uniform\\
               &2 --- exponential\\
\verb|parm[10]|&lower bound for arc cost (uniform)\\
               &$100\lambda$ (exponential)\\
\verb|parm[11]|&upper bound for arc cost (uniform)\\
               &not used (exponential)\\
\verb|parm[12]|&distribution of arc capacities:\\
               &1 --- uniform\\
               &2 --- exponential\\
\verb|parm[13]|&lower bound for arc capacity (uniform)\\
               &$100\lambda$ (exponential)\\
\verb|parm[14]|&upper bound for arc capacity (uniform)\\
               &not used (exponential)\\
\end{tabular}

\subsubsection*{Returns}

If the instance was successfully generated, the routine
\verb|glp_gridgen| returns zero; otherwise, if specified parameters are
inconsistent, the routine returns a non-zero error code.

\subsubsection*{Comments\footnote{This material is based on comments
to the original version of GRIDGEN.}}

This network generator generates a grid-like network plus a super node.
In additional to the arcs connecting the nodes in the grid, there is an
arc from each supply node to the super node and from the super node to
each demand node to guarantee feasiblity. These arcs have very high
costs and very big capacities.

The idea of this network generator is as follows: First, a grid of
$n_1\times n_2$ is generated. For example, $5\times 3$. The nodes are
numbered as 1 to 15, and the supernode is numbered as $n_1\times n_2+1$.
Then arcs between adjacent nodes are generated. For these arcs, the user
is allowed to specify either to generate two-way arcs or one-way arcs.
If two-way arcs are to be generated, two arcs, one in each direction,
will be generated between each adjacent node pairs. Otherwise, only one
arc will be generated. If this is the case, the arcs will be generated
in alterntive directions as shown below.

\bigskip

\noindent\hfil
\xymatrix
{1\ar[r]\ar[d]&2\ar[r]&3\ar[r]\ar[d]&4\ar[r]&5\ar[d]\\
6\ar[d]&7\ar[l]\ar[u]&8\ar[l]\ar[d]&9\ar[l]\ar[u]&10\ar[l]\ar[d]\\
11\ar[r]&12\ar[r]\ar[u]&13\ar[r]&14\ar[r]\ar[u]&15\\
}

\bigskip

Then the arcs between the super node and the source/sink nodes are added
as mentioned before. If the number of arcs still doesn't reach the
requirement, additional arcs will be added by uniformly picking random
node pairs. There is no checking to prevent multiple arcs between any
pair of nodes. However, there will be no self-arcs (arcs that poins back
to its tail node) in the network.

The source and sink nodes are selected uniformly in the network, and
the imbalances of each source/sink node are also assigned by uniform
distribution.

\newpage

\section{Maximum flow problem}

\subsection{Background}

The {\it maximum flow problem} (MAXFLOW) is stated as follows. Let
there be given a directed graph (flow network) $G=(V,A)$, where $V$ is
a set of vertices (nodes), and $A\subseteq V\times V$ is a set of arcs.
Let also for each arc $a=(i,j)\in A$ there be given its capacity
$u_{ij}$. The problem is, for given {\it source} node $s\in V$ and
{\it sink} node $t\in V$, to find flows $x_{ij}$ through every arc of
the network, which satisfy the specified arc capacities and the
conservation constraints at all nodes, and maximize the total flow $F$
through the network from $s$ to $t$. Here the conservation constraint
at a node means that the total flow entering this node through its
incoming arcs (plus $F$, if it is the source node) must be equal to the
total flow leaving this node through its outgoing arcs (plus $F$, if it
is the sink node).

An example of the maximum flow problem, where $s=v_1$ and $t=v_9$, is
shown on Fig.~2.

\bigskip

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

\bigskip

\noindent\hfil
Fig.~2. An example of the maximum flow problem.

\bigskip

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

\medskip

\noindent
\hspace{.5in}maximize
$$F\eqno(4)$$
\hspace{.5in}subject to
$$\sum_{(i,j)\in A}x_{ij}-\sum_{(j,i)\in A}x_{ji}=\left\{
\begin{array}{@{\ }rl}
+F,&\hbox{for}\ i=s\\
 0,&\hbox{for all}\ i\in V\backslash\{s,t\}\\
-F,&\hbox{for}\ i=t\\
\end{array}
\right.\eqno(5)
$$
$$0\leq x_{ij}\leq u_{ij}\ \ \ \hbox{for all}\ (i,j)\in A
\eqno(6)$$

\medskip

\noindent
where $F\geq 0$ is an additional variable playing the role of the
objective.

\newpage

Another LP formulation of the maximum flow problem, which does not
include the variable $F$, is the following:

\medskip

\noindent
\hspace{.5in}maximize
$$z=\sum_{(s,j)\in A}x_{sj}-\sum_{(j,s)\in A}x_{js}\ (=F)\eqno(7)$$
\hspace{.5in}subject to
$$\sum_{(i,j)\in A}x_{ij}-\sum_{(j,i)\in A}x_{ji}\left\{
\begin{array}{@{\ }rl}
\geq 0,&\hbox{for}\ i=s\\
=0,&\hbox{for all}\ i\in V\backslash\{s,t\}\\
\leq 0,&\hbox{for}\ i=t\\
\end{array}
\right.\eqno(8)
$$
$$0\leq x_{ij}\leq u_{ij}\ \ \ \hbox{for all}\ (i,j)\in A
\eqno(9)$$

\subsection{glp\_read\_maxflow---read maximum flow problem data\\in
DIMACS format}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_read_maxflow(glp_graph *G, int *s, int *t, int a_cap,
      const char *fname);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_read_maxflow| reads the maximum flow problem
data from a text file in DIMACS format.

The parameter \verb|G| specifies the graph object, to which the problem
data have to be stored. Note that before reading data the current
content of the graph object is completely erased with the routine
\verb|glp_erase_graph|.

The pointer \verb|s| specifies a location, to which the routine stores
the ordinal number of the source node. If \verb|s| is \verb|NULL|, the
source node number is not stored.

The pointer \verb|t| specifies a location, to which the routine stores
the ordinal number of the sink node. If \verb|t| is \verb|NULL|, the
sink node number is not stored.

The parameter \verb|a_cap| specifies an offset of the field of type
\verb|double| in the arc data block, to which the routine stores
$u_{ij}$, the arc capacity. If \verb|a_cap| $<0$, the arc capacity is
not stored.

The character string \verb|fname| specifies the name of a text file to
be read in. (If the file name name ends with the suffix `\verb|.gz|',
the file is assumed to be compressed, in which case the routine
decompresses it ``on the fly''.)

\subsubsection*{Returns}

If the operation was successful, the routine returns zero. Otherwise,
it prints an error message and returns non-zero.

\subsubsection*{Example}

\begin{verbatim}
typedef struct
{     /* arc data block */
      ...
      double cap;
      ...
} a_data;

int main(void)
{     glp_graph *G;
      int s, t, ret;
      G = glp_create_graph(..., sizeof(a_data));
      ret = glp_read_maxflow(G, &s, &t, offsetof(a_data, cap),
         "sample.max");
      if (ret != 0) goto ...
      ...
}
\end{verbatim}

\subsubsection*{DIMACS maximum flow problem format\footnote{This
material is based on the paper ``The First DIMACS International
Algorithm Implementation Challenge: Problem Definitions and
Specifications'', which is publically available at
{\tt http://dimacs.rutgers.edu/Challenges/}.}}

The DIMACS input file is a plain ASCII text file. It contains
{\it lines} of several types described below. A line is terminated with
an end-of-line character. Fields in each line are separated by at least
one blank space. Each line begins with a one-character designator to
identify the line type.

Note that DIMACS requires all numerical quantities to be integers in
the range $[-2^{31},\ 2^{31}-1]$ while GLPK allows the quantities to be