glpk02.tex

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

%* glpk02.tex *%

\chapter{Basic API Routines}

This chapter describes GLPK API routines intended for using in
application programs.

\subsubsection*{Library header}

All GLPK API data types and routines are defined in the header file
\verb|glpk.h|. It should be included in all source files which use
GLPK API, either directly or indirectly through some other header file
as follows:

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

\subsubsection*{Error handling}

If some GLPK API routine detects erroneous or incorrect data passed by
the application program, it writes appropriate diagnostic messages to
the terminal and then abnormally terminates the application program.
In most practical cases this allows to simplify programming by avoiding
numerous checks of return codes. Thus, in order to prevent crashing the
application program should check all data, which are suspected to be
incorrect, before calling GLPK API routines.

Should note that this kind of error handling is used only in cases of
incorrect data passed by the application program. If, for example, the
application program calls some GLPK API routine to read data from an
input file and these data are incorrect, the GLPK API routine reports
about error in the usual way by means of the return code.

\subsubsection*{Thread safety}

Currently GLPK API routines are non-reentrant and therefore cannot be
used in multi-threaded programs.

\subsubsection*{Array indexing}

Normally all GLPK API routines start array indexing from 1, not from 0
(except the specially stipulated cases). This means, for example, that
if some vector $x$ of the length $n$ is passed as an array to some GLPK
API routine, the latter expects vector components to be placed in
locations \verb|x[1]|, \verb|x[2]|, \dots, \verb|x[n]|, and the location
\verb|x[0]| normally is not used.

In order to avoid indexing errors it is most convenient and most
reliable to declare the array \verb|x| as follows:

\begin{verbatim}
   double x[1+n];
\end{verbatim}

\noindent
or to allocate it as follows:

\begin{verbatim}
   double *x;
   . . .
   x = calloc(1+n, sizeof(double));
\end{verbatim}

\noindent
In both cases one extra location \verb|x[0]| is reserved that allows
passing the array to GLPK routines in a usual way.

\section{Problem object}

All GLPK API routines deal with so called {\it problem object}, which
is a program object of type \verb|glp_prob| and intended to represent
a particular LP or MIP instance.

The type \verb|glp_prob| is a data structure declared in the header
file \verb|glpk.h| as follows:

\begin{verbatim}
   typedef struct { ... } glp_prob;
\end{verbatim}

Problem objects (i.e. program objects of the \verb|glp_prob| type) are
allocated and managed internally by the GLPK API routines. The
application program should never use any members of the \verb|glp_prob|
structure directly and should deal only with pointers to these objects
(that is, \verb|glp_prob *| values).

\pagebreak

The problem object consists of five segments, which are:

$\bullet$ problem segment,

$\bullet$ basis segment,

$\bullet$ interior point segment,

$\bullet$ MIP segment, and

$\bullet$ control parameters and statistics segment.

\subsubsection*{Problem segment}

The {\it problem segment} contains original LP/MIP data, which
corresponds to the problem formulation (1.1)---(1.3) (see Section
\ref{seclp}, page \pageref{seclp}). It includes the following
components:

$\bullet$ rows (auxiliary variables),

$\bullet$ columns (structural variables),

$\bullet$ objective function, and

$\bullet$ constraint matrix.

Rows and columns have the same set of the following attributes:

$\bullet$ ordinal number,

$\bullet$ symbolic name (1 up to 255 arbitrary graphic characters),

$\bullet$ type (free, lower bound, upper bound, double bound, fixed),

$\bullet$ numerical values of lower and upper bounds,

$\bullet$ scale factor.

{\it Ordinal numbers} are intended for referencing rows and columns.
Row ordinal numbers are integers $1, 2, \dots, m$, and column ordinal
numbers are integers $1, 2, \dots, n$, where $m$ and $n$ are,
respectively, the current number of rows and columns in the problem
object.

{\it Symbolic names} are intended for informational purposes. They also
can be used for referencing rows and columns.

{\it Types and bounds} of rows (auxiliary variables) and columns
(structural variables) are explained above (see Section \ref{seclp},
page \pageref{seclp}).

{\it Scale factors} are used internally for scaling rows and columns of
the constraint matrix.

Information about the {\it objective function} includes numerical
values of objective coefficients and a flag, which defines the
optimization direction (i.e. minimization or maximization).

The {\it constraint matrix} is a $m \times n$ rectangular matrix built
of constraint coefficients $a_{ij}$, which defines the system of linear
constraints (1.2) (see Section \ref{seclp}, page \pageref{seclp}). This
matrix is stored in the problem object in both row-wise and column-wise
sparse formats.

Once the problem object has been created, the application program can
access and modify any components of the problem segment in arbitrary
order.

\subsubsection*{Basis segment}

The {\it basis segment} of the problem object keeps information related
to the current basic solution. It includes:

$\bullet$ row and column statuses,

$\bullet$ basic solution statuses,

$\bullet$ factorization of the current basis matrix, and

$\bullet$ basic solution components.

The {\it row and column statuses} define which rows and columns are
basic and which are non-basic. These statuses may be assigned either by
the application program of by some API routines. Note that these
statuses are always defined independently on whether the corresponding
basis is valid or not.

The {\it basic solution statuses} include the {\it primal status} and
the {\it dual status}, which are set by the simplex-based solver once
the problem has been solved. The primal status shows whether a primal
basic solution is feasible, infeasible, or undefined. The dual status
shows the same for a dual basic solution.

The {\it factorization of the basis matrix} is some factorized form
(like LU-factorization) of the current basis matrix (defined by the
current row and column statuses). The factorization is used by the
simplex-based solver and kept when the solver terminates the search.
This feature allows efficiently reoptimizing the problem after some
modifications (for example, after changing some bounds or objective
coefficients). It also allows performing the post-optimal analysis (for
example, computing components of the simplex table, etc.).

The {\it basic solution components} include primal and dual values of
all auxiliary and structural variables for the most recently obtained
basic solution.

\subsubsection*{Interior point segment}

The {\it interior point segment} is automatically allocated after the
problem has been solved using the interior point solver. It contains
interior point solution components, which include the solution status,
and primal and dual values of all auxiliary and structural variables.

\subsubsection*{MIP segment}

The {\it MIP segment} is used only for MIP problems. This segment
includes:

$\bullet$ column kinds,

$\bullet$ MIP solution status, and

$\bullet$ MIP solution components.

The {\it column kinds} define which columns (i.e. structural variables)
are integer and which are continuous.

The {\it MIP solution status} is set by the MIP solver and shows whether
a MIP solution is integer optimal, integer feasible (non-optimal), or
undefined.

The {\it MIP solution components} are computed by the MIP solver and
include primal values of all auxiliary and structural variables for the
most recently obtained MIP solution.

Note that in case of MIP problem the basis segment corresponds to
the optimal solution of LP relaxation, which is also available to the
application program.

Currently the search tree is not kept in the MIP segment. Therefore if
the search has been terminated, it cannot be continued.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\section{Problem creating and modifying routines}

\subsection{glp\_create\_prob---create problem object}

\subsubsection*{Synopsis}

\begin{verbatim}
glp_prob *glp_create_prob(void);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_create_prob| creates a new problem object, which
initially is ``empty'', i.e. has no rows and columns.

\subsubsection*{Returns}

The routine returns a pointer to the created object, which should be
used in any subsequent operations on this object.

\subsection{glp\_set\_prob\_name---assign (change) problem name}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_prob_name(glp_prob *lp, const char *name);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_prob_name| assigns a given symbolic
\verb|name| (1 up to 255 characters) to the specified problem object.

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

\subsection{glp\_set\_obj\_name---assign (change) objective function
name}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_obj_name(glp_prob *lp, const char *name);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_obj_name| assigns a given symbolic
\verb|name| (1 up to 255 characters) to the objective function of the
specified problem object.

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

\subsection{glp\_set\_obj\_dir---set (change) optimization direction\\
flag}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_obj_dir(glp_prob *lp, int dir);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_obj_dir| sets (changes) the optimization
direction flag (i.e. ``sense'' of the objective function) as specified
by the parameter \verb|dir|:

\begin{tabular}{@{}ll}
\verb|GLP_MIN| & minimization; \\
\verb|GLP_MAX| & maximization. \\
\end{tabular}

\noindent
(Note that by default the problem is minimization.)

\subsection{glp\_add\_rows---add new rows to problem object}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_add_rows(glp_prob *lp, int nrs);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_add_rows| adds \verb|nrs| rows (constraints) to
the specified problem object. New rows are always added to the end of
the row list, so the ordinal numbers of existing rows are not changed.

Being added each new row is initially free (unbounded) and has empty
list of the constraint coefficients.

\subsubsection*{Returns}

The routine \verb|glp_add_rows| returns the ordinal number of the first
new row added to the problem object.

\newpage

\subsection{glp\_add\_cols---add new columns to problem object}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_add_cols(glp_prob *lp, int ncs);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_add_cols| adds \verb|ncs| columns (structural
variables) to the specified problem object. New columns are always added
to the end of the column list, so the ordinal numbers of existing
columns are not changed.

Being added each new column is initially fixed at zero and has empty
list of the constraint coefficients.

\subsubsection*{Returns}

The routine \verb|glp_add_cols| returns the ordinal number of the first
new column added to the problem object.

\subsection{glp\_set\_row\_name---assign (change) row name}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_row_name(glp_prob *lp, int i, const char *name);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_row_name| assigns a given symbolic
\verb|name| (1 up to 255 characters) to \verb|i|-th row (auxiliary
variable) of the specified problem object.

If the parameter \verb|name| is \verb|NULL| or empty string, the routine
erases an existing name of $i$-th row.

\subsection{glp\_set\_col\_name---assign (change) column name}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_col_name(glp_prob *lp, int j, const char *name);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_col_name| assigns a given symbolic
\verb|name| (1 up to 255 characters) to \verb|j|-th column (structural
variable) of the specified problem object.

If the parameter \verb|name| is \verb|NULL| or empty string, the routine
erases an existing name of $j$-th column.

\subsection{glp\_set\_row\_bnds---set (change) row bounds}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_row_bnds(glp_prob *lp, int i, int type,
      double lb, double ub);
\end{verbatim}