%* glpk04.tex *%

\chapter{Advanced API Routines}

\section{Background}

\label{basbgd}

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,\dots,x_m)$ is the vector of auxiliary variables;

\noindent

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

variables;

\noindent

$z$ is the objective function;

\noindent

$c=(c_1,\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},\dots,a_{mn})$ is the constraint matrix;

\noindent

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

variables;

\noindent

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

variables;

\noindent

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

structural variables;

\noindent

$u_S=(u_{m+1},\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

\section{LP basis routines}

\label{lpbasis}

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

\subsubsection*{Synopsis}

\begin{verbatim}

int glp_bf_exists(glp_prob *lp);

\end{verbatim}

\subsubsection*{Returns}

If the basis factorization for the current basis associated with the

specified problem object exists and therefore is available for

computations, the routine \verb|glp_bf_exists| returns non-zero.

Otherwise the routine returns zero.

\subsubsection*{Comments}

Let the problem object have $m$ rows and $n$ columns. In GLPK the

{\it basis matrix} $B$ is a square non-singular matrix of the order $m$,

whose columns correspond to basic (auxiliary and/or structural)

variables. It is defined by the following main

equality:\footnote{For more details see Subsection \ref{basbgd},

page \pageref{basbgd}.}

$$(B\ |\ N)=(I\ |-\!A)\Pi^T,$$

where $I$ is the unity matrix of the order $m$, whose columns correspond

to auxiliary variables; $A$ is the original constraint

$m\times n$-matrix, whose columns correspond to structural variables;

$(I\ |-\!A)$ is the augmented constraint\linebreak

$m\times(m+n)$-matrix, whose columns correspond to all (auxiliary and

structural) variables following in the original order; $\Pi$ is a

permutation matrix of the order $m+n$; and $N$ is a rectangular

$m\times n$-matrix, whose columns correspond to non-basic (auxiliary

and/or structural) variables.

For various reasons it may be necessary to solve linear systems with

matrix $B$. To provide this possibility the GLPK implementation

maintains an invertable form of $B$ (that is, some representation of

$B^{-1}$) called the {\it basis factorization}, which is an internal

component of the problem object. Typically, the basis factorization is

computed by the simplex solver, which keeps it in the problem object

to be available for other computations.

Should note that any changes in the problem object, which affects the

basis matrix (e.g. changing the status of a row or column, changing

a basic column of the constraint matrix, removing an active constraint,

etc.), invalidates the basis factorization. So before calling any API

routine, which uses the basis factorization, the application program

must make sure (using the routine \verb|glp_bf_exists|) that the

factorization exists and therefore available for computations.

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

\subsection{glp\_factorize---compute the basis factorization}

\subsubsection*{Synopsis}

\begin{verbatim}

int glp_factorize(glp_prob *lp);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_factorize| computes the basis factorization for

the current basis associated with the specified problem

object.\footnote{The current basis is defined by the current statuses

of rows (auxiliary variables) and columns (structural variables).}

The basis factorization is computed from ``scratch'' even if it exists,

so the application program may use the routine \verb|glp_bf_exists|,

and, if the basis factorization already exists, not to call the routine

\verb|glp_factorize| to prevent an extra work.

The routine \verb|glp_factorize| {\it does not} compute components of

the basic solution (i.e. primal and dual values).

\subsubsection*{Returns}

\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}

0 & The basis factorization has been successfully computed.\\

\verb|GLP_EBADB| & The basis matrix is invalid, because the number of

basic (auxiliary and structural) variables is not the same as the number

of rows in the problem object.\\

\verb|GLP_ESING| & The basis matrix is singular within the working

precision.\\

\verb|GLP_ECOND| & The basis matrix is ill-conditioned, i.e. its

condition number is too large.\\

\end{tabular}

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

\newpage

\subsection{glp\_bf\_updated---check if the basis factorization has\\

been updated}

\subsubsection*{Synopsis}

\begin{verbatim}

int glp_bf_updated(glp_prob *lp);

\end{verbatim}

\subsubsection*{Returns}

If the basis factorization has been just computed from ``scratch'', the

routine \verb|glp_bf_updated| returns zero. Otherwise, if the

factorization has been updated at least once, the routine returns

non-zero.

\subsubsection*{Comments}

{\it Updating} the basis factorization means recomputing it to reflect

changes in the basis matrix. For example, on every iteration of the

simplex method some column of the current basis matrix is replaced by a

new column that gives a new basis matrix corresponding to the adjacent

basis. In this case computing the basis factorization for the adjacent

basis from ``scratch'' (as the routine \verb|glp_factorize| does) would

be too time-consuming.

On the other hand, since the basis factorization update is a numeric

computational procedure, applying it many times may lead to accumulating

round-off errors. Therefore the basis is periodically refactorized

(reinverted) from ``scratch'' (with the routine \verb|glp_factorize|)

that allows improving its numerical properties.

The routine \verb|glp_bf_updated| allows determining if the basis

factorization has been updated at least once since it was computed from

``scratch''.

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

\newpage

\subsection{glp\_get\_bfcp---retrieve basis factorization control

parameters}

\subsubsection*{Synopsis}

\begin{verbatim}

void glp_get_bfcp(glp_prob *lp, glp_bfcp *parm);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_get_bfcp| retrieves control parameters, which are

used on computing and updating the basis factorization associated with

the specified problem object.

Current values of the control parameters are stored in a \verb|glp_bfcp|

structure, which the parameter \verb|parm| points to. For a detailed

description of the structure \verb|glp_bfcp| see comments to the routine

\verb|glp_set_bfcp| in the next subsection.

\subsubsection*{Comments}

The purpose of the routine \verb|glp_get_bfcp| is two-fold. First, it

allows the application program obtaining current values of control

parameters used by internal GLPK routines, which compute and update the

basis factorization.

The second purpose of this routine is to provide proper values for all

fields of the structure \verb|glp_bfcp| in the case when the application

program needs to change some control parameters.

\subsection{glp\_set\_bfcp---change basis factorization control

parameters}

\subsubsection*{Synopsis}

\begin{verbatim}

void glp_set_bfcp(glp_prob *lp, const glp_bfcp *parm);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_bfcp| changes control parameters, which are

used by internal GLPK routines on computing and updating the basis

factorization associated with the specified problem object.

New values of the control parameters should be passed in a structure

\verb|glp_bfcp|, which the parameter \verb|parm| points to. For a

detailed description of the structure \verb|glp_bfcp| see paragraph

``Control parameters'' below.

The parameter \verb|parm| can be specified as \verb|NULL|, in which case

all control parameters are reset to their default values.

\subsubsection*{Comments}

Before changing some control parameters with the routine

\verb|glp_set_bfcp| the application program should retrieve current

values of all control parameters with the routine \verb|glp_get_bfcp|.

This is needed for backward compatibility, because in the future there

may appear new members in the structure \verb|glp_bfcp|.

Note that new values of control parameters come into effect on a next

computation of the basis factorization, not immediately.

\subsubsection*{Example}

\begin{verbatim}

glp_prob *lp;

glp_bfcp parm;

. . .

/* retrieve current values of control parameters */

glp_get_bfcp(lp, &parm);

/* change the threshold pivoting tolerance */

parm.piv_tol = 0.05;

/* set new values of control parameters */

glp_set_bfcp(lp, &parm);

. . .

\end{verbatim}

\subsubsection*{Control parameters}

This paragraph describes all basis factorization control parameters

currently used in the package. Symbolic names of control parameters are

names of corresponding members in the structure \verb|glp_bfcp|.

\def\arraystretch{1}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}

\multicolumn{2}{@{}l}{{\tt int type} (default: {\tt GLP\_BF\_FT})} \\

&Basis factorization type:\\

&\verb|GLP_BF_FT|---$LU$ + Forrest--Tomlin update;\\

&\verb|GLP_BF_BG|---$LU$ + Schur complement + Bartels--Golub update;\\

&\verb|GLP_BF_GR|---$LU$ + Schur complement + Givens rotation update.

\\

&In case of \verb|GLP_BF_FT| the update is applied to matrix $U$, while

in cases of \verb|GLP_BF_BG| and \verb|GLP_BF_GR| the update is applied

to the Schur complement.

\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}

\multicolumn{2}{@{}l}{{\tt int lu\_size} (default: {\tt 0})} \\

&The initial size of the Sparse Vector Area, in non-zeros, used on

computing $LU$-factorization of the basis matrix for the first time.

If this parameter is set to 0, the initial SVA size is determined

automatically.\\

\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}

\multicolumn{2}{@{}l}{{\tt double piv\_tol} (default: {\tt 0.10})} \\

&Threshold pivoting (Markowitz) tolerance, 0 $<$ \verb|piv_tol| $<$ 1,

used on computing $LU$-factorization of the basis matrix. Element

$u_{ij}$ of the active submatrix of factor $U$ fits to be pivot if it

satisfies to the stability criterion

$|u_{ij}| >= {\tt piv\_tol}\cdot\max|u_{i*}|$, i.e. if it is not very

small in the magnitude among other elements in the same row. Decreasing

this parameter may lead to better sparsity at the expense of numerical

accuracy, and vice versa.\\

\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}

\multicolumn{2}{@{}l}{{\tt int piv\_lim} (default: {\tt 4})} \\

&This parameter is used on computing $LU$-factorization of the basis

matrix and specifies how many pivot candidates needs to be considered

on choosing a pivot element, \verb|piv_lim| $\geq$ 1. If \verb|piv_lim|

candidates have been considered, the pivoting routine prematurely

terminates the search with the best candidate found.\\

\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}

\multicolumn{2}{@{}l}{{\tt int suhl} (default: {\tt GLP\_ON})} \\

&This parameter is used on computing $LU$-factorization of the basis

matrix. Being set to {\tt GLP\_ON} it enables applying the following

heuristic proposed by Uwe Suhl: if a column of the active submatrix has

no eligible pivot candidates, it is no more considered until it becomes

a column singleton. In many cases this allows reducing the time needed

for pivot searching. To disable this heuristic the parameter \verb|suhl|

should be set to {\tt GLP\_OFF}.\\

\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}

\multicolumn{2}{@{}l}{{\tt double eps\_tol} (default: {\tt 1e-15})} \\

&Epsilon tolerance, \verb|eps_tol| $\geq$ 0, used on computing

$LU$-factorization of the basis matrix. If an element of the active

submatrix of factor $U$ is less than \verb|eps_tol| in the magnitude,

it is replaced by exact zero.\\

\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}

\multicolumn{2}{@{}l}{{\tt double max\_gro} (default: {\tt 1e+10})} \\

&Maximal growth of elements of factor $U$, \verb|max_gro| $\geq$ 1,

allowable on computing $LU$-factorization of the basis matrix. If on

some elimination step the ratio $u_{big}/b_{max}$ (where $u_{big}$ is

the largest magnitude of elements of factor $U$ appeared in its active

submatrix during all the factorization process, $b_{max}$ is the largest

magnitude of elements of the basis matrix to be factorized), the basis

matrix is considered as ill-conditioned.\\

\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}

\multicolumn{2}{@{}l}{{\tt int nfs\_max} (default: {\tt 100})} \\

&Maximal number of additional row-like factors (entries of the eta

file), \verb|nfs_max| $\geq$ 1, which can be added to $LU$-factorization

of the basis matrix on updating it with the Forrest--Tomlin technique.

This parameter is used only once, before $LU$-factorization is computed

for the first time, to allocate working arrays. As a rule, each update

adds one new factor (however, some updates may need no addition), so

this parameter limits the number of updates between refactorizations.\\

\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}

\multicolumn{2}{@{}l}{{\tt double upd\_tol} (default: {\tt 1e-6})} \\

&Update tolerance, 0 $<$ \verb|upd_tol| $<$ 1, used on updating

$LU$-factorization of the basis matrix with the Forrest--Tomlin

technique. If after updating the magnitude of some diagonal element

$u_{kk}$ of factor $U$ becomes less than

${\tt upd\_tol}\cdot\max(|u_{k*}|, |u_{*k}|)$, the factorization is

considered as inaccurate.\\

\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}

\multicolumn{2}{@{}l}{{\tt int nrs\_max} (default: {\tt 100})} \\

&Maximal number of additional rows and columns, \verb|nrs_max| $\geq$ 1,

which can be added to $LU$-factorization of the basis matrix on updating

it with the Schur complement technique. This parameter is used only

once, before $LU$-factorization is computed for the first time, to

allocate working arrays. As a rule, each update adds one new row and

column (however, some updates may need no addition), so this parameter

limits the number of updates between refactorizations.\\

\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}

\multicolumn{2}{@{}l}{{\tt int rs\_size} (default: {\tt 0})} \\

&The initial size of the Sparse Vector Area, in non-zeros, used to

store non-zero elements of additional rows and columns introduced on

updating $LU$-factorization of the basis matrix with the Schur

complement technique. If this parameter is set to 0, the initial SVA

size is determined automatically.\\

\end{tabular}

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

\newpage

\subsection{glp\_get\_bhead---retrieve the basis header information}

\subsubsection*{Synopsis}

\begin{verbatim}

int glp_get_bhead(glp_prob *lp, int k);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_get_bhead| returns the basis header information

for the current basis associated with the specified problem object.

\subsubsection*{Returns}

If basic variable $(x_B)_k$, $1\leq k\leq m$, is $i$-th auxiliary

variable ($1\leq i\leq m$), the routine returns $i$. Otherwise, if

$(x_B)_k$ is $j$-th structural variable ($1\leq j\leq n$), the routine

returns $m+j$. Here $m$ is the number of rows and $n$ is the number of

columns in the problem object.

\subsubsection*{Comments}

Sometimes the application program may need to know which original

(auxiliary and structural) variable correspond to a given basic

variable, or, that is the same, which column of the augmented constraint

matrix $(I\ |-\!A)$ correspond to a given column of the basis matrix

$B$.

\def\arraystretch{1}

The correspondence is defined as follows:\footnote{For more details see

Subsection \ref{basbgd}, page \pageref{basbgd}.}

$$\left(\begin{array}{@{}c@{}}x_B\\x_N\\\end{array}\right)=

\Pi\left(\begin{array}{@{}c@{}}x_R\\x_S\\\end{array}\right)

\ \ \Leftrightarrow

\ \ \left(\begin{array}{@{}c@{}}x_R\\x_S\\\end{array}\right)=

\Pi^T\left(\begin{array}{@{}c@{}}x_B\\x_N\\\end{array}\right),$$

where $x_B$ is the vector of basic variables, $x_N$ is the vector of

non-basic variables, $x_R$ is the vector of auxiliary variables

following in their original order,\footnote{The original order of

auxiliary and structural variables is defined by the ordinal numbers

of corresponding rows and columns in the problem object.} $x_S$ is the

vector of structural variables following in their original order, $\Pi$

is a permutation matrix (which is a component of the basis

factorization).

Thus, if $(x_B)_k=(x_R)_i$ is $i$-th auxiliary variable, the routine

returns $i$, and if $(x_B)_k=(x_S)_j$ is $j$-th structural variable,

the routine returns $m+j$, where $m$ is the number of rows in the

problem object.

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

\newpage

\subsection{glp\_get\_row\_bind---retrieve row index in the basis\\

header}

\subsubsection*{Synopsis}

\begin{verbatim}

int glp_get_row_bind(glp_prob *lp, int i);

\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_row_bind| returns the index $k$ of basic

variable $(x_B)_k$, $1\leq k\leq m$, which is $i$-th auxiliary variable

(that is, the auxiliary variable corresponding to $i$-th row),

$1\leq i\leq m$, in the current basis associated with the specified

problem object, where $m$ is the number of rows. However, if $i$-th

auxiliary variable is non-basic, the routine returns zero.

\subsubsection*{Comments}

The routine \verb|glp_get_row_bind| is an inverse to the routine

\verb|glp_get_bhead|: if \verb|glp_get_bhead|$(lp,k)$ returns $i$,

\verb|glp_get_row_bind|$(lp,i)$ returns $k$, and vice versa.

\subsection{glp\_get\_col\_bind---retrieve column index in the basis

header}

\subsubsection*{Synopsis}

\begin{verbatim}

int glp_get_col_bind(glp_prob *lp, int j);

\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_col_bind| returns the index $k$ of basic

variable $(x_B)_k$, $1\leq k\leq m$, which is $j$-th structural

variable (that is, the structural variable corresponding to $j$-th

column), $1\leq j\leq n$, in the current basis associated with the

specified problem object, where $m$ is the number of rows, $n$ is the

number of columns. However, if $j$-th structural variable is non-basic,

the routine returns zero.

\subsubsection*{Comments}

The routine \verb|glp_get_col_bind| is an inverse to the routine

\verb|glp_get_bhead|: if \verb|glp_get_bhead|$(lp,k)$ returns $m+j$,

\verb|glp_get_col_bind|$(lp,j)$ returns $k$, and vice versa.

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

\newpage

\subsection{glp\_ftran---perform forward transformation}

\subsubsection*{Synopsis}

\begin{verbatim}

void glp_ftran(glp_prob *lp, double x[]);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_ftran| performs forward transformation (FTRAN),

i.e. it solves the system $Bx=b$, where $B$ is the basis matrix

associated with the specified problem object, $x$ is the vector of

unknowns to be computed, $b$ is the vector of right-hand sides.

On entry to the routine elements of the vector $b$ should be stored in

locations \verb|x[1]|, \dots, \verb|x[m]|, where $m$ is the number of

rows. On exit the routine stores elements of the vector $x$ in the same

locations.

\subsection{glp\_btran---perform backward transformation}

\subsubsection*{Synopsis}

\begin{verbatim}

void glp_btran(glp_prob *lp, double x[]);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_btran| performs backward transformation (BTRAN),

i.e. it solves the system $B^Tx=b$, where $B^T$ is a matrix transposed

to the basis matrix $B$ associated with the specified problem object,

$x$ is the vector of unknowns to be computed, $b$ is the vector of

right-hand sides.

On entry to the routine elements of the vector $b$ should be stored in

locations \verb|x[1]|, \dots, \verb|x[m]|, where $m$ is the number of

rows. On exit the routine stores elements of the vector $x$ in the same

locations.

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

\newpage

\subsection{glp\_warm\_up---``warm up'' LP basis}

\subsubsection*{Synopsis}

\begin{verbatim}

int glp_warm_up(glp_prob *P);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_warm_up| ``warms up'' the LP basis for the

specified problem object using current statuses assigned to rows and

columns (that is, to auxiliary and structural variables).

This operation includes computing factorization of the basis matrix

(if it does not exist), computing primal and dual components of basic

solution, and determining the solution status.

\subsubsection*{Returns}

\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}

0 & The operation has been successfully performed.\\

\verb|GLP_EBADB| & The basis matrix is invalid, because the number of

basic (auxiliary and structural) variables is not the same as the number

of rows in the problem object.\\

\verb|GLP_ESING| & The basis matrix is singular within the working

precision.\\

\verb|GLP_ECOND| & The basis matrix is ill-conditioned, i.e. its

condition number is too large.\\

\end{tabular}

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

\newpage

\section{Simplex tableau routines}

\subsection{glp\_eval\_tab\_row---compute row of the tableau}

\subsubsection*{Synopsis}

\begin{verbatim}

int glp_eval_tab_row(glp_prob *lp, int k, int ind[],

      double val[]);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_eval_tab_row| computes a row of the current

simplex tableau (see Subsection 3.1.1, formula (3.12)), which (row)

corresponds to some basic variable specified by the parameter $k$ as

follows: if $1\leq k\leq m$, the basic variable is $k$-th auxiliary

variable, and if $m+1\leq k\leq m+n$, the basic variable is $(k-m)$-th

structural variable, where $m$ is the number of rows and $n$ is the

number of columns in the specified problem object. The basis

factorization must exist.

The computed row shows how the specified basic variable depends on

non-basic variables:

$$x_k=(x_B)_i=\xi_{i1}(x_N)_1+\xi_{i2}(x_N)_2+\dots+\xi_{in}(x_N)_n,$$

where $\xi_{i1}$, $\xi_{i2}$, \dots, $\xi_{in}$ are elements of the

simplex table row, $(x_N)_1$, $(x_N)_2$, \dots, $(x_N)_n$ are non-basic

(auxiliary and structural) variables.

The routine stores column indices and corresponding numeric values of

non-zero elements of the computed row in unordered sparse format in

locations \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|,

\dots, \verb|val[len]|, respectively, where $0\leq{\tt len}\leq n$ is

the number of non-zero elements in the row returned on exit.

Element indices stored in the array \verb|ind| have the same sense as

index $k$, i.e. indices 1 to $m$ denote auxiliary variables while

indices $m+1$ to $m+n$ denote structural variables (all these variables

are obviously non-basic by definition).

\subsubsection*{Returns}

The routine \verb|glp_eval_tab_row| returns \verb|len|, which is the

number of non-zero elements in the simplex table row stored in the

arrays \verb|ind| and \verb|val|.

\subsubsection*{Comments}

A row of the simplex table is computed as follows. At first, the

routine checks that the specified variable $x_k$ is basic and uses the

permutation matrix $\Pi$ (3.7) to determine index $i$ of basic variable

$(x_B)_i$, which corresponds to $x_k$.

The row to be computed is $i$-th row of the matrix $\Xi$ (3.12),

therefore:

$$\xi_i=e_i^T\Xi=-e_i^TB^{-1}N=-(B^{-T}e_i)^TN,$$

where $e_i$ is $i$-th unity vector. So the routine performs BTRAN to

obtain $i$-th row of the inverse $B^{-1}$:

$$\varrho_i=B^{-T}e_i,$$

and then computes elements of the simplex table row as inner products:

$$\xi_{ij}=-\varrho_i^TN_j,\ \ j=1,2,\dots,n,$$

where $N_j$ is $j$-th column of matrix $N$ (3.9), which (column)

corresponds to non-basic variable $(x_N)_j$. The permutation matrix

$\Pi$ is used again to convert indices $j$ of non-basic columns to

original ordinal numbers of auxiliary and structural variables.

\subsection{glp\_eval\_tab\_col---compute column of the tableau}

\subsubsection*{Synopsis}

\begin{verbatim}

int glp_eval_tab_col(glp_prob *lp, int k, int ind[],

      double val[]);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_eval_tab_col| computes a column of the current

simplex tableau (see Subsection 3.1.1, formula (3.12)), which (column)

corresponds to some non-basic variable specified by the parameter $k$:

if $1\leq k\leq m$, the non-basic variable is $k$-th auxiliary variable,

and if $m+1\leq k\leq m+n$, the non-basic variable is $(k-m)$-th