glpk04.tex

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

%* glpk04.tex *%

\chapter{Advanced API Routines}

\section{LP basis and simplex tableau routines}
\label{lpbasis}

\subsection{Background}
\label{subsecbasbgd}

Using vector and matrix notations LP problem (1.1)---(1.3) (see Section
\ref{seclp}, page \pageref{seclp}) can be stated as follows:

\medskip

\noindent
\hspace{.5in} minimize (or maximize)
$$z=c^Tx_S+c_0\eqno(3.1)$$
\hspace{.5in} subject to linear constraints
$$x_R=Ax_S\eqno(3.2)$$
\hspace{.5in} and bounds of variables
$$
\begin{array}{l@{\ }c@{\ }l@{\ }c@{\ }l}
l_R&\leq&x_R&\leq&u_R\\
l_S&\leq&x_S&\leq&u_S\\
\end{array}\eqno(3.3)
$$
where:

\noindent
$x_R=(x_1,x_2,\dots,x_m)$ is the vector of auxiliary variables;

\noindent
$x_S=(x_{m+1},x_{m+2},\dots,x_{m+n})$ is the vector of structural
variables;

\noindent
$z$ is the objective function;

\noindent
$c=(c_1,c_2,\dots,c_n)$ is the vector of objective coefficients;

\noindent
$c_0$ is the constant term (``shift'') of the objective function;

\noindent
$A=(a_{11},a_{12},\dots,a_{mn})$ is the constraint matrix;

\noindent
$l_R=(l_1,l_2,\dots,l_m)$ is the vector of lower bounds of auxiliary
variables;

\noindent
$u_R=(u_1,u_2,\dots,u_m)$ is the vector of upper bounds of auxiliary
variables;

\noindent
$l_S=(l_{m+1},l_{m+2},\dots,l_{m+n})$ is the vector of lower bounds of
structural variables;

\noindent
$u_S={u_{m+1},u_{m+2},\dots,u_{m+n}}$ is the vector of upper bounds of
structural variables.

\medskip

From the simplex method's standpoint there is no difference between
auxiliary and structural variables. This allows combining all these
variables into one vector that leads to the following problem statement:

\medskip

\noindent
\hspace{.5in} minimize (or maximize)
$$z=(0\ |\ c)^Tx+c_0\eqno(3.4)$$
\hspace{.5in} subject to linear constraints
$$(I\ |-\!A)x=0\eqno(3.5)$$
\hspace{.5in} and bounds of variables
$$l\leq x\leq u\eqno(3.6)$$
where:

\noindent
$x=(x_R\ |\ x_S)$ is the $(m+n)$-vector of (all) variables;

\noindent
$(0\ |\ c)$ is the $(m+n)$-vector of objective
coefficients;\footnote{Subvector 0 corresponds to objective coefficients
at auxiliary variables.}

\noindent
$(I\ |-\!A)$ is the {\it augmented} constraint
$m\times(m+n)$-matrix;\footnote{Note that due to auxiliary variables
matrix $(I\ |-\!A)$ contains the unity submatrix and therefore has full
rank. This means, in particular, that the system (3.5) has no linearly
dependent constraints.}

\noindent
$l=(l_R\ |\ l_S)$ is the $(m+n)$-vector of lower bounds of (all)
variables;

\noindent
$u=(u_R\ |\ u_S)$ is the $(m+n)$-vector of upper bounds of (all)
variables.

\medskip

By definition an {\it LP basic solution} geometrically is a point in
the space of all variables, which is the intersection of planes
corresponding to active constraints\footnote{A constraint is called
{\it active} if in a given point it is satisfied as equality, otherwise
it is called {\it inactive}.}. The space of all variables has the
dimension $m+n$, therefore, to define some basic solution we have to
define $m+n$ active constraints. Note that $m$ constraints (3.5) being
linearly independent equalities are always active, so remaining $n$
active constraints can be chosen only from bound constraints (3.6).

A variable is called {\it non-basic}, if its (lower or upper) bound is
active, otherwise it is called {\it basic}. Since, as was said above,
exactly $n$ bound constraints must be active, in any basic solution
there are always $n$ non-basic variables and $m$ basic variables.
(Note that a free variable also can be non-basic. Although such
variable has no bounds, we can think it as the difference between two
non-negative variables, which both are non-basic in this case.)

Now consider how to determine numeric values of all variables for a
given basic solution.

Let $\Pi$ be an appropriate permutation matrix of the order $(m+n)$.
Then we can write:
$$\left(\begin{array}{@{}c@{}}x_B\\x_N\\\end{array}\right)=
\Pi\left(\begin{array}{@{}c@{}}x_R\\x_S\\\end{array}\right)=\Pi x,
\eqno(3.7)$$
where $x_B$ is the vector of basic variables, $x_N$ is the vector of
non-basic variables, $x=(x_R\ |\ x_S)$ is the vector of all variables
in the original order. In this case the system of linear constraints
(3.5) can be rewritten as follows:
$$(I\ |-\!A)\Pi^T\Pi x=0\ \ \ \Rightarrow\ \ \ (B\ |\ N)
\left(\begin{array}{@{}c@{}}x_B\\x_N\\\end{array}\right)=0,\eqno(3.8)$$
where
$$(B\ |\ N)=(I\ |-\!A)\Pi^T.\eqno(3.9)$$
Matrix $B$ is a square non-singular $m\times m$-matrix, which is
composed from columns of the augmented constraint matrix corresponding
to basic variables. It is called the {\it basis matrix} or simply the
{\it basis}. Matrix $N$ is a rectangular $m\times n$-matrix, which is
composed from columns of the augmented constraint matrix corresponding
to non-basic variables.

From (3.8) it follows that:
$$Bx_B+Nx_N=0,\eqno(3.10)$$
therefore,
$$x_B=-B^{-1}Nx_N.\eqno(3.11)$$
Thus, the formula (3.11) shows how to determine numeric values of basic
variables $x_B$ assuming that non-basic variables $x_N$ are fixed on
their active bounds.

The $m\times n$-matrix
$$\Xi=-B^{-1}N,\eqno(3.12)$$
which appears in (3.11), is called the {\it simplex
tableau}.\footnote{This definition corresponds to the GLPK
implementation.} It shows how basic variables depend on non-basic
variables:
$$x_B=\Xi x_N.\eqno(3.13)$$

The system (3.13) is equivalent to the system (3.5) in the sense that
they both define the same set of points in the space of (primal)
variables, which satisfy to these systems. If, moreover, values of all
basic variables satisfy to their bound constraints (3.3), the
corresponding basic solution is called {\it (primal) feasible},
otherwise {\it (primal) infeasible}. It is understood that any (primal)
feasible basic solution satisfy to all constraints (3.2) and (3.3).

The LP theory says that if LP has optimal solution, it has (at least
one) basic feasible solution, which corresponds to the optimum. And the
most natural way to determine whether a given basic solution is optimal
or not is to use the Karush---Kuhn---Tucker optimality conditions.

\def\arraystretch{1.5}

For the problem statement (3.4)---(3.6) the optimality conditions are
the following:\footnote{These conditions can be appiled to any solution,
not only to a basic solution.}
$$(I\ |-\!A)x=0\eqno(3.14)$$
$$(I\ |-\!A)^T\pi+\lambda_l+\lambda_u=\nabla z=(0\ |\ c)^T\eqno(3.15)$$
$$l\leq x\leq u\eqno(3.16)$$
$$\lambda_l\geq 0,\ \ \lambda_u\leq 0\ \ \mbox{(minimization)}
\eqno(3.17)$$
$$\lambda_l\leq 0,\ \ \lambda_u\geq 0\ \ \mbox{(maximization)}
\eqno(3.18)$$
$$(\lambda_l)_k(x_k-l_k)=0,\ \ (\lambda_u)_k(x_k-u_k)=0,\ \ k=1,2,\dots,
m+n\eqno(3.19)$$
where:
$\pi=(\pi_1,\pi_2,\dots,\pi_m)$ is a $m$-vector of Lagrange
multipliers for equality constraints (3.5);
$\lambda_l=[(\lambda_l)_1,(\lambda_l)_2,\dots,(\lambda_l)_n]$ is a
$n$-vector of Lagrange multipliers for lower bound constraints (3.6);
$\lambda_u=[(\lambda_u)_1,(\lambda_u)_2,\dots,(\lambda_u)_n]$ is a
$n$-vector of Lagrange multipliers for upper bound constraints (3.6).

Condition (3.14) is the {\it primal} (original) system of equality
constraints (3.5).

Condition (3.15) is the {\it dual} system of equality constraints.
It requires the gradient of the objective function to be a linear
combination of normals to the planes defined by constraints of the
original problem.

Condition (3.16) is the primal (original) system of bound constraints
(3.6).

Condition (3.17) (or (3.18) in case of maximization) is the dual system
of bound constraints.

Condition (3.19) is the {\it complementary slackness condition}. It
requires, for each original (auxiliary or structural) variable $x_k$,
that either its (lower or upper) bound must be active, or zero bound of
the corresponding Lagrange multiplier ($(\lambda_l)_k$ or
$(\lambda_u)_k$) must be active.

In GLPK two multipliers $(\lambda_l)_k$ and $(\lambda_u)_k$ for each
primal (original) variable $x_k$, $k=1,2,\dots,m+n$, are combined into
one multiplier:
$$\lambda_k=(\lambda_l)_k+(\lambda_u)_k,\eqno(3.20)$$
which is called a {\it dual variable} for $x_k$. This {\it cannot} lead
to the ambiguity, because both lower and upper bounds of $x_k$ cannot be
active at the same time,\footnote{If $x_k$ is a fixed variable, we can
think it as double-bounded variable $l_k\leq x_k\leq u_k$, where
$l_k=u_k.$} so at least one of $(\lambda_l)_k$ and $(\lambda_u)_k$ must
be equal to zero, and because these multipliers have different signs,
the combined multiplier, which is their sum, uniquely defines each of
them.

\def\arraystretch{1}

Using dual variables $\lambda_k$ the dual system of bound constraints
(3.17) and (3.18) can be written in the form of so called {\it ``rule of
signs''} as follows:

\begin{center}
\begin{tabular}{|@{\,}c@{$\,$}|@{$\,$}c@{$\,$}|@{$\,$}c@{$\,$}|
@{$\,$}c|c@{$\,$}|@{$\,$}c@{$\,$}|@{$\,$}c@{$\,$}|}
\hline
Original bound&\multicolumn{3}{c|}{Minimization}&\multicolumn{3}{c|}
{Maximization}\\
\cline{2-7}
constraint&$(\lambda_l)_k$&$(\lambda_u)_k$&$(\lambda_l)_k+
(\lambda_u)_k$&$(\lambda_l)_k$&$(\lambda_u)_k$&$(\lambda_l)_k+
(\lambda_u)_k$\\
\hline
$-\infty<x_k<+\infty$&$=0$&$=0$&$\lambda_k=0$&$=0$&$=0$&$\lambda_k=0$\\
$x_k\geq l_k$&$\geq 0$&$=0$&$\lambda_k\geq 0$&$\leq 0$&$=0$&$\lambda_k
\leq0$\\
$x_k\leq u_k$&$=0$&$\leq 0$&$\lambda_k\leq 0$&$=0$&$\geq 0$&$\lambda_k
\geq0$\\
$l_k\leq x_k\leq u_k$&$\geq 0$& $\leq 0$& $-\infty\!<\!\lambda_k\!<
\!+\infty$
&$\leq 0$& $\geq 0$& $-\infty\!<\!\lambda_k\!<\!+\infty$\\
$x_k=l_k=u_k$&$\geq 0$& $\leq 0$& $-\infty\!<\!\lambda_k\!<\!+\infty$&
$\leq 0$&
$\geq 0$& $-\infty\!<\!\lambda_k\!<\!+\infty$\\
\hline
\end{tabular}
\end{center}

May note that each primal variable $x_k$ has its dual counterpart
$\lambda_k$ and vice versa. This allows applying the same partition for
the vector of dual variables as (3.7):
$$\left(\begin{array}{@{}c@{}}\lambda_B\\\lambda_N\\\end{array}\right)=
\Pi\lambda,\eqno(3.21)$$
where $\lambda_B$ is a vector of dual variables for basic variables
$x_B$, $\lambda_N$ is a vector of dual variables for non-basic variables
$x_N$.

By definition, bounds of basic variables are inactive constraints, so in
any basic solution $\lambda_B=0$. Corresponding values of dual variables
$\lambda_N$ for non-basic variables $x_N$ can be determined in the
following way. From the dual system (3.15) we have:
$$(I\ |-\!A)^T\pi+\lambda=(0\ |\ c)^T,\eqno(3.22)$$
so multiplying both sides of (3.22) by matrix $\Pi$ gives:
$$\Pi(I\ |-\!A)^T\pi+\Pi\lambda=\Pi(0\ |\ c)^T.\eqno(3.23)$$
From (3.9) it follows that
$$\Pi(I\ |-\!A)^T=[(I\ |-\!A)\Pi^T]^T=(B\ |\ N)^T.\eqno(3.24)$$
Further, we can apply the partition (3.7) also to the vector of
objective coefficients (see (3.4)):
$$\left(\begin{array}{@{}c@{}}c_B\\c_N\\\end{array}\right)=
\Pi\left(\begin{array}{@{}c@{}}0\\c\\\end{array}\right),\eqno(3.25)$$
where $c_B$ is a vector of objective coefficients at basic variables,
$c_N$ is a vector of objective coefficients at non-basic variables.
Now, substituting (3.24), (3.21), and (3.25) into (3.23), leads to:
$$(B\ |\ N)^T\pi+(\lambda_B\ |\ \lambda_N)^T=(c_B\ |\ c_N)^T,
\eqno(3.26)$$
and transposing both sides of (3.26) gives the system:
$$\left(\begin{array}{@{}c@{}}B^T\\N^T\\\end{array}\right)\pi+
\left(\begin{array}{@{}c@{}}\lambda_B\\\lambda_N\\\end{array}\right)=
\left(\begin{array}{@{}c@{}}c_B\\c_T\\\end{array}\right),\eqno(3.27)$$
which can be written as follows:
$$\left\{
\begin{array}{@{\ }r@{\ }c@{\ }r@{\ }c@{\ }l@{\ }}
B^T\pi&+&\lambda_B&=&c_B\\
N^T\pi&+&\lambda_N&=&c_N\\
\end{array}
\right.\eqno(3.28)
$$
Lagrange multipliers $\pi=(\pi_i)$ correspond to equality constraints
(3.5) and therefore can have any sign. This allows resolving the first
subsystem of (3.28) as follows:\footnote{$B^{-T}$ means $(B^T)^{-1}=
(B^{-1})^T$.}
$$\pi=B^{-T}(c_B-\lambda_B)=-B^{-T}\lambda_B+B^{-T}c_B,\eqno(3.29)$$
and substitution of $\pi$ from (3.29) into the second subsystem of
(3.28) gives:
$$\lambda_N=-N^T\pi+c_N=N^TB^{-T}\lambda_B+(c_N-N^TB^{-T}c_B).
\eqno(3.30)$$
The latter system can be written in the following final form:
$$\lambda_N=-\Xi^T\lambda_B+d,\eqno(3.31)$$
where $\Xi$ is the simplex tableau (see (3.12)), and
$$d=c_N-N^TB^{-T}c_B=c_N+\Xi^Tc_B\eqno(3.32)$$
is the vector of so called {\it reduced costs} of non-basic variables.

\pagebreak

Above it was said that in any basic solution $\lambda_B=0$, so
$\lambda_N=d$ as it follows from (3.31).

The system (3.31) is equivalent to the system (3.15) in the sense that
they both define the same set of points in the space of dual variables
$\lambda$, which satisfy to these systems. If, moreover, values of all
dual variables $\lambda_N$ (i.e. reduced costs $d$) satisfy to their
bound constraints (i.e. to the ``rule of signs''; see the table above),
the corresponding basic solution is called {\it dual feasible},
otherwise {\it dual infeasible}. It is understood that any dual feasible
solution satisfy to all constraints (3.15) and (3.17) (or (3.18) in case
of maximization).

It can be easily shown that the complementary slackness condition
(3.19) is always satisfied for {\it any} basic solution. Therefore,
a basic solution\footnote{It is assumed that a complete basic solution
has the form $(x,\lambda)$, i.e. it includes primal as well as dual
variables.} is {\it optimal} if and only if it is primal and dual
feasible, because in this case it satifies to all the optimality
conditions (3.14)---(3.19).

\def\arraystretch{1.5}

The meaning of reduced costs $d=(d_j)$ of non-basic variables can be
explained in the following way. From (3.4), (3.7), and (3.25) it follows
that:
$$z=c_B^Tx_B+c_N^Tx_N+c_0.\eqno(3.33)$$
Substituting $x_B$ from (3.11) into (3.33) we can eliminate basic
variables and express the objective only through non-basic variables:
$$
\begin{array}{r@{\ }c@{\ }l}
z&=&c_B^T(-B^{-1}Nx_N)+c_N^Tx_N+c_0=\\
&=&(c_N^T-c_B^TB^{-1}N)x_N+c_0=\\
&=&(c_N-N^TB^{-T}c_B)^Tx_N+c_0=\\
&=&d^Tx_N+c_0.
\end{array}\eqno(3.34)
$$
From (3.34) it is seen that reduced cost $d_j$ shows how the objective
function $z$ depends on non-basic variable $(x_N)_j$ in the neighborhood
of the current basic solution, i.e. while the current basis remains
unchanged.

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

\newpage

\subsection{glp\_bf\_exists---check if the basis factorization exists}

\subsubsection*{Synopsis}

\begin{verbatim}