glpk06.tex

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

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_read_mincost| reads the minimum cost 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 parameter \verb|v_rhs| specifies an offset of the field of type
\verb|double| in the vertex data block, to which the routine stores
$b_i$, the supply/demand value. If \verb|v_rhs| $<0$, the value is not
stored.

The parameter \verb|a_low| specifies an offset of the field of type
\verb|double| in the arc data block, to which the routine stores
$l_{ij}$, the lower bound to the arc flow. If \verb|a_low| $<0$, the
lower bound 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 upper bound to the arc flow (the arc capacity). If
\verb|a_cap| $<0$, the upper bound 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
$c_{ij}$, the per-unit cost of the arc flow. If \verb|a_cost| $<0$, the
cost 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
{     /* vertex data block */
      ...
      double rhs;
      ...
} v_data;

typedef struct
{     /* arc data block */
      ...
      double low, cap, cost;
      ...
} a_data;

int main(void)
{     glp_graph *G;
      int ret;
      G = glp_create_graph(sizeof(v_data), sizeof(a_data));
      ret = glp_read_mincost(G, offsetof(v_data, rhs),
         offsetof(a_data, low), offsetof(a_data, cap),
         offsetof(a_data, cost), "sample.min");
      if (ret != 0) goto ...
      ...
}
\end{verbatim}

\subsubsection*{DIMACS minimum cost 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
floating-point numbers.

\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 min NODES ARCS
\end{verbatim}

\noindent
The lower-case character \verb|p| signifies that this is a problem line.
The three-character problem designator \verb|min| identifies the file as
containing specification information for the minimum cost 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.} All node descriptor lines must appear
before all arc descriptor lines. The node descriptor lines describe
supply and demand nodes, but not transshipment nodes. That is, only
nodes with non-zero node supply/demand values appear. There is one node
descriptor line for each such node, with the following format:

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

\noindent
The lower-case character \verb|n| signifies that this is a node
descriptor line. The \verb|ID| field gives a node identification number,
an integer between 1 and \verb|NODES|. The \verb|FLOW| field gives the
amount of supply (if positive) or demand (if negative) at node
\verb|ID|.

\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 LOW CAP COST
\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|LOW| field specifies the minimum amount of flow that can be sent
along arc $(i,j)$, and the \verb|CAP| field gives the maximum amount of
flow that can be sent along arc $(i,j)$ in a feasible flow. The
\verb|COST| field contains the per-unit cost of flow sent along arc
$(i,j)$.

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

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

\newpage

\subsection{glp\_write\_mincost---write minimum cost flow problem\\data
in DIMACS format}

\subsubsection*{Synopsis}

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

\subsubsection*{Description}

The routine \verb|glp_write_mincost| writes the minimum cost flow
problem data to a text file in DIMACS format.

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

The parameter \verb|v_rhs| specifies an offset of the field of type
\verb|double| in the vertex data block, which contains $b_i$, the
supply/demand value. If \verb|v_rhs| $<0$, it is assumed that $b_i=0$
for all nodes.

The parameter \verb|a_low| specifies an offset of the field of type
\verb|double| in the arc data block, which contains $l_{ij}$, the lower
bound to the arc flow. If \verb|a_low| $<0$, it is assumed that
$l_{ij}=0$ for all arcs.

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 parameter \verb|a_cost| specifies an offset of the field of type
\verb|double| in the arc data block, which contains $c_{ij}$, the
per-unit cost of the arc flow. If \verb|a_cost| $<0$, it is assumed that
$c_{ij}=0$ 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.

\newpage

\subsection{glp\_mincost\_lp---convert minimum cost flow problem\\to LP}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_mincost_lp(glp_prob *lp, glp_graph *G, int names,
      int v_rhs, int a_low, int a_cap, int a_cost);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_mincost_lp| builds LP problem (1)---(3), which
corresponds to the specified minimum cost 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 minimum cost 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|v_rhs| specifies an offset of the field of type
\verb|double| in the vertex data block, which contains $b_i$, the
supply/demand value. If \verb|v_rhs| $<0$, it is assumed that $b_i=0$
for all nodes.

The parameter \verb|a_low| specifies an offset of the field of type
\verb|double| in the arc data block, which contains $l_{ij}$, the lower
bound to the arc flow. If \verb|a_low| $<0$, it is assumed that
$l_{ij}=0$ for all arcs.

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 parameter \verb|a_cost| specifies an offset of the field of type
\verb|double| in the arc data block, which contains $c_{ij}$, the
per-unit cost of the arc flow. If \verb|a_cost| $<0$, it is assumed that
$c_{ij}=0$ for all arcs.

\subsubsection*{Example}

The example program below reads the minimum cost problem instance in
DIMACS format from file `\verb|sample.min|', converts the instance to
LP, and then writes the resultant LP in CPLEX format to file
`\verb|mincost.lp|'.

\newpage

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

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

int main(void)
{     glp_graph *G;
      glp_prob *lp;
      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");
      lp = glp_create_prob();
      glp_mincost_lp(lp, G, GLP_ON, offsetof(v_data, rhs),
         offsetof(a_data, low), offsetof(a_data, cap),
         offsetof(a_data, cost));
      glp_delete_graph(G);
      glp_write_lp(lp, NULL, "mincost.lp");
      glp_delete_prob(lp);
      return 0;
}
\end{verbatim}

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

\begin{verbatim}
Minimize
 obj: + 3 x(2,4) + 2 x(2,3) + x(3,5) + 7 x(5,7) + 5 x(5,6)
 + x(5,2) + 3 x(7,9) + 9 x(8,9)

Subject To
 r_1: + x(1,2) + x(1,4) = 20
 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) = -20

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
 2 <= x(3,5) <= 12
 0 <= x(4,5) <= 26
 0 <= x(5,7) <= 4
 0 <= x(5,6) <= 25
 0 <= x(5,2) <= 11
 4 <= x(6,8) <= 8
 0 <= x(6,7) <= 7
 0 <= x(7,9) <= 15
 0 <= x(8,9) <= 20

End
\end{verbatim}

\subsection{glp\_mincost\_okalg---solve minimum cost flow problem with
out-of-kilter algorithm}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_mincost_okalg(glp_graph *G, int v_rhs, int a_low,
      int a_cap, int a_cost, double *sol, int a_x, int v_pi);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_mincost_okalg| finds optimal solution to the
minimum cost flow problem with the out-of-kilter
algorithm.\footnote{GLPK implementation of the out-of-kilter algorithm
is based on the following book: L.~R.~Ford,~Jr., and D.~R.~Fulkerson,
``Flows in Networks,'' The RAND Corp., Report R-375-PR (August 1962),
Chap. III ``Minimal Cost Flow Problems,'' pp.~113-26.} 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 minimum cost flow problem instance to be solved.

The parameter \verb|v_rhs| specifies an offset of the field of type
\verb|double| in the vertex data block, which contains $b_i$, the
supply/demand value. This value must be integer in the range
[$-$\verb|INT_MAX|, $+$\verb|INT_MAX|]. If \verb|v_rhs| $<0$, it is
assumed that $b_i=0$ for all nodes.

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

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 [$l_{ij}$, \verb|INT_MAX|]. If \verb|a_cap| $<0$, it is
assumed that $u_{ij}=1$ for all arcs.

The parameter \verb|a_cost| specifies an offset of the field of type
\verb|double| in the arc data block, which contains $c_{ij}$, the
per-unit cost of the arc flow. This value must be integer in the range
[$-$\verb|INT_MAX|, $+$\verb|INT_MAX|]. If \verb|a_cost| $<0$, it is
assumed that $c_{ij}=0$ for all arcs.

The parameter \verb|sol| specifies a location, to which the routine
stores the objective value (that is, the total cost) 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 value is
not stored.

The parameter \verb|v_pi| specifies an offset of the field of type
\verb|double| in the vertex data block, to which the routine stores
$\pi_i$, the node potential, which is the Lagrange multiplier for the
corresponding flow conservation equality constraint (see (2) in
Subsection ``Background''). If necessary, the application program may
use the node potentials to compute $\lambda_{ij}$, reduced costs of the
arc flows $x_{ij}$, which are the Lagrange multipliers for the arc flow
bound constraints (see (3) ibid.), using the following formula:
$$\lambda_{ij}=c_{ij}-(\pi_i-\pi_j),$$
where $c_{ij}$ is the per-unit cost for arc $(i,j)$.

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

\subsubsection*{Returns}

\def\arraystretch{1}

\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
0 & Optimal solution found.\\
\verb|GLP_ENOPFS| & No (primal) feasible solution exists.\\
\verb|GLP_EDATA| & Unable to start the search, because some problem
data are either not integer-valued or out of range. This code is also
returned if the total supply, which is the sum of $b_i$ over all source
nodes (nodes with $b_i>0$), exceeds \verb|INT_MAX|.\\
\end{tabular}

\noindent
\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
\verb|GLP_ERANGE| & The search was prematurely terminated because of
integer overflow.\\
\verb|GLP_EFAIL| & An error has been detected in the program logic.
(If this code is returned for your problem instance, please report to
\verb|<[e-mail]>|.)\\
\end{tabular}

\subsubsection*{Comments}

By design the out-of-kilter algorithm is applicable only to networks,
where $b_i=0$ for {\it all} nodes, i.e. actually this algorithm finds a
minimal cost {\it circulation}. Due to this requirement the routine
\verb|glp_mincost_okalg| converts the original network to a network
suitable for the out-of-kilter algorithm in the following
way:\footnote{The conversion is performed internally and does not change
the original network program object passed to the routine.}

1) it adds two auxiliary nodes $s$ and $t$;

2) for each original node $i$ with $b_i>0$ the routine adds auxiliary
supply arc $(s\rightarrow i)$, flow $x_{si}$ through which is costless
($c_{si}=0$) and fixed to $+b_i$ ($l_{si}=u_{si}=+b_i$);

3) for each original node $i$ with $b_i<0$ the routine adds auxiliary
demand arc $(i\rightarrow t)$, flow $x_{it}$ through which is costless
($c_{it}=0$) and fixed to $-b_i$ ($l_{it}=u_{it}=-b_i$);