glpk06.tex

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

floating-point numbers.

\newpage

\paragraph{Comment lines.} Comment lines give human-readable information
about the file and are ignored by programs. Comment lines can appear
anywhere in the file. Each comment line begins with a lower-case
character \verb|c|.

\begin{verbatim}
   c This is a comment line
\end{verbatim}

\paragraph{Problem line.} There is one problem line per data file. The
problem line must appear before any node or arc descriptor lines. It has
the following format:

\begin{verbatim}
   p max NODES ARCS
\end{verbatim}

\noindent
The lower-case character \verb|p| signifies that this is a problem line.
The three-character problem designator \verb|max| identifies the file as
containing specification information for the maximum flow problem. The
\verb|NODES| field contains an integer value specifying the number of
nodes in the network. The \verb|ARCS| field contains an integer value
specifying the number of arcs in the network.

\paragraph{Node descriptors.} Two node descriptor lines for the source
and sink nodes must appear before all arc descriptor lines. They may
appear in either order, each with the following format:

\begin{verbatim}
   n ID WHICH
\end{verbatim}

\noindent
The lower-case character \verb|n| signifies that this a node descriptor
line. The \verb|ID| field gives a node identification number, an integer
between 1 and \verb|NODES|. The \verb|WHICH| field gives either a
lower-case \verb|s| or \verb|t|, designating the source and sink,
respectively.

\paragraph{Arc descriptors.} There is one arc descriptor line for each
arc in the network. Arc descriptor lines are of the following format:

\begin{verbatim}
a SRC DST CAP
\end{verbatim}

\noindent
The lower-case character \verb|a| signifies that this is an arc
descriptor line. For a directed arc $(i,j)$ the \verb|SRC| field gives
the identification number $i$ for the tail endpoint, and the \verb|DST|
field gives the identification number $j$ for the head endpoint.
Identification numbers are integers between 1 and \verb|NODES|. The
\verb|CAP| field gives the arc capacity, i.e. maximum amount of flow
that can be sent along arc $(i,j)$ in a feasible flow.

\newpage

\paragraph{Example.} Below here is an example of the data file in
DIMACS format corresponding to the maximum flow problem shown on Fig~2.

\begin{verbatim}
c sample.max
c
c This is an example of the maximum flow problem data
c in DIMACS format.
c
p max 9 14
c
n 1 s
n 9 t
c
a 1 2 14
a 1 4 23
a 2 3 10
a 2 4  9
a 3 5 12
a 3 8 18
a 4 5 26
a 5 2 11
a 5 6 25
a 5 7  4
a 6 7  7
a 6 8  8
a 7 9 15
a 8 9 20
c
c eof
\end{verbatim}

\newpage

\subsection{glp\_write\_maxflow---write maximum flow problem data\\
in DIMACS format}

\subsubsection*{Synopsis}

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

\subsubsection*{Description}

The routine \verb|glp_write_maxflow| writes the maximum flow problem
data to a text file in DIMACS format.

The parameter \verb|G| is the graph (network) program object, which
specifies the maximum flow problem instance.

The parameter \verb|s| specifies the ordinal number of the source node.

The parameter \verb|t| specifies the ordinal number of the sink node.

The parameter \verb|a_cap| specifies an offset of the field of type
\verb|double| in the arc data block, which contains $u_{ij}$, the upper
bound to the arc flow (the arc capacity). If the upper bound is
specified as \verb|DBL_MAX|, it is assumed that $u_{ij}=\infty$, i.e.
the arc is uncapacitated. If \verb|a_cap| $<0$, it is assumed that
$u_{ij}=1$ for all arcs.

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

\subsubsection*{Returns}

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

\subsection{glp\_maxflow\_lp---convert maximum flow problem to LP}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_maxflow_lp(glp_prob *lp, glp_graph *G, int names,
      int s, int t, int a_cap);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_maxflow_lp| builds LP problem (7)---(9), which
corresponds to the specified maximum flow problem.

The parameter \verb|lp| is the resultant LP problem object to be built.
Note that on entry its current content is erased with the routine
\verb|glp_erase_prob|.

The parameter \verb|G| is the graph (network) program object, which
specifies the maximum flow problem instance.

The parameter \verb|names| is a flag. If it is \verb|GLP_ON|, the
routine uses symbolic names of the graph object components to assign
symbolic names to the LP problem object components. If the flag is
\verb|GLP_OFF|, no symbolic names are assigned.

The parameter \verb|s| specifies the ordinal number of the source node.

The parameter \verb|t| specifies the ordinal number of the sink node.

The parameter \verb|a_cap| specifies an offset of the field of type
\verb|double| in the arc data block, which contains $u_{ij}$, the upper
bound to the arc flow (the arc capacity). If the upper bound is
specified as \verb|DBL_MAX|, it is assumed that $u_{ij}=\infty$, i.e.
the arc is uncapacitated. If \verb|a_cap| $<0$, it is assumed that
$u_{ij}=1$ for all arcs.

\subsubsection*{Example}

The example program below reads the maximum flow problem in DIMACS
format from file `\verb|sample.max|', converts the instance to LP, and
then writes the resultant LP in CPLEX format to file
`\verb|maxflow.lp|'.

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

int main(void)
{     glp_graph *G;
      glp_prob *lp;
      int s, t;
      G = glp_create_graph(0, sizeof(double));
      glp_read_maxflow(G, &s, &t, 0, "sample.max");
      lp = glp_create_prob();
      glp_maxflow_lp(lp, G, GLP_ON, s, t, 0);
      glp_delete_graph(G);
      glp_write_lp(lp, NULL, "maxflow.lp");
      glp_delete_prob(lp);
      return 0;
}
\end{verbatim}

\newpage

If `\verb|sample.max|' is the example data file from the previous
subsection, the output `\verb|maxflow.lp|' may look like follows:

\begin{verbatim}
Maximize
 obj: + x(1,4) + x(1,2)

Subject To
 r_1: + x(1,2) + x(1,4) >= 0
 r_2: - x(5,2) + x(2,3) + x(2,4) - x(1,2) = 0
 r_3: + x(3,5) + x(3,8) - x(2,3) = 0
 r_4: + x(4,5) - x(2,4) - x(1,4) = 0
 r_5: + x(5,2) + x(5,6) + x(5,7) - x(4,5) - x(3,5) = 0
 r_6: + x(6,7) + x(6,8) - x(5,6) = 0
 r_7: + x(7,9) - x(6,7) - x(5,7) = 0
 r_8: + x(8,9) - x(6,8) - x(3,8) = 0
 r_9: - x(8,9) - x(7,9) <= 0

Bounds
 0 <= x(1,4) <= 23
 0 <= x(1,2) <= 14
 0 <= x(2,4) <= 9
 0 <= x(2,3) <= 10
 0 <= x(3,8) <= 18
 0 <= x(3,5) <= 12
 0 <= x(4,5) <= 26
 0 <= x(5,7) <= 4
 0 <= x(5,6) <= 25
 0 <= x(5,2) <= 11
 0 <= x(6,8) <= 8
 0 <= x(6,7) <= 7
 0 <= x(7,9) <= 15
 0 <= x(8,9) <= 20

End
\end{verbatim}

\newpage

\subsection{glp\_maxflow\_ffalg---solve maximum flow problem with
Ford-Fulkerson algorithm}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_maxflow_ffalg(glp_graph *G, int s, int t, int a_cap,
      double *sol, int a_x, int v_cut);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_mincost_ffalg| finds optimal solution to the
maximum flow problem with the Ford-Fulkerson algorithm.\footnote{GLPK
implementation of the Ford-Fulkerson algorithm is based on the following
book: L.~R.~Ford,~Jr., and D.~R.~Fulkerson, ``Flows in Networks,'' The
RAND Corp., Report\linebreak R-375-PR (August 1962), Chap. I
``Static Maximal Flow,'' pp.~30-33.} Note that this routine requires all
the problem data to be integer-valued.

The parameter \verb|G| is a graph (network) program object which
specifies the maximum flow problem instance to be solved.

The parameter $s$ specifies the ordinal number of the source node.

The parameter $t$ specifies the ordinal number of the sink node.

The parameter \verb|a_cap| specifies an offset of the field of type
\verb|double| in the arc data block, which contains $u_{ij}$, the upper
bound to the arc flow (the arc capacity). This bound must be integer in
the range [0, \verb|INT_MAX|]. If \verb|a_cap| $<0$, it is assumed that
$u_{ij}=1$ for all arcs.

The parameter \verb|sol| specifies a location, to which the routine
stores the objective value (that is, the total flow from $s$ to $t$)
found. If \verb|sol| is NULL, the objective value is not stored.

The parameter \verb|a_x| specifies an offset of the field of type
\verb|double| in the arc data block, to which the routine stores
$x_{ij}$, the arc flow found. If \verb|a_x| $<0$, the arc flow values
are not stored.

The parameter \verb|v_cut| specifies an offset of the field of type
\verb|int| in the vertex data block, to which the routine stores node
flags corresponding to the optimal solution found: if the node flag is
1, the node is labelled, and if the node flag is 0, the node is
unlabelled. The calling program may use these node flags to determine
the {\it minimal cut}, which is a subset of arcs whose one endpoint is
labelled and other is not. If \verb|v_cut| $<0$, the node flags are not
stored.

Note that all solution components (the objective value and arc flows)
computed by the routine are always integer-valued.

\newpage

\subsubsection*{Returns}

\def\arraystretch{1}

\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
0 & Optimal solution found.\\
\verb|GLP_EDATA| & Unable to start the search, because some problem
data are either not integer-valued or out of range.\\
\end{tabular}

\subsubsection*{Example}

The example program shown below reads the maximum flow problem instance
in DIMACS format from file `\verb|sample.max|', solves it using the
routine \verb|glp_maxflow_ffalg|, and write the solution found to the
standard output.

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

typedef struct { int cut; } v_data;
typedef struct { double cap, 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, s, t, ret;
      double sol;
      G = glp_create_graph(sizeof(v_data), sizeof(a_data));
      glp_read_maxflow(G, &s, &t, offsetof(a_data, cap),
         "sample.max");
      ret = glp_maxflow_ffalg(G, s, t, offsetof(a_data, cap),
         &sol, offsetof(a_data, x), offsetof(v_data, cut));
      printf("ret = %d; sol = %5g\n", ret, sol);
      for (i = 1; i <= G->nv; i++)
      {  v = G->v[i];
         for (a = v->out; a != NULL; a = a->t_next)
         {  w = a->head;
            printf("x[%d->%d] = %5g (%d)\n", v->i, w->i,
               arc(a)->x, node(v)->cut ^ node(w)->cut);
         }
      }
      glp_delete_graph(G);
      return 0;
}
\end{verbatim}

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

\begin{verbatim}
Reading maximum flow problem data from `sample.max'...
Flow network has 9 nodes and 14 arcs
24 lines were read
ret = 0; sol =    29
x[1->4] =    19 (0)
x[1->2] =    10 (0)
x[2->4] =     0 (0)
x[2->3] =    10 (1)
x[3->8] =    10 (0)
x[3->5] =     0 (1)
x[4->5] =    19 (0)
x[5->7] =     4 (1)
x[5->6] =    15 (0)
x[5->2] =     0 (0)
x[6->8] =     8 (1)
x[6->7] =     7 (1)
x[7->9] =    11 (0)
x[8->9] =    18 (0)
\end{verbatim}

\newpage

\subsection{glp\_rmfgen---Goldfarb's maximum flow problem generator}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_rmfgen(glp_graph *G, int *s, int *t, int a_cap,
      const int parm[1+5]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_rmfgen| is a GLPK version of the maximum flow
problem generator developed by D.~Goldfarb and
M.~Grigoriadis.\footnote{D.~Goldfarb and M.~D.~Grigoriadis,
``A computational comparison of the Dinic and network simplex methods
for maximum flow.'' Annals of Op. Res. 13 (1988),
pp.~83-123.}$^{,}$\footnote{U.~Derigs and W.~Meier, ``Implementing
Goldberg's max-flow algorithm: A computational investigation.''
Zeitschrift f\"ur Operations Research 33 (1989),
pp.~383-403.}$^{,}$\footnote{The original code of RMFGEN implemented by
Tamas Badics is publically available from
{\tt <ftp://dimacs.rutgers.edu/pub/netflow/generators/network/genrmf>}.}

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 pointers \verb|s| and \verb|t| specify locations, to which the
routine stores the source and sink node numbers, respectively. If
\verb|s| or \verb|t| is \verb|NULL|, corresponding 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 the arc
capacity. If \verb|a_cap| $<0$, the capacity 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|seed|&random number seed (a positive integer)\\
\verb|parm[2]|&\verb|a   |&frame size\\
\verb|parm[3]|&\verb|b   |&depth\\
\verb|parm[4]|&\verb|c1  |&minimal arc capacity\\
\verb|parm[5]|&\verb|c2  |&maximal arc capacity\\
\end{tabular}

\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.

\newpage

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

The generated network is as follows. It has $b$ pieces of frames of
size $a\times a$. (So alltogether the number of vertices is
$a\times a\times b$.)

In each frame all the vertices are connected with their neighbours
(forth and back). In addition the vertices of a frame are connected
one to one with the vertices of next frame using a random permutation
of those vertices.

The source is the lower left vertex of the first frame, the sink is
the upper right vertex of the $b$-th frame.

\begin{verbatim}
                              t
                     +-------+
                     |      .|
                     |     . |
                  /  |    /  |
                 +-------+/ -+ b
                 |    |  |/.
               a |   -v- |/
                 |    |  |/
                 +-------+ 1
                s    a
\end{verbatim}

The capacities are randomly chosen integers from the range of
$[c_1,c_2]$  in the case of interconnecting edges, and $c_2\cdot a^2$
for the in-frame edges.

%* eof *%