lemon-project-template-glpk
view deps/glpk/doc/glpk04.tex @ 9:33de93886c88
Import GLPK 4.47
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 20:59:10 +0100 |
| parents | |
| children |
line source
1 %* glpk04.tex *%
3 \chapter{Advanced API Routines}
5 \section{Background}
6 \label{basbgd}
8 Using vector and matrix notations LP problem (1.1)---(1.3) (see Section
9 \ref{seclp}, page \pageref{seclp}) can be stated as follows:
11 \medskip
13 \noindent
14 \hspace{.5in} minimize (or maximize)
15 $$z=c^Tx_S+c_0\eqno(3.1)$$
16 \hspace{.5in} subject to linear constraints
17 $$x_R=Ax_S\eqno(3.2)$$
18 \hspace{.5in} and bounds of variables
19 $$
20 \begin{array}{l@{\ }c@{\ }l@{\ }c@{\ }l}
21 l_R&\leq&x_R&\leq&u_R\\
22 l_S&\leq&x_S&\leq&u_S\\
23 \end{array}\eqno(3.3)
24 $$
25 where:
27 \noindent
28 $x_R=(x_1,\dots,x_m)$ is the vector of auxiliary variables;
30 \noindent
31 $x_S=(x_{m+1},\dots,x_{m+n})$ is the vector of structural
32 variables;
34 \noindent
35 $z$ is the objective function;
37 \noindent
38 $c=(c_1,\dots,c_n)$ is the vector of objective coefficients;
40 \noindent
41 $c_0$ is the constant term (``shift'') of the objective function;
43 \noindent
44 $A=(a_{11},\dots,a_{mn})$ is the constraint matrix;
46 \noindent
47 $l_R=(l_1,\dots,l_m)$ is the vector of lower bounds of auxiliary
48 variables;
50 \noindent
51 $u_R=(u_1,\dots,u_m)$ is the vector of upper bounds of auxiliary
52 variables;
54 \noindent
55 $l_S=(l_{m+1},\dots,l_{m+n})$ is the vector of lower bounds of
56 structural variables;
58 \noindent
59 $u_S=(u_{m+1},\dots,u_{m+n})$ is the vector of upper bounds of
60 structural variables.
62 \medskip
64 From the simplex method's standpoint there is no difference between
65 auxiliary and structural variables. This allows combining all these
66 variables into one vector that leads to the following problem statement:
68 \medskip
70 \noindent
71 \hspace{.5in} minimize (or maximize)
72 $$z=(0\ |\ c)^Tx+c_0\eqno(3.4)$$
73 \hspace{.5in} subject to linear constraints
74 $$(I\ |-\!A)x=0\eqno(3.5)$$
75 \hspace{.5in} and bounds of variables
76 $$l\leq x\leq u\eqno(3.6)$$
77 where:
79 \noindent
80 $x=(x_R\ |\ x_S)$ is the $(m+n)$-vector of (all) variables;
82 \noindent
83 $(0\ |\ c)$ is the $(m+n)$-vector of objective
84 coefficients;\footnote{Subvector 0 corresponds to objective coefficients
85 at auxiliary variables.}
87 \noindent
88 $(I\ |-\!A)$ is the {\it augmented} constraint
89 $m\times(m+n)$-matrix;\footnote{Note that due to auxiliary variables
90 matrix $(I\ |-\!A)$ contains the unity submatrix and therefore has full
91 rank. This means, in particular, that the system (3.5) has no linearly
92 dependent constraints.}
94 \noindent
95 $l=(l_R\ |\ l_S)$ is the $(m+n)$-vector of lower bounds of (all)
96 variables;
98 \noindent
99 $u=(u_R\ |\ u_S)$ is the $(m+n)$-vector of upper bounds of (all)
100 variables.
102 \medskip
104 By definition an {\it LP basic solution} geometrically is a point in
105 the space of all variables, which is the intersection of planes
106 corresponding to active constraints\footnote{A constraint is called
107 {\it active} if in a given point it is satisfied as equality, otherwise
108 it is called {\it inactive}.}. The space of all variables has the
109 dimension $m+n$, therefore, to define some basic solution we have to
110 define $m+n$ active constraints. Note that $m$ constraints (3.5) being
111 linearly independent equalities are always active, so remaining $n$
112 active constraints can be chosen only from bound constraints (3.6).
114 A variable is called {\it non-basic}, if its (lower or upper) bound is
115 active, otherwise it is called {\it basic}. Since, as was said above,
116 exactly $n$ bound constraints must be active, in any basic solution
117 there are always $n$ non-basic variables and $m$ basic variables.
118 (Note that a free variable also can be non-basic. Although such
119 variable has no bounds, we can think it as the difference between two
120 non-negative variables, which both are non-basic in this case.)
122 Now consider how to determine numeric values of all variables for a
123 given basic solution.
125 Let $\Pi$ be an appropriate permutation matrix of the order $(m+n)$.
126 Then we can write:
127 $$\left(\begin{array}{@{}c@{}}x_B\\x_N\\\end{array}\right)=
128 \Pi\left(\begin{array}{@{}c@{}}x_R\\x_S\\\end{array}\right)=\Pi x,
129 \eqno(3.7)$$
130 where $x_B$ is the vector of basic variables, $x_N$ is the vector of
131 non-basic variables, $x=(x_R\ |\ x_S)$ is the vector of all variables
132 in the original order. In this case the system of linear constraints
133 (3.5) can be rewritten as follows:
134 $$(I\ |-\!A)\Pi^T\Pi x=0\ \ \ \Rightarrow\ \ \ (B\ |\ N)
135 \left(\begin{array}{@{}c@{}}x_B\\x_N\\\end{array}\right)=0,\eqno(3.8)$$
136 where
137 $$(B\ |\ N)=(I\ |-\!A)\Pi^T.\eqno(3.9)$$
138 Matrix $B$ is a square non-singular $m\times m$-matrix, which is
139 composed from columns of the augmented constraint matrix corresponding
140 to basic variables. It is called the {\it basis matrix} or simply the
141 {\it basis}. Matrix $N$ is a rectangular $m\times n$-matrix, which is
142 composed from columns of the augmented constraint matrix corresponding
143 to non-basic variables.
145 From (3.8) it follows that:
146 $$Bx_B+Nx_N=0,\eqno(3.10)$$
147 therefore,
148 $$x_B=-B^{-1}Nx_N.\eqno(3.11)$$
149 Thus, the formula (3.11) shows how to determine numeric values of basic
150 variables $x_B$ assuming that non-basic variables $x_N$ are fixed on
151 their active bounds.
153 The $m\times n$-matrix
154 $$\Xi=-B^{-1}N,\eqno(3.12)$$
155 which appears in (3.11), is called the {\it simplex
156 tableau}.\footnote{This definition corresponds to the GLPK
157 implementation.} It shows how basic variables depend on non-basic
158 variables:
159 $$x_B=\Xi x_N.\eqno(3.13)$$
161 The system (3.13) is equivalent to the system (3.5) in the sense that
162 they both define the same set of points in the space of (primal)
163 variables, which satisfy to these systems. If, moreover, values of all
164 basic variables satisfy to their bound constraints (3.3), the
165 corresponding basic solution is called {\it (primal) feasible},
166 otherwise {\it (primal) infeasible}. It is understood that any (primal)
167 feasible basic solution satisfy to all constraints (3.2) and (3.3).
169 The LP theory says that if LP has optimal solution, it has (at least
170 one) basic feasible solution, which corresponds to the optimum. And the
171 most natural way to determine whether a given basic solution is optimal
172 or not is to use the Karush---Kuhn---Tucker optimality conditions.
174 \def\arraystretch{1.5}
176 For the problem statement (3.4)---(3.6) the optimality conditions are
177 the following:\footnote{These conditions can be appiled to any solution,
178 not only to a basic solution.}
179 $$(I\ |-\!A)x=0\eqno(3.14)$$
180 $$(I\ |-\!A)^T\pi+\lambda_l+\lambda_u=\nabla z=(0\ |\ c)^T\eqno(3.15)$$
181 $$l\leq x\leq u\eqno(3.16)$$
182 $$\lambda_l\geq 0,\ \ \lambda_u\leq 0\ \ \mbox{(minimization)}
183 \eqno(3.17)$$
184 $$\lambda_l\leq 0,\ \ \lambda_u\geq 0\ \ \mbox{(maximization)}
185 \eqno(3.18)$$
186 $$(\lambda_l)_k(x_k-l_k)=0,\ \ (\lambda_u)_k(x_k-u_k)=0,\ \ k=1,2,\dots,
187 m+n\eqno(3.19)$$
188 where:
189 $\pi=(\pi_1,\pi_2,\dots,\pi_m)$ is a $m$-vector of Lagrange
190 multipliers for equality constraints (3.5);
191 $\lambda_l=[(\lambda_l)_1,(\lambda_l)_2,\dots,(\lambda_l)_n]$ is a
192 $n$-vector of Lagrange multipliers for lower bound constraints (3.6);
193 $\lambda_u=[(\lambda_u)_1,(\lambda_u)_2,\dots,(\lambda_u)_n]$ is a
194 $n$-vector of Lagrange multipliers for upper bound constraints (3.6).
196 Condition (3.14) is the {\it primal} (original) system of equality
197 constraints (3.5).
199 Condition (3.15) is the {\it dual} system of equality constraints.
200 It requires the gradient of the objective function to be a linear
201 combination of normals to the planes defined by constraints of the
202 original problem.
204 Condition (3.16) is the primal (original) system of bound constraints
205 (3.6).
207 Condition (3.17) (or (3.18) in case of maximization) is the dual system
208 of bound constraints.
210 Condition (3.19) is the {\it complementary slackness condition}. It
211 requires, for each original (auxiliary or structural) variable $x_k$,
212 that either its (lower or upper) bound must be active, or zero bound of
213 the corresponding Lagrange multiplier ($(\lambda_l)_k$ or
214 $(\lambda_u)_k$) must be active.
216 In GLPK two multipliers $(\lambda_l)_k$ and $(\lambda_u)_k$ for each
217 primal (original) variable $x_k$, $k=1,2,\dots,m+n$, are combined into
218 one multiplier:
219 $$\lambda_k=(\lambda_l)_k+(\lambda_u)_k,\eqno(3.20)$$
220 which is called a {\it dual variable} for $x_k$. This {\it cannot} lead
221 to the ambiguity, because both lower and upper bounds of $x_k$ cannot be
222 active at the same time,\footnote{If $x_k$ is a fixed variable, we can
223 think it as double-bounded variable $l_k\leq x_k\leq u_k$, where
224 $l_k=u_k.$} so at least one of $(\lambda_l)_k$ and $(\lambda_u)_k$ must
225 be equal to zero, and because these multipliers have different signs,
226 the combined multiplier, which is their sum, uniquely defines each of
227 them.
229 \def\arraystretch{1}
231 Using dual variables $\lambda_k$ the dual system of bound constraints
232 (3.17) and (3.18) can be written in the form of so called {\it ``rule of
233 signs''} as follows:
235 \begin{center}
236 \begin{tabular}{|@{\,}c@{$\,$}|@{$\,$}c@{$\,$}|@{$\,$}c@{$\,$}|
237 @{$\,$}c|c@{$\,$}|@{$\,$}c@{$\,$}|@{$\,$}c@{$\,$}|}
238 \hline
239 Original bound&\multicolumn{3}{c|}{Minimization}&\multicolumn{3}{c|}
240 {Maximization}\\
241 \cline{2-7}
242 constraint&$(\lambda_l)_k$&$(\lambda_u)_k$&$(\lambda_l)_k+
243 (\lambda_u)_k$&$(\lambda_l)_k$&$(\lambda_u)_k$&$(\lambda_l)_k+
244 (\lambda_u)_k$\\
245 \hline
246 $-\infty<x_k<+\infty$&$=0$&$=0$&$\lambda_k=0$&$=0$&$=0$&$\lambda_k=0$\\
247 $x_k\geq l_k$&$\geq 0$&$=0$&$\lambda_k\geq 0$&$\leq 0$&$=0$&$\lambda_k
248 \leq0$\\
249 $x_k\leq u_k$&$=0$&$\leq 0$&$\lambda_k\leq 0$&$=0$&$\geq 0$&$\lambda_k
250 \geq0$\\
251 $l_k\leq x_k\leq u_k$&$\geq 0$& $\leq 0$& $-\infty\!<\!\lambda_k\!<
252 \!+\infty$
253 &$\leq 0$& $\geq 0$& $-\infty\!<\!\lambda_k\!<\!+\infty$\\
254 $x_k=l_k=u_k$&$\geq 0$& $\leq 0$& $-\infty\!<\!\lambda_k\!<\!+\infty$&
255 $\leq 0$&
256 $\geq 0$& $-\infty\!<\!\lambda_k\!<\!+\infty$\\
257 \hline
258 \end{tabular}
259 \end{center}
261 May note that each primal variable $x_k$ has its dual counterpart
262 $\lambda_k$ and vice versa. This allows applying the same partition for
263 the vector of dual variables as (3.7):
264 $$\left(\begin{array}{@{}c@{}}\lambda_B\\\lambda_N\\\end{array}\right)=
265 \Pi\lambda,\eqno(3.21)$$
266 where $\lambda_B$ is a vector of dual variables for basic variables
267 $x_B$, $\lambda_N$ is a vector of dual variables for non-basic variables
268 $x_N$.
270 By definition, bounds of basic variables are inactive constraints, so in
271 any basic solution $\lambda_B=0$. Corresponding values of dual variables
272 $\lambda_N$ for non-basic variables $x_N$ can be determined in the
273 following way. From the dual system (3.15) we have:
274 $$(I\ |-\!A)^T\pi+\lambda=(0\ |\ c)^T,\eqno(3.22)$$
275 so multiplying both sides of (3.22) by matrix $\Pi$ gives:
276 $$\Pi(I\ |-\!A)^T\pi+\Pi\lambda=\Pi(0\ |\ c)^T.\eqno(3.23)$$
277 From (3.9) it follows that
278 $$\Pi(I\ |-\!A)^T=[(I\ |-\!A)\Pi^T]^T=(B\ |\ N)^T.\eqno(3.24)$$
279 Further, we can apply the partition (3.7) also to the vector of
280 objective coefficients (see (3.4)):
281 $$\left(\begin{array}{@{}c@{}}c_B\\c_N\\\end{array}\right)=
282 \Pi\left(\begin{array}{@{}c@{}}0\\c\\\end{array}\right),\eqno(3.25)$$
283 where $c_B$ is a vector of objective coefficients at basic variables,
284 $c_N$ is a vector of objective coefficients at non-basic variables.
285 Now, substituting (3.24), (3.21), and (3.25) into (3.23), leads to:
286 $$(B\ |\ N)^T\pi+(\lambda_B\ |\ \lambda_N)^T=(c_B\ |\ c_N)^T,
287 \eqno(3.26)$$
288 and transposing both sides of (3.26) gives the system:
289 $$\left(\begin{array}{@{}c@{}}B^T\\N^T\\\end{array}\right)\pi+
290 \left(\begin{array}{@{}c@{}}\lambda_B\\\lambda_N\\\end{array}\right)=
291 \left(\begin{array}{@{}c@{}}c_B\\c_T\\\end{array}\right),\eqno(3.27)$$
292 which can be written as follows:
293 $$\left\{
294 \begin{array}{@{\ }r@{\ }c@{\ }r@{\ }c@{\ }l@{\ }}
295 B^T\pi&+&\lambda_B&=&c_B\\
296 N^T\pi&+&\lambda_N&=&c_N\\
297 \end{array}
298 \right.\eqno(3.28)
299 $$
300 Lagrange multipliers $\pi=(\pi_i)$ correspond to equality constraints
301 (3.5) and therefore can have any sign. This allows resolving the first
302 subsystem of (3.28) as follows:\footnote{$B^{-T}$ means $(B^T)^{-1}=
303 (B^{-1})^T$.}
304 $$\pi=B^{-T}(c_B-\lambda_B)=-B^{-T}\lambda_B+B^{-T}c_B,\eqno(3.29)$$
305 and substitution of $\pi$ from (3.29) into the second subsystem of
306 (3.28) gives:
307 $$\lambda_N=-N^T\pi+c_N=N^TB^{-T}\lambda_B+(c_N-N^TB^{-T}c_B).
308 \eqno(3.30)$$
309 The latter system can be written in the following final form:
310 $$\lambda_N=-\Xi^T\lambda_B+d,\eqno(3.31)$$
311 where $\Xi$ is the simplex tableau (see (3.12)), and
312 $$d=c_N-N^TB^{-T}c_B=c_N+\Xi^Tc_B\eqno(3.32)$$
313 is the vector of so called {\it reduced costs} of non-basic variables.
315 \pagebreak
317 Above it was said that in any basic solution $\lambda_B=0$, so
318 $\lambda_N=d$ as it follows from (3.31).
320 The system (3.31) is equivalent to the system (3.15) in the sense that
321 they both define the same set of points in the space of dual variables
322 $\lambda$, which satisfy to these systems. If, moreover, values of all
323 dual variables $\lambda_N$ (i.e. reduced costs $d$) satisfy to their
324 bound constraints (i.e. to the ``rule of signs''; see the table above),
325 the corresponding basic solution is called {\it dual feasible},
326 otherwise {\it dual infeasible}. It is understood that any dual feasible
327 solution satisfy to all constraints (3.15) and (3.17) (or (3.18) in case
328 of maximization).
330 It can be easily shown that the complementary slackness condition
331 (3.19) is always satisfied for {\it any} basic solution. Therefore,
332 a basic solution\footnote{It is assumed that a complete basic solution
333 has the form $(x,\lambda)$, i.e. it includes primal as well as dual
334 variables.} is {\it optimal} if and only if it is primal and dual
335 feasible, because in this case it satifies to all the optimality
336 conditions (3.14)---(3.19).
338 \def\arraystretch{1.5}
340 The meaning of reduced costs $d=(d_j)$ of non-basic variables can be
341 explained in the following way. From (3.4), (3.7), and (3.25) it follows
342 that:
343 $$z=c_B^Tx_B+c_N^Tx_N+c_0.\eqno(3.33)$$
344 Substituting $x_B$ from (3.11) into (3.33) we can eliminate basic
345 variables and express the objective only through non-basic variables:
346 $$
347 \begin{array}{r@{\ }c@{\ }l}
348 z&=&c_B^T(-B^{-1}Nx_N)+c_N^Tx_N+c_0=\\
349 &=&(c_N^T-c_B^TB^{-1}N)x_N+c_0=\\
350 &=&(c_N-N^TB^{-T}c_B)^Tx_N+c_0=\\
351 &=&d^Tx_N+c_0.
352 \end{array}\eqno(3.34)
353 $$
354 From (3.34) it is seen that reduced cost $d_j$ shows how the objective
355 function $z$ depends on non-basic variable $(x_N)_j$ in the neighborhood
356 of the current basic solution, i.e. while the current basis remains
357 unchanged.
359 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
361 \newpage
363 \section{LP basis routines}
364 \label{lpbasis}
366 \subsection{glp\_bf\_exists---check if the basis factorization exists}
368 \subsubsection*{Synopsis}
370 \begin{verbatim}
371 int glp_bf_exists(glp_prob *lp);
372 \end{verbatim}
374 \subsubsection*{Returns}
376 If the basis factorization for the current basis associated with the
377 specified problem object exists and therefore is available for
378 computations, the routine \verb|glp_bf_exists| returns non-zero.
379 Otherwise the routine returns zero.
381 \subsubsection*{Comments}
383 Let the problem object have $m$ rows and $n$ columns. In GLPK the
384 {\it basis matrix} $B$ is a square non-singular matrix of the order $m$,
385 whose columns correspond to basic (auxiliary and/or structural)
386 variables. It is defined by the following main
387 equality:\footnote{For more details see Subsection \ref{basbgd},
388 page \pageref{basbgd}.}
389 $$(B\ |\ N)=(I\ |-\!A)\Pi^T,$$
390 where $I$ is the unity matrix of the order $m$, whose columns correspond
391 to auxiliary variables; $A$ is the original constraint
392 $m\times n$-matrix, whose columns correspond to structural variables;
393 $(I\ |-\!A)$ is the augmented constraint\linebreak
394 $m\times(m+n)$-matrix, whose columns correspond to all (auxiliary and
395 structural) variables following in the original order; $\Pi$ is a
396 permutation matrix of the order $m+n$; and $N$ is a rectangular
397 $m\times n$-matrix, whose columns correspond to non-basic (auxiliary
398 and/or structural) variables.
400 For various reasons it may be necessary to solve linear systems with
401 matrix $B$. To provide this possibility the GLPK implementation
402 maintains an invertable form of $B$ (that is, some representation of
403 $B^{-1}$) called the {\it basis factorization}, which is an internal
404 component of the problem object. Typically, the basis factorization is
405 computed by the simplex solver, which keeps it in the problem object
406 to be available for other computations.
408 Should note that any changes in the problem object, which affects the
409 basis matrix (e.g. changing the status of a row or column, changing
410 a basic column of the constraint matrix, removing an active constraint,
411 etc.), invalidates the basis factorization. So before calling any API
412 routine, which uses the basis factorization, the application program
413 must make sure (using the routine \verb|glp_bf_exists|) that the
414 factorization exists and therefore available for computations.
416 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
418 \subsection{glp\_factorize---compute the basis factorization}
420 \subsubsection*{Synopsis}
422 \begin{verbatim}
423 int glp_factorize(glp_prob *lp);
424 \end{verbatim}
426 \subsubsection*{Description}
428 The routine \verb|glp_factorize| computes the basis factorization for
429 the current basis associated with the specified problem
430 object.\footnote{The current basis is defined by the current statuses
431 of rows (auxiliary variables) and columns (structural variables).}
433 The basis factorization is computed from ``scratch'' even if it exists,
434 so the application program may use the routine \verb|glp_bf_exists|,
435 and, if the basis factorization already exists, not to call the routine
436 \verb|glp_factorize| to prevent an extra work.
438 The routine \verb|glp_factorize| {\it does not} compute components of
439 the basic solution (i.e. primal and dual values).
441 \subsubsection*{Returns}
443 \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
444 0 & The basis factorization has been successfully computed.\\
445 \verb|GLP_EBADB| & The basis matrix is invalid, because the number of
446 basic (auxiliary and structural) variables is not the same as the number
447 of rows in the problem object.\\
448 \verb|GLP_ESING| & The basis matrix is singular within the working
449 precision.\\
450 \verb|GLP_ECOND| & The basis matrix is ill-conditioned, i.e. its
451 condition number is too large.\\
452 \end{tabular}
454 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
456 \newpage
458 \subsection{glp\_bf\_updated---check if the basis factorization has\\
459 been updated}
461 \subsubsection*{Synopsis}
463 \begin{verbatim}
464 int glp_bf_updated(glp_prob *lp);
465 \end{verbatim}
467 \subsubsection*{Returns}
469 If the basis factorization has been just computed from ``scratch'', the
470 routine \verb|glp_bf_updated| returns zero. Otherwise, if the
471 factorization has been updated at least once, the routine returns
472 non-zero.
474 \subsubsection*{Comments}
476 {\it Updating} the basis factorization means recomputing it to reflect
477 changes in the basis matrix. For example, on every iteration of the
478 simplex method some column of the current basis matrix is replaced by a
479 new column that gives a new basis matrix corresponding to the adjacent
480 basis. In this case computing the basis factorization for the adjacent
481 basis from ``scratch'' (as the routine \verb|glp_factorize| does) would
482 be too time-consuming.
484 On the other hand, since the basis factorization update is a numeric
485 computational procedure, applying it many times may lead to accumulating
486 round-off errors. Therefore the basis is periodically refactorized
487 (reinverted) from ``scratch'' (with the routine \verb|glp_factorize|)
488 that allows improving its numerical properties.
490 The routine \verb|glp_bf_updated| allows determining if the basis
491 factorization has been updated at least once since it was computed from
492 ``scratch''.
494 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
496 \newpage
498 \subsection{glp\_get\_bfcp---retrieve basis factorization control
499 parameters}
501 \subsubsection*{Synopsis}
503 \begin{verbatim}
504 void glp_get_bfcp(glp_prob *lp, glp_bfcp *parm);
505 \end{verbatim}
507 \subsubsection*{Description}
509 The routine \verb|glp_get_bfcp| retrieves control parameters, which are
510 used on computing and updating the basis factorization associated with
511 the specified problem object.
513 Current values of the control parameters are stored in a \verb|glp_bfcp|
514 structure, which the parameter \verb|parm| points to. For a detailed
515 description of the structure \verb|glp_bfcp| see comments to the routine
516 \verb|glp_set_bfcp| in the next subsection.
518 \subsubsection*{Comments}
520 The purpose of the routine \verb|glp_get_bfcp| is two-fold. First, it
521 allows the application program obtaining current values of control
522 parameters used by internal GLPK routines, which compute and update the
523 basis factorization.
525 The second purpose of this routine is to provide proper values for all
526 fields of the structure \verb|glp_bfcp| in the case when the application
527 program needs to change some control parameters.
529 \subsection{glp\_set\_bfcp---change basis factorization control
530 parameters}
532 \subsubsection*{Synopsis}
534 \begin{verbatim}
535 void glp_set_bfcp(glp_prob *lp, const glp_bfcp *parm);
536 \end{verbatim}
538 \subsubsection*{Description}
540 The routine \verb|glp_set_bfcp| changes control parameters, which are
541 used by internal GLPK routines on computing and updating the basis
542 factorization associated with the specified problem object.
544 New values of the control parameters should be passed in a structure
545 \verb|glp_bfcp|, which the parameter \verb|parm| points to. For a
546 detailed description of the structure \verb|glp_bfcp| see paragraph
547 ``Control parameters'' below.
549 The parameter \verb|parm| can be specified as \verb|NULL|, in which case
550 all control parameters are reset to their default values.
552 \subsubsection*{Comments}
554 Before changing some control parameters with the routine
555 \verb|glp_set_bfcp| the application program should retrieve current
556 values of all control parameters with the routine \verb|glp_get_bfcp|.
557 This is needed for backward compatibility, because in the future there
558 may appear new members in the structure \verb|glp_bfcp|.
560 Note that new values of control parameters come into effect on a next
561 computation of the basis factorization, not immediately.
563 \subsubsection*{Example}
565 \begin{verbatim}
566 glp_prob *lp;
567 glp_bfcp parm;
568 . . .
569 /* retrieve current values of control parameters */
570 glp_get_bfcp(lp, &parm);
571 /* change the threshold pivoting tolerance */
572 parm.piv_tol = 0.05;
573 /* set new values of control parameters */
574 glp_set_bfcp(lp, &parm);
575 . . .
576 \end{verbatim}
578 \subsubsection*{Control parameters}
580 This paragraph describes all basis factorization control parameters
581 currently used in the package. Symbolic names of control parameters are
582 names of corresponding members in the structure \verb|glp_bfcp|.
584 \def\arraystretch{1}
586 \medskip
588 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
589 \multicolumn{2}{@{}l}{{\tt int type} (default: {\tt GLP\_BF\_FT})} \\
590 &Basis factorization type:\\
591 &\verb|GLP_BF_FT|---$LU$ + Forrest--Tomlin update;\\
592 &\verb|GLP_BF_BG|---$LU$ + Schur complement + Bartels--Golub update;\\
593 &\verb|GLP_BF_GR|---$LU$ + Schur complement + Givens rotation update.
594 \\
595 &In case of \verb|GLP_BF_FT| the update is applied to matrix $U$, while
596 in cases of \verb|GLP_BF_BG| and \verb|GLP_BF_GR| the update is applied
597 to the Schur complement.
598 \end{tabular}
600 \medskip
602 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
603 \multicolumn{2}{@{}l}{{\tt int lu\_size} (default: {\tt 0})} \\
604 &The initial size of the Sparse Vector Area, in non-zeros, used on
605 computing $LU$-factorization of the basis matrix for the first time.
606 If this parameter is set to 0, the initial SVA size is determined
607 automatically.\\
608 \end{tabular}
610 \medskip
612 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
613 \multicolumn{2}{@{}l}{{\tt double piv\_tol} (default: {\tt 0.10})} \\
614 &Threshold pivoting (Markowitz) tolerance, 0 $<$ \verb|piv_tol| $<$ 1,
615 used on computing $LU$-factorization of the basis matrix. Element
616 $u_{ij}$ of the active submatrix of factor $U$ fits to be pivot if it
617 satisfies to the stability criterion
618 $|u_{ij}| >= {\tt piv\_tol}\cdot\max|u_{i*}|$, i.e. if it is not very
619 small in the magnitude among other elements in the same row. Decreasing
620 this parameter may lead to better sparsity at the expense of numerical
621 accuracy, and vice versa.\\
622 \end{tabular}
624 \medskip
626 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
627 \multicolumn{2}{@{}l}{{\tt int piv\_lim} (default: {\tt 4})} \\
628 &This parameter is used on computing $LU$-factorization of the basis
629 matrix and specifies how many pivot candidates needs to be considered
630 on choosing a pivot element, \verb|piv_lim| $\geq$ 1. If \verb|piv_lim|
631 candidates have been considered, the pivoting routine prematurely
632 terminates the search with the best candidate found.\\
633 \end{tabular}
635 \medskip
637 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
638 \multicolumn{2}{@{}l}{{\tt int suhl} (default: {\tt GLP\_ON})} \\
639 &This parameter is used on computing $LU$-factorization of the basis
640 matrix. Being set to {\tt GLP\_ON} it enables applying the following
641 heuristic proposed by Uwe Suhl: if a column of the active submatrix has
642 no eligible pivot candidates, it is no more considered until it becomes
643 a column singleton. In many cases this allows reducing the time needed
644 for pivot searching. To disable this heuristic the parameter \verb|suhl|
645 should be set to {\tt GLP\_OFF}.\\
646 \end{tabular}
648 \medskip
650 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
651 \multicolumn{2}{@{}l}{{\tt double eps\_tol} (default: {\tt 1e-15})} \\
652 &Epsilon tolerance, \verb|eps_tol| $\geq$ 0, used on computing
653 $LU$-factorization of the basis matrix. If an element of the active
654 submatrix of factor $U$ is less than \verb|eps_tol| in the magnitude,
655 it is replaced by exact zero.\\
656 \end{tabular}
658 \medskip
660 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
661 \multicolumn{2}{@{}l}{{\tt double max\_gro} (default: {\tt 1e+10})} \\
662 &Maximal growth of elements of factor $U$, \verb|max_gro| $\geq$ 1,
663 allowable on computing $LU$-factorization of the basis matrix. If on
664 some elimination step the ratio $u_{big}/b_{max}$ (where $u_{big}$ is
665 the largest magnitude of elements of factor $U$ appeared in its active
666 submatrix during all the factorization process, $b_{max}$ is the largest
667 magnitude of elements of the basis matrix to be factorized), the basis
668 matrix is considered as ill-conditioned.\\
669 \end{tabular}
671 \medskip
673 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
674 \multicolumn{2}{@{}l}{{\tt int nfs\_max} (default: {\tt 100})} \\
675 &Maximal number of additional row-like factors (entries of the eta
676 file), \verb|nfs_max| $\geq$ 1, which can be added to $LU$-factorization
677 of the basis matrix on updating it with the Forrest--Tomlin technique.
678 This parameter is used only once, before $LU$-factorization is computed
679 for the first time, to allocate working arrays. As a rule, each update
680 adds one new factor (however, some updates may need no addition), so
681 this parameter limits the number of updates between refactorizations.\\
682 \end{tabular}
684 \medskip
686 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
687 \multicolumn{2}{@{}l}{{\tt double upd\_tol} (default: {\tt 1e-6})} \\
688 &Update tolerance, 0 $<$ \verb|upd_tol| $<$ 1, used on updating
689 $LU$-factorization of the basis matrix with the Forrest--Tomlin
690 technique. If after updating the magnitude of some diagonal element
691 $u_{kk}$ of factor $U$ becomes less than
692 ${\tt upd\_tol}\cdot\max(|u_{k*}|, |u_{*k}|)$, the factorization is
693 considered as inaccurate.\\
694 \end{tabular}
696 \medskip
698 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
699 \multicolumn{2}{@{}l}{{\tt int nrs\_max} (default: {\tt 100})} \\
700 &Maximal number of additional rows and columns, \verb|nrs_max| $\geq$ 1,
701 which can be added to $LU$-factorization of the basis matrix on updating
702 it with the Schur complement technique. This parameter is used only
703 once, before $LU$-factorization is computed for the first time, to
704 allocate working arrays. As a rule, each update adds one new row and
705 column (however, some updates may need no addition), so this parameter
706 limits the number of updates between refactorizations.\\
707 \end{tabular}
709 \medskip
711 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
712 \multicolumn{2}{@{}l}{{\tt int rs\_size} (default: {\tt 0})} \\
713 &The initial size of the Sparse Vector Area, in non-zeros, used to
714 store non-zero elements of additional rows and columns introduced on
715 updating $LU$-factorization of the basis matrix with the Schur
716 complement technique. If this parameter is set to 0, the initial SVA
717 size is determined automatically.\\
718 \end{tabular}
720 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
722 \newpage
724 \subsection{glp\_get\_bhead---retrieve the basis header information}
726 \subsubsection*{Synopsis}
728 \begin{verbatim}
729 int glp_get_bhead(glp_prob *lp, int k);
730 \end{verbatim}
732 \subsubsection*{Description}
734 The routine \verb|glp_get_bhead| returns the basis header information
735 for the current basis associated with the specified problem object.
737 \subsubsection*{Returns}
739 If basic variable $(x_B)_k$, $1\leq k\leq m$, is $i$-th auxiliary
740 variable ($1\leq i\leq m$), the routine returns $i$. Otherwise, if
741 $(x_B)_k$ is $j$-th structural variable ($1\leq j\leq n$), the routine
742 returns $m+j$. Here $m$ is the number of rows and $n$ is the number of
743 columns in the problem object.
745 \subsubsection*{Comments}
747 Sometimes the application program may need to know which original
748 (auxiliary and structural) variable correspond to a given basic
749 variable, or, that is the same, which column of the augmented constraint
750 matrix $(I\ |-\!A)$ correspond to a given column of the basis matrix
751 $B$.
753 \def\arraystretch{1}
755 The correspondence is defined as follows:\footnote{For more details see
756 Subsection \ref{basbgd}, page \pageref{basbgd}.}
757 $$\left(\begin{array}{@{}c@{}}x_B\\x_N\\\end{array}\right)=
758 \Pi\left(\begin{array}{@{}c@{}}x_R\\x_S\\\end{array}\right)
759 \ \ \Leftrightarrow
760 \ \ \left(\begin{array}{@{}c@{}}x_R\\x_S\\\end{array}\right)=
761 \Pi^T\left(\begin{array}{@{}c@{}}x_B\\x_N\\\end{array}\right),$$
762 where $x_B$ is the vector of basic variables, $x_N$ is the vector of
763 non-basic variables, $x_R$ is the vector of auxiliary variables
764 following in their original order,\footnote{The original order of
765 auxiliary and structural variables is defined by the ordinal numbers
766 of corresponding rows and columns in the problem object.} $x_S$ is the
767 vector of structural variables following in their original order, $\Pi$
768 is a permutation matrix (which is a component of the basis
769 factorization).
771 Thus, if $(x_B)_k=(x_R)_i$ is $i$-th auxiliary variable, the routine
772 returns $i$, and if $(x_B)_k=(x_S)_j$ is $j$-th structural variable,
773 the routine returns $m+j$, where $m$ is the number of rows in the
774 problem object.
776 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
778 \newpage
780 \subsection{glp\_get\_row\_bind---retrieve row index in the basis\\
781 header}
783 \subsubsection*{Synopsis}
785 \begin{verbatim}
786 int glp_get_row_bind(glp_prob *lp, int i);
787 \end{verbatim}
789 \subsubsection*{Returns}
791 The routine \verb|glp_get_row_bind| returns the index $k$ of basic
792 variable $(x_B)_k$, $1\leq k\leq m$, which is $i$-th auxiliary variable
793 (that is, the auxiliary variable corresponding to $i$-th row),
794 $1\leq i\leq m$, in the current basis associated with the specified
795 problem object, where $m$ is the number of rows. However, if $i$-th
796 auxiliary variable is non-basic, the routine returns zero.
798 \subsubsection*{Comments}
800 The routine \verb|glp_get_row_bind| is an inverse to the routine
801 \verb|glp_get_bhead|: if \verb|glp_get_bhead|$(lp,k)$ returns $i$,
802 \verb|glp_get_row_bind|$(lp,i)$ returns $k$, and vice versa.
804 \subsection{glp\_get\_col\_bind---retrieve column index in the basis
805 header}
807 \subsubsection*{Synopsis}
809 \begin{verbatim}
810 int glp_get_col_bind(glp_prob *lp, int j);
811 \end{verbatim}
813 \subsubsection*{Returns}
815 The routine \verb|glp_get_col_bind| returns the index $k$ of basic
816 variable $(x_B)_k$, $1\leq k\leq m$, which is $j$-th structural
817 variable (that is, the structural variable corresponding to $j$-th
818 column), $1\leq j\leq n$, in the current basis associated with the
819 specified problem object, where $m$ is the number of rows, $n$ is the
820 number of columns. However, if $j$-th structural variable is non-basic,
821 the routine returns zero.
823 \subsubsection*{Comments}
825 The routine \verb|glp_get_col_bind| is an inverse to the routine
826 \verb|glp_get_bhead|: if \verb|glp_get_bhead|$(lp,k)$ returns $m+j$,
827 \verb|glp_get_col_bind|$(lp,j)$ returns $k$, and vice versa.
829 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
831 \newpage
833 \subsection{glp\_ftran---perform forward transformation}
835 \subsubsection*{Synopsis}
837 \begin{verbatim}
838 void glp_ftran(glp_prob *lp, double x[]);
839 \end{verbatim}
841 \subsubsection*{Description}
843 The routine \verb|glp_ftran| performs forward transformation (FTRAN),
844 i.e. it solves the system $Bx=b$, where $B$ is the basis matrix
845 associated with the specified problem object, $x$ is the vector of
846 unknowns to be computed, $b$ is the vector of right-hand sides.
848 On entry to the routine elements of the vector $b$ should be stored in
849 locations \verb|x[1]|, \dots, \verb|x[m]|, where $m$ is the number of
850 rows. On exit the routine stores elements of the vector $x$ in the same
851 locations.
853 \subsection{glp\_btran---perform backward transformation}
855 \subsubsection*{Synopsis}
857 \begin{verbatim}
858 void glp_btran(glp_prob *lp, double x[]);
859 \end{verbatim}
861 \subsubsection*{Description}
863 The routine \verb|glp_btran| performs backward transformation (BTRAN),
864 i.e. it solves the system $B^Tx=b$, where $B^T$ is a matrix transposed
865 to the basis matrix $B$ associated with the specified problem object,
866 $x$ is the vector of unknowns to be computed, $b$ is the vector of
867 right-hand sides.
869 On entry to the routine elements of the vector $b$ should be stored in
870 locations \verb|x[1]|, \dots, \verb|x[m]|, where $m$ is the number of
871 rows. On exit the routine stores elements of the vector $x$ in the same
872 locations.
874 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
876 \newpage
878 \subsection{glp\_warm\_up---``warm up'' LP basis}
880 \subsubsection*{Synopsis}
882 \begin{verbatim}
883 int glp_warm_up(glp_prob *P);
884 \end{verbatim}
886 \subsubsection*{Description}
888 The routine \verb|glp_warm_up| ``warms up'' the LP basis for the
889 specified problem object using current statuses assigned to rows and
890 columns (that is, to auxiliary and structural variables).
892 This operation includes computing factorization of the basis matrix
893 (if it does not exist), computing primal and dual components of basic
894 solution, and determining the solution status.
896 \subsubsection*{Returns}
898 \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
899 0 & The operation has been successfully performed.\\
900 \verb|GLP_EBADB| & The basis matrix is invalid, because the number of
901 basic (auxiliary and structural) variables is not the same as the number
902 of rows in the problem object.\\
903 \verb|GLP_ESING| & The basis matrix is singular within the working
904 precision.\\
905 \verb|GLP_ECOND| & The basis matrix is ill-conditioned, i.e. its
906 condition number is too large.\\
907 \end{tabular}
909 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
911 \newpage
913 \section{Simplex tableau routines}
915 \subsection{glp\_eval\_tab\_row---compute row of the tableau}
917 \subsubsection*{Synopsis}
919 \begin{verbatim}
920 int glp_eval_tab_row(glp_prob *lp, int k, int ind[],
921 double val[]);
922 \end{verbatim}
924 \subsubsection*{Description}
926 The routine \verb|glp_eval_tab_row| computes a row of the current
927 simplex tableau (see Subsection 3.1.1, formula (3.12)), which (row)
928 corresponds to some basic variable specified by the parameter $k$ as
929 follows: if $1\leq k\leq m$, the basic variable is $k$-th auxiliary
930 variable, and if $m+1\leq k\leq m+n$, the basic variable is $(k-m)$-th
931 structural variable, where $m$ is the number of rows and $n$ is the
932 number of columns in the specified problem object. The basis
933 factorization must exist.
935 The computed row shows how the specified basic variable depends on
936 non-basic variables:
937 $$x_k=(x_B)_i=\xi_{i1}(x_N)_1+\xi_{i2}(x_N)_2+\dots+\xi_{in}(x_N)_n,$$
938 where $\xi_{i1}$, $\xi_{i2}$, \dots, $\xi_{in}$ are elements of the
939 simplex table row, $(x_N)_1$, $(x_N)_2$, \dots, $(x_N)_n$ are non-basic
940 (auxiliary and structural) variables.
942 The routine stores column indices and corresponding numeric values of
943 non-zero elements of the computed row in unordered sparse format in
944 locations \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|,
945 \dots, \verb|val[len]|, respectively, where $0\leq{\tt len}\leq n$ is
946 the number of non-zero elements in the row returned on exit.
948 Element indices stored in the array \verb|ind| have the same sense as
949 index $k$, i.e. indices 1 to $m$ denote auxiliary variables while
950 indices $m+1$ to $m+n$ denote structural variables (all these variables
951 are obviously non-basic by definition).
953 \subsubsection*{Returns}
955 The routine \verb|glp_eval_tab_row| returns \verb|len|, which is the
956 number of non-zero elements in the simplex table row stored in the
957 arrays \verb|ind| and \verb|val|.
959 \subsubsection*{Comments}
961 A row of the simplex table is computed as follows. At first, the
962 routine checks that the specified variable $x_k$ is basic and uses the
963 permutation matrix $\Pi$ (3.7) to determine index $i$ of basic variable
964 $(x_B)_i$, which corresponds to $x_k$.
966 The row to be computed is $i$-th row of the matrix $\Xi$ (3.12),
967 therefore:
968 $$\xi_i=e_i^T\Xi=-e_i^TB^{-1}N=-(B^{-T}e_i)^TN,$$
969 where $e_i$ is $i$-th unity vector. So the routine performs BTRAN to
970 obtain $i$-th row of the inverse $B^{-1}$:
971 $$\varrho_i=B^{-T}e_i,$$
972 and then computes elements of the simplex table row as inner products:
973 $$\xi_{ij}=-\varrho_i^TN_j,\ \ j=1,2,\dots,n,$$
974 where $N_j$ is $j$-th column of matrix $N$ (3.9), which (column)
975 corresponds to non-basic variable $(x_N)_j$. The permutation matrix
976 $\Pi$ is used again to convert indices $j$ of non-basic columns to
977 original ordinal numbers of auxiliary and structural variables.
979 \subsection{glp\_eval\_tab\_col---compute column of the tableau}
981 \subsubsection*{Synopsis}
983 \begin{verbatim}
984 int glp_eval_tab_col(glp_prob *lp, int k, int ind[],
985 double val[]);
986 \end{verbatim}
988 \subsubsection*{Description}
990 The routine \verb|glp_eval_tab_col| computes a column of the current
991 simplex tableau (see Subsection 3.1.1, formula (3.12)), which (column)
992 corresponds to some non-basic variable specified by the parameter $k$:
993 if $1\leq k\leq m$, the non-basic variable is $k$-th auxiliary variable,
994 and if $m+1\leq k\leq m+n$, the non-basic variable is $(k-m)$-th
995 structural variable, where $m$ is the number of rows and $n$ is the
996 number of columns in the specified problem object. The basis
997 factorization must exist.
999 The computed column shows how basic variables depends on the specified
1000 non-basic variable $x_k=(x_N)_j$:
1001 $$
1002 \begin{array}{r@{\ }c@{\ }l@{\ }l}
1003 (x_B)_1&=&\dots+\xi_{1j}(x_N)_j&+\dots\\
1004 (x_B)_2&=&\dots+\xi_{2j}(x_N)_j&+\dots\\
1005 .\ \ .&.&.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\\
1006 (x_B)_m&=&\dots+\xi_{mj}(x_N)_j&+\dots\\
1007 \end{array}
1008 $$
1009 where $\xi_{1j}$, $\xi_{2j}$, \dots, $\xi_{mj}$ are elements of the
1010 simplex table column, $(x_B)_1$, $(x_B)_2$, \dots, $(x_B)_m$ are basic
1011 (auxiliary and structural) variables.
1013 The routine stores row indices and corresponding numeric values of
1014 non-zero elements of the computed column in unordered sparse format in
1015 locations \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|,
1016 \dots, \verb|val[len]|, respectively, where $0\leq{\tt len}\leq m$ is
1017 the number of non-zero elements in the column returned on exit.
1019 Element indices stored in the array \verb|ind| have the same sense as
1020 index $k$, i.e. indices 1 to $m$ denote auxiliary variables while
1021 indices $m+1$ to $m+n$ denote structural variables (all these variables
1022 are obviously basic by definition).
1024 \subsubsection*{Returns}
1026 The routine \verb|glp_eval_tab_col| returns \verb|len|, which is the
1027 number of non-zero elements in the simplex table column stored in the
1028 arrays \verb|ind| and \verb|val|.
1030 \subsubsection*{Comments}
1032 A column of the simplex table is computed as follows. At first, the
1033 routine checks that the specified variable $x_k$ is non-basic and uses
1034 the permutation matrix $\Pi$ (3.7) to determine index $j$ of non-basic
1035 variable $(x_N)_j$, which corresponds to $x_k$.
1037 The column to be computed is $j$-th column of the matrix $\Xi$ (3.12),
1038 therefore:
1039 $$\Xi_j=\Xi e_j=-B^{-1}Ne_j=-B^{-1}N_j,$$
1040 where $e_j$ is $j$-th unity vector, $N_j$ is $j$-th column of matrix
1041 $N$ (3.9). So the routine performs FTRAN to transform $N_j$ to the
1042 simplex table column $\Xi_j=(\xi_{ij})$ and uses the permutation matrix
1043 $\Pi$ to convert row indices $i$ to original ordinal numbers of
1044 auxiliary and structural variables.
1046 \newpage
1048 \subsection{glp\_transform\_row---transform explicitly specified\\
1049 row}
1051 \subsubsection*{Synopsis}
1053 \begin{verbatim}
1054 int glp_transform_row(glp_prob *P, int len, int ind[],
1055 double val[]);
1056 \end{verbatim}
1058 \subsubsection*{Description}
1060 The routine \verb|glp_transform_row| performs the same operation as the
1061 routine \verb|glp_eval_tab_row| with exception that the row to be
1062 transformed is specified explicitly as a sparse vector.
1064 The explicitly specified row may be thought as a linear form:
1065 $$x=a_1x_{m+1}+a_2x_{m+2}+\dots+a_nx_{m+n},$$
1066 where $x$ is an auxiliary variable for this row, $a_j$ are coefficients
1067 of the linear form, $x_{m+j}$ are structural variables.
1069 On entry column indices and numerical values of non-zero coefficients
1070 $a_j$ of the specified row should be placed in locations \verb|ind[1]|,
1071 \dots, \verb|ind[len]| and \verb|val[1]|, \dots, \verb|val[len]|, where
1072 \verb|len| is number of non-zero coefficients.
1074 This routine uses the system of equality constraints and the current
1075 basis in order to express the auxiliary variable $x$ through the current
1076 non-basic variables (as if the transformed row were added to the problem
1077 object and the auxiliary variable $x$ were basic), i.e. the resultant
1078 row has the form:
1079 $$x=\xi_1(x_N)_1+\xi_2(x_N)_2+\dots+\xi_n(x_N)_n,$$
1080 where $\xi_j$ are influence coefficients, $(x_N)_j$ are non-basic
1081 (auxiliary and structural) variables, $n$ is the number of columns in
1082 the problem object.
1084 On exit the routine stores indices and numerical values of non-zero
1085 coefficients $\xi_j$ of the resultant row in locations \verb|ind[1]|,
1086 \dots, \verb|ind[len']| and \verb|val[1]|, \dots, \verb|val[len']|,
1087 where $0\leq{\tt len'}\leq n$ is the number of non-zero coefficients in
1088 the resultant row returned by the routine. Note that indices of
1089 non-basic variables stored in the array \verb|ind| correspond to
1090 original ordinal numbers of variables: indices 1 to $m$ mean auxiliary
1091 variables and indices $m+1$ to $m+n$ mean structural ones.
1093 \subsubsection*{Returns}
1095 The routine \verb|glp_transform_row| returns \verb|len'|, the number of
1096 non-zero coefficients in the resultant row stored in the arrays
1097 \verb|ind| and \verb|val|.
1099 \subsection{glp\_transform\_col---transform explicitly specified\\
1100 column}
1102 \subsubsection*{Synopsis}
1104 \begin{verbatim}
1105 int glp_transform_col(glp_prob *P, int len, int ind[],
1106 double val[]);
1107 \end{verbatim}
1109 \subsubsection*{Description}
1111 The routine \verb|glp_transform_col| performs the same operation as the
1112 routine \verb|glp_eval_tab_col| with exception that the column to be
1113 transformed is specified explicitly as a sparse vector.
1115 The explicitly specified column may be thought as it were added to
1116 the original system of equality constraints:
1117 $$
1118 \begin{array}{l@{\ }c@{\ }r@{\ }c@{\ }r@{\ }c@{\ }r}
1119 x_1&=&a_{11}x_{m+1}&+\dots+&a_{1n}x_{m+n}&+&a_1x \\
1120 x_2&=&a_{21}x_{m+1}&+\dots+&a_{2n}x_{m+n}&+&a_2x \\
1121 \multicolumn{7}{c}
1122 {.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .}\\
1123 x_m&=&a_{m1}x_{m+1}&+\dots+&a_{mn}x_{m+n}&+&a_mx \\
1124 \end{array}
1125 $$
1126 where $x_i$ are auxiliary variables, $x_{m+j}$ are structural variables
1127 (presented in the problem object), $x$ is a structural variable for the
1128 explicitly specified column, $a_i$ are constraint coefficients at $x$.
1130 On entry row indices and numerical values of non-zero coefficients
1131 $a_i$ of the specified column should be placed in locations
1132 \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|, \dots,
1133 \verb|val[len]|, where \verb|len| is number of non-zero coefficients.
1135 This routine uses the system of equality constraints and the current
1136 basis in order to express the current basic variables through the
1137 structural variable $x$ (as if the transformed column were added to the
1138 problem object and the variable $x$ were non-basic):
1139 $$
1140 \begin{array}{l@{\ }c@{\ }r}
1141 (x_B)_1&=\dots+&\xi_{1}x\\
1142 (x_B)_2&=\dots+&\xi_{2}x\\
1143 \multicolumn{3}{c}{.\ \ .\ \ .\ \ .\ \ .\ \ .}\\
1144 (x_B)_m&=\dots+&\xi_{m}x\\
1145 \end{array}
1146 $$
1147 where $\xi_i$ are influence coefficients, $x_B$ are basic (auxiliary
1148 and structural) variables, $m$ is the number of rows in the problem
1149 object.
1151 On exit the routine stores indices and numerical values of non-zero
1152 coefficients $\xi_i$ of the resultant column in locations \verb|ind[1]|,
1153 \dots, \verb|ind[len']| and \verb|val[1]|, \dots, \verb|val[len']|,
1154 where $0\leq{\tt len'}\leq m$ is the number of non-zero coefficients in
1155 the resultant column returned by the routine. Note that indices of basic
1156 variables stored in the array \verb|ind| correspond to original ordinal
1157 numbers of variables, i.e. indices 1 to $m$ mean auxiliary variables,
1158 indices $m+1$ to $m+n$ mean structural ones.
1160 \subsubsection*{Returns}
1162 The routine \verb|glp_transform_col| returns \verb|len'|, the number of
1163 non-zero coefficients in the resultant column stored in the arrays
1164 \verb|ind| and \verb|val|.
1166 \subsection{glp\_prim\_rtest---perform primal ratio test}
1168 \subsubsection*{Synopsis}
1170 \begin{verbatim}
1171 int glp_prim_rtest(glp_prob *P, int len, const int ind[],
1172 const double val[], int dir, double eps);
1173 \end{verbatim}
1175 \subsubsection*{Description}
1177 The routine \verb|glp_prim_rtest| performs the primal ratio test using
1178 an explicitly specified column of the simplex table.
1180 The current basic solution associated with the LP problem object must be
1181 primal feasible.
1183 The explicitly specified column of the simplex table shows how the basic
1184 variables $x_B$ depend on some non-basic variable $x$ (which is not
1185 necessarily presented in the problem object):
1186 $$
1187 \begin{array}{l@{\ }c@{\ }r}
1188 (x_B)_1&=\dots+&\xi_{1}x\\
1189 (x_B)_2&=\dots+&\xi_{2}x\\
1190 \multicolumn{3}{c}{.\ \ .\ \ .\ \ .\ \ .\ \ .}\\
1191 (x_B)_m&=\dots+&\xi_{m}x\\
1192 \end{array}
1193 $$
1195 The column is specifed on entry to the routine in sparse format. Ordinal
1196 numbers of basic variables $(x_B)_i$ should be placed in locations
1197 \verb|ind[1]|, \dots, \verb|ind[len]|, where ordinal number 1 to $m$
1198 denote auxiliary variables, and ordinal numbers $m+1$ to $m+n$ denote
1199 structural variables. The corresponding non-zero coefficients $\xi_i$
1200 should be placed in locations \verb|val[1]|, \dots, \verb|val[len]|. The
1201 arrays \verb|ind| and \verb|val| are not changed by the routine.
1203 The parameter \verb|dir| specifies direction in which the variable $x$
1204 changes on entering the basis: $+1$ means increasing, $-1$ means
1205 decreasing.
1207 The parameter \verb|eps| is an absolute tolerance (small positive
1208 number, say, $10^{-9}$) used by the routine to skip $\xi_i$'s whose
1209 magnitude is less than \verb|eps|.
1211 The routine determines which basic variable (among those specified in
1212 \verb|ind[1]|, \dots, \verb|ind[len]|) reaches its (lower or upper)
1213 bound first before any other basic variables do, and which, therefore,
1214 should leave the basis in order to keep primal feasibility.
1216 \subsubsection*{Returns}
1218 The routine \verb|glp_prim_rtest| returns the index, \verb|piv|, in the
1219 arrays \verb|ind| and \verb|val| corresponding to the pivot element
1220 chosen, $1\leq$ \verb|piv| $\leq$ \verb|len|. If the adjacent basic
1221 solution is primal unbounded, and therefore the choice cannot be made,
1222 the routine returns zero.
1224 \subsubsection*{Comments}
1226 If the non-basic variable $x$ is presented in the LP problem object, the
1227 input column can be computed with the routine \verb|glp_eval_tab_col|;
1228 otherwise, it can be computed with the routine \verb|glp_transform_col|.
1230 \subsection{glp\_dual\_rtest---perform dual ratio test}
1232 \subsubsection*{Synopsis}
1234 \begin{verbatim}
1235 int glp_dual_rtest(glp_prob *P, int len, const int ind[],
1236 const double val[], int dir, double eps);
1237 \end{verbatim}
1239 \subsubsection*{Description}
1241 The routine \verb|glp_dual_rtest| performs the dual ratio test using
1242 an explicitly specified row of the simplex table.
1244 The current basic solution associated with the LP problem object must be
1245 dual feasible.
1247 The explicitly specified row of the simplex table is a linear form
1248 that shows how some basic variable $x$ (which is not necessarily
1249 presented in the problem object) depends on non-basic variables $x_N$:
1250 $$x=\xi_1(x_N)_1+\xi_2(x_N)_2+\dots+\xi_n(x_N)_n.$$
1252 The row is specified on entry to the routine in sparse format. Ordinal
1253 numbers of non-basic variables $(x_N)_j$ should be placed in locations
1254 \verb|ind[1]|, \dots, \verb|ind[len]|, where ordinal numbers 1 to $m$
1255 denote auxiliary variables, and ordinal numbers $m+1$ to $m+n$ denote
1256 structural variables. The corresponding non-zero coefficients $\xi_j$
1257 should be placed in locations \verb|val[1]|, \dots, \verb|val[len]|.
1258 The arrays \verb|ind| and \verb|val| are not changed by the routine.
1260 The parameter \verb|dir| specifies direction in which the variable $x$
1261 changes on leaving the basis: $+1$ means that $x$ goes on its lower
1262 bound, so its reduced cost (dual variable) is increasing (minimization)
1263 or decreasing (maximization); $-1$ means that $x$ goes on its upper
1264 bound, so its reduced cost is decreasing (minimization) or increasing
1265 (maximization).
1267 The parameter \verb|eps| is an absolute tolerance (small positive
1268 number, say, $10^{-9}$) used by the routine to skip $\xi_j$'s whose
1269 magnitude is less than \verb|eps|.
1271 The routine determines which non-basic variable (among those specified
1272 in \verb|ind[1]|, \dots, \verb|ind[len]|) should enter the basis in
1273 order to keep dual feasibility, because its reduced cost reaches the
1274 (zero) bound first before this occurs for any other non-basic variables.
1276 \subsubsection*{Returns}
1278 The routine \verb|glp_dual_rtest| returns the index, \verb|piv|, in the
1279 arrays \verb|ind| and \verb|val| corresponding to the pivot element
1280 chosen, $1\leq$ \verb|piv| $\leq$ \verb|len|. If the adjacent basic
1281 solution is dual unbounded, and therefore the choice cannot be made,
1282 the routine returns zero.
1284 \subsubsection*{Comments}
1286 If the basic variable $x$ is presented in the LP problem object, the
1287 input row can be computed with the routine \verb|glp_eval_tab_row|;
1288 otherwise, it can be computed with the routine \verb|glp_transform_row|.
1290 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1292 \newpage
1294 \section{Post-optimal analysis routines}
1296 \subsection{glp\_analyze\_bound---analyze active bound of non-basic
1297 variable}
1299 \subsubsection*{Synopsis}
1301 \begin{verbatim}
1302 void glp_analyze_bound(glp_prob *P, int k, double *limit1,
1303 int *var1, double *limit2, int *var2);
1304 \end{verbatim}
1306 \subsubsection*{Description}
1308 The routine \verb|glp_analyze_bound| analyzes the effect of varying the
1309 active bound of specified non-basic variable.
1311 The non-basic variable is specified by the parameter $k$, where
1312 $1\leq k\leq m$ means auxiliary variable of corresponding row, and
1313 $m+1\leq k\leq m+n$ means structural variable (column).
1315 Note that the current basic solution must be optimal, and the basis
1316 factorization must exist.
1318 Results of the analysis have the following meaning.
1320 \verb|value1| is the minimal value of the active bound, at which the
1321 basis still remains primal feasible and thus optimal. \verb|-DBL_MAX|
1322 means that the active bound has no lower limit.
1324 \verb|var1| is the ordinal number of an auxiliary (1 to $m$) or
1325 structural ($m+1$ to $m+n$) basic variable, which reaches its bound
1326 first and thereby limits further decreasing the active bound being
1327 analyzed. if \verb|value1| = \verb|-DBL_MAX|, \verb|var1| is set to 0.
1329 \verb|value2| is the maximal value of the active bound, at which the
1330 basis still remains primal feasible and thus optimal. \verb|+DBL_MAX|
1331 means that the active bound has no upper limit.
1333 \verb|var2| is the ordinal number of an auxiliary (1 to $m$) or
1334 structural ($m+1$ to $m+n$) basic variable, which reaches its bound
1335 first and thereby limits further increasing the active bound being
1336 analyzed. if \verb|value2| = \verb|+DBL_MAX|, \verb|var2| is set to 0.
1338 The parameters \verb|value1|, \verb|var1|, \verb|value2|, \verb|var2|
1339 can be specified as \verb|NULL|, in which case corresponding information
1340 is not stored.
1342 \newpage
1344 \subsection{glp\_analyze\_coef---analyze objective coefficient at basic
1345 variable}
1347 \subsubsection*{Synopsis}
1349 \begin{verbatim}
1350 void glp_analyze_coef(glp_prob *P, int k, double *coef1,
1351 int *var1, double *value1, double *coef2, int *var2,
1352 double *value2);
1353 \end{verbatim}
1355 \subsubsection*{Description}
1357 The routine \verb|glp_analyze_coef| analyzes the effect of varying the
1358 objective coefficient at specified basic variable.
1360 The basic variable is specified by the parameter $k$, where
1361 $1\leq k\leq m$ means auxiliary variable of corresponding row, and
1362 $m+1\leq k\leq m+n$ means structural variable (column).
1364 Note that the current basic solution must be optimal, and the basis
1365 factorization must exist.
1367 Results of the analysis have the following meaning.
1369 \verb|coef1| is the minimal value of the objective coefficient, at
1370 which the basis still remains dual feasible and thus optimal.
1371 \verb|-DBL_MAX| means that the objective coefficient has no lower limit.
1373 \verb|var1| is the ordinal number of an auxiliary (1 to $m$) or
1374 structural ($m+1$ to $m+n$) non-basic variable, whose reduced cost
1375 reaches its zero bound first and thereby limits further decreasing the
1376 objective coefficient being analyzed. If \verb|coef1| = \verb|-DBL_MAX|,
1377 \verb|var1| is set to 0.
1379 \verb|value1| is value of the basic variable being analyzed in an
1380 adjacent basis, which is defined as follows. Let the objective
1381 coefficient reaches its minimal value (\verb|coef1|) and continues
1382 decreasing. Then the reduced cost of the limiting non-basic variable
1383 (\verb|var1|) becomes dual infeasible and the current basis becomes
1384 non-optimal that forces the limiting non-basic variable to enter the
1385 basis replacing there some basic variable that leaves the basis to keep
1386 primal feasibility. Should note that on determining the adjacent basis
1387 current bounds of the basic variable being analyzed are ignored as if
1388 it were free (unbounded) variable, so it cannot leave the basis. It may
1389 happen that no dual feasible adjacent basis exists, in which case
1390 \verb|value1| is set to \verb|-DBL_MAX| or \verb|+DBL_MAX|.
1392 \verb|coef2| is the maximal value of the objective coefficient, at
1393 which the basis still remains dual feasible and thus optimal.
1394 \verb|+DBL_MAX| means that the objective coefficient has no upper limit.
1396 \verb|var2| is the ordinal number of an auxiliary (1 to $m$) or
1397 structural ($m+1$ to $m+n$) non-basic variable, whose reduced cost
1398 reaches its zero bound first and thereby limits further increasing the
1399 objective coefficient being analyzed. If \verb|coef2| = \verb|+DBL_MAX|,
1400 \verb|var2| is set to 0.
1402 \verb|value2| is value of the basic variable being analyzed in an
1403 adjacent basis, which is defined exactly in the same way as
1404 \verb|value1| above with exception that now the objective coefficient
1405 is increasing.
1407 The parameters \verb|coef1|, \verb|var1|, \verb|value1|, \verb|coef2|,
1408 \verb|var2|, \verb|value2| can be specified as \verb|NULL|, in which
1409 case corresponding information is not stored.
1411 %* eof *%