COIN-OR::LEMON - Graph Library

source: lemon-project-template-glpk/deps/glpk/doc/glpk02.tex @ 9:33de93886c88

subpack-glpk
Last change on this file since 9:33de93886c88 was 9:33de93886c88, checked in by Alpar Juttner <alpar@…>, 13 years ago

Import GLPK 4.47

File size: 111.6 KB
Line 
1%* glpk02.tex *%
2
3\chapter{Basic API Routines}
4
5This chapter describes GLPK API routines intended for using in
6application programs.
7
8\subsubsection*{Library header}
9
10All GLPK API data types and routines are defined in the header file
11\verb|glpk.h|. It should be included in all source files which use
12GLPK API, either directly or indirectly through some other header file
13as follows:
14
15\begin{verbatim}
16   #include <glpk.h>
17\end{verbatim}
18
19\subsubsection*{Error handling}
20
21If some GLPK API routine detects erroneous or incorrect data passed by
22the application program, it writes appropriate diagnostic messages to
23the terminal and then abnormally terminates the application program.
24In most practical cases this allows to simplify programming by avoiding
25numerous checks of return codes. Thus, in order to prevent crashing the
26application program should check all data, which are suspected to be
27incorrect, before calling GLPK API routines.
28
29Should note that this kind of error handling is used only in cases of
30incorrect data passed by the application program. If, for example, the
31application program calls some GLPK API routine to read data from an
32input file and these data are incorrect, the GLPK API routine reports
33about error in the usual way by means of the return code.
34
35\subsubsection*{Thread safety}
36
37Currently GLPK API routines are non-reentrant and therefore cannot be
38used in multi-threaded programs.
39
40\subsubsection*{Array indexing}
41
42Normally all GLPK API routines start array indexing from 1, not from 0
43(except the specially stipulated cases). This means, for example, that
44if some vector $x$ of the length $n$ is passed as an array to some GLPK
45API routine, the latter expects vector components to be placed in
46locations \verb|x[1]|, \verb|x[2]|, \dots, \verb|x[n]|, and the location
47\verb|x[0]| normally is not used.
48
49In order to avoid indexing errors it is most convenient and most
50reliable to declare the array \verb|x| as follows:
51
52\begin{verbatim}
53   double x[1+n];
54\end{verbatim}
55
56\noindent
57or to allocate it as follows:
58
59\begin{verbatim}
60   double *x;
61   . . .
62   x = calloc(1+n, sizeof(double));
63\end{verbatim}
64
65\noindent
66In both cases one extra location \verb|x[0]| is reserved that allows
67passing the array to GLPK routines in a usual way.
68
69\section{Problem object}
70
71All GLPK API routines deal with so called {\it problem object}, which
72is a program object of type \verb|glp_prob| and intended to represent
73a particular LP or MIP instance.
74
75The type \verb|glp_prob| is a data structure declared in the header
76file \verb|glpk.h| as follows:
77
78\begin{verbatim}
79   typedef struct { ... } glp_prob;
80\end{verbatim}
81
82Problem objects (i.e. program objects of the \verb|glp_prob| type) are
83allocated and managed internally by the GLPK API routines. The
84application program should never use any members of the \verb|glp_prob|
85structure directly and should deal only with pointers to these objects
86(that is, \verb|glp_prob *| values).
87
88\pagebreak
89
90The problem object consists of five segments, which are:
91
92$\bullet$ problem segment,
93
94$\bullet$ basis segment,
95
96$\bullet$ interior point segment,
97
98$\bullet$ MIP segment, and
99
100$\bullet$ control parameters and statistics segment.
101
102\subsubsection*{Problem segment}
103
104The {\it problem segment} contains original LP/MIP data, which
105corresponds to the problem formulation (1.1)---(1.3) (see Section
106\ref{seclp}, page \pageref{seclp}). It includes the following
107components:
108
109$\bullet$ rows (auxiliary variables),
110
111$\bullet$ columns (structural variables),
112
113$\bullet$ objective function, and
114
115$\bullet$ constraint matrix.
116
117Rows and columns have the same set of the following attributes:
118
119$\bullet$ ordinal number,
120
121$\bullet$ symbolic name (1 up to 255 arbitrary graphic characters),
122
123$\bullet$ type (free, lower bound, upper bound, double bound, fixed),
124
125$\bullet$ numerical values of lower and upper bounds,
126
127$\bullet$ scale factor.
128
129{\it Ordinal numbers} are intended for referencing rows and columns.
130Row ordinal numbers are integers $1, 2, \dots, m$, and column ordinal
131numbers are integers $1, 2, \dots, n$, where $m$ and $n$ are,
132respectively, the current number of rows and columns in the problem
133object.
134
135{\it Symbolic names} are intended for informational purposes. They also
136can be used for referencing rows and columns.
137
138{\it Types and bounds} of rows (auxiliary variables) and columns
139(structural variables) are explained above (see Section \ref{seclp},
140page \pageref{seclp}).
141
142{\it Scale factors} are used internally for scaling rows and columns of
143the constraint matrix.
144
145Information about the {\it objective function} includes numerical
146values of objective coefficients and a flag, which defines the
147optimization direction (i.e. minimization or maximization).
148
149The {\it constraint matrix} is a $m \times n$ rectangular matrix built
150of constraint coefficients $a_{ij}$, which defines the system of linear
151constraints (1.2) (see Section \ref{seclp}, page \pageref{seclp}). This
152matrix is stored in the problem object in both row-wise and column-wise
153sparse formats.
154
155Once the problem object has been created, the application program can
156access and modify any components of the problem segment in arbitrary
157order.
158
159\subsubsection*{Basis segment}
160
161The {\it basis segment} of the problem object keeps information related
162to the current basic solution. It includes:
163
164$\bullet$ row and column statuses,
165
166$\bullet$ basic solution statuses,
167
168$\bullet$ factorization of the current basis matrix, and
169
170$\bullet$ basic solution components.
171
172The {\it row and column statuses} define which rows and columns are
173basic and which are non-basic. These statuses may be assigned either by
174the application program of by some API routines. Note that these
175statuses are always defined independently on whether the corresponding
176basis is valid or not.
177
178The {\it basic solution statuses} include the {\it primal status} and
179the {\it dual status}, which are set by the simplex-based solver once
180the problem has been solved. The primal status shows whether a primal
181basic solution is feasible, infeasible, or undefined. The dual status
182shows the same for a dual basic solution.
183
184The {\it factorization of the basis matrix} is some factorized form
185(like LU-factorization) of the current basis matrix (defined by the
186current row and column statuses). The factorization is used by the
187simplex-based solver and kept when the solver terminates the search.
188This feature allows efficiently reoptimizing the problem after some
189modifications (for example, after changing some bounds or objective
190coefficients). It also allows performing the post-optimal analysis (for
191example, computing components of the simplex table, etc.).
192
193The {\it basic solution components} include primal and dual values of
194all auxiliary and structural variables for the most recently obtained
195basic solution.
196
197\subsubsection*{Interior point segment}
198
199The {\it interior point segment} is automatically allocated after the
200problem has been solved using the interior point solver. It contains
201interior point solution components, which include the solution status,
202and primal and dual values of all auxiliary and structural variables.
203
204\subsubsection*{MIP segment}
205
206The {\it MIP segment} is used only for MIP problems. This segment
207includes:
208
209$\bullet$ column kinds,
210
211$\bullet$ MIP solution status, and
212
213$\bullet$ MIP solution components.
214
215The {\it column kinds} define which columns (i.e. structural variables)
216are integer and which are continuous.
217
218The {\it MIP solution status} is set by the MIP solver and shows whether
219a MIP solution is integer optimal, integer feasible (non-optimal), or
220undefined.
221
222The {\it MIP solution components} are computed by the MIP solver and
223include primal values of all auxiliary and structural variables for the
224most recently obtained MIP solution.
225
226Note that in case of MIP problem the basis segment corresponds to
227the optimal solution of LP relaxation, which is also available to the
228application program.
229
230Currently the search tree is not kept in the MIP segment. Therefore if
231the search has been terminated, it cannot be continued.
232
233%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
234
235\newpage
236
237\section{Problem creating and modifying routines}
238
239\subsection{glp\_create\_prob---create problem object}
240
241\subsubsection*{Synopsis}
242
243\begin{verbatim}
244glp_prob *glp_create_prob(void);
245\end{verbatim}
246
247\subsubsection*{Description}
248
249The routine \verb|glp_create_prob| creates a new problem object, which
250initially is ``empty'', i.e. has no rows and columns.
251
252\subsubsection*{Returns}
253
254The routine returns a pointer to the created object, which should be
255used in any subsequent operations on this object.
256
257\subsection{glp\_set\_prob\_name---assign (change) problem name}
258
259\subsubsection*{Synopsis}
260
261\begin{verbatim}
262void glp_set_prob_name(glp_prob *lp, const char *name);
263\end{verbatim}
264
265\subsubsection*{Description}
266
267The routine \verb|glp_set_prob_name| assigns a given symbolic
268\verb|name| (1 up to 255 characters) to the specified problem object.
269
270If the parameter \verb|name| is \verb|NULL| or empty string, the routine
271erases an existing symbolic name of the problem object.
272
273\subsection{glp\_set\_obj\_name---assign (change) objective function
274name}
275
276\subsubsection*{Synopsis}
277
278\begin{verbatim}
279void glp_set_obj_name(glp_prob *lp, const char *name);
280\end{verbatim}
281
282\subsubsection*{Description}
283
284The routine \verb|glp_set_obj_name| assigns a given symbolic
285\verb|name| (1 up to 255 characters) to the objective function of the
286specified problem object.
287
288If the parameter \verb|name| is \verb|NULL| or empty string, the routine
289erases an existing symbolic name of the objective function.
290
291\subsection{glp\_set\_obj\_dir---set (change) optimization direction\\
292flag}
293
294\subsubsection*{Synopsis}
295
296\begin{verbatim}
297void glp_set_obj_dir(glp_prob *lp, int dir);
298\end{verbatim}
299
300\subsubsection*{Description}
301
302The routine \verb|glp_set_obj_dir| sets (changes) the optimization
303direction flag (i.e. ``sense'' of the objective function) as specified
304by the parameter \verb|dir|:
305
306\begin{tabular}{@{}ll}
307\verb|GLP_MIN| & minimization; \\
308\verb|GLP_MAX| & maximization. \\
309\end{tabular}
310
311\noindent
312(Note that by default the problem is minimization.)
313
314\subsection{glp\_add\_rows---add new rows to problem object}
315
316\subsubsection*{Synopsis}
317
318\begin{verbatim}
319int glp_add_rows(glp_prob *lp, int nrs);
320\end{verbatim}
321
322\subsubsection*{Description}
323
324The routine \verb|glp_add_rows| adds \verb|nrs| rows (constraints) to
325the specified problem object. New rows are always added to the end of
326the row list, so the ordinal numbers of existing rows are not changed.
327
328Being added each new row is initially free (unbounded) and has empty
329list of the constraint coefficients.
330
331\subsubsection*{Returns}
332
333The routine \verb|glp_add_rows| returns the ordinal number of the first
334new row added to the problem object.
335
336\newpage
337
338\subsection{glp\_add\_cols---add new columns to problem object}
339
340\subsubsection*{Synopsis}
341
342\begin{verbatim}
343int glp_add_cols(glp_prob *lp, int ncs);
344\end{verbatim}
345
346\subsubsection*{Description}
347
348The routine \verb|glp_add_cols| adds \verb|ncs| columns (structural
349variables) to the specified problem object. New columns are always added
350to the end of the column list, so the ordinal numbers of existing
351columns are not changed.
352
353Being added each new column is initially fixed at zero and has empty
354list of the constraint coefficients.
355
356\subsubsection*{Returns}
357
358The routine \verb|glp_add_cols| returns the ordinal number of the first
359new column added to the problem object.
360
361\subsection{glp\_set\_row\_name---assign (change) row name}
362
363\subsubsection*{Synopsis}
364
365\begin{verbatim}
366void glp_set_row_name(glp_prob *lp, int i, const char *name);
367\end{verbatim}
368
369\subsubsection*{Description}
370
371The routine \verb|glp_set_row_name| assigns a given symbolic
372\verb|name| (1 up to 255 characters) to \verb|i|-th row (auxiliary
373variable) of the specified problem object.
374
375If the parameter \verb|name| is \verb|NULL| or empty string, the routine
376erases an existing name of $i$-th row.
377
378\subsection{glp\_set\_col\_name---assign (change) column name}
379
380\subsubsection*{Synopsis}
381
382\begin{verbatim}
383void glp_set_col_name(glp_prob *lp, int j, const char *name);
384\end{verbatim}
385
386\subsubsection*{Description}
387
388The routine \verb|glp_set_col_name| assigns a given symbolic
389\verb|name| (1 up to 255 characters) to \verb|j|-th column (structural
390variable) of the specified problem object.
391
392If the parameter \verb|name| is \verb|NULL| or empty string, the routine
393erases an existing name of $j$-th column.
394
395\subsection{glp\_set\_row\_bnds---set (change) row bounds}
396
397\subsubsection*{Synopsis}
398
399\begin{verbatim}
400void glp_set_row_bnds(glp_prob *lp, int i, int type,
401      double lb, double ub);
402\end{verbatim}
403
404\subsubsection*{Description}
405
406The routine \verb|glp_set_row_bnds| sets (changes) the type and bounds
407of \verb|i|-th row (auxiliary variable) of the specified problem object.
408
409The parameters \verb|type|, \verb|lb|, and \verb|ub| specify the type,
410lower bound, and upper bound, respectively, as follows:
411
412\begin{center}
413\begin{tabular}{cr@{}c@{}ll}
414Type & \multicolumn{3}{c}{Bounds} & Comment \\
415\hline
416\verb|GLP_FR| & $-\infty <$ &$\ x\ $& $< +\infty$
417   & Free (unbounded) variable \\
418\verb|GLP_LO| & $lb \leq$ &$\ x\ $& $< +\infty$
419   & Variable with lower bound \\
420\verb|GLP_UP| & $-\infty <$ &$\ x\ $& $\leq ub$
421   & Variable with upper bound \\
422\verb|GLP_DB| & $lb \leq$ &$\ x\ $& $\leq ub$
423   & Double-bounded variable \\
424\verb|GLP_FX| & $lb =$ &$\ x\ $& $= ub$
425   & Fixed variable \\
426\end{tabular}
427\end{center}
428
429\noindent
430where $x$ is the auxiliary variable associated with $i$-th row.
431
432If the row has no lower bound, the parameter \verb|lb| is ignored. If
433the row has no upper bound, the parameter \verb|ub| is ignored. If the
434row is an equality constraint (i.e. the corresponding auxiliary variable
435is of fixed type), only the parameter \verb|lb| is used while the
436parameter \verb|ub| is ignored.
437
438Being added to the problem object each row is initially free, i.e. its
439type is \verb|GLP_FR|.
440
441\newpage
442
443\subsection{glp\_set\_col\_bnds---set (change) column bounds}
444
445\subsubsection*{Synopsis}
446
447\begin{verbatim}
448void glp_set_col_bnds(glp_prob *lp, int j, int type,
449      double lb, double ub);
450\end{verbatim}
451
452\subsubsection*{Description}
453
454The routine \verb|glp_set_col_bnds| sets (changes) the type and bounds
455of \verb|j|-th column (structural variable) of the specified problem
456object.
457
458The parameters \verb|type|, \verb|lb|, and \verb|ub| specify the type,
459lower bound, and upper bound, respectively, as follows:
460
461\begin{center}
462\begin{tabular}{cr@{}c@{}ll}
463Type & \multicolumn{3}{c}{Bounds} & Comment \\
464\hline
465\verb|GLP_FR| & $-\infty <$ &$\ x\ $& $< +\infty$
466   & Free (unbounded) variable \\
467\verb|GLP_LO| & $lb \leq$ &$\ x\ $& $< +\infty$
468   & Variable with lower bound \\
469\verb|GLP_UP| & $-\infty <$ &$\ x\ $& $\leq ub$
470   & Variable with upper bound \\
471\verb|GLP_DB| & $lb \leq$ &$\ x\ $& $\leq ub$
472   & Double-bounded variable \\
473\verb|GLP_FX| & $lb =$ &$\ x\ $& $= ub$
474   & Fixed variable \\
475\end{tabular}
476\end{center}
477
478\noindent
479where $x$ is the structural variable associated with $j$-th column.
480
481If the column has no lower bound, the parameter \verb|lb| is ignored.
482If the column has no upper bound, the parameter \verb|ub| is ignored.
483If the column is of fixed type, only the parameter \verb|lb| is used
484while the parameter \verb|ub| is ignored.
485
486Being added to the problem object each column is initially fixed at
487zero, i.e. its type is \verb|GLP_FX| and both bounds are 0.
488
489\subsection{glp\_set\_obj\_coef---set (change) objective coefficient
490or constant term}
491
492\subsubsection*{Synopsis}
493
494\begin{verbatim}
495void glp_set_obj_coef(glp_prob *lp, int j, double coef);
496\end{verbatim}
497
498\subsubsection*{Description}
499
500The routine \verb|glp_set_obj_coef| sets (changes) the objective
501coefficient at \verb|j|-th column (structural variable). A new value of
502the objective coefficient is specified by the parameter \verb|coef|.
503
504If the parameter \verb|j| is 0, the routine sets (changes) the constant
505term (``shift'') of the objective function.
506
507\subsection{glp\_set\_mat\_row---set (replace) row of the constraint
508matrix}
509
510\subsubsection*{Synopsis}
511
512\begin{verbatim}
513void glp_set_mat_row(glp_prob *lp, int i, int len,
514      const int ind[], const double val[]);
515\end{verbatim}
516
517\subsubsection*{Description}
518
519The routine \verb|glp_set_mat_row| stores (replaces) the contents of
520\verb|i|-th row of the constraint matrix of the specified problem
521object.
522
523Column indices and numerical values of new row elements must be placed
524in locations \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|,
525\dots, \verb|val[len]|, respectively, where $0 \leq$ \verb|len| $\leq n$
526is the new length of $i$-th row, $n$ is the current number of columns in
527the problem object. Elements with identical column indices are not
528allowed. Zero elements are allowed, but they are not stored in the
529constraint matrix.
530
531If the parameter \verb|len| is 0, the parameters \verb|ind| and/or
532\verb|val| can be specified as \verb|NULL|.
533
534\subsection{glp\_set\_mat\_col---set (replace) column of the
535constr\-aint matrix}
536
537\subsubsection*{Synopsis}
538
539\begin{verbatim}
540void glp_set_mat_col(glp_prob *lp, int j, int len,
541      const int ind[], const double val[]);
542\end{verbatim}
543
544\subsubsection*{Description}
545
546The routine \verb|glp_set_mat_col| stores (replaces) the contents of
547\verb|j|-th column of the constraint matrix of the specified problem
548object.
549
550Row indices and numerical values of new column elements must be placed
551in locations \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|,
552\dots, \verb|val[len]|, respectively, where $0 \leq$ \verb|len| $\leq m$
553is the new length of $j$-th column, $m$ is the current number of rows in
554the problem object. Elements with identical row indices are not allowed.
555Zero elements are allowed, but they are not stored in the constraint
556matrix.
557
558If the parameter \verb|len| is 0, the parameters \verb|ind| and/or
559\verb|val| can be specified as \verb|NULL|.
560
561\subsection{glp\_load\_matrix---load (replace) the whole constraint
562matrix}
563
564\subsubsection*{Synopsis}
565
566\begin{verbatim}
567void glp_load_matrix(glp_prob *lp, int ne, const int ia[],
568      const int ja[], const double ar[]);
569\end{verbatim}
570
571\subsubsection*{Description}
572
573The routine \verb|glp_load_matrix| loads the constraint matrix passed
574in  the arrays \verb|ia|, \verb|ja|, and \verb|ar| into the specified
575problem object. Before loading the current contents of the constraint
576matrix is destroyed.
577
578Constraint coefficients (elements of the constraint matrix) must be
579specified as triplets (\verb|ia[k]|, \verb|ja[k]|, \verb|ar[k]|) for
580$k=1,\dots,ne$, where \verb|ia[k]| is the row index, \verb|ja[k]| is
581the column index, and \verb|ar[k]| is a numeric value of corresponding
582constraint coefficient. The parameter \verb|ne| specifies the total
583number of (non-zero) elements in the matrix to be loaded. Coefficients
584with identical indices are not allowed. Zero coefficients are allowed,
585however, they are not stored in the constraint matrix.
586
587If the parameter \verb|ne| is 0, the parameters \verb|ia|, \verb|ja|,
588and/or \verb|ar| can be specified as \verb|NULL|.
589
590\subsection{glp\_check\_dup---check for duplicate elements in sparse
591matrix}
592
593\subsubsection*{Synopsis}
594
595\begin{verbatim}
596int glp_check_dup(int m, int n, int ne, const int ia[],
597   const int ja[]);
598\end{verbatim}
599
600\subsubsection*{Description}
601
602The routine \verb|glp_check_dup checks| for duplicate elements (that
603is, elements with identical indices) in a sparse matrix specified in
604the coordinate format.
605
606The parameters $m$ and $n$ specifies, respectively, the number of rows
607and columns in the matrix, $m\geq 0$, $n\geq 0$.
608
609The parameter {\it ne} specifies the number of (structurally) non-zero
610elements in the matrix, {\it ne} $\geq 0$.
611
612Elements of the matrix are specified as doublets $(ia[k],ja[k])$ for
613$k=1,\dots,ne$, where $ia[k]$ is a row index, $ja[k]$ is a column index.
614
615The routine \verb|glp_check_dup| can be used prior to a call to the
616routine \verb|glp_load_matrix| to check that the constraint matrix to
617be loaded has no duplicate elements.
618
619\subsubsection*{Returns}
620
621The routine \verb|glp_check_dup| returns one of the following values:
622
623\noindent
624\begin{tabular}{@{}r@{\ }c@{\ }l@{}}
6250&---&the matrix has no duplicate elements;\\
626$-k$&---&indices $ia[k]$ or/and $ja[k]$ are out of range;\\
627$+k$&---&element $(ia[k],ja[k])$ is duplicate.\\
628\end{tabular}
629
630\subsection{glp\_sort\_matrix---sort elements of the constraint matrix}
631
632\subsubsection*{Synopsis}
633
634\begin{verbatim}
635void glp_sort_matrix(glp_prob *P);
636\end{verbatim}
637
638\subsubsection*{Description}
639
640The routine \verb|glp_sort_matrix| sorts elements of the constraint
641matrix rebuilding its row and column linked lists. On exit from the
642routine the constraint matrix is not changed, however, elements in the
643row linked lists become ordered by ascending column indices, and the
644elements in the column linked lists become ordered by ascending row
645indices.
646
647\subsection{glp\_del\_rows---delete rows from problem object}
648
649\subsubsection*{Synopsis}
650
651\begin{verbatim}
652void glp_del_rows(glp_prob *lp, int nrs, const int num[]);
653\end{verbatim}
654
655\subsubsection*{Description}
656
657The routine \verb|glp_del_rows| deletes rows from the specified problem
658ob-\linebreak ject. Ordinal numbers of rows to be deleted should be
659placed in locations \verb|num[1]|, \dots, \verb|num[nrs]|, where
660${\tt nrs}>0$.
661
662Note that deleting rows involves changing ordinal numbers of other
663rows remaining in the problem object. New ordinal numbers of the
664remaining rows are assigned under the assumption that the original
665order of rows is not changed. Let, for example, before deletion there
666be five rows $a$, $b$, $c$, $d$, $e$ with ordinal numbers 1, 2, 3, 4, 5,
667and let rows $b$ and $d$ have been deleted. Then after deletion the
668remaining rows $a$, $c$, $e$ are assigned new oridinal numbers 1, 2, 3.
669
670\subsection{glp\_del\_cols---delete columns from problem object}
671
672\subsubsection*{Synopsis}
673
674\begin{verbatim}
675void glp_del_cols(glp_prob *lp, int ncs, const int num[]);
676\end{verbatim}
677
678\subsubsection*{Description}
679
680The routine \verb|glp_del_cols| deletes columns from the specified
681problem object. Ordinal numbers of columns to be deleted should be
682placed in locations \verb|num[1]|, \dots, \verb|num[ncs]|, where
683${\tt ncs}>0$.
684
685Note that deleting columns involves changing ordinal numbers of other
686columns remaining in the problem object. New ordinal numbers of the
687remaining columns are assigned under the assumption that the original
688order of columns is not changed. Let, for example, before deletion there
689be six columns $p$, $q$, $r$, $s$, $t$, $u$ with ordinal numbers 1, 2,
6903, 4, 5, 6, and let columns $p$, $q$, $s$ have been deleted. Then after
691deletion the remaining columns $r$, $t$, $u$ are assigned new ordinal
692numbers 1, 2, 3.
693
694\subsection{glp\_copy\_prob---copy problem object content}
695
696\subsubsection*{Synopsis}
697
698\begin{verbatim}
699void glp_copy_prob(glp_prob *dest, glp_prob *prob, int names);
700\end{verbatim}
701
702\subsubsection*{Description}
703
704The routine \verb|glp_copy_prob| copies the content of the problem
705object \verb|prob| to the problem object \verb|dest|.
706
707The parameter \verb|names| is a flag. If it is \verb|GLP_ON|,
708the routine also copies all symbolic names; otherwise, if it is
709\verb|GLP_OFF|, no symbolic names are copied.
710
711\newpage
712
713\subsection{glp\_erase\_prob---erase problem object content}
714
715\subsubsection*{Synopsis}
716
717\begin{verbatim}
718void glp_erase_prob(glp_prob *lp);
719\end{verbatim}
720
721\subsubsection*{Description}
722
723The routine \verb|glp_erase_prob| erases the content of the specified
724problem object. The effect of this operation is the same as if the
725problem object would be deleted with the routine \verb|glp_delete_prob|
726and then created anew with the routine \verb|glp_create_prob|, with the
727only exception that the handle (pointer) to the problem object remains
728valid.
729
730\subsection{glp\_delete\_prob---delete problem object}
731
732\subsubsection*{Synopsis}
733
734\begin{verbatim}
735void glp_delete_prob(glp_prob *lp);
736\end{verbatim}
737
738\subsubsection*{Description}
739
740The routine \verb|glp_delete_prob| deletes a problem object, which the
741parameter \verb|lp| points to, freeing all the memory allocated to this
742object.
743
744%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
745
746\newpage
747
748\section{Problem retrieving routines}
749
750\subsection{glp\_get\_prob\_name---retrieve problem name}
751
752\subsubsection*{Synopsis}
753
754\begin{verbatim}
755const char *glp_get_prob_name(glp_prob *lp);
756\end{verbatim}
757
758\subsubsection*{Returns}
759
760The routine \verb|glp_get_prob_name| returns a pointer to an internal
761buffer, which contains symbolic name of the problem. However, if the
762problem has no assigned name, the routine returns \verb|NULL|.
763
764\subsection{glp\_get\_obj\_name---retrieve objective function name}
765
766\subsubsection*{Synopsis}
767
768\begin{verbatim}
769const char *glp_get_obj_name(glp_prob *lp);
770\end{verbatim}
771
772\subsubsection*{Returns}
773
774The routine \verb|glp_get_obj_name| returns a pointer to an internal
775buffer, which contains symbolic name assigned to the objective
776function. However, if the objective function has no assigned name, the
777routine returns \verb|NULL|.
778
779\subsection{glp\_get\_obj\_dir---retrieve optimization direction flag}
780
781\subsubsection*{Synopsis}
782
783\begin{verbatim}
784int glp_get_obj_dir(glp_prob *lp);
785\end{verbatim}
786
787\subsubsection*{Returns}
788
789The routine \verb|glp_get_obj_dir| returns the optimization direction
790flag (i.e. ``sense'' of the objective function):
791
792\begin{tabular}{@{}ll}
793\verb|GLP_MIN| & minimization; \\
794\verb|GLP_MAX| & maximization. \\
795\end{tabular}
796
797\pagebreak
798
799\subsection{glp\_get\_num\_rows---retrieve number of rows}
800
801\subsubsection*{Synopsis}
802
803\begin{verbatim}
804int glp_get_num_rows(glp_prob *lp);
805\end{verbatim}
806
807\subsubsection*{Returns}
808
809The routine \verb|glp_get_num_rows| returns the current number of rows
810in the specified problem object.
811
812\subsection{glp\_get\_num\_cols---retrieve number of columns}
813
814\subsubsection*{Synopsis}
815
816\begin{verbatim}
817int glp_get_num_cols(glp_prob *lp);
818\end{verbatim}
819
820\subsubsection*{Returns}
821
822The routine \verb|glp_get_num_cols| returns the current number of
823columns the specified problem object.
824
825\subsection{glp\_get\_row\_name---retrieve row name}
826
827\subsubsection*{Synopsis}
828
829\begin{verbatim}
830const char *glp_get_row_name(glp_prob *lp, int i);
831\end{verbatim}
832
833\subsubsection*{Returns}
834
835The routine \verb|glp_get_row_name| returns a pointer to an internal
836buffer, which contains a symbolic name assigned to \verb|i|-th row.
837However, if the row has no assigned name, the routine returns
838\verb|NULL|.
839
840\subsection{glp\_get\_col\_name---retrieve column name}
841
842\subsubsection*{Synopsis}
843
844\begin{verbatim}
845const char *glp_get_col_name(glp_prob *lp, int j);
846\end{verbatim}
847
848\subsubsection*{Returns}
849
850The routine \verb|glp_get_col_name| returns a pointer to an internal
851buffer, which contains a symbolic name assigned to \verb|j|-th column.
852However, if the column has no assigned name, the routine returns
853\verb|NULL|.
854
855\subsection{glp\_get\_row\_type---retrieve row type}
856
857\subsubsection*{Synopsis}
858
859\begin{verbatim}
860int glp_get_row_type(glp_prob *lp, int i);
861\end{verbatim}
862
863\subsubsection*{Returns}
864
865The routine \verb|glp_get_row_type| returns the type of \verb|i|-th
866row, i.e. the type of corresponding auxiliary variable, as follows:
867
868\begin{tabular}{@{}ll}
869\verb|GLP_FR| & free (unbounded) variable; \\
870\verb|GLP_LO| & variable with lower bound; \\
871\verb|GLP_UP| & variable with upper bound; \\
872\verb|GLP_DB| & double-bounded variable; \\
873\verb|GLP_FX| & fixed variable. \\
874\end{tabular}
875
876\subsection{glp\_get\_row\_lb---retrieve row lower bound}
877
878\subsubsection*{Synopsis}
879
880\begin{verbatim}
881double glp_get_row_lb(glp_prob *lp, int i);
882\end{verbatim}
883
884\subsubsection*{Returns}
885
886The routine \verb|glp_get_row_lb| returns the lower bound of
887\verb|i|-th row, i.e. the lower bound of corresponding auxiliary
888variable. However, if the row has no lower bound, the routine returns
889\verb|-DBL_MAX|.
890
891\subsection{glp\_get\_row\_ub---retrieve row upper bound}
892
893\subsubsection*{Synopsis}
894
895\begin{verbatim}
896double glp_get_row_ub(glp_prob *lp, int i);
897\end{verbatim}
898
899\subsubsection*{Returns}
900
901The routine \verb|glp_get_row_ub| returns the upper bound of
902\verb|i|-th row, i.e. the upper bound of corresponding auxiliary
903variable. However, if the row has no upper bound, the routine returns
904\verb|+DBL_MAX|.
905
906\subsection{glp\_get\_col\_type---retrieve column type}
907
908\subsubsection*{Synopsis}
909
910\begin{verbatim}
911int glp_get_col_type(glp_prob *lp, int j);
912\end{verbatim}
913
914\subsubsection*{Returns}
915
916The routine \verb|glp_get_col_type| returns the type of \verb|j|-th
917column, i.e. the type of corresponding structural variable, as follows:
918
919\begin{tabular}{@{}ll}
920\verb|GLP_FR| & free (unbounded) variable; \\
921\verb|GLP_LO| & variable with lower bound; \\
922\verb|GLP_UP| & variable with upper bound; \\
923\verb|GLP_DB| & double-bounded variable; \\
924\verb|GLP_FX| & fixed variable. \\
925\end{tabular}
926
927\subsection{glp\_get\_col\_lb---retrieve column lower bound}
928
929\subsubsection*{Synopsis}
930
931\begin{verbatim}
932double glp_get_col_lb(glp_prob *lp, int j);
933\end{verbatim}
934
935\subsubsection*{Returns}
936
937The routine \verb|glp_get_col_lb| returns the lower bound of
938\verb|j|-th column, i.e. the lower bound of corresponding structural
939variable. However, if the column has no lower bound, the routine returns
940\verb|-DBL_MAX|.
941
942\subsection{glp\_get\_col\_ub---retrieve column upper bound}
943
944\subsubsection*{Synopsis}
945
946\begin{verbatim}
947double glp_get_col_ub(glp_prob *lp, int j);
948\end{verbatim}
949
950\subsubsection*{Returns}
951
952The routine \verb|glp_get_col_ub| returns the upper bound of
953\verb|j|-th column, i.e. the upper bound of corresponding structural
954variable. However, if the column has no upper bound, the routine returns
955\verb|+DBL_MAX|.
956
957\subsection{glp\_get\_obj\_coef---retrieve objective coefficient or\\
958constant term}
959
960\subsubsection*{Synopsis}
961
962\begin{verbatim}
963double glp_get_obj_coef(glp_prob *lp, int j);
964\end{verbatim}
965
966\subsubsection*{Returns}
967
968The routine \verb|glp_get_obj_coef| returns the objective coefficient
969at \verb|j|-th structural variable (column).
970
971If the parameter \verb|j| is 0, the routine returns the constant term
972(``shift'') of the objective function.
973
974\subsection{glp\_get\_num\_nz---retrieve number of constraint
975coefficients}
976
977\subsubsection*{Synopsis}
978
979\begin{verbatim}
980int glp_get_num_nz(glp_prob *lp);
981\end{verbatim}
982
983\subsubsection*{Returns}
984
985The routine \verb|glp_get_num_nz| returns the number of non-zero
986elements in the constraint matrix of the specified problem object.
987
988\subsection{glp\_get\_mat\_row---retrieve row of the constraint
989matrix}
990
991\subsubsection*{Synopsis}
992
993\begin{verbatim}
994int glp_get_mat_row(glp_prob *lp, int i, int ind[],
995      double val[]);
996\end{verbatim}
997
998\subsubsection*{Description}
999
1000The routine \verb|glp_get_mat_row| scans (non-zero) elements of
1001\verb|i|-th row of the constraint matrix of the specified problem object
1002and stores their column indices and numeric values to locations
1003\verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|, \dots,
1004\verb|val[len]|, respectively, where $0\leq{\tt len}\leq n$ is the
1005number of elements in $i$-th row, $n$ is the number of columns.
1006
1007The parameter \verb|ind| and/or \verb|val| can be specified as
1008\verb|NULL|, in which case corresponding information is not stored.
1009
1010\subsubsection*{Returns}
1011
1012The routine \verb|glp_get_mat_row| returns the length \verb|len|, i.e.
1013the number of (non-zero) elements in \verb|i|-th row.
1014
1015\subsection{glp\_get\_mat\_col---retrieve column of the constraint\\
1016matrix}
1017
1018\subsubsection*{Synopsis}
1019
1020\begin{verbatim}
1021int glp_get_mat_col(glp_prob *lp, int j, int ind[],
1022      double val[]);
1023\end{verbatim}
1024
1025\subsubsection*{Description}
1026
1027The routine \verb|glp_get_mat_col| scans (non-zero) elements of
1028\verb|j|-th column of the constraint matrix of the specified problem
1029object and stores their row indices and numeric values to locations
1030\verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|, \dots,
1031\verb|val[len]|, respectively, where $0\leq{\tt len}\leq m$ is the
1032number of elements in $j$-th column, $m$ is the number of rows.
1033
1034The parameter \verb|ind| and/or \verb|val| can be specified as
1035\verb|NULL|, in which case corresponding information is not stored.
1036
1037\subsubsection*{Returns}
1038
1039The routine \verb|glp_get_mat_col| returns the length \verb|len|, i.e.
1040the number of (non-zero) elements in \verb|j|-th column.
1041
1042%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1043
1044\newpage
1045
1046\section{Row and column searching routines}
1047
1048\subsection{glp\_create\_index---create the name index}
1049
1050\subsubsection*{Synopsis}
1051
1052\begin{verbatim}
1053void glp_create_index(glp_prob *lp);
1054\end{verbatim}
1055
1056\subsubsection*{Description}
1057
1058The routine \verb|glp_create_index| creates the name index for the
1059specified problem object. The name index is an auxiliary data structure,
1060which is intended to quickly (i.e. for logarithmic time) find rows and
1061columns by their names.
1062
1063This routine can be called at any time. If the name index already
1064exists, the routine does nothing.
1065
1066\subsection{glp\_find\_row---find row by its name}
1067
1068\subsubsection*{Synopsis}
1069
1070\begin{verbatim}
1071int glp_find_row(glp_prob *lp, const char *name);
1072\end{verbatim}
1073
1074\subsubsection*{Returns}
1075
1076The routine \verb|glp_find_row| returns the ordinal number of a row,
1077which is assigned (by the routine \verb|glp_set_row_name|) the specified
1078symbolic \verb|name|. If no such row exists, the routine returns 0.
1079
1080\subsection{glp\_find\_col---find column by its name}
1081
1082\subsubsection*{Synopsis}
1083
1084\begin{verbatim}
1085int glp_find_col(glp_prob *lp, const char *name);
1086\end{verbatim}
1087
1088\subsubsection*{Returns}
1089
1090The routine \verb|glp_find_col| returns the ordinal number of a column,
1091which is assigned (by the routine \verb|glp_set_col_name|) the specified
1092symbolic \verb|name|. If no such column exists, the routine returns 0.
1093
1094\subsection{glp\_delete\_index---delete the name index}
1095
1096\subsubsection*{Synopsis}
1097
1098\begin{verbatim}
1099void glp_delete_index(glp_prob *lp);
1100\end{verbatim}
1101
1102\subsubsection*{Description}
1103
1104The routine \verb|glp_delete_index| deletes the name index previously
1105created by the routine \verb|glp_create_index| and frees the memory
1106allocated to this auxiliary data structure.
1107
1108This routine can be called at any time. If the name index does not
1109exist, the routine does nothing.
1110
1111%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1112
1113\newpage
1114
1115\section{Problem scaling routines}
1116
1117\subsection{Background}
1118
1119In GLPK the {\it scaling} means a linear transformation applied to the
1120constraint matrix to improve its numerical properties.\footnote{In many
1121cases a proper scaling allows making the constraint matrix to be better
1122conditioned, i.e. decreasing its condition number, that makes
1123computations numerically more stable.}
1124
1125The main equality is the following:
1126$$\widetilde{A}=RAS,\eqno(2.1)$$
1127where $A=(a_{ij})$ is the original constraint matrix, $R=(r_{ii})>0$ is
1128a diagonal matrix used to scale rows (constraints), $S=(s_{jj})>0$ is a
1129diagonal matrix used to scale columns (variables), $\widetilde{A}$ is
1130the scaled constraint matrix.
1131
1132From (2.1) it follows that in the {\it scaled} problem instance each
1133original constraint coefficient $a_{ij}$ is replaced by corresponding
1134scaled constraint coefficient:
1135$$\widetilde{a}_{ij}=r_{ii}a_{ij}s_{jj}.\eqno(2.2)$$
1136
1137Note that the scaling is performed internally and therefore
1138transparently to the user. This means that on API level the user always
1139deal with unscaled data.
1140
1141Scale factors $r_{ii}$ and $s_{jj}$ can be set or changed at any time
1142either directly by the application program in a problem specific way
1143(with the routines \verb|glp_set_rii| and \verb|glp_set_sjj|), or by
1144some API routines intended for automatic scaling.
1145
1146\subsection{glp\_set\_rii---set (change) row scale factor}
1147
1148\subsubsection*{Synopsis}
1149
1150\begin{verbatim}
1151void glp_set_rii(glp_prob *lp, int i, double rii);
1152\end{verbatim}
1153
1154\subsubsection*{Description}
1155
1156The routine \verb|glp_set_rii| sets (changes) the scale factor $r_{ii}$
1157for $i$-th row of the specified problem object.
1158
1159\subsection{glp\_set\_sjj---set (change) column scale factor}
1160
1161\subsubsection*{Synopsis}
1162
1163\begin{verbatim}
1164void glp_set_sjj(glp_prob *lp, int j, double sjj);
1165\end{verbatim}
1166
1167\subsubsection*{Description}
1168
1169The routine \verb|glp_set_sjj| sets (changes) the scale factor $s_{jj}$
1170for $j$-th column of the specified problem object.
1171
1172\subsection{glp\_get\_rii---retrieve row scale factor}
1173
1174\subsubsection*{Synopsis}
1175
1176\begin{verbatim}
1177double glp_get_rii(glp_prob *lp, int i);
1178\end{verbatim}
1179
1180\subsubsection*{Returns}
1181
1182The routine \verb|glp_get_rii| returns current scale factor $r_{ii}$ for
1183$i$-th row of the specified problem object.
1184
1185\subsection{glp\_get\_sjj---retrieve column scale factor}
1186
1187\subsubsection*{Synopsis}
1188
1189\begin{verbatim}
1190double glp_get_sjj(glp_prob *lp, int j);
1191\end{verbatim}
1192
1193\subsubsection*{Returns}
1194
1195The routine \verb|glp_get_sjj| returns current scale factor $s_{jj}$ for
1196$j$-th column of the specified problem object.
1197
1198\subsection{glp\_scale\_prob---scale problem data}
1199
1200\subsubsection*{Synopsis}
1201
1202\begin{verbatim}
1203void glp_scale_prob(glp_prob *lp, int flags);
1204\end{verbatim}
1205
1206\subsubsection*{Description}
1207
1208The routine \verb|glp_scale_prob| performs automatic scaling of problem
1209data for the specified problem object.
1210
1211The parameter \verb|flags| specifies scaling options used by the
1212routine. The options can be combined with the bitwise OR operator and
1213may be the following:
1214
1215\begin{tabular}{@{}ll}
1216\verb|GLP_SF_GM| & perform geometric mean scaling;\\
1217\verb|GLP_SF_EQ| & perform equilibration scaling;\\
1218\verb|GLP_SF_2N| & round scale factors to nearest power of two;\\
1219\verb|GLP_SF_SKIP| & skip scaling, if the problem is well scaled.\\
1220\end{tabular}
1221
1222The parameter \verb|flags| may be specified as \verb|GLP_SF_AUTO|, in
1223which case the routine chooses the scaling options automatically.
1224
1225\subsection{glp\_unscale\_prob---unscale problem data}
1226
1227\subsubsection*{Synopsis}
1228
1229\begin{verbatim}
1230void glp_unscale_prob(glp_prob *lp);
1231\end{verbatim}
1232
1233The routine \verb|glp_unscale_prob| performs unscaling of problem data
1234for the specified problem object.
1235
1236``Unscaling'' means replacing the current scaling matrices $R$ and $S$
1237by unity matrices that cancels the scaling effect.
1238
1239%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1240
1241\newpage
1242
1243\section{LP basis constructing routines}
1244
1245\subsection{Background}
1246
1247To start the search the simplex method needs a valid initial basis. In
1248GLPK the basis is completely defined by a set of {\it statuses} assigned
1249to {\it all} (auxiliary and structural) variables, where the status may
1250be one of the following:
1251
1252\begin{tabular}{@{}ll}
1253\verb|GLP_BS| & basic variable;\\
1254\verb|GLP_NL| & non-basic variable having active lower bound;\\
1255\verb|GLP_NU| & non-basic variable having active upper bound;\\
1256\verb|GLP_NF| & non-basic free variable;\\
1257\verb|GLP_NS| & non-basic fixed variable.\\
1258\end{tabular}
1259
1260The basis is {\it valid}, if the basis matrix, which is a matrix built
1261of columns of the augmented constraint matrix $(I\:|-A)$ corresponding
1262to basic variables, is non-singular. This, in particular, means that
1263the number of basic variables must be the same as the number of rows in
1264the problem object. (For more details see Section \ref{lpbasis}, page
1265\pageref{lpbasis}.)
1266
1267Any initial basis may be constructed (or restored) with the API
1268routines \verb|glp_set_row_stat| and \verb|glp_set_col_stat| by
1269assigning appropriate statuses to auxiliary and structural variables.
1270Another way to construct an initial basis is to use API routines like
1271\verb|glp_adv_basis|, which implement so called
1272{\it crashing}.\footnote{This term is from early linear programming
1273systems and means a heuristic to construct a valid initial basis.} Note
1274that on normal exit the simplex solver remains the basis valid, so in
1275case of reoptimization there is no need to construct an initial basis
1276from scratch.
1277
1278\subsection{glp\_set\_row\_stat---set (change) row status}
1279
1280\subsubsection*{Synopsis}
1281
1282\begin{verbatim}
1283void glp_set_row_stat(glp_prob *lp, int i, int stat);
1284\end{verbatim}
1285
1286\subsubsection*{Description}
1287
1288The routine \verb|glp_set_row_stat| sets (changes) the current status
1289of \verb|i|-th row (auxiliary variable) as specified by the parameter
1290\verb|stat|:
1291
1292\begin{tabular}{@{}lp{104.2mm}@{}}
1293\verb|GLP_BS| & make the row basic (make the constraint inactive); \\
1294\verb|GLP_NL| & make the row non-basic (make the constraint active); \\
1295\end{tabular}
1296
1297\newpage
1298
1299\begin{tabular}{@{}lp{104.2mm}@{}}
1300\verb|GLP_NU| & make the row non-basic and set it to the upper bound;
1301   if the row is not double-bounded, this status is equivalent to
1302   \verb|GLP_NL| (only in the case of this routine); \\
1303\verb|GLP_NF| & the same as \verb|GLP_NL| (only in the case of this
1304   routine); \\
1305\verb|GLP_NS| & the same as \verb|GLP_NL| (only in the case of this
1306   routine). \\
1307\end{tabular}
1308
1309\subsection{glp\_set\_col\_stat---set (change) column status}
1310
1311\subsubsection*{Synopsis}
1312
1313\begin{verbatim}
1314void glp_set_col_stat(glp_prob *lp, int j, int stat);
1315\end{verbatim}
1316
1317\subsubsection*{Description}
1318
1319The routine \verb|glp_set_col_stat sets| (changes) the current status
1320of \verb|j|-th column (structural variable) as specified by the
1321parameter \verb|stat|:
1322
1323\begin{tabular}{@{}lp{104.2mm}@{}}
1324\verb|GLP_BS| & make the column basic; \\
1325\verb|GLP_NL| & make the column non-basic; \\
1326\verb|GLP_NU| & make the column non-basic and set it to the upper
1327   bound; if the column is not double-bounded, this status is equivalent
1328   to \verb|GLP_NL| (only in the case of this routine); \\
1329\verb|GLP_NF| & the same as \verb|GLP_NL| (only in the case of this
1330   routine); \\
1331\verb|GLP_NS| & the same as \verb|GLP_NL| (only in the case of this
1332   routine).
1333\end{tabular}
1334
1335\subsection{glp\_std\_basis---construct standard initial LP basis}
1336
1337\subsubsection*{Synopsis}
1338
1339\begin{verbatim}
1340void glp_std_basis(glp_prob *lp);
1341\end{verbatim}
1342
1343\subsubsection*{Description}
1344
1345The routine \verb|glp_std_basis| constructs the ``standard'' (trivial)
1346initial LP basis for the specified problem object.
1347
1348In the ``standard'' LP basis all auxiliary variables (rows) are basic,
1349and all structural variables (columns) are non-basic (so the
1350corresponding basis matrix is unity).
1351
1352\newpage
1353
1354\subsection{glp\_adv\_basis---construct advanced initial LP basis}
1355
1356\subsubsection*{Synopsis}
1357
1358\begin{verbatim}
1359void glp_adv_basis(glp_prob *lp, int flags);
1360\end{verbatim}
1361
1362\subsubsection*{Description}
1363
1364The routine \verb|glp_adv_basis| constructs an advanced initial LP
1365basis for the specified problem object.
1366
1367The parameter \verb|flags| is reserved for use in the future and must
1368be specified as zero.
1369
1370In order to construct the advanced initial LP basis the routine does
1371the following:
1372
13731) includes in the basis all non-fixed auxiliary variables;
1374
13752) includes in the basis as many non-fixed structural variables as
1376possible keeping the triangular form of the basis matrix;
1377
13783) includes in the basis appropriate (fixed) auxiliary variables to
1379complete the basis.
1380
1381As a result the initial LP basis has as few fixed variables as possible
1382and the corresponding basis matrix is triangular.
1383
1384\subsection{glp\_cpx\_basis---construct Bixby's initial LP basis}
1385
1386\subsubsection*{Synopsis}
1387
1388\begin{verbatim}
1389void glp_cpx_basis(glp_prob *lp);
1390\end{verbatim}
1391
1392\subsubsection*{Description}
1393
1394The routine \verb|glp_cpx_basis| constructs an initial basis for the
1395specified problem object with the algorithm proposed by
1396R.~Bixby.\footnote{Robert E. Bixby, ``Implementing the Simplex Method:
1397The Initial Basis.'' ORSA Journal on Computing, Vol. 4, No. 3, 1992,
1398pp. 267-84.}
1399
1400%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1401
1402\newpage
1403
1404\section{Simplex method routines}
1405
1406The {\it simplex method} is a well known efficient numerical procedure
1407to solve LP problems.
1408
1409On each iteration the simplex method transforms the original system of
1410equaility constraints (1.2) resolving them through different sets of
1411variables to an equivalent system called {\it the simplex table} (or
1412sometimes {\it the simplex tableau}), which has the following form:
1413$$
1414\begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}
1415z&=&d_1(x_N)_1&+&d_2(x_N)_2&+ \dots +&d_n(x_N)_n \\
1416(x_B)_1&=&\xi_{11}(x_N)_1& +& \xi_{12}(x_N)_2& + \dots +&
1417   \xi_{1n}(x_N)_n \\
1418(x_B)_2&=& \xi_{21}(x_N)_1& +& \xi_{22}(x_N)_2& + \dots +&
1419   \xi_{2n}(x_N)_n \\
1420\multicolumn{7}{c}
1421{.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .} \\
1422(x_B)_m&=&\xi_{m1}(x_N)_1& +& \xi_{m2}(x_N)_2& + \dots +&
1423   \xi_{mn}(x_N)_n \\
1424\end{array} \eqno (2.3)
1425$$
1426where: $(x_B)_1, (x_B)_2, \dots, (x_B)_m$ are basic variables;
1427$(x_N)_1, (x_N)_2, \dots, (x_N)_n$ are non-basic variables;
1428$d_1, d_2, \dots, d_n$ are reduced costs;
1429$\xi_{11}, \xi_{12}, \dots, \xi_{mn}$ are coefficients of the
1430simplex table. (May note that the original LP problem (1.1)---(1.3) also
1431has the form of a simplex table, where all equalities are resolved
1432through auxiliary variables.)
1433
1434From the linear programming theory it is known that if an optimal
1435solution of the LP problem (1.1)---(1.3) exists, it can always be
1436written in the form (2.3), where non-basic variables are set on their
1437bounds while values of the objective function and basic variables are
1438determined by the corresponding equalities of the simplex table.
1439
1440A set of values of all basic and non-basic variables determined by the
1441simplex table is called {\it basic solution}. If all basic variables are
1442within their bounds, the basic solution is called {\it (primal)
1443feasible}, otherwise it is called {\it (primal) infeasible}. A feasible
1444basic solution, which provides a smallest (in case of minimization) or
1445a largest (in case of maximization) value of the objective function is
1446called {\it optimal}. Therefore, for solving LP problem the simplex
1447method tries to find its optimal basic solution.
1448
1449Primal feasibility of some basic solution may be stated by simple
1450checking if all basic variables are within their bounds. Basic solution
1451is optimal if additionally the following optimality conditions are
1452satisfied for all non-basic variables:
1453\begin{center}
1454\begin{tabular}{lcc}
1455Status of $(x_N)_j$ & Minimization & Maximization \\
1456\hline
1457$(x_N)_j$ is free & $d_j = 0$ & $d_j = 0$ \\
1458$(x_N)_j$ is on its lower bound & $d_j \geq 0$ & $d_j \leq 0$ \\
1459$(x_N)_j$ is on its upper bound & $d_j \leq 0$ & $d_j \geq 0$ \\
1460\end{tabular}
1461\end{center}
1462In other words, basic solution is optimal if there is no non-basic
1463variable, which changing in the feasible direction (i.e. increasing if
1464it is free or on its lower bound, or decreasing if it is free or on its
1465upper bound) can improve (i.e. decrease in case of minimization or
1466increase in case of maximization) the objective function.
1467
1468If all non-basic variables satisfy to the optimality conditions shown
1469above (independently on whether basic variables are within their bounds
1470or not), the basic solution is called {\it dual feasible}, otherwise it
1471is called {\it dual infeasible}.
1472
1473It may happen that some LP problem has no primal feasible solution due
1474to incorrect formulation---this means that its constraints conflict
1475with each other. It also may happen that some LP problem has unbounded
1476solution again due to incorrect formulation---this means that some
1477non-basic variable can improve the objective function, i.e. the
1478optimality conditions are violated, and at the same time this variable
1479can infinitely change in the feasible direction meeting no resistance
1480from basic variables. (May note that in the latter case the LP problem
1481has no dual feasible solution.)
1482
1483%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1484
1485\subsection{glp\_simplex---solve LP problem with the primal or dual
1486simplex method}
1487
1488\subsubsection*{Synopsis}
1489
1490\begin{verbatim}
1491int glp_simplex(glp_prob *lp, const glp_smcp *parm);
1492\end{verbatim}
1493
1494\subsubsection*{Description}
1495
1496The routine \verb|glp_simplex| is a driver to the LP solver based on
1497the simplex method. This routine retrieves problem data from the
1498specified problem object, calls the solver to solve the problem
1499instance, and stores results of computations back into the problem
1500object.
1501
1502The simplex solver has a set of control parameters. Values of the
1503control parameters can be passed in the structure \verb|glp_smcp|,
1504which the parameter \verb|parm| points to. For detailed description of
1505this structure see paragraph ``Control parameters'' below.
1506Before specifying some control parameters the application program
1507should initialize the structure \verb|glp_smcp| by default values of
1508all control parameters using the routine \verb|glp_init_smcp| (see the
1509next subsection). This is needed for backward compatibility, because in
1510the future there may appear new members in the structure
1511\verb|glp_smcp|.
1512
1513The parameter \verb|parm| can be specified as \verb|NULL|, in which
1514case the solver uses default settings.
1515
1516\subsubsection*{Returns}
1517
1518\def\arraystretch{1}
1519
1520\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
15210 & The LP problem instance has been successfully solved. (This code
1522does {\it not} necessarily mean that the solver has found optimal
1523solution. It only means that the solution process was successful.) \\
1524\verb|GLP_EBADB| & Unable to start the search, because the initial basis
1525specified in the problem object is invalid---the number of basic
1526(auxiliary and structural) variables is not the same as the number of
1527rows in the problem object.\\
1528\verb|GLP_ESING| & Unable to start the search, because the basis matrix
1529corresponding to the initial basis is singular within the working
1530precision.\\
1531\verb|GLP_ECOND| & Unable to start the search, because the basis matrix
1532corresponding to the initial basis is ill-conditioned, i.e. its
1533condition number is too large.\\
1534\verb|GLP_EBOUND| & Unable to start the search, because some
1535double-bounded (auxiliary or structural) variables have incorrect
1536bounds.\\
1537\verb|GLP_EFAIL| & The search was prematurely terminated due to the
1538solver failure.\\
1539\verb|GLP_EOBJLL| & The search was prematurely terminated, because the
1540objective function being maximized has reached its lower limit and
1541continues decreasing (the dual simplex only).\\
1542\verb|GLP_EOBJUL| & The search was prematurely terminated, because the
1543objective function being minimized has reached its upper limit and
1544continues increasing (the dual simplex only).\\
1545\verb|GLP_EITLIM| & The search was prematurely terminated, because the
1546simplex iteration limit has been exceeded.\\
1547\verb|GLP_ETMLIM| & The search was prematurely terminated, because the
1548time limit has been exceeded.\\
1549\verb|GLP_ENOPFS| & The LP problem instance has no primal feasible
1550solution (only if the LP presolver is used).\\
1551\verb|GLP_ENODFS| & The LP problem instance has no dual feasible
1552solution (only if the LP presolver is used).\\
1553\end{tabular}
1554
1555\subsubsection*{Built-in LP presolver}
1556
1557The simplex solver has {\it built-in LP presolver}. It is a subprogram
1558that transforms the original LP problem specified in the problem object
1559to an equivalent LP problem, which may be easier for solving with the
1560simplex method than the original one. This is attained mainly due to
1561reducing the problem size and improving its numeric properties (for
1562example, by removing some inactive constraints or by fixing some
1563non-basic variables). Once the transformed LP problem has been solved,
1564the presolver transforms its basic solution back to the corresponding
1565basic solution of the original problem.
1566
1567Presolving is an optional feature of the routine \verb|glp_simplex|,
1568and by default it is disabled. In order to enable the LP presolver the
1569control parameter \verb|presolve| should be set to \verb|GLP_ON| (see
1570paragraph ``Control parameters'' below). Presolving may be used when
1571the problem instance is solved for the first time. However, on
1572performing re-optimization the presolver should be disabled.
1573
1574The presolving procedure is transparent to the API user in the sense
1575that all necessary processing is performed internally, and a basic
1576solution of the original problem recovered by the presolver is the same
1577as if it were computed directly, i.e. without presolving.
1578
1579Note that the presolver is able to recover only optimal solutions. If
1580a computed solution is infeasible or non-optimal, the corresponding
1581solution of the original problem cannot be recovered and therefore
1582remains undefined. If you need to know a basic solution even if it is
1583infeasible or non-optimal, the presolver should be disabled.
1584
1585\subsubsection*{Terminal output}
1586
1587Solving large problem instances may take a long time, so the solver
1588reports some information about the current basic solution, which is sent
1589to the terminal. This information has the following format:
1590
1591\begin{verbatim}
1592nnn:  obj = xxx  infeas = yyy (ddd)
1593\end{verbatim}
1594
1595\noindent
1596where: `\verb|nnn|' is the iteration number, `\verb|xxx|' is the
1597current value of the objective function (it is is unscaled and has
1598correct sign); `\verb|yyy|' is the current sum of primal or dual
1599infeasibilities (it is scaled and therefore may be used only for visual
1600estimating), `\verb|ddd|' is the current number of fixed basic
1601variables.
1602
1603The symbol preceding the iteration number indicates which phase of the
1604simplex method is in effect:
1605
1606{\it Blank} means that the solver is searching for primal feasible
1607solution using the primal simplex or for dual feasible solution using
1608the dual simplex;
1609
1610{\it Asterisk} (\verb|*|) means that the solver is searching for
1611optimal solution using the primal simplex;
1612
1613{\it Vertical dash} (\verb/|/) means that the solver is searching for
1614optimal solution using the dual simplex.
1615
1616\subsubsection*{Control parameters}
1617
1618This paragraph describes all control parameters currently used in the
1619simplex solver. Symbolic names of control parameters are names of
1620corresponding members in the structure \verb|glp_smcp|.
1621
1622\medskip
1623
1624\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
1625\multicolumn{2}{@{}l}{{\tt int msg\_lev} (default: {\tt GLP\_MSG\_ALL})}
1626\\
1627&Message level for terminal output:\\
1628&\verb|GLP_MSG_OFF|---no output;\\
1629&\verb|GLP_MSG_ERR|---error and warning messages only;\\
1630&\verb|GLP_MSG_ON |---normal output;\\
1631&\verb|GLP_MSG_ALL|---full output (including informational messages).
1632\\
1633\end{tabular}
1634
1635\medskip
1636
1637\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
1638\multicolumn{2}{@{}l}{{\tt int meth} (default: {\tt GLP\_PRIMAL})}
1639\\
1640&Simplex method option:\\
1641&\verb|GLP_PRIMAL|---use two-phase primal simplex;\\
1642&\verb|GLP_DUAL  |---use two-phase dual simplex;\\
1643&\verb|GLP_DUALP |---use two-phase dual simplex, and if it fails,
1644switch to the\\
1645&\verb|            |$\:$ primal simplex.\\
1646\end{tabular}
1647
1648\medskip
1649
1650\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
1651\multicolumn{2}{@{}l}{{\tt int pricing} (default: {\tt GLP\_PT\_PSE})}
1652\\
1653&Pricing technique:\\
1654&\verb|GLP_PT_STD|---standard (textbook);\\
1655&\verb|GLP_PT_PSE|---projected steepest edge.\\
1656\end{tabular}
1657
1658\medskip
1659
1660\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
1661\multicolumn{2}{@{}l}{{\tt int r\_test} (default: {\tt GLP\_RT\_HAR})}
1662\\
1663&Ratio test technique:\\
1664&\verb|GLP_RT_STD|---standard (textbook);\\
1665&\verb|GLP_RT_HAR|---Harris' two-pass ratio test.\\
1666\end{tabular}
1667
1668\medskip
1669
1670\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
1671\multicolumn{2}{@{}l}{{\tt double tol\_bnd} (default: {\tt 1e-7})}
1672\\
1673&Tolerance used to check if the basic solution is primal feasible.
1674(Do not change this parameter without detailed understanding its
1675purpose.)\\
1676\end{tabular}
1677
1678\medskip
1679
1680\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
1681\multicolumn{2}{@{}l}{{\tt double tol\_dj} (default: {\tt 1e-7})}
1682\\
1683&Tolerance used to check if the basic solution is dual feasible.
1684(Do not change this parameter without detailed understanding its
1685purpose.)\\
1686\end{tabular}
1687
1688\medskip
1689
1690\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
1691\multicolumn{2}{@{}l}{{\tt double tol\_piv} (default: {\tt 1e-10})}
1692\\
1693&Tolerance used to choose eligble pivotal elements of the simplex table.
1694(Do not change this parameter without detailed understanding its
1695purpose.)\\
1696\end{tabular}
1697
1698\medskip
1699
1700\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
1701\multicolumn{2}{@{}l}{{\tt double obj\_ll} (default: {\tt -DBL\_MAX})}
1702\\
1703&Lower limit of the objective function. If the objective function
1704reaches this limit and continues decreasing, the solver terminates the
1705search. (Used in the dual simplex only.)\\
1706\end{tabular}
1707
1708\medskip
1709
1710\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
1711\multicolumn{2}{@{}l}{{\tt double obj\_ul} (default: {\tt +DBL\_MAX})}
1712\\
1713&Upper limit of the objective function. If the objective function
1714reaches this limit and continues increasing, the solver terminates the
1715search. (Used in the dual simplex only.)\\
1716\end{tabular}
1717
1718\medskip
1719
1720\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
1721\multicolumn{2}{@{}l}{{\tt int it\_lim} (default: {\tt INT\_MAX})}
1722\\
1723&Simplex iteration limit.\\
1724\end{tabular}
1725
1726\medskip
1727
1728\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
1729\multicolumn{2}{@{}l}{{\tt int tm\_lim} (default: {\tt INT\_MAX})}
1730\\
1731&Searching time limit, in milliseconds.\\
1732\end{tabular}
1733
1734\medskip
1735
1736\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
1737\multicolumn{2}{@{}l}{{\tt int out\_frq} (default: {\tt 500})}
1738\\
1739&Output frequency, in iterations. This parameter specifies how
1740frequently the solver sends information about the solution process to
1741the terminal.\\
1742\end{tabular}
1743
1744\medskip
1745
1746\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
1747\multicolumn{2}{@{}l}{{\tt int out\_dly} (default: {\tt 0})}
1748\\
1749&Output delay, in milliseconds. This parameter specifies how long the
1750solver should delay sending information about the solution process to
1751the terminal.\\
1752\end{tabular}
1753
1754\medskip
1755
1756\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
1757\multicolumn{2}{@{}l}{{\tt int presolve} (default: {\tt GLP\_OFF})}
1758\\
1759&LP presolver option:\\
1760&\verb|GLP_ON |---enable using the LP presolver;\\
1761&\verb|GLP_OFF|---disable using the LP presolver.\\
1762\end{tabular}
1763
1764\subsubsection*{Example 1}
1765
1766The following main program reads LP problem instance in fixed MPS
1767format from file \verb|25fv47.mps|,\footnote{This instance in fixed MPS
1768format can be found in the Netlib LP collection; see
1769{\tt ftp://ftp.netlib.org/lp/data/}.} constructs an advanced initial
1770basis, solves the instance with the primal simplex method (by default),
1771and writes the solution to file \verb|25fv47.txt|.
1772
1773\newpage
1774
1775\begin{footnotesize}
1776\begin{verbatim}
1777/* spxsamp1.c */
1778
1779#include <stdio.h>
1780#include <stdlib.h>
1781#include <glpk.h>
1782
1783int main(void)
1784{     glp_prob *P;
1785      P = glp_create_prob();
1786      glp_read_mps(P, GLP_MPS_DECK, NULL, "25fv47.mps");
1787      glp_adv_basis(P, 0);
1788      glp_simplex(P, NULL);
1789      glp_print_sol(P, "25fv47.txt");
1790      glp_delete_prob(P);
1791      return 0;
1792}
1793
1794/* eof */
1795\end{verbatim}
1796\end{footnotesize}
1797
1798\noindent
1799Below here is shown the terminal output from this example program.
1800
1801\begin{footnotesize}
1802\begin{verbatim}
1803Reading problem data from `25fv47.mps'...
1804Problem: 25FV47
1805Objective: R0000
1806822 rows, 1571 columns, 11127 non-zeros
18076919 records were read
1808Crashing...
1809Size of triangular part = 799
1810      0: obj =   1.627307307e+04  infeas =  5.194e+04 (23)
1811    200: obj =   1.474901610e+04  infeas =  1.233e+04 (19)
1812    400: obj =   1.343909995e+04  infeas =  3.648e+03 (13)
1813    600: obj =   1.756052217e+04  infeas =  4.179e+02 (7)
1814*   775: obj =   1.789251591e+04  infeas =  4.982e-14 (1)
1815*   800: obj =   1.663354510e+04  infeas =  2.857e-14 (1)
1816*  1000: obj =   1.024935068e+04  infeas =  1.958e-12 (1)
1817*  1200: obj =   7.860174791e+03  infeas =  2.810e-29 (1)
1818*  1400: obj =   6.642378184e+03  infeas =  2.036e-16 (1)
1819*  1600: obj =   6.037014568e+03  infeas =  0.000e+00 (1)
1820*  1800: obj =   5.662171307e+03  infeas =  6.447e-15 (1)
1821*  2000: obj =   5.528146165e+03  infeas =  9.764e-13 (1)
1822*  2125: obj =   5.501845888e+03  infeas =  0.000e+00 (1)
1823OPTIMAL SOLUTION FOUND
1824Writing basic solution to `25fv47.txt'...
1825\end{verbatim}
1826\end{footnotesize}
1827
1828\newpage
1829
1830\subsubsection*{Example 2}
1831
1832The following main program solves the same LP problem instance as in
1833Example 1 above, however, it uses the dual simplex method, which starts
1834from the standard initial basis.
1835
1836\begin{footnotesize}
1837\begin{verbatim}
1838/* spxsamp2.c */
1839
1840#include <stdio.h>
1841#include <stdlib.h>
1842#include <glpk.h>
1843
1844int main(void)
1845{     glp_prob *P;
1846      glp_smcp parm;
1847      P = glp_create_prob();
1848      glp_read_mps(P, GLP_MPS_DECK, NULL, "25fv47.mps");
1849      glp_init_smcp(&parm);
1850      parm.meth = GLP_DUAL;
1851      glp_simplex(P, &parm);
1852      glp_print_sol(P, "25fv47.txt");
1853      glp_delete_prob(P);
1854      return 0;
1855}
1856
1857/* eof */
1858\end{verbatim}
1859\end{footnotesize}
1860
1861\noindent
1862Below here is shown the terminal output from this example program.
1863
1864\begin{footnotesize}
1865\begin{verbatim}
1866Reading problem data from `25fv47.mps'...
1867Problem: 25FV47
1868Objective: R0000
1869822 rows, 1571 columns, 11127 non-zeros
18706919 records were read
1871      0:                          infeas =  1.223e+03 (516)
1872    200:                          infeas =  7.000e+00 (471)
1873    240:                          infeas =  1.106e-14 (461)
1874|   400: obj =  -5.394267152e+03  infeas =  5.571e-16 (391)
1875|   600: obj =  -4.586395752e+03  infeas =  1.389e-15 (340)
1876|   800: obj =  -4.158268146e+03  infeas =  1.640e-15 (264)
1877|  1000: obj =  -3.725320045e+03  infeas =  5.181e-15 (245)
1878|  1200: obj =  -3.104802163e+03  infeas =  1.019e-14 (210)
1879|  1400: obj =  -2.584190499e+03  infeas =  8.865e-15 (178)
1880|  1600: obj =  -2.073852927e+03  infeas =  7.867e-15 (142)
1881|  1800: obj =  -1.164037407e+03  infeas =  8.792e-15 (109)
1882|  2000: obj =  -4.370590250e+02  infeas =  2.591e-14 (85)
1883|  2200: obj =   1.068240144e+03  infeas =  1.025e-13 (70)
1884|  2400: obj =   1.607481126e+03  infeas =  3.272e-14 (67)
1885|  2600: obj =   3.038230551e+03  infeas =  4.850e-14 (52)
1886|  2800: obj =   4.316238187e+03  infeas =  2.622e-14 (36)
1887|  3000: obj =   5.443842629e+03  infeas =  3.976e-15 (11)
1888|  3060: obj =   5.501845888e+03  infeas =  8.806e-15 (2)
1889OPTIMAL SOLUTION FOUND
1890Writing basic solution to `25fv47.txt'...
1891\end{verbatim}
1892\end{footnotesize}
1893
1894\subsection{glp\_exact---solve LP problem in exact arithmetic}
1895
1896\subsubsection*{Synopsis}
1897
1898\begin{verbatim}
1899int glp_exact(glp_prob *lp, const glp_smcp *parm);
1900\end{verbatim}
1901
1902\subsubsection*{Description}
1903
1904The routine \verb|glp_exact| is a tentative implementation of the
1905primal two-phase simplex method based on exact (rational) arithmetic.
1906It is similar to the routine \verb|glp_simplex|, however, for all
1907internal computations it uses arithmetic of rational numbers, which is
1908exact in mathematical sense, i.e. free of round-off errors unlike
1909floating-point arithmetic.
1910
1911Note that the routine \verb|glp_exact| uses only two control parameters
1912passed in the structure \verb|glp_smcp|, namely, \verb|it_lim| and
1913\verb|tm_lim|.
1914
1915\subsubsection*{Returns}
1916
1917\def\arraystretch{1}
1918
1919\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
19200 & The LP problem instance has been successfully solved. (This code
1921does {\it not} necessarily mean that the solver has found optimal
1922solution. It only means that the solution process was successful.) \\
1923\verb|GLP_EBADB| & Unable to start the search, because the initial basis
1924specified in the problem object is invalid---the number of basic
1925(auxiliary and structural) variables is not the same as the number of
1926rows in the problem object.\\
1927\verb|GLP_ESING| & Unable to start the search, because the basis matrix
1928corresponding to the initial basis is exactly singular.\\
1929\verb|GLP_EBOUND| & Unable to start the search, because some
1930double-bounded (auxiliary or structural) variables have incorrect
1931bounds.\\
1932\verb|GLP_EFAIL| & The problem instance has no rows/columns.\\
1933\verb|GLP_EITLIM| & The search was prematurely terminated, because the
1934simplex iteration limit has been exceeded.\\
1935\verb|GLP_ETMLIM| & The search was prematurely terminated, because the
1936time limit has been exceeded.\\
1937\end{tabular}
1938
1939\subsubsection*{Comments}
1940
1941Computations in exact arithmetic are very time consuming, so solving
1942LP problem with the routine \verb|glp_exact| from the very beginning is
1943not a good idea. It is much better at first to find an optimal basis
1944with the routine \verb|glp_simplex| and only then to call
1945\verb|glp_exact|, in which case only a few simplex iterations need to
1946be performed in exact arithmetic.
1947
1948\subsection{glp\_init\_smcp---initialize simplex solver control
1949parameters}
1950
1951\subsubsection*{Synopsis}
1952
1953\begin{verbatim}
1954int glp_init_smcp(glp_smcp *parm);
1955\end{verbatim}
1956
1957\subsubsection*{Description}
1958
1959The routine \verb|glp_init_smcp| initializes control parameters, which
1960are used by the simplex solver, with default values.
1961
1962Default values of the control parameters are stored in a \verb|glp_smcp|
1963structure, which the parameter \verb|parm| points to.
1964
1965\subsection{glp\_get\_status---determine generic status of basic
1966solution}
1967
1968\subsubsection*{Synopsis}
1969
1970\begin{verbatim}
1971int glp_get_status(glp_prob *lp);
1972\end{verbatim}
1973
1974\subsubsection*{Returns}
1975
1976The routine \verb|glp_get_status| reports the generic status of the
1977current basic solution for the specified problem object as follows:
1978
1979\begin{tabular}{@{}ll}
1980\verb|GLP_OPT|    & solution is optimal; \\
1981\verb|GLP_FEAS|   & solution is feasible; \\
1982\verb|GLP_INFEAS| & solution is infeasible; \\
1983\verb|GLP_NOFEAS| & problem has no feasible solution; \\
1984\verb|GLP_UNBND|  & problem has unbounded solution; \\
1985\verb|GLP_UNDEF|  & solution is undefined. \\
1986\end{tabular}
1987
1988More detailed information about the status of basic solution can be
1989retrieved with the routines \verb|glp_get_prim_stat| and
1990\verb|glp_get_dual_stat|.
1991
1992\newpage
1993
1994\subsection{glp\_get\_prim\_stat---retrieve status of primal basic
1995solution}
1996
1997\subsubsection*{Synopsis}
1998
1999\begin{verbatim}
2000int glp_get_prim_stat(glp_prob *lp);
2001\end{verbatim}
2002
2003\subsubsection*{Returns}
2004
2005The routine \verb|glp_get_prim_stat| reports the status of the primal
2006basic solution for the specified problem object as follows:
2007
2008\begin{tabular}{@{}ll}
2009\verb|GLP_UNDEF|  & primal solution is undefined; \\
2010\verb|GLP_FEAS|   & primal solution is feasible; \\
2011\verb|GLP_INFEAS| & primal solution is infeasible; \\
2012\verb|GLP_NOFEAS| & no primal feasible solution exists. \\
2013\end{tabular}
2014
2015\subsection{glp\_get\_dual\_stat---retrieve status of dual basic
2016solution}
2017
2018\subsubsection*{Synopsis}
2019
2020\begin{verbatim}
2021int glp_get_dual_stat(glp_prob *lp);
2022\end{verbatim}
2023
2024\subsubsection*{Returns}
2025
2026The routine \verb|glp_get_dual_stat| reports the status of the dual
2027basic solution for the specified problem object as follows:
2028
2029\begin{tabular}{@{}ll}
2030\verb|GLP_UNDEF|  & dual solution is undefined; \\
2031\verb|GLP_FEAS|   & dual solution is feasible; \\
2032\verb|GLP_INFEAS| & dual solution is infeasible; \\
2033\verb|GLP_NOFEAS| & no dual feasible solution exists. \\
2034\end{tabular}
2035
2036\subsection{glp\_get\_obj\_val---retrieve objective value}
2037
2038\subsubsection*{Synopsis}
2039
2040\begin{verbatim}
2041double glp_get_obj_val(glp_prob *lp);
2042\end{verbatim}
2043
2044\subsubsection*{Returns}
2045
2046The routine \verb|glp_get_obj_val| returns current value of the
2047objective function.
2048
2049\subsection{glp\_get\_row\_stat---retrieve row status}
2050
2051\subsubsection*{Synopsis}
2052
2053\begin{verbatim}
2054int glp_get_row_stat(glp_prob *lp, int i);
2055\end{verbatim}
2056
2057\subsubsection*{Returns}
2058
2059The routine \verb|glp_get_row_stat| returns current status assigned to
2060the auxiliary variable associated with \verb|i|-th row as follows:
2061
2062\begin{tabular}{@{}ll}
2063\verb|GLP_BS| & basic variable; \\
2064\verb|GLP_NL| & non-basic variable on its lower bound; \\
2065\verb|GLP_NU| & non-basic variable on its upper bound; \\
2066\verb|GLP_NF| & non-basic free (unbounded) variable; \\
2067\verb|GLP_NS| & non-basic fixed variable. \\
2068\end{tabular}
2069
2070\subsection{glp\_get\_row\_prim---retrieve row primal value}
2071
2072\subsubsection*{Synopsis}
2073
2074\begin{verbatim}
2075double glp_get_row_prim(glp_prob *lp, int i);
2076\end{verbatim}
2077
2078\subsubsection*{Returns}
2079
2080The routine \verb|glp_get_row_prim| returns primal value of the
2081auxiliary variable associated with \verb|i|-th row.
2082
2083\subsection{glp\_get\_row\_dual---retrieve row dual value}
2084
2085\subsubsection*{Synopsis}
2086
2087\begin{verbatim}
2088double glp_get_row_dual(glp_prob *lp, int i);
2089\end{verbatim}
2090
2091\subsubsection*{Returns}
2092
2093The routine \verb|glp_get_row_dual| returns dual value (i.e. reduced
2094cost) of the auxiliary variable associated with \verb|i|-th row.
2095
2096\newpage
2097
2098\subsection{glp\_get\_col\_stat---retrieve column status}
2099
2100\subsubsection*{Synopsis}
2101
2102\begin{verbatim}
2103int glp_get_col_stat(glp_prob *lp, int j);
2104\end{verbatim}
2105
2106\subsubsection*{Returns}
2107
2108The routine \verb|glp_get_col_stat| returns current status assigned to
2109the structural variable associated with \verb|j|-th column as follows:
2110
2111\begin{tabular}{@{}ll}
2112\verb|GLP_BS| & basic variable; \\
2113\verb|GLP_NL| & non-basic variable on its lower bound; \\
2114\verb|GLP_NU| & non-basic variable on its upper bound; \\
2115\verb|GLP_NF| & non-basic free (unbounded) variable; \\
2116\verb|GLP_NS| & non-basic fixed variable. \\
2117\end{tabular}
2118
2119\subsection{glp\_get\_col\_prim---retrieve column primal value}
2120
2121\subsubsection*{Synopsis}
2122
2123\begin{verbatim}
2124double glp_get_col_prim(glp_prob *lp, int j);
2125\end{verbatim}
2126
2127\subsubsection*{Returns}
2128
2129The routine \verb|glp_get_col_prim| returns primal value of the
2130structural variable associated with \verb|j|-th column.
2131
2132\subsection{glp\_get\_col\_dual---retrieve column dual value}
2133
2134\subsubsection*{Synopsis}
2135
2136\begin{verbatim}
2137double glp_get_col_dual(glp_prob *lp, int j);
2138\end{verbatim}
2139
2140\subsubsection*{Returns}
2141
2142The routine \verb|glp_get_col_dual| returns dual value (i.e. reduced
2143cost) of the structural variable associated with \verb|j|-th column.
2144
2145\newpage
2146
2147\subsection{glp\_get\_unbnd\_ray---determine variable causing\\
2148unboundedness}
2149
2150\subsubsection*{Synopsis}
2151
2152\begin{verbatim}
2153int glp_get_unbnd_ray(glp_prob *lp);
2154\end{verbatim}
2155
2156\subsubsection*{Returns}
2157
2158The routine \verb|glp_get_unbnd_ray| returns the number $k$ of
2159a variable, which causes primal or dual unboundedness.
2160If $1\leq k\leq m$, it is $k$-th auxiliary variable, and if
2161$m+1\leq k\leq m+n$, it is $(k-m)$-th structural variable, where $m$ is
2162the number of rows, $n$ is the number of columns in the problem object.
2163If such variable is not defined, the routine returns 0.
2164
2165\subsubsection*{Comments}
2166
2167If it is not exactly known which version of the simplex solver
2168detected unboundedness, i.e. whether the unboundedness is primal or
2169dual, it is sufficient to check the status of the variable
2170with the routine \verb|glp_get_row_stat| or \verb|glp_get_col_stat|.
2171If the variable is non-basic, the unboundedness is primal, otherwise,
2172if the variable is basic, the unboundedness is dual (the latter case
2173means that the problem has no primal feasible dolution).
2174
2175%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2176
2177\newpage
2178
2179\section{Interior-point method routines}
2180
2181{\it Interior-point methods} (also known as {\it barrier methods}) are
2182more modern and powerful numerical methods for large-scale linear
2183programming. Such methods are especially efficient for very sparse LP
2184problems and allow solving such problems much faster than the simplex
2185method.
2186
2187In brief, the GLPK interior-point solver works as follows.
2188
2189At first, the solver transforms the original LP to a {\it working} LP
2190in the standard format:
2191
2192\medskip
2193
2194\noindent
2195\hspace{.5in} minimize
2196$$z = c_1x_{m+1} + c_2x_{m+2} + \dots + c_nx_{m+n} + c_0 \eqno (2.4)$$
2197\hspace{.5in} subject to linear constraints
2198$$
2199\begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}l}
2200a_{11}x_{m+1}&+&a_{12}x_{m+2}&+ \dots +&a_{1n}x_{m+n}&=&b_1 \\
2201a_{21}x_{m+1}&+&a_{22}x_{m+2}&+ \dots +&a_{2n}x_{m+n}&=&b_2 \\
2202\multicolumn{7}{c}
2203{.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .} \\
2204a_{m1}x_{m+1}&+&a_{m2}x_{m+2}&+ \dots +&a_{mn}x_{m+n}&=&b_m \\
2205\end{array} \eqno (2.5)
2206$$
2207\hspace{.5in} and non-negative variables
2208$$x_1\geq 0,\ \ x_2\geq 0,\ \ \dots,\ \ x_n\geq 0 \eqno(2.6)$$
2209where: $z$ is the objective function; $x_1$, \dots, $x_n$ are variables;
2210$c_1$, \dots, $c_n$ are objective coefficients; $c_0$ is a constant term
2211of the objective function;\linebreak $a_{11}$, \dots, $a_{mn}$ are
2212constraint coefficients; $b_1$, \dots, $b_m$ are right-hand sides.
2213
2214Using vector and matrix notations the working LP (2.4)---(2.6) can be
2215written as follows:
2216$$z=c^Tx+c_0\ \rightarrow\ \min,\eqno(2.7)$$
2217$$Ax=b,\eqno(2.8)$$
2218$$x\geq 0,\eqno(2.9)$$
2219where: $x=(x_j)$ is $n$-vector of variables, $c=(c_j)$ is $n$-vector of
2220objective coefficients, $A=(a_{ij})$ is $m\times n$-matrix of
2221constraint coefficients, and $b=(b_i)$ is $m$-vector of right-hand
2222sides.
2223
2224Karush--Kuhn--Tucker optimality conditions for LP (2.7)---(2.9) are the
2225following:
2226
2227\newpage
2228
2229$$Ax=b,\eqno(2.10)$$
2230$$A^T\pi+\lambda=c,\eqno(2.11)$$
2231$$\lambda^Tx=0,\eqno(2.12)$$
2232$$x\geq 0,\ \ \lambda\geq 0,\eqno(2.13)$$
2233where: $\pi$ is $m$-vector of Lagrange multipliers (dual variables) for
2234equality constraints (2.8), $\lambda$ is $n$-vector of Lagrange
2235multipliers (dual variables) for non-negativity constraints (2.9),
2236(2.10) is the primal feasibility condition, (2.11) is the dual
2237feasibility condition, (2.12) is the primal-dual complementarity
2238condition, and (2.13) is the non-negativity conditions.
2239
2240The main idea of the primal-dual interior-point method is based on
2241finding a point in the primal-dual space (i.e. in the space of all
2242primal and dual variables $x$, $\pi$, and $\lambda$), which satisfies
2243to all optimality conditions (2.10)---(2.13). Obviously, $x$-component
2244of such point then provides an optimal solution to the working LP
2245(2.7)---(2.9).
2246
2247To find the optimal point $(x^*,\pi^*,\lambda^*)$ the interior-point
2248method attempts to solve the system of equations (2.10)---(2.12), which
2249is closed in the sense that the number of variables $x_j$, $\pi_i$, and
2250$\lambda_j$ and the number equations are the same and equal to $m+2n$.
2251Due to condition (2.12) this system of equations is non-linear, so it
2252can be solved with a version of {\it Newton's method} provided with
2253additional rules to keep the current point within the positive orthant
2254as required by the non-negativity conditions (2.13).
2255
2256Finally, once the optimal point $(x^*,\pi^*,\lambda^*)$ has been found,
2257the solver performs inverse transformations to recover corresponding
2258solution to the original LP passed to the solver from the application
2259program.
2260
2261\subsection{glp\_interior---solve LP problem with the interior-point
2262method}
2263
2264\subsubsection*{Synopsis}
2265
2266\begin{verbatim}
2267int glp_interior(glp_prob *P, const glp_iptcp *parm);
2268\end{verbatim}
2269
2270\subsubsection*{Description}
2271
2272The routine \verb|glp_interior| is a driver to the LP solver based on
2273the primal-dual interior-point method. This routine retrieves problem
2274data from the specified problem object, calls the solver to solve the
2275problem instance, and stores results of computations back into the
2276problem object.
2277
2278The interior-point solver has a set of control parameters. Values of
2279the control parameters can be passed in the structure \verb|glp_iptcp|,
2280which the parameter \verb|parm| points to. For detailed description of
2281this structure see paragraph ``Control parameters'' below. Before
2282specifying some control parameters the application program should
2283initialize the structure \verb|glp_iptcp| by default values of all
2284control parameters using the routine \verb|glp_init_iptcp| (see the
2285next subsection). This is needed for backward compatibility, because in
2286the future there may appear new members in the structure
2287\verb|glp_iptcp|.
2288
2289The parameter \verb|parm| can be specified as \verb|NULL|, in which
2290case the solver uses default settings.
2291
2292\subsubsection*{Returns}
2293
2294\def\arraystretch{1}
2295
2296\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
22970 & The LP problem instance has been successfully solved. (This code
2298does {\it not} necessarily mean that the solver has found optimal
2299solution. It only means that the solution process was successful.) \\
2300\verb|GLP_EFAIL| & The problem has no rows/columns.\\
2301\verb|GLP_ENOCVG| & Very slow convergence or divergence.\\
2302\verb|GLP_EITLIM| & Iteration limit exceeded.\\
2303\verb|GLP_EINSTAB| & Numerical instability on solving Newtonian
2304system.\\
2305\end{tabular}
2306
2307\subsubsection*{Comments}
2308
2309The routine \verb|glp_interior| implements an easy version of
2310the primal-dual interior-point method based on Mehrotra's
2311technique.\footnote{S. Mehrotra. On the implementation of a primal-dual
2312interior point method. SIAM J. on Optim., 2(4), pp. 575-601, 1992.}
2313
2314Note that currently the GLPK interior-point solver does not include
2315many important features, in particular:
2316
2317$\bullet$ it is not able to process dense columns. Thus, if the
2318constraint matrix of the LP problem has dense columns, the solving
2319process may be inefficient;
2320
2321$\bullet$ it has no features against numerical instability. For some
2322LP problems premature termination may happen if the matrix $ADA^T$
2323becomes singular or ill-conditioned;
2324
2325$\bullet$ it is not able to identify the optimal basis, which
2326corresponds to the interior-point solution found.
2327
2328\newpage
2329
2330\subsubsection*{Terminal output}
2331
2332Solving large LP problems may take a long time, so the solver reports
2333some information about every interior-point iteration,\footnote{Unlike
2334the simplex method the interior point method usually needs 30---50
2335iterations (independently on the problem size) in order to find an
2336optimal solution.} which is sent to the terminal. This information has
2337the following format:
2338
2339\begin{verbatim}
2340nnn: obj = fff; rpi = ppp; rdi = ddd; gap = ggg
2341\end{verbatim}
2342
2343\noindent where: \verb|nnn| is iteration number, \verb|fff| is the
2344current value of the objective function (in the case of maximization it
2345has wrong sign), \verb|ppp| is the current relative primal
2346infeasibility (cf. (2.10)):
2347$$\frac{\|Ax^{(k)}-b\|}{1+\|b\|},\eqno(2.14)$$
2348\verb|ddd| is the current relative dual infeasibility (cf. (2.11)):
2349$$\frac{\|A^T\pi^{(k)}+\lambda^{(k)}-c\|}{1+\|c\|},\eqno(2.15)$$
2350\verb|ggg| is the current primal-dual gap (cf. (2.12)):
2351$$\frac{|c^Tx^{(k)}-b^T\pi^{(k)}|}{1+|c^Tx^{(k)}|},\eqno(2.16)$$
2352and $[x^{(k)},\pi^{(k)},\lambda^{(k)}]$ is the current point on $k$-th
2353iteration, $k=0,1,2,\dots$\ . Note that all solution components are
2354internally scaled, so information sent to the terminal is suitable only
2355for visual inspection.
2356
2357\subsubsection*{Control parameters}
2358
2359This paragraph describes all control parameters currently used in the
2360interior-point solver. Symbolic names of control parameters are names of
2361corresponding members in the structure \verb|glp_iptcp|.
2362
2363\medskip
2364
2365\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2366\multicolumn{2}{@{}l}{{\tt int msg\_lev} (default: {\tt GLP\_MSG\_ALL})}
2367\\
2368&Message level for terminal output:\\
2369&\verb|GLP_MSG_OFF|---no output;\\
2370&\verb|GLP_MSG_ERR|---error and warning messages only;\\
2371&\verb|GLP_MSG_ON |---normal output;\\
2372&\verb|GLP_MSG_ALL|---full output (including informational messages).
2373\\
2374\end{tabular}
2375
2376\medskip
2377
2378\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2379\multicolumn{2}{@{}l}{{\tt int ord\_alg} (default: {\tt GLP\_ORD\_AMD})}
2380\\
2381&Ordering algorithm used prior to Cholesky factorization:\\
2382&\verb|GLP_ORD_NONE  |---use natural (original) ordering;\\
2383&\verb|GLP_ORD_QMD   |---quotient minimum degree (QMD);\\
2384&\verb|GLP_ORD_AMD   |---approximate minimum degree (AMD);\\
2385&\verb|GLP_ORD_SYMAMD|---approximate minimum degree (SYMAMD).\\
2386\end{tabular}
2387
2388\subsubsection*{Example}
2389
2390The following main program reads LP problem instance in fixed MPS
2391format from file \verb|25fv47.mps|,\footnote{This instance in fixed MPS
2392format can be found in the Netlib LP collection; see
2393{\tt ftp://ftp.netlib.org/lp/data/}.} solves it with the interior-point
2394solver, and writes the solution to file \verb|25fv47.txt|.
2395
2396\begin{footnotesize}
2397\begin{verbatim}
2398/* iptsamp.c */
2399
2400#include <stdio.h>
2401#include <stdlib.h>
2402#include <glpk.h>
2403
2404int main(void)
2405{     glp_prob *P;
2406      P = glp_create_prob();
2407      glp_read_mps(P, GLP_MPS_DECK, NULL, "25fv47.mps");
2408      glp_interior(P, NULL);
2409      glp_print_ipt(P, "25fv47.txt");
2410      glp_delete_prob(P);
2411      return 0;
2412}
2413
2414/* eof */
2415\end{verbatim}
2416\end{footnotesize}
2417
2418\noindent
2419Below here is shown the terminal output from this example program.
2420
2421\begin{footnotesize}
2422\begin{verbatim}
2423Reading problem data from `25fv47.mps'...
2424Problem: 25FV47
2425Objective: R0000
2426822 rows, 1571 columns, 11127 non-zeros
24276919 records were read
2428Original LP has 822 row(s), 1571 column(s), and 11127 non-zero(s)
2429Working LP has 821 row(s), 1876 column(s), and 10705 non-zero(s)
2430Matrix A has 10705 non-zeros
2431Matrix S = A*A' has 11895 non-zeros (upper triangle)
2432Minimal degree ordering...
2433Computing Cholesky factorization S = L'*L...
2434Matrix L has 35411 non-zeros
2435Guessing initial point...
2436Optimization begins...
2437  0: obj =   1.823377629e+05; rpi =  1.3e+01; rdi =  1.4e+01; gap =  9.3e-01
2438  1: obj =   9.260045192e+04; rpi =  5.3e+00; rdi =  5.6e+00; gap =  6.8e+00
2439  2: obj =   3.596999742e+04; rpi =  1.5e+00; rdi =  1.2e+00; gap =  1.8e+01
2440  3: obj =   1.989627568e+04; rpi =  4.7e-01; rdi =  3.0e-01; gap =  1.9e+01
2441  4: obj =   1.430215557e+04; rpi =  1.1e-01; rdi =  8.6e-02; gap =  1.4e+01
2442  5: obj =   1.155716505e+04; rpi =  2.3e-02; rdi =  2.4e-02; gap =  6.8e+00
2443  6: obj =   9.660273208e+03; rpi =  6.7e-03; rdi =  4.6e-03; gap =  3.9e+00
2444  7: obj =   8.694348283e+03; rpi =  3.7e-03; rdi =  1.7e-03; gap =  2.0e+00
2445  8: obj =   8.019543639e+03; rpi =  2.4e-03; rdi =  3.9e-04; gap =  1.0e+00
2446  9: obj =   7.122676293e+03; rpi =  1.2e-03; rdi =  1.5e-04; gap =  6.6e-01
2447 10: obj =   6.514534518e+03; rpi =  6.1e-04; rdi =  4.3e-05; gap =  4.1e-01
2448 11: obj =   6.361572203e+03; rpi =  4.8e-04; rdi =  2.2e-05; gap =  3.0e-01
2449 12: obj =   6.203355508e+03; rpi =  3.2e-04; rdi =  1.7e-05; gap =  2.6e-01
2450 13: obj =   6.032943411e+03; rpi =  2.0e-04; rdi =  9.3e-06; gap =  2.1e-01
2451 14: obj =   5.796553021e+03; rpi =  9.8e-05; rdi =  3.2e-06; gap =  1.0e-01
2452 15: obj =   5.667032431e+03; rpi =  4.4e-05; rdi =  1.1e-06; gap =  5.6e-02
2453 16: obj =   5.613911867e+03; rpi =  2.5e-05; rdi =  4.1e-07; gap =  3.5e-02
2454 17: obj =   5.560572626e+03; rpi =  9.9e-06; rdi =  2.3e-07; gap =  2.1e-02
2455 18: obj =   5.537276001e+03; rpi =  5.5e-06; rdi =  8.4e-08; gap =  1.1e-02
2456 19: obj =   5.522746942e+03; rpi =  2.2e-06; rdi =  4.0e-08; gap =  6.7e-03
2457 20: obj =   5.509956679e+03; rpi =  7.5e-07; rdi =  1.8e-08; gap =  2.9e-03
2458 21: obj =   5.504571733e+03; rpi =  1.6e-07; rdi =  5.8e-09; gap =  1.1e-03
2459 22: obj =   5.502576367e+03; rpi =  3.4e-08; rdi =  1.0e-09; gap =  2.5e-04
2460 23: obj =   5.502057119e+03; rpi =  8.1e-09; rdi =  3.0e-10; gap =  7.7e-05
2461 24: obj =   5.501885996e+03; rpi =  9.4e-10; rdi =  1.2e-10; gap =  2.4e-05
2462 25: obj =   5.501852464e+03; rpi =  1.4e-10; rdi =  1.2e-11; gap =  3.0e-06
2463 26: obj =   5.501846549e+03; rpi =  1.4e-11; rdi =  1.2e-12; gap =  3.0e-07
2464 27: obj =   5.501845954e+03; rpi =  1.4e-12; rdi =  1.2e-13; gap =  3.0e-08
2465 28: obj =   5.501845895e+03; rpi =  1.5e-13; rdi =  1.2e-14; gap =  3.0e-09
2466OPTIMAL SOLUTION FOUND
2467Writing interior-point solution to `25fv47.txt'...
2468\end{verbatim}
2469\end{footnotesize}
2470
2471\subsection{glp\_init\_iptcp---initialize interior-point solver control
2472parameters}
2473
2474\subsubsection*{Synopsis}
2475
2476\begin{verbatim}
2477int glp_init_iptcp(glp_iptcp *parm);
2478\end{verbatim}
2479
2480\subsubsection*{Description}
2481
2482The routine \verb|glp_init_iptcp| initializes control parameters, which
2483are used by the interior-point solver, with default values.
2484
2485Default values of the control parameters are stored in the structure
2486\verb|glp_iptcp|, which the parameter \verb|parm| points to.
2487
2488\subsection{glp\_ipt\_status---determine solution status}
2489
2490\subsubsection*{Synopsis}
2491
2492\begin{verbatim}
2493int glp_ipt_status(glp_prob *lp);
2494\end{verbatim}
2495
2496\subsubsection*{Returns}
2497
2498The routine \verb|glp_ipt_status| reports the status of a solution
2499found by the interior-point solver as follows:
2500
2501\begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
2502\verb|GLP_UNDEF| & interior-point solution is undefined. \\
2503\verb|GLP_OPT|   & interior-point solution is optimal. \\
2504\verb|GLP_INFEAS|& interior-point solution is infeasible. \\
2505\verb|GLP_NOFEAS|& no feasible primal-dual solution exists.\\
2506\end{tabular}
2507
2508\subsection{glp\_ipt\_obj\_val---retrieve objective value}
2509
2510\subsubsection*{Synopsis}
2511
2512\begin{verbatim}
2513double glp_ipt_obj_val(glp_prob *lp);
2514\end{verbatim}
2515
2516\subsubsection*{Returns}
2517
2518The routine \verb|glp_ipt_obj_val| returns value of the objective
2519function for interior-point solution.
2520
2521\subsection{glp\_ipt\_row\_prim---retrieve row primal value}
2522
2523\subsubsection*{Synopsis}
2524
2525\begin{verbatim}
2526double glp_ipt_row_prim(glp_prob *lp, int i);
2527\end{verbatim}
2528
2529\subsubsection*{Returns}
2530
2531The routine \verb|glp_ipt_row_prim| returns primal value of the
2532auxiliary variable associated with \verb|i|-th row.
2533
2534\newpage
2535
2536\subsection{glp\_ipt\_row\_dual---retrieve row dual value}
2537
2538\subsubsection*{Synopsis}
2539
2540\begin{verbatim}
2541double glp_ipt_row_dual(glp_prob *lp, int i);
2542\end{verbatim}
2543
2544\subsubsection*{Returns}
2545
2546The routine \verb|glp_ipt_row_dual| returns dual value (i.e. reduced
2547cost) of the auxiliary variable associated with \verb|i|-th row.
2548
2549\subsection{glp\_ipt\_col\_prim---retrieve column primal value}
2550
2551\subsubsection*{Synopsis}
2552
2553\begin{verbatim}
2554double glp_ipt_col_prim(glp_prob *lp, int j);
2555\end{verbatim}
2556
2557\subsubsection*{Returns}
2558
2559The routine \verb|glp_ipt_col_prim| returns primal value of the
2560structural variable associated with \verb|j|-th column.
2561
2562\subsection{glp\_ipt\_col\_dual---retrieve column dual value}
2563
2564\subsubsection*{Synopsis}
2565
2566\begin{verbatim}
2567double glp_ipt_col_dual(glp_prob *lp, int j);
2568\end{verbatim}
2569
2570\subsubsection*{Returns}
2571
2572The routine \verb|glp_ipt_col_dual| returns dual value (i.e. reduced
2573cost) of the structural variable associated with \verb|j|-th column.
2574
2575%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2576
2577\newpage
2578
2579\section{Mixed integer programming routines}
2580
2581\subsection{glp\_set\_col\_kind---set (change) column kind}
2582
2583\subsubsection*{Synopsis}
2584
2585\begin{verbatim}
2586void glp_set_col_kind(glp_prob *mip, int j, int kind);
2587\end{verbatim}
2588
2589\subsubsection*{Description}
2590
2591The routine \verb|glp_set_col_kind| sets (changes) the kind of
2592\verb|j|-th column (structural variable) as specified by the parameter
2593\verb|kind|:
2594
2595\begin{tabular}{@{}ll}
2596\verb|GLP_CV| & continuous variable; \\
2597\verb|GLP_IV| & integer variable; \\
2598\verb|GLP_BV| & binary variable. \\
2599\end{tabular}
2600
2601%If a column is set to \verb|GLP_IV|, its bounds must be exact integer
2602%numbers with no tolerance, such that the condition
2603%\verb|bnd == floor(bnd)| would hold.
2604
2605Setting a column to \verb|GLP_BV| has the same effect as if it were
2606set to \verb|GLP_IV|, its lower bound were set 0, and its upper bound
2607were set to 1.
2608
2609\subsection{glp\_get\_col\_kind---retrieve column kind}
2610
2611\subsubsection*{Synopsis}
2612
2613\begin{verbatim}
2614int glp_get_col_kind(glp_prob *mip, int j);
2615\end{verbatim}
2616
2617\subsubsection*{Returns}
2618
2619The routine \verb|glp_get_col_kind| returns the kind of \verb|j|-th
2620column (structural variable) as follows:
2621
2622\begin{tabular}{@{}ll}
2623\verb|GLP_CV| & continuous variable; \\
2624\verb|GLP_IV| & integer variable; \\
2625\verb|GLP_BV| & binary variable. \\
2626\end{tabular}
2627
2628\subsection{glp\_get\_num\_int---retrieve number of integer columns}
2629
2630\subsubsection*{Synopsis}
2631
2632\begin{verbatim}
2633int glp_get_num_int(glp_prob *mip);
2634\end{verbatim}
2635
2636\subsubsection*{Returns}
2637
2638The routine \verb|glp_get_num_int| returns the number of columns
2639(structural variables), which are marked as integer. Note that this
2640number {\it does} include binary columns.
2641
2642\subsection{glp\_get\_num\_bin---retrieve number of binary columns}
2643
2644\subsubsection*{Synopsis}
2645
2646\begin{verbatim}
2647int glp_get_num_bin(glp_prob *mip);
2648\end{verbatim}
2649
2650\subsubsection*{Returns}
2651
2652The routine \verb|glp_get_num_bin| returns the number of columns
2653(structural variables), which are marked as integer and whose lower
2654bound is zero and upper bound is one.
2655
2656\subsection{glp\_intopt---solve MIP problem with the branch-and-cut
2657method}
2658
2659\subsubsection*{Synopsis}
2660
2661\begin{verbatim}
2662int glp_intopt(glp_prob *mip, const glp_iocp *parm);
2663\end{verbatim}
2664
2665\subsubsection*{Description}
2666
2667The routine \verb|glp_intopt| is a driver to the MIP solver based on
2668the branch-and-cut method, which is a hybrid of branch-and-bound and
2669cutting plane methods.
2670
2671If the presolver is disabled (see paragraph ``Control parameters''
2672below), on entry to the routine \verb|glp_intopt| the problem object,
2673which the parameter \verb|mip| points to, should contain optimal
2674solution to LP relaxation (it can be obtained, for example, with the
2675routine \verb|glp_simplex|). Otherwise, if the presolver is enabled, it
2676is not necessary.
2677
2678The MIP solver has a set of control parameters. Values of the control
2679parameters can be passed in the structure \verb|glp_iocp|, which the
2680parameter \verb|parm| points to. For detailed description of this
2681structure see paragraph ``Control parameters'' below. Before specifying
2682some control parameters the application program should initialize the
2683structure \verb|glp_iocp| by default values of all control parameters
2684using the routine \verb|glp_init_iocp| (see the next subsection). This
2685is needed for backward compatibility, because in the future there may
2686appear new members in the structure \verb|glp_iocp|.
2687
2688The parameter \verb|parm| can be specified as \verb|NULL|, in which case
2689the solver uses default settings.
2690
2691Note that the GLPK branch-and-cut solver is not perfect, so it is unable
2692to solve hard or very large scale MIP instances for a reasonable time.
2693
2694\subsubsection*{Returns}
2695
2696\def\arraystretch{1}
2697
2698\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
26990 & The MIP problem instance has been successfully solved. (This code
2700does {\it not} necessarily mean that the solver has found optimal
2701solution. It only means that the solution process was successful.) \\
2702\verb|GLP_EBOUND| & Unable to start the search, because some
2703double-bounded variables have incorrect bounds or some integer variables
2704have non-integer (fractional) bounds.\\
2705\verb|GLP_EROOT| & Unable to start the search, because optimal basis for
2706initial LP relaxation is not provided. (This code may appear only if the
2707presolver is disabled.)\\
2708\verb|GLP_ENOPFS| & Unable to start the search, because LP relaxation
2709of the MIP problem instance has no primal feasible solution. (This code
2710may appear only if the presolver is enabled.)\\
2711\verb|GLP_ENODFS| & Unable to start the search, because LP relaxation
2712of the MIP problem instance has no dual feasible solution. In other
2713word, this code means that if the LP relaxation has at least one primal
2714feasible solution, its optimal solution is unbounded, so if the MIP
2715problem has at least one integer feasible solution, its (integer)
2716optimal solution is also unbounded. (This code may appear only if the
2717presolver is enabled.)\\
2718\verb|GLP_EFAIL| & The search was prematurely terminated due to the
2719solver failure.\\
2720\verb|GLP_EMIPGAP| & The search was prematurely terminated, because the
2721relative mip gap tolerance has been reached.\\
2722\verb|GLP_ETMLIM| & The search was prematurely terminated, because the
2723time limit has been exceeded.\\
2724\verb|GLP_ESTOP| & The search was prematurely terminated by application.
2725(This code may appear only if the advanced solver interface is used.)\\
2726\end{tabular}
2727
2728\subsubsection*{Built-in MIP presolver}
2729
2730The branch-and-cut solver has {\it built-in MIP presolver}. It is
2731a subprogram that transforms the original MIP problem specified in the
2732problem object to an equivalent MIP problem, which may be easier for
2733solving with the branch-and-cut method than the original one. For
2734example, the presolver can remove redundant constraints and variables,
2735whose optimal values are known, perform bound and coefficient reduction,
2736etc. Once the transformed MIP problem has been solved, the presolver
2737transforms its solution back to corresponding solution of the original
2738problem.
2739
2740Presolving is an optional feature of the routine \verb|glp_intopt|, and
2741by default it is disabled. In order to enable the MIP presolver, the
2742control parameter \verb|presolve| should be set to \verb|GLP_ON| (see
2743paragraph ``Control parameters'' below).
2744
2745\subsubsection*{Advanced solver interface}
2746
2747The routine \verb|glp_intopt| allows the user to control the
2748branch-and-cut search by passing to the solver a user-defined callback
2749routine. For more details see Chapter ``Branch-and-Cut API Routines''.
2750
2751\subsubsection*{Terminal output}
2752
2753Solving a MIP problem may take a long time, so the solver reports some
2754information about best known solutions, which is sent to the terminal.
2755This information has the following format:
2756
2757\begin{verbatim}
2758+nnn: mip = xxx <rho> yyy gap (ppp; qqq)
2759\end{verbatim}
2760
2761\noindent
2762where: `\verb|nnn|' is the simplex iteration number; `\verb|xxx|' is a
2763value of the objective function for the best known integer feasible
2764solution (if no integer feasible solution has been found yet,
2765`\verb|xxx|' is the text `\verb|not found yet|'); `\verb|rho|' is the
2766string `\verb|>=|' (in case of minimization) or `\verb|<=|' (in case of
2767maximization); `\verb|yyy|' is a global bound for exact integer optimum
2768(i.e. the exact integer optimum is always in the range from `\verb|xxx|'
2769to `\verb|yyy|'); `\verb|gap|' is the relative mip gap, in percents,
2770computed as $gap=|xxx-yyy|/(|xxx|+{\tt DBL\_EPSILON})\cdot 100\%$ (if
2771$gap$ is greater than $999.9\%$, it is not printed); `\verb|ppp|' is the
2772number of subproblems in the active list, `\verb|qqq|' is the number of
2773subproblems which have been already fathomed and therefore removed from
2774the branch-and-bound search tree.
2775
2776\subsubsection{Control parameters}
2777
2778This paragraph describes all control parameters currently used in the
2779MIP solver. Symbolic names of control parameters are names of
2780corresponding members in the structure \verb|glp_iocp|.
2781
2782\medskip
2783
2784\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2785\multicolumn{2}{@{}l}{{\tt int msg\_lev} (default: {\tt GLP\_MSG\_ALL})}
2786\\
2787&Message level for terminal output:\\
2788&\verb|GLP_MSG_OFF|---no output;\\
2789&\verb|GLP_MSG_ERR|---error and warning messages only;\\
2790&\verb|GLP_MSG_ON |---normal output;\\
2791&\verb|GLP_MSG_ALL|---full output (including informational messages).
2792\\
2793\end{tabular}
2794
2795\medskip
2796
2797\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2798\multicolumn{2}{@{}l}{{\tt int br\_tech} (default: {\tt GLP\_BR\_DTH})}
2799\\
2800&Branching technique option:\\
2801&\verb|GLP_BR_FFV|---first fractional variable;\\
2802&\verb|GLP_BR_LFV|---last fractional variable;\\
2803&\verb|GLP_BR_MFV|---most fractional variable;\\
2804&\verb|GLP_BR_DTH|---heuristic by Driebeck and Tomlin;\\
2805&\verb|GLP_BR_PCH|---hybrid pseudocost heuristic.\\
2806\end{tabular}
2807
2808\medskip
2809
2810\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2811\multicolumn{2}{@{}l}{{\tt int bt\_tech} (default: {\tt GLP\_BT\_BLB})}
2812\\
2813&Backtracking technique option:\\
2814&\verb|GLP_BT_DFS|---depth first search;\\
2815&\verb|GLP_BT_BFS|---breadth first search;\\
2816&\verb|GLP_BT_BLB|---best local bound;\\
2817&\verb|GLP_BT_BPH|---best projection heuristic.\\
2818\end{tabular}
2819
2820\medskip
2821
2822\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2823\multicolumn{2}{@{}l}{{\tt int pp\_tech} (default: {\tt GLP\_PP\_ALL})}
2824\\
2825&Preprocessing technique option:\\
2826&\verb|GLP_PP_NONE|---disable preprocessing;\\
2827&\verb|GLP_PP_ROOT|---perform preprocessing only on the root level;\\
2828&\verb|GLP_PP_ALL |---perform preprocessing on all levels.\\
2829\end{tabular}
2830
2831\medskip
2832
2833\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2834\multicolumn{2}{@{}l}{{\tt int fp\_heur} (default: {\tt GLP\_OFF})}
2835\\
2836&Feasibility pump heuristic option:\\
2837&\verb|GLP_ON |---enable applying the feasibility pump heuristic;\\
2838&\verb|GLP_OFF|---disable applying the feasibility pump heuristic.\\
2839\end{tabular}
2840
2841\medskip
2842
2843\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2844\multicolumn{2}{@{}l}{{\tt int gmi\_cuts} (default: {\tt GLP\_OFF})}\\
2845&Gomory's mixed integer cut option:\\
2846&\verb|GLP_ON |---enable generating Gomory's cuts;\\
2847&\verb|GLP_OFF|---disable generating Gomory's cuts.\\
2848\end{tabular}
2849
2850\medskip
2851
2852\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2853\multicolumn{2}{@{}l}{{\tt int mir\_cuts} (default: {\tt GLP\_OFF})}\\
2854&Mixed integer rounding (MIR) cut option:\\
2855&\verb|GLP_ON |---enable generating MIR cuts;\\
2856&\verb|GLP_OFF|---disable generating MIR cuts.\\
2857\end{tabular}
2858
2859\medskip
2860
2861\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2862\multicolumn{2}{@{}l}{{\tt int cov\_cuts} (default: {\tt GLP\_OFF})}\\
2863&Mixed cover cut option:\\
2864&\verb|GLP_ON |---enable generating mixed cover cuts;\\
2865&\verb|GLP_OFF|---disable generating mixed cover cuts.\\
2866\end{tabular}
2867
2868\medskip
2869
2870\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2871\multicolumn{2}{@{}l}{{\tt int clq\_cuts} (default: {\tt GLP\_OFF})}\\
2872&Clique cut option:\\
2873&\verb|GLP_ON |---enable generating clique cuts;\\
2874&\verb|GLP_OFF|---disable generating clique cuts.\\
2875\end{tabular}
2876
2877\medskip
2878
2879\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2880\multicolumn{2}{@{}l}{{\tt double tol\_int} (default: {\tt 1e-5})}\\
2881&Absolute tolerance used to check if optimal solution to the current LP
2882relaxation is integer feasible. (Do not change this parameter without
2883detailed understanding its purpose.)\\
2884\end{tabular}
2885
2886\medskip
2887
2888\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2889\multicolumn{2}{@{}l}{{\tt double tol\_obj} (default: {\tt 1e-7})}\\
2890&Relative tolerance used to check if the objective value in optimal
2891solution to the current LP relaxation is not better than in the best
2892known integer feasible solution. (Do not change this parameter without
2893detailed understanding its purpose.)\\
2894\end{tabular}
2895
2896\medskip
2897
2898\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2899\multicolumn{2}{@{}l}{{\tt double mip\_gap} (default: {\tt 0.0})}\\
2900&The relative mip gap tolerance. If the relative mip gap for currently
2901known best integer feasible solution falls below this tolerance, the
2902solver terminates the search. This allows obtainig suboptimal integer
2903feasible solutions if solving the problem to optimality takes too long
2904time.\\
2905\end{tabular}
2906
2907\medskip
2908
2909\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2910\multicolumn{2}{@{}l}{{\tt int tm\_lim} (default: {\tt INT\_MAX})}\\
2911&Searching time limit, in milliseconds.\\
2912\end{tabular}
2913
2914\medskip
2915
2916\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2917\multicolumn{2}{@{}l}{{\tt int out\_frq} (default: {\tt 5000})}\\
2918&Output frequency, in milliseconds. This parameter specifies how
2919frequently the solver sends information about the solution process to
2920the terminal.\\
2921\end{tabular}
2922
2923\medskip
2924
2925\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2926\multicolumn{2}{@{}l}{{\tt int out\_dly} (default: {\tt 10000})}\\
2927&Output delay, in milliseconds. This parameter specifies how long the
2928solver should delay sending information about solution of the current
2929LP relaxation with the simplex method to the terminal.\\
2930\end{tabular}
2931
2932\medskip
2933
2934\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2935\multicolumn{2}{@{}l}
2936{{\tt void (*cb\_func)(glp\_tree *tree, void *info)}
2937(default: {\tt NULL})}\\
2938&Entry point to the user-defined callback routine. \verb|NULL| means
2939the advanced solver interface is not used. For more details see Chapter
2940``Branch-and-Cut API Routines''.\\
2941\end{tabular}
2942
2943\medskip
2944
2945\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2946\multicolumn{2}{@{}l}{{\tt void *cb\_info} (default: {\tt NULL})}\\
2947&Transit pointer passed to the routine \verb|cb_func| (see above).\\
2948\end{tabular}
2949
2950\medskip
2951
2952\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2953\multicolumn{2}{@{}l}{{\tt int cb\_size} (default: {\tt 0})}\\
2954&The number of extra (up to 256) bytes allocated for each node of the
2955branch-and-bound tree to store application-specific data. On creating
2956a node these bytes are initialized by binary zeros.\\
2957\end{tabular}
2958
2959\medskip
2960
2961\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2962\multicolumn{2}{@{}l}{{\tt int presolve} (default: {\tt GLP\_OFF})}\\
2963&MIP presolver option:\\
2964&\verb|GLP_ON |---enable using the MIP presolver;\\
2965&\verb|GLP_OFF|---disable using the MIP presolver.\\
2966\end{tabular}
2967
2968\medskip
2969
2970\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
2971\multicolumn{2}{@{}l}{{\tt int binarize} (default: {\tt GLP\_OFF})}\\
2972&Binarization option (used only if the presolver is enabled):\\
2973&\verb|GLP_ON |---replace general integer variables by binary ones;\\
2974&\verb|GLP_OFF|---do not use binarization.\\
2975\end{tabular}
2976
2977\subsection{glp\_init\_iocp---initialize integer optimizer control
2978parameters}
2979
2980\subsubsection*{Synopsis}
2981
2982\begin{verbatim}
2983void glp_init_iocp(glp_iocp *parm);
2984\end{verbatim}
2985
2986\subsubsection*{Description}
2987
2988The routine \verb|glp_init_iocp| initializes control parameters, which
2989are used by the branch-and-cut solver, with default values.
2990
2991Default values of the control parameters are stored in a \verb|glp_iocp|
2992structure, which the parameter \verb|parm| points to.
2993
2994\subsection{glp\_mip\_status---determine status of MIP solution}
2995
2996\subsubsection*{Synopsis}
2997
2998\begin{verbatim}
2999int glp_mip_status(glp_prob *mip);
3000\end{verbatim}
3001
3002\subsubsection*{Returns}
3003
3004The routine \verb|glp_mip_status| reports the status of a MIP solution
3005found by the MIP solver as follows:
3006
3007\smallskip
3008
3009\begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
3010\verb|GLP_UNDEF| & MIP solution is undefined. \\
3011\verb|GLP_OPT|   & MIP solution is integer optimal. \\
3012\verb|GLP_FEAS|  & MIP solution is integer feasible, however, its
3013   optimality (or non-optimality) has not been proven, perhaps due to
3014   premature termination of the search. \\
3015\end{tabular}
3016
3017\begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
3018\verb|GLP_NOFEAS| & problem has no integer feasible solution (proven by
3019   the solver). \\
3020\end{tabular}
3021
3022\subsection{glp\_mip\_obj\_val---retrieve objective value}
3023
3024\subsubsection*{Synopsis}
3025
3026\begin{verbatim}
3027double glp_mip_obj_val(glp_prob *mip);
3028\end{verbatim}
3029
3030\subsubsection*{Returns}
3031
3032The routine \verb|glp_mip_obj_val| returns value of the objective
3033function for MIP solution.
3034
3035\subsection{glp\_mip\_row\_val---retrieve row value}
3036
3037\subsubsection*{Synopsis}
3038
3039\begin{verbatim}
3040double glp_mip_row_val(glp_prob *mip, int i);
3041\end{verbatim}
3042
3043\subsubsection*{Returns}
3044
3045The routine \verb|glp_mip_row_val| returns value of the auxiliary
3046variable associated with \verb|i|-th row for MIP solution.
3047
3048\subsection{glp\_mip\_col\_val---retrieve column value}
3049
3050\subsubsection*{Synopsis}
3051
3052\begin{verbatim}
3053double glp_mip_col_val(glp_prob *mip, int j);
3054\end{verbatim}
3055
3056\subsubsection*{Returns}
3057
3058The routine \verb|glp_mip_col_val| returns value of the structural
3059variable associated with \verb|j|-th column for MIP solution.
3060
3061%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3062
3063\newpage
3064
3065\section{Additional routines}
3066
3067\subsection{lpx\_check\_kkt---check Karush-Kuhn-Tucker optimality
3068conditions}
3069
3070\subsubsection*{Synopsis}
3071
3072\begin{verbatim}
3073void lpx_check_kkt(glp_prob *lp, int scaled, LPXKKT *kkt);
3074\end{verbatim}
3075
3076\subsubsection*{Description}
3077
3078The routine \verb|lpx_check_kkt| checks Karush-Kuhn-Tucker optimality
3079conditions for basic solution. It is assumed that both primal and dual
3080components of basic solution are valid.
3081
3082If the parameter \verb|scaled| is zero, the optimality conditions are
3083checked for the original, unscaled LP problem. Otherwise, if the
3084parameter \verb|scaled| is non-zero, the routine checks the conditions
3085for an internally scaled LP problem.
3086
3087The parameter \verb|kkt| is a pointer to the structure \verb|LPXKKT|,
3088to which the routine stores results of the check. Members of this
3089structure are shown in the table below.
3090
3091\begin{table}[h]
3092\begin{center}
3093\begin{tabular}{@{}c|l|l@{}}
3094Condition & Member & Comment \\
3095\hline
3096(KKT.PE) & \verb|pe_ae_max| &
3097         Largest absolute error \\
3098         & \verb|pe_ae_row| &
3099         Number of row with largest absolute error \\
3100         & \verb|pe_re_max| &
3101         Largest relative error \\
3102         & \verb|pe_re_row| &
3103         Number of row with largest relative error \\
3104         & \verb|pe_quality| &
3105         Quality of primal solution \\
3106\hline
3107(KKT.PB) & \verb|pb_ae_max| &
3108         Largest absolute error \\
3109         & \verb|pb_ae_ind| &
3110         Number of variable with largest absolute error \\
3111         & \verb|pb_re_max| &
3112         Largest relative error \\
3113         & \verb|pb_re_ind| &
3114         Number of variable with largest relative error \\
3115         & \verb|pb_quality| &
3116         Quality of primal feasibility \\
3117\hline
3118(KKT.DE) & \verb|de_ae_max| &
3119         Largest absolute error \\
3120         & \verb|de_ae_col| &
3121         Number of column with largest absolute error \\
3122         & \verb|de_re_max| &
3123         Largest relative error \\
3124         & \verb|de_re_col| &
3125         Number of column with largest relative error \\
3126         & \verb|de_quality| &
3127         Quality of dual solution \\
3128\hline
3129(KKT.DB) & \verb|db_ae_max| &
3130         Largest absolute error \\
3131         & \verb|db_ae_ind| &
3132         Number of variable with largest absolute error \\
3133         & \verb|db_re_max| &
3134         Largest relative error \\
3135         & \verb|db_re_ind| &
3136         Number of variable with largest relative error \\
3137         & \verb|db_quality| &
3138         Quality of dual feasibility \\
3139\end{tabular}
3140\end{center}
3141\end{table}
3142
3143The routine performs all computations using only components of the
3144given LP problem and the current basic solution.
3145
3146\subsubsection*{Background}
3147
3148The first condition checked by the routine is:
3149$$x_R - A x_S = 0, \eqno{\rm (KKT.PE)}$$
3150where $x_R$ is the subvector of auxiliary variables (rows), $x_S$ is the
3151subvector of structural variables (columns), $A$ is the constraint
3152matrix. This condition expresses the requirement that all primal
3153variables must satisfy to the system of equality constraints of the
3154original LP problem. In case of exact arithmetic this condition would be
3155satisfied for any basic solution; however, in case of inexact
3156(floating-point) arithmetic, this condition shows how accurate the
3157primal basic solution is, that depends on accuracy of a representation
3158of the basis matrix used by the simplex method routines.
3159
3160The second condition checked by the routine is:
3161$$l_k \leq x_k \leq u_k {\rm \ \ \ for\ all}\ k=1,\dots,m+n,
3162\eqno{\rm (KKT.PB)}$$
3163where $x_k$ is auxiliary ($1\leq k\leq m$) or structural
3164($m+1\leq k\leq m+n$) variable, $l_k$ and $u_k$ are, respectively,
3165lower and upper bounds of the variable $x_k$ (including cases of
3166infinite bounds). This condition expresses the requirement that all
3167primal variables must satisfy to bound constraints of the original LP
3168problem. Since in case of basic solution all non-basic variables are
3169placed on their bounds, actually the condition (KKT.PB) needs to be
3170checked for basic variables only. If the primal basic solution has
3171sufficient accuracy, this condition shows primal feasibility of the
3172solution.
3173
3174The third condition checked by the routine is:
3175$${\rm grad}\;Z = c = (\tilde{A})^T \pi + d,$$
3176where $Z$ is the objective function, $c$ is the vector of objective
3177coefficients, $(\tilde{A})^T$ is a matrix transposed to the expanded
3178constraint matrix $\tilde{A} = (I|-A)$, $\pi$ is a vector of Lagrange
3179multipliers that correspond to equality constraints of the original LP
3180problem, $d$ is a vector of Lagrange multipliers that correspond to
3181bound constraints for all (auxiliary and structural) variables of the
3182original LP problem. Geometrically the third condition expresses the
3183requirement that the gradient of the objective function must belong to
3184the orthogonal complement of a linear subspace defined by the equality
3185and active bound constraints, i.e. that the gradient must be a linear
3186combination of normals to the constraint planes, where Lagrange
3187multipliers $\pi$ and $d$ are coefficients of that linear combination.
3188
3189To eliminate the vector $\pi$ the third condition can be rewritten as:
3190$$
3191\left(\begin{array}{@{}c@{}}I \\ -A^T\end{array}\right) \pi =
3192\left(\begin{array}{@{}c@{}}d_R \\ d_S\end{array}\right) +
3193\left(\begin{array}{@{}c@{}}c_R \\ c_S\end{array}\right),
3194$$
3195or, equivalently:
3196$$
3197\begin{array}{r@{}c@{}c}
3198\pi + d_R&\ =\ &c_R, \\
3199-A^T\pi + d_S&\ =\ &c_S. \\
3200\end{array}
3201$$
3202Then substituting the vector $\pi$ from the first equation into the
3203second one we have:
3204$$A^T (d_R - c_R) + (d_S - c_S) = 0, \eqno{\rm (KKT.DE)}$$
3205where $d_R$ is the subvector of reduced costs of auxiliary variables
3206(rows), $d_S$ is the subvector of reduced costs of structural variables
3207(columns), $c_R$ and $c_S$ are subvectors of objective coefficients at,
3208respectively, auxiliary and structural variables, $A^T$ is a matrix
3209transposed to the constraint matrix of the original LP problem. In case
3210of exact arithmetic this condition would be satisfied for any basic
3211solution; however, in case of inexact (floating-point) arithmetic, this
3212condition shows how accurate the dual basic solution is, that depends on
3213accuracy of a representation of the basis matrix used by the simplex
3214method routines.
3215
3216The last, fourth condition checked by the routine is (KKT.DB):
3217
3218\medskip
3219
3220\begin{tabular}{r@{}c@{}ll}
3221&$\ d_k\ $& $=0,$&if $x_k$ is basic or free non-basic variable \\
3222$0\leq$&$\ d_k\ $&$<+\infty$&if $x_k$ is non-basic on its lower
3223(minimization) \\
3224&&&or upper (maximization) bound \\
3225$-\infty<$&$\ d_k\ $&$\leq 0$&if $x_k$ is non-basic on its upper
3226(minimization) \\
3227&&&or lower (maximization) bound \\
3228$-\infty<$&$\ d_k\ $&$<+\infty$&if $x_k$ is non-basic fixed variable \\
3229\end{tabular}
3230
3231\medskip
3232
3233\noindent
3234for all $k=1,\dots,m+n$, where $d_k$ is a reduced cost (Lagrange
3235multiplier) of auxiliary ($1\leq k\leq m$) or structural
3236($m+1\leq k\leq m+n$) variable $x_k$. Geometrically this condition
3237expresses the requirement that constraints of the original problem must
3238"hold" the point preventing its movement along the anti-gradient (in
3239case of minimization) or the gradient (in case of maximization) of the
3240objective function. Since in case of basic solution reduced costs of
3241all basic variables are placed on their (zero) bounds, actually the
3242condition (KKT.DB) needs to be checked for non-basic variables only.
3243If the dual basic solution has sufficient accuracy, this condition shows
3244dual feasibility of the solution.
3245
3246Should note that the complete set of Karush-Kuhn-Tucker optimality
3247conditions also includes the fifth, so called complementary slackness
3248condition, which expresses the requirement that at least either a primal
3249variable $x_k$ or its dual counterpart $d_k$ must be on its bound for
3250all $k=1,\dots,m+n$. However, being always satisfied by definition for
3251any basic solution that condition is not checked by the routine.
3252
3253To check the first condition (KKT.PE) the routine computes a vector of
3254residuals:
3255$$g = x_R - A x_S,$$
3256determines component of this vector that correspond to largest absolute
3257and relative errors:
3258
3259\medskip
3260
3261\hspace{30mm}
3262\verb|pe_ae_max| $\displaystyle{= \max_{1\leq i\leq m}|g_i|}$,
3263
3264\medskip
3265
3266\hspace{30mm}
3267\verb|pe_re_max| $\displaystyle{= \max_{1\leq i\leq m}
3268\frac{|g_i|}{1+|(x_R)_i|}}$,
3269
3270\medskip
3271
3272\noindent
3273and stores these quantities and corresponding row indices to the
3274structure \verb|LPXKKT|.
3275
3276To check the second condition (KKT.PB) the routine computes a vector
3277of residuals:
3278$$
3279h_k = \left\{
3280\begin{array}{ll}
32810,         & {\rm if}\ l_k \leq x_k \leq u_k \\
3282x_k - l_k, & {\rm if}\ x_k < l_k \\
3283x_k - u_k, & {\rm if}\ x_k > u_k \\
3284\end{array}
3285\right.
3286$$
3287for all $k=1,\dots,m+n$, determines components of this vector that
3288correspond to largest absolute and relative errors:
3289
3290\medskip
3291
3292\hspace{30mm}
3293\verb|pb_ae_max| $\displaystyle{= \max_{1\leq k \leq m+n}|h_k|}$,
3294
3295\medskip
3296
3297\hspace{30mm}
3298\verb|pb_re_max| $\displaystyle{= \max_{1\leq k \leq m+n}
3299\frac{|h_k|}{1+|x_k|}}$,
3300
3301\medskip
3302
3303\noindent
3304and stores these quantities and corresponding variable indices to the
3305structure \verb|LPXKKT|.
3306
3307To check the third condition (KKT.DE) the routine computes a vector of
3308residuals:
3309$$u = A^T (d_R - c_R) + (d_S - c_S),$$
3310determines components of this vector that correspond to largest
3311absolute and relative errors:
3312
3313\medskip
3314
3315\hspace{30mm}
3316\verb|de_ae_max| $\displaystyle{= \max_{1\leq j\leq n}|u_j|}$,
3317
3318\medskip
3319
3320\hspace{30mm}
3321\verb|de_re_max| $\displaystyle{= \max_{1\leq j\leq n}
3322\frac{|u_j|}{1+|(d_S)_j - (c_S)_j|}}$,
3323
3324\medskip
3325
3326\noindent
3327and stores these quantities and corresponding column indices to the
3328structure \verb|LPXKKT|.
3329
3330To check the fourth condition (KKT.DB) the routine computes a vector
3331of residuals:
3332
3333$$
3334v_k = \left\{
3335\begin{array}{ll}
33360,         & {\rm if}\ d_k\ {\rm has\ correct\ sign} \\
3337d_k,       & {\rm if}\ d_k\ {\rm has\ wrong\ sign} \\
3338\end{array}
3339\right.
3340$$
3341for all $k=1,\dots,m+n$, determines components of this vector that
3342correspond to largest absolute and relative errors:
3343
3344\medskip
3345
3346\hspace{30mm}
3347\verb|db_ae_max| $\displaystyle{= \max_{1\leq k\leq m+n}|v_k|}$,
3348
3349\medskip
3350
3351\hspace{30mm}
3352\verb|db_re_max| $\displaystyle{= \max_{1\leq k\leq m+n}
3353\frac{|v_k|}{1+|d_k - c_k|}}$,
3354
3355\medskip
3356
3357\noindent
3358and stores these quantities and corresponding variable indices to the
3359structure \verb|LPXKKT|.
3360
3361Using the relative errors for all the four conditions listed above the
3362routine
3363\verb|lpx_check_kkt| also estimates a "quality" of the basic solution
3364from the standpoint of these conditions and stores corresponding
3365quality indicators to the structure \verb|LPXKKT|:
3366
3367\verb|pe_quality|---quality of primal solution;
3368
3369\verb|pb_quality|---quality of primal feasibility;
3370
3371\verb|de_quality|---quality of dual solution;
3372
3373\verb|db_quality|---quality of dual feasibility.
3374
3375Each of these indicators is assigned to one of the following four
3376values:
3377
3378\verb|'H'| means high quality,
3379
3380\verb|'M'| means medium quality,
3381
3382\verb|'L'| means low quality, or
3383
3384\verb|'?'| means wrong or infeasible solution.
3385
3386If all the indicators show high or medium quality (for an internally
3387scaled LP problem, i.e. when the parameter \verb|scaled| in a call to
3388the routine \verb|lpx_check_kkt| is non-zero), the user can be sure that
3389the obtained basic solution is quite accurate.
3390
3391If some of the indicators show low quality, the solution can still be
3392considered as relevant, though an additional analysis is needed
3393depending on which indicator shows low quality.
3394
3395If the indicator \verb|pe_quality| is assigned to \verb|'?'|, the
3396primal solution is wrong. If the indicator \verb|de_quality| is assigned
3397to \verb|'?'|, the dual solution is wrong.
3398
3399If the indicator \verb|db_quality| is assigned to \verb|'?'| while
3400other indicators show a good quality, this means that the current
3401basic solution being primal feasible is not dual feasible. Similarly,
3402if the indicator \verb|pb_quality| is assigned to \verb|'?'| while
3403other indicators are not, this means that the current basic solution
3404being dual feasible is not primal feasible.
3405
3406%* eof *%
Note: See TracBrowser for help on using the repository browser.