alpar@1: %* glpk04.tex *%
alpar@1: 
alpar@1: \chapter{Advanced API Routines}
alpar@1: 
alpar@1: \section{Background}
alpar@1: \label{basbgd}
alpar@1: 
alpar@1: Using vector and matrix notations LP problem (1.1)---(1.3) (see Section
alpar@1: \ref{seclp}, page \pageref{seclp}) can be stated as follows:
alpar@1: 
alpar@1: \medskip
alpar@1: 
alpar@1: \noindent
alpar@1: \hspace{.5in} minimize (or maximize)
alpar@1: $$z=c^Tx_S+c_0\eqno(3.1)$$
alpar@1: \hspace{.5in} subject to linear constraints
alpar@1: $$x_R=Ax_S\eqno(3.2)$$
alpar@1: \hspace{.5in} and bounds of variables
alpar@1: $$
alpar@1: \begin{array}{l@{\ }c@{\ }l@{\ }c@{\ }l}
alpar@1: l_R&\leq&x_R&\leq&u_R\\
alpar@1: l_S&\leq&x_S&\leq&u_S\\
alpar@1: \end{array}\eqno(3.3)
alpar@1: $$
alpar@1: where:
alpar@1: 
alpar@1: \noindent
alpar@1: $x_R=(x_1,\dots,x_m)$ is the vector of auxiliary variables;
alpar@1: 
alpar@1: \noindent
alpar@1: $x_S=(x_{m+1},\dots,x_{m+n})$ is the vector of structural
alpar@1: variables;
alpar@1: 
alpar@1: \noindent
alpar@1: $z$ is the objective function;
alpar@1: 
alpar@1: \noindent
alpar@1: $c=(c_1,\dots,c_n)$ is the vector of objective coefficients;
alpar@1: 
alpar@1: \noindent
alpar@1: $c_0$ is the constant term (``shift'') of the objective function;
alpar@1: 
alpar@1: \noindent
alpar@1: $A=(a_{11},\dots,a_{mn})$ is the constraint matrix;
alpar@1: 
alpar@1: \noindent
alpar@1: $l_R=(l_1,\dots,l_m)$ is the vector of lower bounds of auxiliary
alpar@1: variables;
alpar@1: 
alpar@1: \noindent
alpar@1: $u_R=(u_1,\dots,u_m)$ is the vector of upper bounds of auxiliary
alpar@1: variables;
alpar@1: 
alpar@1: \noindent
alpar@1: $l_S=(l_{m+1},\dots,l_{m+n})$ is the vector of lower bounds of
alpar@1: structural variables;
alpar@1: 
alpar@1: \noindent
alpar@1: $u_S=(u_{m+1},\dots,u_{m+n})$ is the vector of upper bounds of
alpar@1: structural variables.
alpar@1: 
alpar@1: \medskip
alpar@1: 
alpar@1: From the simplex method's standpoint there is no difference between
alpar@1: auxiliary and structural variables. This allows combining all these
alpar@1: variables into one vector that leads to the following problem statement:
alpar@1: 
alpar@1: \medskip
alpar@1: 
alpar@1: \noindent
alpar@1: \hspace{.5in} minimize (or maximize)
alpar@1: $$z=(0\ |\ c)^Tx+c_0\eqno(3.4)$$
alpar@1: \hspace{.5in} subject to linear constraints
alpar@1: $$(I\ |-\!A)x=0\eqno(3.5)$$
alpar@1: \hspace{.5in} and bounds of variables
alpar@1: $$l\leq x\leq u\eqno(3.6)$$
alpar@1: where:
alpar@1: 
alpar@1: \noindent
alpar@1: $x=(x_R\ |\ x_S)$ is the $(m+n)$-vector of (all) variables;
alpar@1: 
alpar@1: \noindent
alpar@1: $(0\ |\ c)$ is the $(m+n)$-vector of objective
alpar@1: coefficients;\footnote{Subvector 0 corresponds to objective coefficients
alpar@1: at auxiliary variables.}
alpar@1: 
alpar@1: \noindent
alpar@1: $(I\ |-\!A)$ is the {\it augmented} constraint
alpar@1: $m\times(m+n)$-matrix;\footnote{Note that due to auxiliary variables
alpar@1: matrix $(I\ |-\!A)$ contains the unity submatrix and therefore has full
alpar@1: rank. This means, in particular, that the system (3.5) has no linearly
alpar@1: dependent constraints.}
alpar@1: 
alpar@1: \noindent
alpar@1: $l=(l_R\ |\ l_S)$ is the $(m+n)$-vector of lower bounds of (all)
alpar@1: variables;
alpar@1: 
alpar@1: \noindent
alpar@1: $u=(u_R\ |\ u_S)$ is the $(m+n)$-vector of upper bounds of (all)
alpar@1: variables.
alpar@1: 
alpar@1: \medskip
alpar@1: 
alpar@1: By definition an {\it LP basic solution} geometrically is a point in
alpar@1: the space of all variables, which is the intersection of planes
alpar@1: corresponding to active constraints\footnote{A constraint is called
alpar@1: {\it active} if in a given point it is satisfied as equality, otherwise
alpar@1: it is called {\it inactive}.}. The space of all variables has the
alpar@1: dimension $m+n$, therefore, to define some basic solution we have to
alpar@1: define $m+n$ active constraints. Note that $m$ constraints (3.5) being
alpar@1: linearly independent equalities are always active, so remaining $n$
alpar@1: active constraints can be chosen only from bound constraints (3.6).
alpar@1: 
alpar@1: A variable is called {\it non-basic}, if its (lower or upper) bound is
alpar@1: active, otherwise it is called {\it basic}. Since, as was said above,
alpar@1: exactly $n$ bound constraints must be active, in any basic solution
alpar@1: there are always $n$ non-basic variables and $m$ basic variables.
alpar@1: (Note that a free variable also can be non-basic. Although such
alpar@1: variable has no bounds, we can think it as the difference between two
alpar@1: non-negative variables, which both are non-basic in this case.)
alpar@1: 
alpar@1: Now consider how to determine numeric values of all variables for a
alpar@1: given basic solution.
alpar@1: 
alpar@1: Let $\Pi$ be an appropriate permutation matrix of the order $(m+n)$.
alpar@1: Then we can write:
alpar@1: $$\left(\begin{array}{@{}c@{}}x_B\\x_N\\\end{array}\right)=
alpar@1: \Pi\left(\begin{array}{@{}c@{}}x_R\\x_S\\\end{array}\right)=\Pi x,
alpar@1: \eqno(3.7)$$
alpar@1: where $x_B$ is the vector of basic variables, $x_N$ is the vector of
alpar@1: non-basic variables, $x=(x_R\ |\ x_S)$ is the vector of all variables
alpar@1: in the original order. In this case the system of linear constraints
alpar@1: (3.5) can be rewritten as follows:
alpar@1: $$(I\ |-\!A)\Pi^T\Pi x=0\ \ \ \Rightarrow\ \ \ (B\ |\ N)
alpar@1: \left(\begin{array}{@{}c@{}}x_B\\x_N\\\end{array}\right)=0,\eqno(3.8)$$
alpar@1: where
alpar@1: $$(B\ |\ N)=(I\ |-\!A)\Pi^T.\eqno(3.9)$$
alpar@1: Matrix $B$ is a square non-singular $m\times m$-matrix, which is
alpar@1: composed from columns of the augmented constraint matrix corresponding
alpar@1: to basic variables. It is called the {\it basis matrix} or simply the
alpar@1: {\it basis}. Matrix $N$ is a rectangular $m\times n$-matrix, which is
alpar@1: composed from columns of the augmented constraint matrix corresponding
alpar@1: to non-basic variables.
alpar@1: 
alpar@1: From (3.8) it follows that:
alpar@1: $$Bx_B+Nx_N=0,\eqno(3.10)$$
alpar@1: therefore,
alpar@1: $$x_B=-B^{-1}Nx_N.\eqno(3.11)$$
alpar@1: Thus, the formula (3.11) shows how to determine numeric values of basic
alpar@1: variables $x_B$ assuming that non-basic variables $x_N$ are fixed on
alpar@1: their active bounds.
alpar@1: 
alpar@1: The $m\times n$-matrix
alpar@1: $$\Xi=-B^{-1}N,\eqno(3.12)$$
alpar@1: which appears in (3.11), is called the {\it simplex
alpar@1: tableau}.\footnote{This definition corresponds to the GLPK
alpar@1: implementation.} It shows how basic variables depend on non-basic
alpar@1: variables:
alpar@1: $$x_B=\Xi x_N.\eqno(3.13)$$
alpar@1: 
alpar@1: The system (3.13) is equivalent to the system (3.5) in the sense that
alpar@1: they both define the same set of points in the space of (primal)
alpar@1: variables, which satisfy to these systems. If, moreover, values of all
alpar@1: basic variables satisfy to their bound constraints (3.3), the
alpar@1: corresponding basic solution is called {\it (primal) feasible},
alpar@1: otherwise {\it (primal) infeasible}. It is understood that any (primal)
alpar@1: feasible basic solution satisfy to all constraints (3.2) and (3.3).
alpar@1: 
alpar@1: The LP theory says that if LP has optimal solution, it has (at least
alpar@1: one) basic feasible solution, which corresponds to the optimum. And the
alpar@1: most natural way to determine whether a given basic solution is optimal
alpar@1: or not is to use the Karush---Kuhn---Tucker optimality conditions.
alpar@1: 
alpar@1: \def\arraystretch{1.5}
alpar@1: 
alpar@1: For the problem statement (3.4)---(3.6) the optimality conditions are
alpar@1: the following:\footnote{These conditions can be appiled to any solution,
alpar@1: not only to a basic solution.}
alpar@1: $$(I\ |-\!A)x=0\eqno(3.14)$$
alpar@1: $$(I\ |-\!A)^T\pi+\lambda_l+\lambda_u=\nabla z=(0\ |\ c)^T\eqno(3.15)$$
alpar@1: $$l\leq x\leq u\eqno(3.16)$$
alpar@1: $$\lambda_l\geq 0,\ \ \lambda_u\leq 0\ \ \mbox{(minimization)}
alpar@1: \eqno(3.17)$$
alpar@1: $$\lambda_l\leq 0,\ \ \lambda_u\geq 0\ \ \mbox{(maximization)}
alpar@1: \eqno(3.18)$$
alpar@1: $$(\lambda_l)_k(x_k-l_k)=0,\ \ (\lambda_u)_k(x_k-u_k)=0,\ \ k=1,2,\dots,
alpar@1: m+n\eqno(3.19)$$
alpar@1: where:
alpar@1: $\pi=(\pi_1,\pi_2,\dots,\pi_m)$ is a $m$-vector of Lagrange
alpar@1: multipliers for equality constraints (3.5);
alpar@1: $\lambda_l=[(\lambda_l)_1,(\lambda_l)_2,\dots,(\lambda_l)_n]$ is a
alpar@1: $n$-vector of Lagrange multipliers for lower bound constraints (3.6);
alpar@1: $\lambda_u=[(\lambda_u)_1,(\lambda_u)_2,\dots,(\lambda_u)_n]$ is a
alpar@1: $n$-vector of Lagrange multipliers for upper bound constraints (3.6).
alpar@1: 
alpar@1: Condition (3.14) is the {\it primal} (original) system of equality
alpar@1: constraints (3.5).
alpar@1: 
alpar@1: Condition (3.15) is the {\it dual} system of equality constraints.
alpar@1: It requires the gradient of the objective function to be a linear
alpar@1: combination of normals to the planes defined by constraints of the
alpar@1: original problem.
alpar@1: 
alpar@1: Condition (3.16) is the primal (original) system of bound constraints
alpar@1: (3.6).
alpar@1: 
alpar@1: Condition (3.17) (or (3.18) in case of maximization) is the dual system
alpar@1: of bound constraints.
alpar@1: 
alpar@1: Condition (3.19) is the {\it complementary slackness condition}. It
alpar@1: requires, for each original (auxiliary or structural) variable $x_k$,
alpar@1: that either its (lower or upper) bound must be active, or zero bound of
alpar@1: the corresponding Lagrange multiplier ($(\lambda_l)_k$ or
alpar@1: $(\lambda_u)_k$) must be active.
alpar@1: 
alpar@1: In GLPK two multipliers $(\lambda_l)_k$ and $(\lambda_u)_k$ for each
alpar@1: primal (original) variable $x_k$, $k=1,2,\dots,m+n$, are combined into
alpar@1: one multiplier:
alpar@1: $$\lambda_k=(\lambda_l)_k+(\lambda_u)_k,\eqno(3.20)$$
alpar@1: which is called a {\it dual variable} for $x_k$. This {\it cannot} lead
alpar@1: to the ambiguity, because both lower and upper bounds of $x_k$ cannot be
alpar@1: active at the same time,\footnote{If $x_k$ is a fixed variable, we can
alpar@1: think it as double-bounded variable $l_k\leq x_k\leq u_k$, where
alpar@1: $l_k=u_k.$} so at least one of $(\lambda_l)_k$ and $(\lambda_u)_k$ must
alpar@1: be equal to zero, and because these multipliers have different signs,
alpar@1: the combined multiplier, which is their sum, uniquely defines each of
alpar@1: them.
alpar@1: 
alpar@1: \def\arraystretch{1}
alpar@1: 
alpar@1: Using dual variables $\lambda_k$ the dual system of bound constraints
alpar@1: (3.17) and (3.18) can be written in the form of so called {\it ``rule of
alpar@1: signs''} as follows:
alpar@1: 
alpar@1: \begin{center}
alpar@1: \begin{tabular}{|@{\,}c@{$\,$}|@{$\,$}c@{$\,$}|@{$\,$}c@{$\,$}|
alpar@1: @{$\,$}c|c@{$\,$}|@{$\,$}c@{$\,$}|@{$\,$}c@{$\,$}|}
alpar@1: \hline
alpar@1: Original bound&\multicolumn{3}{c|}{Minimization}&\multicolumn{3}{c|}
alpar@1: {Maximization}\\
alpar@1: \cline{2-7}
alpar@1: constraint&$(\lambda_l)_k$&$(\lambda_u)_k$&$(\lambda_l)_k+
alpar@1: (\lambda_u)_k$&$(\lambda_l)_k$&$(\lambda_u)_k$&$(\lambda_l)_k+
alpar@1: (\lambda_u)_k$\\
alpar@1: \hline
alpar@1: $-\infty<x_k<+\infty$&$=0$&$=0$&$\lambda_k=0$&$=0$&$=0$&$\lambda_k=0$\\
alpar@1: $x_k\geq l_k$&$\geq 0$&$=0$&$\lambda_k\geq 0$&$\leq 0$&$=0$&$\lambda_k
alpar@1: \leq0$\\
alpar@1: $x_k\leq u_k$&$=0$&$\leq 0$&$\lambda_k\leq 0$&$=0$&$\geq 0$&$\lambda_k
alpar@1: \geq0$\\
alpar@1: $l_k\leq x_k\leq u_k$&$\geq 0$& $\leq 0$& $-\infty\!<\!\lambda_k\!<
alpar@1: \!+\infty$
alpar@1: &$\leq 0$& $\geq 0$& $-\infty\!<\!\lambda_k\!<\!+\infty$\\
alpar@1: $x_k=l_k=u_k$&$\geq 0$& $\leq 0$& $-\infty\!<\!\lambda_k\!<\!+\infty$&
alpar@1: $\leq 0$&
alpar@1: $\geq 0$& $-\infty\!<\!\lambda_k\!<\!+\infty$\\
alpar@1: \hline
alpar@1: \end{tabular}
alpar@1: \end{center}
alpar@1: 
alpar@1: May note that each primal variable $x_k$ has its dual counterpart
alpar@1: $\lambda_k$ and vice versa. This allows applying the same partition for
alpar@1: the vector of dual variables as (3.7):
alpar@1: $$\left(\begin{array}{@{}c@{}}\lambda_B\\\lambda_N\\\end{array}\right)=
alpar@1: \Pi\lambda,\eqno(3.21)$$
alpar@1: where $\lambda_B$ is a vector of dual variables for basic variables
alpar@1: $x_B$, $\lambda_N$ is a vector of dual variables for non-basic variables
alpar@1: $x_N$.
alpar@1: 
alpar@1: By definition, bounds of basic variables are inactive constraints, so in
alpar@1: any basic solution $\lambda_B=0$. Corresponding values of dual variables
alpar@1: $\lambda_N$ for non-basic variables $x_N$ can be determined in the
alpar@1: following way. From the dual system (3.15) we have:
alpar@1: $$(I\ |-\!A)^T\pi+\lambda=(0\ |\ c)^T,\eqno(3.22)$$
alpar@1: so multiplying both sides of (3.22) by matrix $\Pi$ gives:
alpar@1: $$\Pi(I\ |-\!A)^T\pi+\Pi\lambda=\Pi(0\ |\ c)^T.\eqno(3.23)$$
alpar@1: From (3.9) it follows that
alpar@1: $$\Pi(I\ |-\!A)^T=[(I\ |-\!A)\Pi^T]^T=(B\ |\ N)^T.\eqno(3.24)$$
alpar@1: Further, we can apply the partition (3.7) also to the vector of
alpar@1: objective coefficients (see (3.4)):
alpar@1: $$\left(\begin{array}{@{}c@{}}c_B\\c_N\\\end{array}\right)=
alpar@1: \Pi\left(\begin{array}{@{}c@{}}0\\c\\\end{array}\right),\eqno(3.25)$$
alpar@1: where $c_B$ is a vector of objective coefficients at basic variables,
alpar@1: $c_N$ is a vector of objective coefficients at non-basic variables.
alpar@1: Now, substituting (3.24), (3.21), and (3.25) into (3.23), leads to:
alpar@1: $$(B\ |\ N)^T\pi+(\lambda_B\ |\ \lambda_N)^T=(c_B\ |\ c_N)^T,
alpar@1: \eqno(3.26)$$
alpar@1: and transposing both sides of (3.26) gives the system:
alpar@1: $$\left(\begin{array}{@{}c@{}}B^T\\N^T\\\end{array}\right)\pi+
alpar@1: \left(\begin{array}{@{}c@{}}\lambda_B\\\lambda_N\\\end{array}\right)=
alpar@1: \left(\begin{array}{@{}c@{}}c_B\\c_T\\\end{array}\right),\eqno(3.27)$$
alpar@1: which can be written as follows:
alpar@1: $$\left\{
alpar@1: \begin{array}{@{\ }r@{\ }c@{\ }r@{\ }c@{\ }l@{\ }}
alpar@1: B^T\pi&+&\lambda_B&=&c_B\\
alpar@1: N^T\pi&+&\lambda_N&=&c_N\\
alpar@1: \end{array}
alpar@1: \right.\eqno(3.28)
alpar@1: $$
alpar@1: Lagrange multipliers $\pi=(\pi_i)$ correspond to equality constraints
alpar@1: (3.5) and therefore can have any sign. This allows resolving the first
alpar@1: subsystem of (3.28) as follows:\footnote{$B^{-T}$ means $(B^T)^{-1}=
alpar@1: (B^{-1})^T$.}
alpar@1: $$\pi=B^{-T}(c_B-\lambda_B)=-B^{-T}\lambda_B+B^{-T}c_B,\eqno(3.29)$$
alpar@1: and substitution of $\pi$ from (3.29) into the second subsystem of
alpar@1: (3.28) gives:
alpar@1: $$\lambda_N=-N^T\pi+c_N=N^TB^{-T}\lambda_B+(c_N-N^TB^{-T}c_B).
alpar@1: \eqno(3.30)$$
alpar@1: The latter system can be written in the following final form:
alpar@1: $$\lambda_N=-\Xi^T\lambda_B+d,\eqno(3.31)$$
alpar@1: where $\Xi$ is the simplex tableau (see (3.12)), and
alpar@1: $$d=c_N-N^TB^{-T}c_B=c_N+\Xi^Tc_B\eqno(3.32)$$
alpar@1: is the vector of so called {\it reduced costs} of non-basic variables.
alpar@1: 
alpar@1: \pagebreak
alpar@1: 
alpar@1: Above it was said that in any basic solution $\lambda_B=0$, so
alpar@1: $\lambda_N=d$ as it follows from (3.31).
alpar@1: 
alpar@1: The system (3.31) is equivalent to the system (3.15) in the sense that
alpar@1: they both define the same set of points in the space of dual variables
alpar@1: $\lambda$, which satisfy to these systems. If, moreover, values of all
alpar@1: dual variables $\lambda_N$ (i.e. reduced costs $d$) satisfy to their
alpar@1: bound constraints (i.e. to the ``rule of signs''; see the table above),
alpar@1: the corresponding basic solution is called {\it dual feasible},
alpar@1: otherwise {\it dual infeasible}. It is understood that any dual feasible
alpar@1: solution satisfy to all constraints (3.15) and (3.17) (or (3.18) in case
alpar@1: of maximization).
alpar@1: 
alpar@1: It can be easily shown that the complementary slackness condition
alpar@1: (3.19) is always satisfied for {\it any} basic solution. Therefore,
alpar@1: a basic solution\footnote{It is assumed that a complete basic solution
alpar@1: has the form $(x,\lambda)$, i.e. it includes primal as well as dual
alpar@1: variables.} is {\it optimal} if and only if it is primal and dual
alpar@1: feasible, because in this case it satifies to all the optimality
alpar@1: conditions (3.14)---(3.19).
alpar@1: 
alpar@1: \def\arraystretch{1.5}
alpar@1: 
alpar@1: The meaning of reduced costs $d=(d_j)$ of non-basic variables can be
alpar@1: explained in the following way. From (3.4), (3.7), and (3.25) it follows
alpar@1: that:
alpar@1: $$z=c_B^Tx_B+c_N^Tx_N+c_0.\eqno(3.33)$$
alpar@1: Substituting $x_B$ from (3.11) into (3.33) we can eliminate basic
alpar@1: variables and express the objective only through non-basic variables:
alpar@1: $$
alpar@1: \begin{array}{r@{\ }c@{\ }l}
alpar@1: z&=&c_B^T(-B^{-1}Nx_N)+c_N^Tx_N+c_0=\\
alpar@1: &=&(c_N^T-c_B^TB^{-1}N)x_N+c_0=\\
alpar@1: &=&(c_N-N^TB^{-T}c_B)^Tx_N+c_0=\\
alpar@1: &=&d^Tx_N+c_0.
alpar@1: \end{array}\eqno(3.34)
alpar@1: $$
alpar@1: From (3.34) it is seen that reduced cost $d_j$ shows how the objective
alpar@1: function $z$ depends on non-basic variable $(x_N)_j$ in the neighborhood
alpar@1: of the current basic solution, i.e. while the current basis remains
alpar@1: unchanged.
alpar@1: 
alpar@1: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@1: 
alpar@1: \newpage
alpar@1: 
alpar@1: \section{LP basis routines}
alpar@1: \label{lpbasis}
alpar@1: 
alpar@1: \subsection{glp\_bf\_exists---check if the basis factorization exists}
alpar@1: 
alpar@1: \subsubsection*{Synopsis}
alpar@1: 
alpar@1: \begin{verbatim}
alpar@1: int glp_bf_exists(glp_prob *lp);
alpar@1: \end{verbatim}
alpar@1: 
alpar@1: \subsubsection*{Returns}
alpar@1: 
alpar@1: If the basis factorization for the current basis associated with the
alpar@1: specified problem object exists and therefore is available for
alpar@1: computations, the routine \verb|glp_bf_exists| returns non-zero.
alpar@1: Otherwise the routine returns zero.
alpar@1: 
alpar@1: \subsubsection*{Comments}
alpar@1: 
alpar@1: Let the problem object have $m$ rows and $n$ columns. In GLPK the
alpar@1: {\it basis matrix} $B$ is a square non-singular matrix of the order $m$,
alpar@1: whose columns correspond to basic (auxiliary and/or structural)
alpar@1: variables. It is defined by the following main
alpar@1: equality:\footnote{For more details see Subsection \ref{basbgd},
alpar@1: page \pageref{basbgd}.}
alpar@1: $$(B\ |\ N)=(I\ |-\!A)\Pi^T,$$
alpar@1: where $I$ is the unity matrix of the order $m$, whose columns correspond
alpar@1: to auxiliary variables; $A$ is the original constraint
alpar@1: $m\times n$-matrix, whose columns correspond to structural variables;
alpar@1: $(I\ |-\!A)$ is the augmented constraint\linebreak
alpar@1: $m\times(m+n)$-matrix, whose columns correspond to all (auxiliary and
alpar@1: structural) variables following in the original order; $\Pi$ is a
alpar@1: permutation matrix of the order $m+n$; and $N$ is a rectangular
alpar@1: $m\times n$-matrix, whose columns correspond to non-basic (auxiliary
alpar@1: and/or structural) variables.
alpar@1: 
alpar@1: For various reasons it may be necessary to solve linear systems with
alpar@1: matrix $B$. To provide this possibility the GLPK implementation
alpar@1: maintains an invertable form of $B$ (that is, some representation of
alpar@1: $B^{-1}$) called the {\it basis factorization}, which is an internal
alpar@1: component of the problem object. Typically, the basis factorization is
alpar@1: computed by the simplex solver, which keeps it in the problem object
alpar@1: to be available for other computations.
alpar@1: 
alpar@1: Should note that any changes in the problem object, which affects the
alpar@1: basis matrix (e.g. changing the status of a row or column, changing
alpar@1: a basic column of the constraint matrix, removing an active constraint,
alpar@1: etc.), invalidates the basis factorization. So before calling any API
alpar@1: routine, which uses the basis factorization, the application program
alpar@1: must make sure (using the routine \verb|glp_bf_exists|) that the
alpar@1: factorization exists and therefore available for computations.
alpar@1: 
alpar@1: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@1: 
alpar@1: \subsection{glp\_factorize---compute the basis factorization}
alpar@1: 
alpar@1: \subsubsection*{Synopsis}
alpar@1: 
alpar@1: \begin{verbatim}
alpar@1: int glp_factorize(glp_prob *lp);
alpar@1: \end{verbatim}
alpar@1: 
alpar@1: \subsubsection*{Description}
alpar@1: 
alpar@1: The routine \verb|glp_factorize| computes the basis factorization for
alpar@1: the current basis associated with the specified problem
alpar@1: object.\footnote{The current basis is defined by the current statuses
alpar@1: of rows (auxiliary variables) and columns (structural variables).}
alpar@1: 
alpar@1: The basis factorization is computed from ``scratch'' even if it exists,
alpar@1: so the application program may use the routine \verb|glp_bf_exists|,
alpar@1: and, if the basis factorization already exists, not to call the routine
alpar@1: \verb|glp_factorize| to prevent an extra work.
alpar@1: 
alpar@1: The routine \verb|glp_factorize| {\it does not} compute components of
alpar@1: the basic solution (i.e. primal and dual values).
alpar@1: 
alpar@1: \subsubsection*{Returns}
alpar@1: 
alpar@1: \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
alpar@1: 0 & The basis factorization has been successfully computed.\\
alpar@1: \verb|GLP_EBADB| & The basis matrix is invalid, because the number of
alpar@1: basic (auxiliary and structural) variables is not the same as the number
alpar@1: of rows in the problem object.\\
alpar@1: \verb|GLP_ESING| & The basis matrix is singular within the working
alpar@1: precision.\\
alpar@1: \verb|GLP_ECOND| & The basis matrix is ill-conditioned, i.e. its
alpar@1: condition number is too large.\\
alpar@1: \end{tabular}
alpar@1: 
alpar@1: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@1: 
alpar@1: \newpage
alpar@1: 
alpar@1: \subsection{glp\_bf\_updated---check if the basis factorization has\\
alpar@1: been updated}
alpar@1: 
alpar@1: \subsubsection*{Synopsis}
alpar@1: 
alpar@1: \begin{verbatim}
alpar@1: int glp_bf_updated(glp_prob *lp);
alpar@1: \end{verbatim}
alpar@1: 
alpar@1: \subsubsection*{Returns}
alpar@1: 
alpar@1: If the basis factorization has been just computed from ``scratch'', the
alpar@1: routine \verb|glp_bf_updated| returns zero. Otherwise, if the
alpar@1: factorization has been updated at least once, the routine returns
alpar@1: non-zero.
alpar@1: 
alpar@1: \subsubsection*{Comments}
alpar@1: 
alpar@1: {\it Updating} the basis factorization means recomputing it to reflect
alpar@1: changes in the basis matrix. For example, on every iteration of the
alpar@1: simplex method some column of the current basis matrix is replaced by a
alpar@1: new column that gives a new basis matrix corresponding to the adjacent
alpar@1: basis. In this case computing the basis factorization for the adjacent
alpar@1: basis from ``scratch'' (as the routine \verb|glp_factorize| does) would
alpar@1: be too time-consuming.
alpar@1: 
alpar@1: On the other hand, since the basis factorization update is a numeric
alpar@1: computational procedure, applying it many times may lead to accumulating
alpar@1: round-off errors. Therefore the basis is periodically refactorized
alpar@1: (reinverted) from ``scratch'' (with the routine \verb|glp_factorize|)
alpar@1: that allows improving its numerical properties.
alpar@1: 
alpar@1: The routine \verb|glp_bf_updated| allows determining if the basis
alpar@1: factorization has been updated at least once since it was computed from
alpar@1: ``scratch''.
alpar@1: 
alpar@1: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@1: 
alpar@1: \newpage
alpar@1: 
alpar@1: \subsection{glp\_get\_bfcp---retrieve basis factorization control
alpar@1: parameters}
alpar@1: 
alpar@1: \subsubsection*{Synopsis}
alpar@1: 
alpar@1: \begin{verbatim}
alpar@1: void glp_get_bfcp(glp_prob *lp, glp_bfcp *parm);
alpar@1: \end{verbatim}
alpar@1: 
alpar@1: \subsubsection*{Description}
alpar@1: 
alpar@1: The routine \verb|glp_get_bfcp| retrieves control parameters, which are
alpar@1: used on computing and updating the basis factorization associated with
alpar@1: the specified problem object.
alpar@1: 
alpar@1: Current values of the control parameters are stored in a \verb|glp_bfcp|
alpar@1: structure, which the parameter \verb|parm| points to. For a detailed
alpar@1: description of the structure \verb|glp_bfcp| see comments to the routine
alpar@1: \verb|glp_set_bfcp| in the next subsection.
alpar@1: 
alpar@1: \subsubsection*{Comments}
alpar@1: 
alpar@1: The purpose of the routine \verb|glp_get_bfcp| is two-fold. First, it
alpar@1: allows the application program obtaining current values of control
alpar@1: parameters used by internal GLPK routines, which compute and update the
alpar@1: basis factorization.
alpar@1: 
alpar@1: The second purpose of this routine is to provide proper values for all
alpar@1: fields of the structure \verb|glp_bfcp| in the case when the application
alpar@1: program needs to change some control parameters.
alpar@1: 
alpar@1: \subsection{glp\_set\_bfcp---change basis factorization control
alpar@1: parameters}
alpar@1: 
alpar@1: \subsubsection*{Synopsis}
alpar@1: 
alpar@1: \begin{verbatim}
alpar@1: void glp_set_bfcp(glp_prob *lp, const glp_bfcp *parm);
alpar@1: \end{verbatim}
alpar@1: 
alpar@1: \subsubsection*{Description}
alpar@1: 
alpar@1: The routine \verb|glp_set_bfcp| changes control parameters, which are
alpar@1: used by internal GLPK routines on computing and updating the basis
alpar@1: factorization associated with the specified problem object.
alpar@1: 
alpar@1: New values of the control parameters should be passed in a structure
alpar@1: \verb|glp_bfcp|, which the parameter \verb|parm| points to. For a
alpar@1: detailed description of the structure \verb|glp_bfcp| see paragraph
alpar@1: ``Control parameters'' below.
alpar@1: 
alpar@1: The parameter \verb|parm| can be specified as \verb|NULL|, in which case
alpar@1: all control parameters are reset to their default values.
alpar@1: 
alpar@1: \subsubsection*{Comments}
alpar@1: 
alpar@1: Before changing some control parameters with the routine
alpar@1: \verb|glp_set_bfcp| the application program should retrieve current
alpar@1: values of all control parameters with the routine \verb|glp_get_bfcp|.
alpar@1: This is needed for backward compatibility, because in the future there
alpar@1: may appear new members in the structure \verb|glp_bfcp|.
alpar@1: 
alpar@1: Note that new values of control parameters come into effect on a next
alpar@1: computation of the basis factorization, not immediately.
alpar@1: 
alpar@1: \subsubsection*{Example}
alpar@1: 
alpar@1: \begin{verbatim}
alpar@1: glp_prob *lp;
alpar@1: glp_bfcp parm;
alpar@1: . . .
alpar@1: /* retrieve current values of control parameters */
alpar@1: glp_get_bfcp(lp, &parm);
alpar@1: /* change the threshold pivoting tolerance */
alpar@1: parm.piv_tol = 0.05;
alpar@1: /* set new values of control parameters */
alpar@1: glp_set_bfcp(lp, &parm);
alpar@1: . . .
alpar@1: \end{verbatim}
alpar@1: 
alpar@1: \subsubsection*{Control parameters}
alpar@1: 
alpar@1: This paragraph describes all basis factorization control parameters
alpar@1: currently used in the package. Symbolic names of control parameters are
alpar@1: names of corresponding members in the structure \verb|glp_bfcp|.
alpar@1: 
alpar@1: \def\arraystretch{1}
alpar@1: 
alpar@1: \medskip
alpar@1: 
alpar@1: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@1: \multicolumn{2}{@{}l}{{\tt int type} (default: {\tt GLP\_BF\_FT})} \\
alpar@1: &Basis factorization type:\\
alpar@1: &\verb|GLP_BF_FT|---$LU$ + Forrest--Tomlin update;\\
alpar@1: &\verb|GLP_BF_BG|---$LU$ + Schur complement + Bartels--Golub update;\\
alpar@1: &\verb|GLP_BF_GR|---$LU$ + Schur complement + Givens rotation update.
alpar@1: \\
alpar@1: &In case of \verb|GLP_BF_FT| the update is applied to matrix $U$, while
alpar@1: in cases of \verb|GLP_BF_BG| and \verb|GLP_BF_GR| the update is applied
alpar@1: to the Schur complement.
alpar@1: \end{tabular}
alpar@1: 
alpar@1: \medskip
alpar@1: 
alpar@1: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@1: \multicolumn{2}{@{}l}{{\tt int lu\_size} (default: {\tt 0})} \\
alpar@1: &The initial size of the Sparse Vector Area, in non-zeros, used on
alpar@1: computing $LU$-factorization of the basis matrix for the first time.
alpar@1: If this parameter is set to 0, the initial SVA size is determined
alpar@1: automatically.\\
alpar@1: \end{tabular}
alpar@1: 
alpar@1: \medskip
alpar@1: 
alpar@1: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@1: \multicolumn{2}{@{}l}{{\tt double piv\_tol} (default: {\tt 0.10})} \\
alpar@1: &Threshold pivoting (Markowitz) tolerance, 0 $<$ \verb|piv_tol| $<$ 1,
alpar@1: used on computing $LU$-factorization of the basis matrix. Element
alpar@1: $u_{ij}$ of the active submatrix of factor $U$ fits to be pivot if it
alpar@1: satisfies to the stability criterion
alpar@1: $|u_{ij}| >= {\tt piv\_tol}\cdot\max|u_{i*}|$, i.e. if it is not very
alpar@1: small in the magnitude among other elements in the same row. Decreasing
alpar@1: this parameter may lead to better sparsity at the expense of numerical
alpar@1: accuracy, and vice versa.\\
alpar@1: \end{tabular}
alpar@1: 
alpar@1: \medskip
alpar@1: 
alpar@1: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@1: \multicolumn{2}{@{}l}{{\tt int piv\_lim} (default: {\tt 4})} \\
alpar@1: &This parameter is used on computing $LU$-factorization of the basis
alpar@1: matrix and specifies how many pivot candidates needs to be considered
alpar@1: on choosing a pivot element, \verb|piv_lim| $\geq$ 1. If \verb|piv_lim|
alpar@1: candidates have been considered, the pivoting routine prematurely
alpar@1: terminates the search with the best candidate found.\\
alpar@1: \end{tabular}
alpar@1: 
alpar@1: \medskip
alpar@1: 
alpar@1: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@1: \multicolumn{2}{@{}l}{{\tt int suhl} (default: {\tt GLP\_ON})} \\
alpar@1: &This parameter is used on computing $LU$-factorization of the basis
alpar@1: matrix. Being set to {\tt GLP\_ON} it enables applying the following
alpar@1: heuristic proposed by Uwe Suhl: if a column of the active submatrix has
alpar@1: no eligible pivot candidates, it is no more considered until it becomes
alpar@1: a column singleton. In many cases this allows reducing the time needed
alpar@1: for pivot searching. To disable this heuristic the parameter \verb|suhl|
alpar@1: should be set to {\tt GLP\_OFF}.\\
alpar@1: \end{tabular}
alpar@1: 
alpar@1: \medskip
alpar@1: 
alpar@1: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@1: \multicolumn{2}{@{}l}{{\tt double eps\_tol} (default: {\tt 1e-15})} \\
alpar@1: &Epsilon tolerance, \verb|eps_tol| $\geq$ 0, used on computing
alpar@1: $LU$-factorization of the basis matrix. If an element of the active
alpar@1: submatrix of factor $U$ is less than \verb|eps_tol| in the magnitude,
alpar@1: it is replaced by exact zero.\\
alpar@1: \end{tabular}
alpar@1: 
alpar@1: \medskip
alpar@1: 
alpar@1: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@1: \multicolumn{2}{@{}l}{{\tt double max\_gro} (default: {\tt 1e+10})} \\
alpar@1: &Maximal growth of elements of factor $U$, \verb|max_gro| $\geq$ 1,
alpar@1: allowable on computing $LU$-factorization of the basis matrix. If on
alpar@1: some elimination step the ratio $u_{big}/b_{max}$ (where $u_{big}$ is
alpar@1: the largest magnitude of elements of factor $U$ appeared in its active
alpar@1: submatrix during all the factorization process, $b_{max}$ is the largest
alpar@1: magnitude of elements of the basis matrix to be factorized), the basis
alpar@1: matrix is considered as ill-conditioned.\\
alpar@1: \end{tabular}
alpar@1: 
alpar@1: \medskip
alpar@1: 
alpar@1: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@1: \multicolumn{2}{@{}l}{{\tt int nfs\_max} (default: {\tt 100})} \\
alpar@1: &Maximal number of additional row-like factors (entries of the eta
alpar@1: file), \verb|nfs_max| $\geq$ 1, which can be added to $LU$-factorization
alpar@1: of the basis matrix on updating it with the Forrest--Tomlin technique.
alpar@1: This parameter is used only once, before $LU$-factorization is computed
alpar@1: for the first time, to allocate working arrays. As a rule, each update
alpar@1: adds one new factor (however, some updates may need no addition), so
alpar@1: this parameter limits the number of updates between refactorizations.\\
alpar@1: \end{tabular}
alpar@1: 
alpar@1: \medskip
alpar@1: 
alpar@1: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@1: \multicolumn{2}{@{}l}{{\tt double upd\_tol} (default: {\tt 1e-6})} \\
alpar@1: &Update tolerance, 0 $<$ \verb|upd_tol| $<$ 1, used on updating
alpar@1: $LU$-factorization of the basis matrix with the Forrest--Tomlin
alpar@1: technique. If after updating the magnitude of some diagonal element
alpar@1: $u_{kk}$ of factor $U$ becomes less than
alpar@1: ${\tt upd\_tol}\cdot\max(|u_{k*}|, |u_{*k}|)$, the factorization is
alpar@1: considered as inaccurate.\\
alpar@1: \end{tabular}
alpar@1: 
alpar@1: \medskip
alpar@1: 
alpar@1: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@1: \multicolumn{2}{@{}l}{{\tt int nrs\_max} (default: {\tt 100})} \\
alpar@1: &Maximal number of additional rows and columns, \verb|nrs_max| $\geq$ 1,
alpar@1: which can be added to $LU$-factorization of the basis matrix on updating
alpar@1: it with the Schur complement technique. This parameter is used only
alpar@1: once, before $LU$-factorization is computed for the first time, to
alpar@1: allocate working arrays. As a rule, each update adds one new row and
alpar@1: column (however, some updates may need no addition), so this parameter
alpar@1: limits the number of updates between refactorizations.\\
alpar@1: \end{tabular}
alpar@1: 
alpar@1: \medskip
alpar@1: 
alpar@1: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@1: \multicolumn{2}{@{}l}{{\tt int rs\_size} (default: {\tt 0})} \\
alpar@1: &The initial size of the Sparse Vector Area, in non-zeros, used to
alpar@1: store non-zero elements of additional rows and columns introduced on
alpar@1: updating $LU$-factorization of the basis matrix with the Schur
alpar@1: complement technique. If this parameter is set to 0, the initial SVA
alpar@1: size is determined automatically.\\
alpar@1: \end{tabular}
alpar@1: 
alpar@1: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@1: 
alpar@1: \newpage
alpar@1: 
alpar@1: \subsection{glp\_get\_bhead---retrieve the basis header information}
alpar@1: 
alpar@1: \subsubsection*{Synopsis}
alpar@1: 
alpar@1: \begin{verbatim}
alpar@1: int glp_get_bhead(glp_prob *lp, int k);
alpar@1: \end{verbatim}
alpar@1: 
alpar@1: \subsubsection*{Description}
alpar@1: 
alpar@1: The routine \verb|glp_get_bhead| returns the basis header information
alpar@1: for the current basis associated with the specified problem object.
alpar@1: 
alpar@1: \subsubsection*{Returns}
alpar@1: 
alpar@1: If basic variable $(x_B)_k$, $1\leq k\leq m$, is $i$-th auxiliary
alpar@1: variable ($1\leq i\leq m$), the routine returns $i$. Otherwise, if
alpar@1: $(x_B)_k$ is $j$-th structural variable ($1\leq j\leq n$), the routine
alpar@1: returns $m+j$. Here $m$ is the number of rows and $n$ is the number of
alpar@1: columns in the problem object.
alpar@1: 
alpar@1: \subsubsection*{Comments}
alpar@1: 
alpar@1: Sometimes the application program may need to know which original
alpar@1: (auxiliary and structural) variable correspond to a given basic
alpar@1: variable, or, that is the same, which column of the augmented constraint
alpar@1: matrix $(I\ |-\!A)$ correspond to a given column of the basis matrix
alpar@1: $B$.
alpar@1: 
alpar@1: \def\arraystretch{1}
alpar@1: 
alpar@1: The correspondence is defined as follows:\footnote{For more details see
alpar@1: Subsection \ref{basbgd}, page \pageref{basbgd}.}
alpar@1: $$\left(\begin{array}{@{}c@{}}x_B\\x_N\\\end{array}\right)=
alpar@1: \Pi\left(\begin{array}{@{}c@{}}x_R\\x_S\\\end{array}\right)
alpar@1: \ \ \Leftrightarrow
alpar@1: \ \ \left(\begin{array}{@{}c@{}}x_R\\x_S\\\end{array}\right)=
alpar@1: \Pi^T\left(\begin{array}{@{}c@{}}x_B\\x_N\\\end{array}\right),$$
alpar@1: where $x_B$ is the vector of basic variables, $x_N$ is the vector of
alpar@1: non-basic variables, $x_R$ is the vector of auxiliary variables
alpar@1: following in their original order,\footnote{The original order of
alpar@1: auxiliary and structural variables is defined by the ordinal numbers
alpar@1: of corresponding rows and columns in the problem object.} $x_S$ is the
alpar@1: vector of structural variables following in their original order, $\Pi$
alpar@1: is a permutation matrix (which is a component of the basis
alpar@1: factorization).
alpar@1: 
alpar@1: Thus, if $(x_B)_k=(x_R)_i$ is $i$-th auxiliary variable, the routine
alpar@1: returns $i$, and if $(x_B)_k=(x_S)_j$ is $j$-th structural variable,
alpar@1: the routine returns $m+j$, where $m$ is the number of rows in the
alpar@1: problem object.
alpar@1: 
alpar@1: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@1: 
alpar@1: \newpage
alpar@1: 
alpar@1: \subsection{glp\_get\_row\_bind---retrieve row index in the basis\\
alpar@1: header}
alpar@1: 
alpar@1: \subsubsection*{Synopsis}
alpar@1: 
alpar@1: \begin{verbatim}
alpar@1: int glp_get_row_bind(glp_prob *lp, int i);
alpar@1: \end{verbatim}
alpar@1: 
alpar@1: \subsubsection*{Returns}
alpar@1: 
alpar@1: The routine \verb|glp_get_row_bind| returns the index $k$ of basic
alpar@1: variable $(x_B)_k$, $1\leq k\leq m$, which is $i$-th auxiliary variable
alpar@1: (that is, the auxiliary variable corresponding to $i$-th row),
alpar@1: $1\leq i\leq m$, in the current basis associated with the specified
alpar@1: problem object, where $m$ is the number of rows. However, if $i$-th
alpar@1: auxiliary variable is non-basic, the routine returns zero.
alpar@1: 
alpar@1: \subsubsection*{Comments}
alpar@1: 
alpar@1: The routine \verb|glp_get_row_bind| is an inverse to the routine
alpar@1: \verb|glp_get_bhead|: if \verb|glp_get_bhead|$(lp,k)$ returns $i$,
alpar@1: \verb|glp_get_row_bind|$(lp,i)$ returns $k$, and vice versa.
alpar@1: 
alpar@1: \subsection{glp\_get\_col\_bind---retrieve column index in the basis
alpar@1: header}
alpar@1: 
alpar@1: \subsubsection*{Synopsis}
alpar@1: 
alpar@1: \begin{verbatim}
alpar@1: int glp_get_col_bind(glp_prob *lp, int j);
alpar@1: \end{verbatim}
alpar@1: 
alpar@1: \subsubsection*{Returns}
alpar@1: 
alpar@1: The routine \verb|glp_get_col_bind| returns the index $k$ of basic
alpar@1: variable $(x_B)_k$, $1\leq k\leq m$, which is $j$-th structural
alpar@1: variable (that is, the structural variable corresponding to $j$-th
alpar@1: column), $1\leq j\leq n$, in the current basis associated with the
alpar@1: specified problem object, where $m$ is the number of rows, $n$ is the
alpar@1: number of columns. However, if $j$-th structural variable is non-basic,
alpar@1: the routine returns zero.
alpar@1: 
alpar@1: \subsubsection*{Comments}
alpar@1: 
alpar@1: The routine \verb|glp_get_col_bind| is an inverse to the routine
alpar@1: \verb|glp_get_bhead|: if \verb|glp_get_bhead|$(lp,k)$ returns $m+j$,
alpar@1: \verb|glp_get_col_bind|$(lp,j)$ returns $k$, and vice versa.
alpar@1: 
alpar@1: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@1: 
alpar@1: \newpage
alpar@1: 
alpar@1: \subsection{glp\_ftran---perform forward transformation}
alpar@1: 
alpar@1: \subsubsection*{Synopsis}
alpar@1: 
alpar@1: \begin{verbatim}
alpar@1: void glp_ftran(glp_prob *lp, double x[]);
alpar@1: \end{verbatim}
alpar@1: 
alpar@1: \subsubsection*{Description}
alpar@1: 
alpar@1: The routine \verb|glp_ftran| performs forward transformation (FTRAN),
alpar@1: i.e. it solves the system $Bx=b$, where $B$ is the basis matrix
alpar@1: associated with the specified problem object, $x$ is the vector of
alpar@1: unknowns to be computed, $b$ is the vector of right-hand sides.
alpar@1: 
alpar@1: On entry to the routine elements of the vector $b$ should be stored in
alpar@1: locations \verb|x[1]|, \dots, \verb|x[m]|, where $m$ is the number of
alpar@1: rows. On exit the routine stores elements of the vector $x$ in the same
alpar@1: locations.
alpar@1: 
alpar@1: \subsection{glp\_btran---perform backward transformation}
alpar@1: 
alpar@1: \subsubsection*{Synopsis}
alpar@1: 
alpar@1: \begin{verbatim}
alpar@1: void glp_btran(glp_prob *lp, double x[]);
alpar@1: \end{verbatim}
alpar@1: 
alpar@1: \subsubsection*{Description}
alpar@1: 
alpar@1: The routine \verb|glp_btran| performs backward transformation (BTRAN),
alpar@1: i.e. it solves the system $B^Tx=b$, where $B^T$ is a matrix transposed
alpar@1: to the basis matrix $B$ associated with the specified problem object,
alpar@1: $x$ is the vector of unknowns to be computed, $b$ is the vector of
alpar@1: right-hand sides.
alpar@1: 
alpar@1: On entry to the routine elements of the vector $b$ should be stored in
alpar@1: locations \verb|x[1]|, \dots, \verb|x[m]|, where $m$ is the number of
alpar@1: rows. On exit the routine stores elements of the vector $x$ in the same
alpar@1: locations.
alpar@1: 
alpar@1: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@1: 
alpar@1: \newpage
alpar@1: 
alpar@1: \subsection{glp\_warm\_up---``warm up'' LP basis}
alpar@1: 
alpar@1: \subsubsection*{Synopsis}
alpar@1: 
alpar@1: \begin{verbatim}
alpar@1: int glp_warm_up(glp_prob *P);
alpar@1: \end{verbatim}
alpar@1: 
alpar@1: \subsubsection*{Description}
alpar@1: 
alpar@1: The routine \verb|glp_warm_up| ``warms up'' the LP basis for the
alpar@1: specified problem object using current statuses assigned to rows and
alpar@1: columns (that is, to auxiliary and structural variables).
alpar@1: 
alpar@1: This operation includes computing factorization of the basis matrix
alpar@1: (if it does not exist), computing primal and dual components of basic
alpar@1: solution, and determining the solution status.
alpar@1: 
alpar@1: \subsubsection*{Returns}
alpar@1: 
alpar@1: \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
alpar@1: 0 & The operation has been successfully performed.\\
alpar@1: \verb|GLP_EBADB| & The basis matrix is invalid, because the number of
alpar@1: basic (auxiliary and structural) variables is not the same as the number
alpar@1: of rows in the problem object.\\
alpar@1: \verb|GLP_ESING| & The basis matrix is singular within the working
alpar@1: precision.\\
alpar@1: \verb|GLP_ECOND| & The basis matrix is ill-conditioned, i.e. its
alpar@1: condition number is too large.\\
alpar@1: \end{tabular}
alpar@1: 
alpar@1: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@1: 
alpar@1: \newpage
alpar@1: 
alpar@1: \section{Simplex tableau routines}
alpar@1: 
alpar@1: \subsection{glp\_eval\_tab\_row---compute row of the tableau}
alpar@1: 
alpar@1: \subsubsection*{Synopsis}
alpar@1: 
alpar@1: \begin{verbatim}
alpar@1: int glp_eval_tab_row(glp_prob *lp, int k, int ind[],
alpar@1:       double val[]);
alpar@1: \end{verbatim}
alpar@1: 
alpar@1: \subsubsection*{Description}
alpar@1: 
alpar@1: The routine \verb|glp_eval_tab_row| computes a row of the current
alpar@1: simplex tableau (see Subsection 3.1.1, formula (3.12)), which (row)
alpar@1: corresponds to some basic variable specified by the parameter $k$ as
alpar@1: follows: if $1\leq k\leq m$, the basic variable is $k$-th auxiliary
alpar@1: variable, and if $m+1\leq k\leq m+n$, the basic variable is $(k-m)$-th
alpar@1: structural variable, where $m$ is the number of rows and $n$ is the
alpar@1: number of columns in the specified problem object. The basis
alpar@1: factorization must exist.
alpar@1: 
alpar@1: The computed row shows how the specified basic variable depends on
alpar@1: non-basic variables:
alpar@1: $$x_k=(x_B)_i=\xi_{i1}(x_N)_1+\xi_{i2}(x_N)_2+\dots+\xi_{in}(x_N)_n,$$
alpar@1: where $\xi_{i1}$, $\xi_{i2}$, \dots, $\xi_{in}$ are elements of the
alpar@1: simplex table row, $(x_N)_1$, $(x_N)_2$, \dots, $(x_N)_n$ are non-basic
alpar@1: (auxiliary and structural) variables.
alpar@1: 
alpar@1: The routine stores column indices and corresponding numeric values of
alpar@1: non-zero elements of the computed row in unordered sparse format in
alpar@1: locations \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|,
alpar@1: \dots, \verb|val[len]|, respectively, where $0\leq{\tt len}\leq n$ is
alpar@1: the number of non-zero elements in the row returned on exit.
alpar@1: 
alpar@1: Element indices stored in the array \verb|ind| have the same sense as
alpar@1: index $k$, i.e. indices 1 to $m$ denote auxiliary variables while
alpar@1: indices $m+1$ to $m+n$ denote structural variables (all these variables
alpar@1: are obviously non-basic by definition).
alpar@1: 
alpar@1: \subsubsection*{Returns}
alpar@1: 
alpar@1: The routine \verb|glp_eval_tab_row| returns \verb|len|, which is the
alpar@1: number of non-zero elements in the simplex table row stored in the
alpar@1: arrays \verb|ind| and \verb|val|.
alpar@1: 
alpar@1: \subsubsection*{Comments}
alpar@1: 
alpar@1: A row of the simplex table is computed as follows. At first, the
alpar@1: routine checks that the specified variable $x_k$ is basic and uses the
alpar@1: permutation matrix $\Pi$ (3.7) to determine index $i$ of basic variable
alpar@1: $(x_B)_i$, which corresponds to $x_k$.
alpar@1: 
alpar@1: The row to be computed is $i$-th row of the matrix $\Xi$ (3.12),
alpar@1: therefore:
alpar@1: $$\xi_i=e_i^T\Xi=-e_i^TB^{-1}N=-(B^{-T}e_i)^TN,$$
alpar@1: where $e_i$ is $i$-th unity vector. So the routine performs BTRAN to
alpar@1: obtain $i$-th row of the inverse $B^{-1}$:
alpar@1: $$\varrho_i=B^{-T}e_i,$$
alpar@1: and then computes elements of the simplex table row as inner products:
alpar@1: $$\xi_{ij}=-\varrho_i^TN_j,\ \ j=1,2,\dots,n,$$
alpar@1: where $N_j$ is $j$-th column of matrix $N$ (3.9), which (column)
alpar@1: corresponds to non-basic variable $(x_N)_j$. The permutation matrix
alpar@1: $\Pi$ is used again to convert indices $j$ of non-basic columns to
alpar@1: original ordinal numbers of auxiliary and structural variables.
alpar@1: 
alpar@1: \subsection{glp\_eval\_tab\_col---compute column of the tableau}
alpar@1: 
alpar@1: \subsubsection*{Synopsis}
alpar@1: 
alpar@1: \begin{verbatim}
alpar@1: int glp_eval_tab_col(glp_prob *lp, int k, int ind[],
alpar@1:       double val[]);
alpar@1: \end{verbatim}
alpar@1: 
alpar@1: \subsubsection*{Description}
alpar@1: 
alpar@1: The routine \verb|glp_eval_tab_col| computes a column of the current
alpar@1: simplex tableau (see Subsection 3.1.1, formula (3.12)), which (column)
alpar@1: corresponds to some non-basic variable specified by the parameter $k$:
alpar@1: if $1\leq k\leq m$, the non-basic variable is $k$-th auxiliary variable,
alpar@1: and if $m+1\leq k\leq m+n$, the non-basic variable is $(k-m)$-th
alpar@1: structural variable, where $m$ is the number of rows and $n$ is the
alpar@1: number of columns in the specified problem object. The basis
alpar@1: factorization must exist.
alpar@1: 
alpar@1: The computed column shows how basic variables depends on the specified
alpar@1: non-basic variable $x_k=(x_N)_j$:
alpar@1: $$
alpar@1: \begin{array}{r@{\ }c@{\ }l@{\ }l}
alpar@1: (x_B)_1&=&\dots+\xi_{1j}(x_N)_j&+\dots\\
alpar@1: (x_B)_2&=&\dots+\xi_{2j}(x_N)_j&+\dots\\
alpar@1: .\ \ .&.&.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\\
alpar@1: (x_B)_m&=&\dots+\xi_{mj}(x_N)_j&+\dots\\
alpar@1: \end{array}
alpar@1: $$
alpar@1: where $\xi_{1j}$, $\xi_{2j}$, \dots, $\xi_{mj}$ are elements of the
alpar@1: simplex table column, $(x_B)_1$, $(x_B)_2$, \dots, $(x_B)_m$ are basic
alpar@1: (auxiliary and structural) variables.
alpar@1: 
alpar@1: The routine stores row indices and corresponding numeric values of
alpar@1: non-zero elements of the computed column in unordered sparse format in
alpar@1: locations \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|,
alpar@1: \dots, \verb|val[len]|, respectively, where $0\leq{\tt len}\leq m$ is
alpar@1: the number of non-zero elements in the column returned on exit.
alpar@1: 
alpar@1: Element indices stored in the array \verb|ind| have the same sense as
alpar@1: index $k$, i.e. indices 1 to $m$ denote auxiliary variables while
alpar@1: indices $m+1$ to $m+n$ denote structural variables (all these variables
alpar@1: are obviously basic by definition).
alpar@1: 
alpar@1: \subsubsection*{Returns}
alpar@1: 
alpar@1: The routine \verb|glp_eval_tab_col| returns \verb|len|, which is the
alpar@1: number of non-zero elements in the simplex table column stored in the
alpar@1: arrays \verb|ind| and \verb|val|.
alpar@1: 
alpar@1: \subsubsection*{Comments}
alpar@1: 
alpar@1: A column of the simplex table is computed as follows. At first, the
alpar@1: routine checks that the specified variable $x_k$ is non-basic and uses
alpar@1: the permutation matrix $\Pi$ (3.7) to determine index $j$ of non-basic
alpar@1: variable $(x_N)_j$, which corresponds to $x_k$.
alpar@1: 
alpar@1: The column to be computed is $j$-th column of the matrix $\Xi$ (3.12),
alpar@1: therefore:
alpar@1: $$\Xi_j=\Xi e_j=-B^{-1}Ne_j=-B^{-1}N_j,$$
alpar@1: where $e_j$ is $j$-th unity vector, $N_j$ is $j$-th column of matrix
alpar@1: $N$ (3.9). So the routine performs FTRAN to transform $N_j$ to the
alpar@1: simplex table column $\Xi_j=(\xi_{ij})$ and uses the permutation matrix
alpar@1: $\Pi$ to convert row indices $i$ to original ordinal numbers of
alpar@1: auxiliary and structural variables.
alpar@1: 
alpar@1: \newpage
alpar@1: 
alpar@1: \subsection{glp\_transform\_row---transform explicitly specified\\
alpar@1: row}
alpar@1: 
alpar@1: \subsubsection*{Synopsis}
alpar@1: 
alpar@1: \begin{verbatim}
alpar@1: int glp_transform_row(glp_prob *P, int len, int ind[],
alpar@1:       double val[]);
alpar@1: \end{verbatim}
alpar@1: 
alpar@1: \subsubsection*{Description}
alpar@1: 
alpar@1: The routine \verb|glp_transform_row| performs the same operation as the
alpar@1: routine \verb|glp_eval_tab_row| with exception that the row to be
alpar@1: transformed is specified explicitly as a sparse vector.
alpar@1: 
alpar@1: The explicitly specified row may be thought as a linear form:
alpar@1: $$x=a_1x_{m+1}+a_2x_{m+2}+\dots+a_nx_{m+n},$$
alpar@1: where $x$ is an auxiliary variable for this row, $a_j$ are coefficients
alpar@1: of the linear form, $x_{m+j}$ are structural variables.
alpar@1: 
alpar@1: On entry column indices and numerical values of non-zero coefficients
alpar@1: $a_j$ of the specified row should be placed in locations \verb|ind[1]|,
alpar@1: \dots, \verb|ind[len]| and \verb|val[1]|, \dots, \verb|val[len]|, where
alpar@1: \verb|len| is number of non-zero coefficients.
alpar@1: 
alpar@1: This routine uses the system of equality constraints and the current
alpar@1: basis in order to express the auxiliary variable $x$ through the current
alpar@1: non-basic variables (as if the transformed row were added to the problem
alpar@1: object and the auxiliary variable $x$ were basic), i.e. the resultant
alpar@1: row has the form:
alpar@1: $$x=\xi_1(x_N)_1+\xi_2(x_N)_2+\dots+\xi_n(x_N)_n,$$
alpar@1: where $\xi_j$ are influence coefficients, $(x_N)_j$ are non-basic
alpar@1: (auxiliary and structural) variables, $n$ is the number of columns in
alpar@1: the problem object.
alpar@1: 
alpar@1: On exit the routine stores indices and numerical values of non-zero
alpar@1: coefficients $\xi_j$ of the resultant row in locations \verb|ind[1]|,
alpar@1: \dots, \verb|ind[len']| and \verb|val[1]|, \dots, \verb|val[len']|,
alpar@1: where $0\leq{\tt len'}\leq n$ is the number of non-zero coefficients in
alpar@1: the resultant row returned by the routine. Note that indices of
alpar@1: non-basic variables stored in the array \verb|ind| correspond to
alpar@1: original ordinal numbers of variables: indices 1 to $m$ mean auxiliary
alpar@1: variables and indices $m+1$ to $m+n$ mean structural ones.
alpar@1: 
alpar@1: \subsubsection*{Returns}
alpar@1: 
alpar@1: The routine \verb|glp_transform_row| returns \verb|len'|, the number of
alpar@1: non-zero coefficients in the resultant row stored in the arrays
alpar@1: \verb|ind| and \verb|val|.
alpar@1: 
alpar@1: \subsection{glp\_transform\_col---transform explicitly specified\\
alpar@1: column}
alpar@1: 
alpar@1: \subsubsection*{Synopsis}
alpar@1: 
alpar@1: \begin{verbatim}
alpar@1: int glp_transform_col(glp_prob *P, int len, int ind[],
alpar@1:       double val[]);
alpar@1: \end{verbatim}
alpar@1: 
alpar@1: \subsubsection*{Description}
alpar@1: 
alpar@1: The routine \verb|glp_transform_col| performs the same operation as the
alpar@1: routine \verb|glp_eval_tab_col| with exception that the column to be
alpar@1: transformed is specified explicitly as a sparse vector.
alpar@1: 
alpar@1: The explicitly specified column may be thought as it were added to
alpar@1: the original system of equality constraints:
alpar@1: $$
alpar@1: \begin{array}{l@{\ }c@{\ }r@{\ }c@{\ }r@{\ }c@{\ }r}
alpar@1: x_1&=&a_{11}x_{m+1}&+\dots+&a_{1n}x_{m+n}&+&a_1x \\
alpar@1: x_2&=&a_{21}x_{m+1}&+\dots+&a_{2n}x_{m+n}&+&a_2x \\
alpar@1: \multicolumn{7}{c}
alpar@1: {.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .}\\
alpar@1: x_m&=&a_{m1}x_{m+1}&+\dots+&a_{mn}x_{m+n}&+&a_mx \\
alpar@1: \end{array}
alpar@1: $$
alpar@1: where $x_i$ are auxiliary variables, $x_{m+j}$ are structural variables
alpar@1: (presented in the problem object), $x$ is a structural variable for the
alpar@1: explicitly specified column, $a_i$ are constraint coefficients at $x$.
alpar@1: 
alpar@1: On entry row indices and numerical values of non-zero coefficients
alpar@1: $a_i$ of the specified column should be placed in locations
alpar@1: \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|, \dots,
alpar@1: \verb|val[len]|, where \verb|len| is number of non-zero coefficients.
alpar@1: 
alpar@1: This routine uses the system of equality constraints and the current
alpar@1: basis in order to express the current basic variables through the
alpar@1: structural variable $x$ (as if the transformed column were added to the
alpar@1: problem object and the variable $x$ were non-basic):
alpar@1: $$
alpar@1: \begin{array}{l@{\ }c@{\ }r}
alpar@1: (x_B)_1&=\dots+&\xi_{1}x\\
alpar@1: (x_B)_2&=\dots+&\xi_{2}x\\
alpar@1: \multicolumn{3}{c}{.\ \ .\ \ .\ \ .\ \ .\ \ .}\\
alpar@1: (x_B)_m&=\dots+&\xi_{m}x\\
alpar@1: \end{array}
alpar@1: $$
alpar@1: where $\xi_i$ are influence coefficients, $x_B$ are basic (auxiliary
alpar@1: and structural) variables, $m$ is the number of rows in the problem
alpar@1: object.
alpar@1: 
alpar@1: On exit the routine stores indices and numerical values of non-zero
alpar@1: coefficients $\xi_i$ of the resultant column in locations \verb|ind[1]|,
alpar@1: \dots, \verb|ind[len']| and \verb|val[1]|, \dots, \verb|val[len']|,
alpar@1: where $0\leq{\tt len'}\leq m$ is the number of non-zero coefficients in
alpar@1: the resultant column returned by the routine. Note that indices of basic
alpar@1: variables stored in the array \verb|ind| correspond to original ordinal
alpar@1: numbers of variables, i.e. indices 1 to $m$ mean auxiliary variables,
alpar@1: indices $m+1$ to $m+n$ mean structural ones.
alpar@1: 
alpar@1: \subsubsection*{Returns}
alpar@1: 
alpar@1: The routine \verb|glp_transform_col| returns \verb|len'|, the number of
alpar@1: non-zero coefficients in the resultant column stored in the arrays
alpar@1: \verb|ind| and \verb|val|.
alpar@1: 
alpar@1: \subsection{glp\_prim\_rtest---perform primal ratio test}
alpar@1: 
alpar@1: \subsubsection*{Synopsis}
alpar@1: 
alpar@1: \begin{verbatim}
alpar@1: int glp_prim_rtest(glp_prob *P, int len, const int ind[],
alpar@1:       const double val[], int dir, double eps);
alpar@1: \end{verbatim}
alpar@1: 
alpar@1: \subsubsection*{Description}
alpar@1: 
alpar@1: The routine \verb|glp_prim_rtest| performs the primal ratio test using
alpar@1: an explicitly specified column of the simplex table.
alpar@1: 
alpar@1: The current basic solution associated with the LP problem object must be
alpar@1: primal feasible.
alpar@1: 
alpar@1: The explicitly specified column of the simplex table shows how the basic
alpar@1: variables $x_B$ depend on some non-basic variable $x$ (which is not
alpar@1: necessarily presented in the problem object):
alpar@1: $$
alpar@1: \begin{array}{l@{\ }c@{\ }r}
alpar@1: (x_B)_1&=\dots+&\xi_{1}x\\
alpar@1: (x_B)_2&=\dots+&\xi_{2}x\\
alpar@1: \multicolumn{3}{c}{.\ \ .\ \ .\ \ .\ \ .\ \ .}\\
alpar@1: (x_B)_m&=\dots+&\xi_{m}x\\
alpar@1: \end{array}
alpar@1: $$
alpar@1: 
alpar@1: The column is specifed on entry to the routine in sparse format. Ordinal
alpar@1: numbers of basic variables $(x_B)_i$ should be placed in locations
alpar@1: \verb|ind[1]|, \dots, \verb|ind[len]|, where ordinal number 1 to $m$
alpar@1: denote auxiliary variables, and ordinal numbers $m+1$ to $m+n$ denote
alpar@1: structural variables. The corresponding non-zero coefficients $\xi_i$
alpar@1: should be placed in locations \verb|val[1]|, \dots, \verb|val[len]|. The
alpar@1: arrays \verb|ind| and \verb|val| are not changed by the routine.
alpar@1: 
alpar@1: The parameter \verb|dir| specifies direction in which the variable $x$
alpar@1: changes on entering the basis: $+1$ means increasing, $-1$ means
alpar@1: decreasing.
alpar@1: 
alpar@1: The parameter \verb|eps| is an absolute tolerance (small positive
alpar@1: number, say, $10^{-9}$) used by the routine to skip $\xi_i$'s whose
alpar@1: magnitude is less than \verb|eps|.
alpar@1: 
alpar@1: The routine determines which basic variable (among those specified in
alpar@1: \verb|ind[1]|, \dots, \verb|ind[len]|) reaches its (lower or upper)
alpar@1: bound first before any other basic variables do, and which, therefore,
alpar@1: should leave the basis in order to keep primal feasibility.
alpar@1: 
alpar@1: \subsubsection*{Returns}
alpar@1: 
alpar@1: The routine \verb|glp_prim_rtest| returns the index, \verb|piv|, in the
alpar@1: arrays \verb|ind| and \verb|val| corresponding to the pivot element
alpar@1: chosen, $1\leq$ \verb|piv| $\leq$ \verb|len|. If the adjacent basic
alpar@1: solution is primal unbounded, and therefore the choice cannot be made,
alpar@1: the routine returns zero.
alpar@1: 
alpar@1: \subsubsection*{Comments}
alpar@1: 
alpar@1: If the non-basic variable $x$ is presented in the LP problem object, the
alpar@1: input column can be computed with the routine \verb|glp_eval_tab_col|;
alpar@1: otherwise, it can be computed with the routine \verb|glp_transform_col|.
alpar@1: 
alpar@1: \subsection{glp\_dual\_rtest---perform dual ratio test}
alpar@1: 
alpar@1: \subsubsection*{Synopsis}
alpar@1: 
alpar@1: \begin{verbatim}
alpar@1: int glp_dual_rtest(glp_prob *P, int len, const int ind[],
alpar@1:       const double val[], int dir, double eps);
alpar@1: \end{verbatim}
alpar@1: 
alpar@1: \subsubsection*{Description}
alpar@1: 
alpar@1: The routine \verb|glp_dual_rtest| performs the dual ratio test using
alpar@1: an explicitly specified row of the simplex table.
alpar@1: 
alpar@1: The current basic solution associated with the LP problem object must be
alpar@1: dual feasible.
alpar@1: 
alpar@1: The explicitly specified row of the simplex table is a linear form
alpar@1: that shows how some basic variable $x$ (which is not necessarily
alpar@1: presented in the problem object) depends on non-basic variables $x_N$:
alpar@1: $$x=\xi_1(x_N)_1+\xi_2(x_N)_2+\dots+\xi_n(x_N)_n.$$
alpar@1: 
alpar@1: The row is specified on entry to the routine in sparse format. Ordinal
alpar@1: numbers of non-basic variables $(x_N)_j$ should be placed in locations
alpar@1: \verb|ind[1]|, \dots, \verb|ind[len]|, where ordinal numbers 1 to $m$
alpar@1: denote auxiliary variables, and ordinal numbers $m+1$ to $m+n$ denote
alpar@1: structural variables. The corresponding non-zero coefficients $\xi_j$
alpar@1: should be placed in locations \verb|val[1]|, \dots, \verb|val[len]|.
alpar@1: The arrays \verb|ind| and \verb|val| are not changed by the routine.
alpar@1: 
alpar@1: The parameter \verb|dir| specifies direction in which the variable $x$
alpar@1: changes on leaving the basis: $+1$ means that $x$ goes on its lower
alpar@1: bound, so its reduced cost (dual variable) is increasing (minimization)
alpar@1: or decreasing (maximization); $-1$ means that $x$ goes on its upper
alpar@1: bound, so its reduced cost is decreasing (minimization) or increasing
alpar@1: (maximization).
alpar@1: 
alpar@1: The parameter \verb|eps| is an absolute tolerance (small positive
alpar@1: number, say, $10^{-9}$) used by the routine to skip $\xi_j$'s whose
alpar@1: magnitude is less than \verb|eps|.
alpar@1: 
alpar@1: The routine determines which non-basic variable (among those specified
alpar@1: in \verb|ind[1]|, \dots, \verb|ind[len]|) should enter the basis in
alpar@1: order to keep dual feasibility, because its reduced cost reaches the
alpar@1: (zero) bound first before this occurs for any other non-basic variables.
alpar@1: 
alpar@1: \subsubsection*{Returns}
alpar@1: 
alpar@1: The routine \verb|glp_dual_rtest| returns the index, \verb|piv|, in the
alpar@1: arrays \verb|ind| and \verb|val| corresponding to the pivot element
alpar@1: chosen, $1\leq$ \verb|piv| $\leq$ \verb|len|. If the adjacent basic
alpar@1: solution is dual unbounded, and therefore the choice cannot be made,
alpar@1: the routine returns zero.
alpar@1: 
alpar@1: \subsubsection*{Comments}
alpar@1: 
alpar@1: If the basic variable $x$ is presented in the LP problem object, the
alpar@1: input row can be computed with the routine \verb|glp_eval_tab_row|;
alpar@1: otherwise, it can be computed with the routine \verb|glp_transform_row|.
alpar@1: 
alpar@1: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@1: 
alpar@1: \newpage
alpar@1: 
alpar@1: \section{Post-optimal analysis routines}
alpar@1: 
alpar@1: \subsection{glp\_analyze\_bound---analyze active bound of non-basic
alpar@1: variable}
alpar@1: 
alpar@1: \subsubsection*{Synopsis}
alpar@1: 
alpar@1: \begin{verbatim}
alpar@1: void glp_analyze_bound(glp_prob *P, int k, double *limit1,
alpar@1:       int *var1, double *limit2, int *var2);
alpar@1: \end{verbatim}
alpar@1: 
alpar@1: \subsubsection*{Description}
alpar@1: 
alpar@1: The routine \verb|glp_analyze_bound| analyzes the effect of varying the
alpar@1: active bound of specified non-basic variable.
alpar@1: 
alpar@1: The non-basic variable is specified by the parameter $k$, where
alpar@1: $1\leq k\leq m$ means auxiliary variable of corresponding row, and
alpar@1: $m+1\leq k\leq m+n$ means structural variable (column).
alpar@1: 
alpar@1: Note that the current basic solution must be optimal, and the basis
alpar@1: factorization must exist.
alpar@1: 
alpar@1: Results of the analysis have the following meaning.
alpar@1: 
alpar@1: \verb|value1| is the minimal value of the active bound, at which the
alpar@1: basis still remains primal feasible and thus optimal. \verb|-DBL_MAX|
alpar@1: means that the active bound has no lower limit.
alpar@1: 
alpar@1: \verb|var1| is the ordinal number of an auxiliary (1 to $m$) or
alpar@1: structural ($m+1$ to $m+n$) basic variable, which reaches its bound
alpar@1: first and thereby limits further decreasing the active bound being
alpar@1: analyzed. if \verb|value1| = \verb|-DBL_MAX|, \verb|var1| is set to 0.
alpar@1: 
alpar@1: \verb|value2| is the maximal value of the active bound, at which the
alpar@1: basis still remains primal feasible and thus optimal. \verb|+DBL_MAX|
alpar@1: means that the active bound has no upper limit.
alpar@1: 
alpar@1: \verb|var2| is the ordinal number of an auxiliary (1 to $m$) or
alpar@1: structural ($m+1$ to $m+n$) basic variable, which reaches its bound
alpar@1: first and thereby limits further increasing the active bound being
alpar@1: analyzed. if \verb|value2| = \verb|+DBL_MAX|, \verb|var2| is set to 0.
alpar@1: 
alpar@1: The parameters \verb|value1|, \verb|var1|, \verb|value2|, \verb|var2|
alpar@1: can be specified as \verb|NULL|, in which case corresponding information
alpar@1: is not stored.
alpar@1: 
alpar@1: \newpage
alpar@1: 
alpar@1: \subsection{glp\_analyze\_coef---analyze objective coefficient at basic
alpar@1: variable}
alpar@1: 
alpar@1: \subsubsection*{Synopsis}
alpar@1: 
alpar@1: \begin{verbatim}
alpar@1: void glp_analyze_coef(glp_prob *P, int k, double *coef1,
alpar@1:       int *var1, double *value1, double *coef2, int *var2,
alpar@1:       double *value2);
alpar@1: \end{verbatim}
alpar@1: 
alpar@1: \subsubsection*{Description}
alpar@1: 
alpar@1: The routine \verb|glp_analyze_coef| analyzes the effect of varying the
alpar@1: objective coefficient at specified basic variable.
alpar@1: 
alpar@1: The basic variable is specified by the parameter $k$, where
alpar@1: $1\leq k\leq m$ means auxiliary variable of corresponding row, and
alpar@1: $m+1\leq k\leq m+n$ means structural variable (column).
alpar@1: 
alpar@1: Note that the current basic solution must be optimal, and the basis
alpar@1: factorization must exist.
alpar@1: 
alpar@1: Results of the analysis have the following meaning.
alpar@1: 
alpar@1: \verb|coef1| is the minimal value of the objective coefficient, at
alpar@1: which the basis still remains dual feasible and thus optimal.
alpar@1: \verb|-DBL_MAX| means that the objective coefficient has no lower limit.
alpar@1: 
alpar@1: \verb|var1| is the ordinal number of an auxiliary (1 to $m$) or
alpar@1: structural ($m+1$ to $m+n$) non-basic variable, whose reduced cost
alpar@1: reaches its zero bound first and thereby limits further decreasing the
alpar@1: objective coefficient being analyzed. If \verb|coef1| = \verb|-DBL_MAX|,
alpar@1: \verb|var1| is set to 0.
alpar@1: 
alpar@1: \verb|value1| is value of the basic variable being analyzed in an
alpar@1: adjacent basis, which is defined as follows. Let the objective
alpar@1: coefficient reaches its minimal value (\verb|coef1|) and continues
alpar@1: decreasing. Then the reduced cost of the limiting non-basic variable
alpar@1: (\verb|var1|) becomes dual infeasible and the current basis becomes
alpar@1: non-optimal that forces the limiting non-basic variable to enter the
alpar@1: basis replacing there some basic variable that leaves the basis to keep
alpar@1: primal feasibility. Should note that on determining the adjacent basis
alpar@1: current bounds of the basic variable being analyzed are ignored as if
alpar@1: it were free (unbounded) variable, so it cannot leave the basis. It may
alpar@1: happen that no dual feasible adjacent basis exists, in which case
alpar@1: \verb|value1| is set to \verb|-DBL_MAX| or \verb|+DBL_MAX|.
alpar@1: 
alpar@1: \verb|coef2| is the maximal value of the objective coefficient, at
alpar@1: which the basis still remains dual feasible and thus optimal.
alpar@1: \verb|+DBL_MAX| means that the objective coefficient has no upper limit.
alpar@1: 
alpar@1: \verb|var2| is the ordinal number of an auxiliary (1 to $m$) or
alpar@1: structural ($m+1$ to $m+n$) non-basic variable, whose reduced cost
alpar@1: reaches its zero bound first and thereby limits further increasing the
alpar@1: objective coefficient being analyzed. If \verb|coef2| = \verb|+DBL_MAX|,
alpar@1: \verb|var2| is set to 0.
alpar@1: 
alpar@1: \verb|value2| is value of the basic variable being analyzed in an
alpar@1: adjacent basis, which is defined exactly in the same way as
alpar@1: \verb|value1| above with exception that now the objective coefficient
alpar@1: is increasing.
alpar@1: 
alpar@1: The parameters \verb|coef1|, \verb|var1|, \verb|value1|, \verb|coef2|,
alpar@1: \verb|var2|, \verb|value2| can be specified as \verb|NULL|, in which
alpar@1: case corresponding information is not stored.
alpar@1: 
alpar@1: %* eof *%