lemon-project-template-glpk
view deps/glpk/doc/glpk02.tex @ 9:33de93886c88
Import GLPK 4.47
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 20:59:10 +0100 |
| parents | |
| children |
line source
1 %* glpk02.tex *%
3 \chapter{Basic API Routines}
5 This chapter describes GLPK API routines intended for using in
6 application programs.
8 \subsubsection*{Library header}
10 All 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
12 GLPK API, either directly or indirectly through some other header file
13 as follows:
15 \begin{verbatim}
16 #include <glpk.h>
17 \end{verbatim}
19 \subsubsection*{Error handling}
21 If some GLPK API routine detects erroneous or incorrect data passed by
22 the application program, it writes appropriate diagnostic messages to
23 the terminal and then abnormally terminates the application program.
24 In most practical cases this allows to simplify programming by avoiding
25 numerous checks of return codes. Thus, in order to prevent crashing the
26 application program should check all data, which are suspected to be
27 incorrect, before calling GLPK API routines.
29 Should note that this kind of error handling is used only in cases of
30 incorrect data passed by the application program. If, for example, the
31 application program calls some GLPK API routine to read data from an
32 input file and these data are incorrect, the GLPK API routine reports
33 about error in the usual way by means of the return code.
35 \subsubsection*{Thread safety}
37 Currently GLPK API routines are non-reentrant and therefore cannot be
38 used in multi-threaded programs.
40 \subsubsection*{Array indexing}
42 Normally all GLPK API routines start array indexing from 1, not from 0
43 (except the specially stipulated cases). This means, for example, that
44 if some vector $x$ of the length $n$ is passed as an array to some GLPK
45 API routine, the latter expects vector components to be placed in
46 locations \verb|x[1]|, \verb|x[2]|, \dots, \verb|x[n]|, and the location
47 \verb|x[0]| normally is not used.
49 In order to avoid indexing errors it is most convenient and most
50 reliable to declare the array \verb|x| as follows:
52 \begin{verbatim}
53 double x[1+n];
54 \end{verbatim}
56 \noindent
57 or to allocate it as follows:
59 \begin{verbatim}
60 double *x;
61 . . .
62 x = calloc(1+n, sizeof(double));
63 \end{verbatim}
65 \noindent
66 In both cases one extra location \verb|x[0]| is reserved that allows
67 passing the array to GLPK routines in a usual way.
69 \section{Problem object}
71 All GLPK API routines deal with so called {\it problem object}, which
72 is a program object of type \verb|glp_prob| and intended to represent
73 a particular LP or MIP instance.
75 The type \verb|glp_prob| is a data structure declared in the header
76 file \verb|glpk.h| as follows:
78 \begin{verbatim}
79 typedef struct { ... } glp_prob;
80 \end{verbatim}
82 Problem objects (i.e. program objects of the \verb|glp_prob| type) are
83 allocated and managed internally by the GLPK API routines. The
84 application program should never use any members of the \verb|glp_prob|
85 structure directly and should deal only with pointers to these objects
86 (that is, \verb|glp_prob *| values).
88 \pagebreak
90 The problem object consists of five segments, which are:
92 $\bullet$ problem segment,
94 $\bullet$ basis segment,
96 $\bullet$ interior point segment,
98 $\bullet$ MIP segment, and
100 $\bullet$ control parameters and statistics segment.
102 \subsubsection*{Problem segment}
104 The {\it problem segment} contains original LP/MIP data, which
105 corresponds to the problem formulation (1.1)---(1.3) (see Section
106 \ref{seclp}, page \pageref{seclp}). It includes the following
107 components:
109 $\bullet$ rows (auxiliary variables),
111 $\bullet$ columns (structural variables),
113 $\bullet$ objective function, and
115 $\bullet$ constraint matrix.
117 Rows and columns have the same set of the following attributes:
119 $\bullet$ ordinal number,
121 $\bullet$ symbolic name (1 up to 255 arbitrary graphic characters),
123 $\bullet$ type (free, lower bound, upper bound, double bound, fixed),
125 $\bullet$ numerical values of lower and upper bounds,
127 $\bullet$ scale factor.
129 {\it Ordinal numbers} are intended for referencing rows and columns.
130 Row ordinal numbers are integers $1, 2, \dots, m$, and column ordinal
131 numbers are integers $1, 2, \dots, n$, where $m$ and $n$ are,
132 respectively, the current number of rows and columns in the problem
133 object.
135 {\it Symbolic names} are intended for informational purposes. They also
136 can be used for referencing rows and columns.
138 {\it Types and bounds} of rows (auxiliary variables) and columns
139 (structural variables) are explained above (see Section \ref{seclp},
140 page \pageref{seclp}).
142 {\it Scale factors} are used internally for scaling rows and columns of
143 the constraint matrix.
145 Information about the {\it objective function} includes numerical
146 values of objective coefficients and a flag, which defines the
147 optimization direction (i.e. minimization or maximization).
149 The {\it constraint matrix} is a $m \times n$ rectangular matrix built
150 of constraint coefficients $a_{ij}$, which defines the system of linear
151 constraints (1.2) (see Section \ref{seclp}, page \pageref{seclp}). This
152 matrix is stored in the problem object in both row-wise and column-wise
153 sparse formats.
155 Once the problem object has been created, the application program can
156 access and modify any components of the problem segment in arbitrary
157 order.
159 \subsubsection*{Basis segment}
161 The {\it basis segment} of the problem object keeps information related
162 to the current basic solution. It includes:
164 $\bullet$ row and column statuses,
166 $\bullet$ basic solution statuses,
168 $\bullet$ factorization of the current basis matrix, and
170 $\bullet$ basic solution components.
172 The {\it row and column statuses} define which rows and columns are
173 basic and which are non-basic. These statuses may be assigned either by
174 the application program of by some API routines. Note that these
175 statuses are always defined independently on whether the corresponding
176 basis is valid or not.
178 The {\it basic solution statuses} include the {\it primal status} and
179 the {\it dual status}, which are set by the simplex-based solver once
180 the problem has been solved. The primal status shows whether a primal
181 basic solution is feasible, infeasible, or undefined. The dual status
182 shows the same for a dual basic solution.
184 The {\it factorization of the basis matrix} is some factorized form
185 (like LU-factorization) of the current basis matrix (defined by the
186 current row and column statuses). The factorization is used by the
187 simplex-based solver and kept when the solver terminates the search.
188 This feature allows efficiently reoptimizing the problem after some
189 modifications (for example, after changing some bounds or objective
190 coefficients). It also allows performing the post-optimal analysis (for
191 example, computing components of the simplex table, etc.).
193 The {\it basic solution components} include primal and dual values of
194 all auxiliary and structural variables for the most recently obtained
195 basic solution.
197 \subsubsection*{Interior point segment}
199 The {\it interior point segment} is automatically allocated after the
200 problem has been solved using the interior point solver. It contains
201 interior point solution components, which include the solution status,
202 and primal and dual values of all auxiliary and structural variables.
204 \subsubsection*{MIP segment}
206 The {\it MIP segment} is used only for MIP problems. This segment
207 includes:
209 $\bullet$ column kinds,
211 $\bullet$ MIP solution status, and
213 $\bullet$ MIP solution components.
215 The {\it column kinds} define which columns (i.e. structural variables)
216 are integer and which are continuous.
218 The {\it MIP solution status} is set by the MIP solver and shows whether
219 a MIP solution is integer optimal, integer feasible (non-optimal), or
220 undefined.
222 The {\it MIP solution components} are computed by the MIP solver and
223 include primal values of all auxiliary and structural variables for the
224 most recently obtained MIP solution.
226 Note that in case of MIP problem the basis segment corresponds to
227 the optimal solution of LP relaxation, which is also available to the
228 application program.
230 Currently the search tree is not kept in the MIP segment. Therefore if
231 the search has been terminated, it cannot be continued.
233 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
235 \newpage
237 \section{Problem creating and modifying routines}
239 \subsection{glp\_create\_prob---create problem object}
241 \subsubsection*{Synopsis}
243 \begin{verbatim}
244 glp_prob *glp_create_prob(void);
245 \end{verbatim}
247 \subsubsection*{Description}
249 The routine \verb|glp_create_prob| creates a new problem object, which
250 initially is ``empty'', i.e. has no rows and columns.
252 \subsubsection*{Returns}
254 The routine returns a pointer to the created object, which should be
255 used in any subsequent operations on this object.
257 \subsection{glp\_set\_prob\_name---assign (change) problem name}
259 \subsubsection*{Synopsis}
261 \begin{verbatim}
262 void glp_set_prob_name(glp_prob *lp, const char *name);
263 \end{verbatim}
265 \subsubsection*{Description}
267 The routine \verb|glp_set_prob_name| assigns a given symbolic
268 \verb|name| (1 up to 255 characters) to the specified problem object.
270 If the parameter \verb|name| is \verb|NULL| or empty string, the routine
271 erases an existing symbolic name of the problem object.
273 \subsection{glp\_set\_obj\_name---assign (change) objective function
274 name}
276 \subsubsection*{Synopsis}
278 \begin{verbatim}
279 void glp_set_obj_name(glp_prob *lp, const char *name);
280 \end{verbatim}
282 \subsubsection*{Description}
284 The routine \verb|glp_set_obj_name| assigns a given symbolic
285 \verb|name| (1 up to 255 characters) to the objective function of the
286 specified problem object.
288 If the parameter \verb|name| is \verb|NULL| or empty string, the routine
289 erases an existing symbolic name of the objective function.
291 \subsection{glp\_set\_obj\_dir---set (change) optimization direction\\
292 flag}
294 \subsubsection*{Synopsis}
296 \begin{verbatim}
297 void glp_set_obj_dir(glp_prob *lp, int dir);
298 \end{verbatim}
300 \subsubsection*{Description}
302 The routine \verb|glp_set_obj_dir| sets (changes) the optimization
303 direction flag (i.e. ``sense'' of the objective function) as specified
304 by the parameter \verb|dir|:
306 \begin{tabular}{@{}ll}
307 \verb|GLP_MIN| & minimization; \\
308 \verb|GLP_MAX| & maximization. \\
309 \end{tabular}
311 \noindent
312 (Note that by default the problem is minimization.)
314 \subsection{glp\_add\_rows---add new rows to problem object}
316 \subsubsection*{Synopsis}
318 \begin{verbatim}
319 int glp_add_rows(glp_prob *lp, int nrs);
320 \end{verbatim}
322 \subsubsection*{Description}
324 The routine \verb|glp_add_rows| adds \verb|nrs| rows (constraints) to
325 the specified problem object. New rows are always added to the end of
326 the row list, so the ordinal numbers of existing rows are not changed.
328 Being added each new row is initially free (unbounded) and has empty
329 list of the constraint coefficients.
331 \subsubsection*{Returns}
333 The routine \verb|glp_add_rows| returns the ordinal number of the first
334 new row added to the problem object.
336 \newpage
338 \subsection{glp\_add\_cols---add new columns to problem object}
340 \subsubsection*{Synopsis}
342 \begin{verbatim}
343 int glp_add_cols(glp_prob *lp, int ncs);
344 \end{verbatim}
346 \subsubsection*{Description}
348 The routine \verb|glp_add_cols| adds \verb|ncs| columns (structural
349 variables) to the specified problem object. New columns are always added
350 to the end of the column list, so the ordinal numbers of existing
351 columns are not changed.
353 Being added each new column is initially fixed at zero and has empty
354 list of the constraint coefficients.
356 \subsubsection*{Returns}
358 The routine \verb|glp_add_cols| returns the ordinal number of the first
359 new column added to the problem object.
361 \subsection{glp\_set\_row\_name---assign (change) row name}
363 \subsubsection*{Synopsis}
365 \begin{verbatim}
366 void glp_set_row_name(glp_prob *lp, int i, const char *name);
367 \end{verbatim}
369 \subsubsection*{Description}
371 The routine \verb|glp_set_row_name| assigns a given symbolic
372 \verb|name| (1 up to 255 characters) to \verb|i|-th row (auxiliary
373 variable) of the specified problem object.
375 If the parameter \verb|name| is \verb|NULL| or empty string, the routine
376 erases an existing name of $i$-th row.
378 \subsection{glp\_set\_col\_name---assign (change) column name}
380 \subsubsection*{Synopsis}
382 \begin{verbatim}
383 void glp_set_col_name(glp_prob *lp, int j, const char *name);
384 \end{verbatim}
386 \subsubsection*{Description}
388 The routine \verb|glp_set_col_name| assigns a given symbolic
389 \verb|name| (1 up to 255 characters) to \verb|j|-th column (structural
390 variable) of the specified problem object.
392 If the parameter \verb|name| is \verb|NULL| or empty string, the routine
393 erases an existing name of $j$-th column.
395 \subsection{glp\_set\_row\_bnds---set (change) row bounds}
397 \subsubsection*{Synopsis}
399 \begin{verbatim}
400 void glp_set_row_bnds(glp_prob *lp, int i, int type,
401 double lb, double ub);
402 \end{verbatim}
404 \subsubsection*{Description}
406 The routine \verb|glp_set_row_bnds| sets (changes) the type and bounds
407 of \verb|i|-th row (auxiliary variable) of the specified problem object.
409 The parameters \verb|type|, \verb|lb|, and \verb|ub| specify the type,
410 lower bound, and upper bound, respectively, as follows:
412 \begin{center}
413 \begin{tabular}{cr@{}c@{}ll}
414 Type & \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}
429 \noindent
430 where $x$ is the auxiliary variable associated with $i$-th row.
432 If the row has no lower bound, the parameter \verb|lb| is ignored. If
433 the row has no upper bound, the parameter \verb|ub| is ignored. If the
434 row is an equality constraint (i.e. the corresponding auxiliary variable
435 is of fixed type), only the parameter \verb|lb| is used while the
436 parameter \verb|ub| is ignored.
438 Being added to the problem object each row is initially free, i.e. its
439 type is \verb|GLP_FR|.
441 \newpage
443 \subsection{glp\_set\_col\_bnds---set (change) column bounds}
445 \subsubsection*{Synopsis}
447 \begin{verbatim}
448 void glp_set_col_bnds(glp_prob *lp, int j, int type,
449 double lb, double ub);
450 \end{verbatim}
452 \subsubsection*{Description}
454 The routine \verb|glp_set_col_bnds| sets (changes) the type and bounds
455 of \verb|j|-th column (structural variable) of the specified problem
456 object.
458 The parameters \verb|type|, \verb|lb|, and \verb|ub| specify the type,
459 lower bound, and upper bound, respectively, as follows:
461 \begin{center}
462 \begin{tabular}{cr@{}c@{}ll}
463 Type & \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}
478 \noindent
479 where $x$ is the structural variable associated with $j$-th column.
481 If the column has no lower bound, the parameter \verb|lb| is ignored.
482 If the column has no upper bound, the parameter \verb|ub| is ignored.
483 If the column is of fixed type, only the parameter \verb|lb| is used
484 while the parameter \verb|ub| is ignored.
486 Being added to the problem object each column is initially fixed at
487 zero, i.e. its type is \verb|GLP_FX| and both bounds are 0.
489 \subsection{glp\_set\_obj\_coef---set (change) objective coefficient
490 or constant term}
492 \subsubsection*{Synopsis}
494 \begin{verbatim}
495 void glp_set_obj_coef(glp_prob *lp, int j, double coef);
496 \end{verbatim}
498 \subsubsection*{Description}
500 The routine \verb|glp_set_obj_coef| sets (changes) the objective
501 coefficient at \verb|j|-th column (structural variable). A new value of
502 the objective coefficient is specified by the parameter \verb|coef|.
504 If the parameter \verb|j| is 0, the routine sets (changes) the constant
505 term (``shift'') of the objective function.
507 \subsection{glp\_set\_mat\_row---set (replace) row of the constraint
508 matrix}
510 \subsubsection*{Synopsis}
512 \begin{verbatim}
513 void glp_set_mat_row(glp_prob *lp, int i, int len,
514 const int ind[], const double val[]);
515 \end{verbatim}
517 \subsubsection*{Description}
519 The routine \verb|glp_set_mat_row| stores (replaces) the contents of
520 \verb|i|-th row of the constraint matrix of the specified problem
521 object.
523 Column indices and numerical values of new row elements must be placed
524 in 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$
526 is the new length of $i$-th row, $n$ is the current number of columns in
527 the problem object. Elements with identical column indices are not
528 allowed. Zero elements are allowed, but they are not stored in the
529 constraint matrix.
531 If the parameter \verb|len| is 0, the parameters \verb|ind| and/or
532 \verb|val| can be specified as \verb|NULL|.
534 \subsection{glp\_set\_mat\_col---set (replace) column of the
535 constr\-aint matrix}
537 \subsubsection*{Synopsis}
539 \begin{verbatim}
540 void glp_set_mat_col(glp_prob *lp, int j, int len,
541 const int ind[], const double val[]);
542 \end{verbatim}
544 \subsubsection*{Description}
546 The routine \verb|glp_set_mat_col| stores (replaces) the contents of
547 \verb|j|-th column of the constraint matrix of the specified problem
548 object.
550 Row indices and numerical values of new column elements must be placed
551 in 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$
553 is the new length of $j$-th column, $m$ is the current number of rows in
554 the problem object. Elements with identical row indices are not allowed.
555 Zero elements are allowed, but they are not stored in the constraint
556 matrix.
558 If the parameter \verb|len| is 0, the parameters \verb|ind| and/or
559 \verb|val| can be specified as \verb|NULL|.
561 \subsection{glp\_load\_matrix---load (replace) the whole constraint
562 matrix}
564 \subsubsection*{Synopsis}
566 \begin{verbatim}
567 void glp_load_matrix(glp_prob *lp, int ne, const int ia[],
568 const int ja[], const double ar[]);
569 \end{verbatim}
571 \subsubsection*{Description}
573 The routine \verb|glp_load_matrix| loads the constraint matrix passed
574 in the arrays \verb|ia|, \verb|ja|, and \verb|ar| into the specified
575 problem object. Before loading the current contents of the constraint
576 matrix is destroyed.
578 Constraint coefficients (elements of the constraint matrix) must be
579 specified 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
581 the column index, and \verb|ar[k]| is a numeric value of corresponding
582 constraint coefficient. The parameter \verb|ne| specifies the total
583 number of (non-zero) elements in the matrix to be loaded. Coefficients
584 with identical indices are not allowed. Zero coefficients are allowed,
585 however, they are not stored in the constraint matrix.
587 If the parameter \verb|ne| is 0, the parameters \verb|ia|, \verb|ja|,
588 and/or \verb|ar| can be specified as \verb|NULL|.
590 \subsection{glp\_check\_dup---check for duplicate elements in sparse
591 matrix}
593 \subsubsection*{Synopsis}
595 \begin{verbatim}
596 int glp_check_dup(int m, int n, int ne, const int ia[],
597 const int ja[]);
598 \end{verbatim}
600 \subsubsection*{Description}
602 The routine \verb|glp_check_dup checks| for duplicate elements (that
603 is, elements with identical indices) in a sparse matrix specified in
604 the coordinate format.
606 The parameters $m$ and $n$ specifies, respectively, the number of rows
607 and columns in the matrix, $m\geq 0$, $n\geq 0$.
609 The parameter {\it ne} specifies the number of (structurally) non-zero
610 elements in the matrix, {\it ne} $\geq 0$.
612 Elements 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.
615 The routine \verb|glp_check_dup| can be used prior to a call to the
616 routine \verb|glp_load_matrix| to check that the constraint matrix to
617 be loaded has no duplicate elements.
619 \subsubsection*{Returns}
621 The routine \verb|glp_check_dup| returns one of the following values:
623 \noindent
624 \begin{tabular}{@{}r@{\ }c@{\ }l@{}}
625 0&---&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}
630 \subsection{glp\_sort\_matrix---sort elements of the constraint matrix}
632 \subsubsection*{Synopsis}
634 \begin{verbatim}
635 void glp_sort_matrix(glp_prob *P);
636 \end{verbatim}
638 \subsubsection*{Description}
640 The routine \verb|glp_sort_matrix| sorts elements of the constraint
641 matrix rebuilding its row and column linked lists. On exit from the
642 routine the constraint matrix is not changed, however, elements in the
643 row linked lists become ordered by ascending column indices, and the
644 elements in the column linked lists become ordered by ascending row
645 indices.
647 \subsection{glp\_del\_rows---delete rows from problem object}
649 \subsubsection*{Synopsis}
651 \begin{verbatim}
652 void glp_del_rows(glp_prob *lp, int nrs, const int num[]);
653 \end{verbatim}
655 \subsubsection*{Description}
657 The routine \verb|glp_del_rows| deletes rows from the specified problem
658 ob-\linebreak ject. Ordinal numbers of rows to be deleted should be
659 placed in locations \verb|num[1]|, \dots, \verb|num[nrs]|, where
660 ${\tt nrs}>0$.
662 Note that deleting rows involves changing ordinal numbers of other
663 rows remaining in the problem object. New ordinal numbers of the
664 remaining rows are assigned under the assumption that the original
665 order of rows is not changed. Let, for example, before deletion there
666 be five rows $a$, $b$, $c$, $d$, $e$ with ordinal numbers 1, 2, 3, 4, 5,
667 and let rows $b$ and $d$ have been deleted. Then after deletion the
668 remaining rows $a$, $c$, $e$ are assigned new oridinal numbers 1, 2, 3.
670 \subsection{glp\_del\_cols---delete columns from problem object}
672 \subsubsection*{Synopsis}
674 \begin{verbatim}
675 void glp_del_cols(glp_prob *lp, int ncs, const int num[]);
676 \end{verbatim}
678 \subsubsection*{Description}
680 The routine \verb|glp_del_cols| deletes columns from the specified
681 problem object. Ordinal numbers of columns to be deleted should be
682 placed in locations \verb|num[1]|, \dots, \verb|num[ncs]|, where
683 ${\tt ncs}>0$.
685 Note that deleting columns involves changing ordinal numbers of other
686 columns remaining in the problem object. New ordinal numbers of the
687 remaining columns are assigned under the assumption that the original
688 order of columns is not changed. Let, for example, before deletion there
689 be six columns $p$, $q$, $r$, $s$, $t$, $u$ with ordinal numbers 1, 2,
690 3, 4, 5, 6, and let columns $p$, $q$, $s$ have been deleted. Then after
691 deletion the remaining columns $r$, $t$, $u$ are assigned new ordinal
692 numbers 1, 2, 3.
694 \subsection{glp\_copy\_prob---copy problem object content}
696 \subsubsection*{Synopsis}
698 \begin{verbatim}
699 void glp_copy_prob(glp_prob *dest, glp_prob *prob, int names);
700 \end{verbatim}
702 \subsubsection*{Description}
704 The routine \verb|glp_copy_prob| copies the content of the problem
705 object \verb|prob| to the problem object \verb|dest|.
707 The parameter \verb|names| is a flag. If it is \verb|GLP_ON|,
708 the routine also copies all symbolic names; otherwise, if it is
709 \verb|GLP_OFF|, no symbolic names are copied.
711 \newpage
713 \subsection{glp\_erase\_prob---erase problem object content}
715 \subsubsection*{Synopsis}
717 \begin{verbatim}
718 void glp_erase_prob(glp_prob *lp);
719 \end{verbatim}
721 \subsubsection*{Description}
723 The routine \verb|glp_erase_prob| erases the content of the specified
724 problem object. The effect of this operation is the same as if the
725 problem object would be deleted with the routine \verb|glp_delete_prob|
726 and then created anew with the routine \verb|glp_create_prob|, with the
727 only exception that the handle (pointer) to the problem object remains
728 valid.
730 \subsection{glp\_delete\_prob---delete problem object}
732 \subsubsection*{Synopsis}
734 \begin{verbatim}
735 void glp_delete_prob(glp_prob *lp);
736 \end{verbatim}
738 \subsubsection*{Description}
740 The routine \verb|glp_delete_prob| deletes a problem object, which the
741 parameter \verb|lp| points to, freeing all the memory allocated to this
742 object.
744 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
746 \newpage
748 \section{Problem retrieving routines}
750 \subsection{glp\_get\_prob\_name---retrieve problem name}
752 \subsubsection*{Synopsis}
754 \begin{verbatim}
755 const char *glp_get_prob_name(glp_prob *lp);
756 \end{verbatim}
758 \subsubsection*{Returns}
760 The routine \verb|glp_get_prob_name| returns a pointer to an internal
761 buffer, which contains symbolic name of the problem. However, if the
762 problem has no assigned name, the routine returns \verb|NULL|.
764 \subsection{glp\_get\_obj\_name---retrieve objective function name}
766 \subsubsection*{Synopsis}
768 \begin{verbatim}
769 const char *glp_get_obj_name(glp_prob *lp);
770 \end{verbatim}
772 \subsubsection*{Returns}
774 The routine \verb|glp_get_obj_name| returns a pointer to an internal
775 buffer, which contains symbolic name assigned to the objective
776 function. However, if the objective function has no assigned name, the
777 routine returns \verb|NULL|.
779 \subsection{glp\_get\_obj\_dir---retrieve optimization direction flag}
781 \subsubsection*{Synopsis}
783 \begin{verbatim}
784 int glp_get_obj_dir(glp_prob *lp);
785 \end{verbatim}
787 \subsubsection*{Returns}
789 The routine \verb|glp_get_obj_dir| returns the optimization direction
790 flag (i.e. ``sense'' of the objective function):
792 \begin{tabular}{@{}ll}
793 \verb|GLP_MIN| & minimization; \\
794 \verb|GLP_MAX| & maximization. \\
795 \end{tabular}
797 \pagebreak
799 \subsection{glp\_get\_num\_rows---retrieve number of rows}
801 \subsubsection*{Synopsis}
803 \begin{verbatim}
804 int glp_get_num_rows(glp_prob *lp);
805 \end{verbatim}
807 \subsubsection*{Returns}
809 The routine \verb|glp_get_num_rows| returns the current number of rows
810 in the specified problem object.
812 \subsection{glp\_get\_num\_cols---retrieve number of columns}
814 \subsubsection*{Synopsis}
816 \begin{verbatim}
817 int glp_get_num_cols(glp_prob *lp);
818 \end{verbatim}
820 \subsubsection*{Returns}
822 The routine \verb|glp_get_num_cols| returns the current number of
823 columns the specified problem object.
825 \subsection{glp\_get\_row\_name---retrieve row name}
827 \subsubsection*{Synopsis}
829 \begin{verbatim}
830 const char *glp_get_row_name(glp_prob *lp, int i);
831 \end{verbatim}
833 \subsubsection*{Returns}
835 The routine \verb|glp_get_row_name| returns a pointer to an internal
836 buffer, which contains a symbolic name assigned to \verb|i|-th row.
837 However, if the row has no assigned name, the routine returns
838 \verb|NULL|.
840 \subsection{glp\_get\_col\_name---retrieve column name}
842 \subsubsection*{Synopsis}
844 \begin{verbatim}
845 const char *glp_get_col_name(glp_prob *lp, int j);
846 \end{verbatim}
848 \subsubsection*{Returns}
850 The routine \verb|glp_get_col_name| returns a pointer to an internal
851 buffer, which contains a symbolic name assigned to \verb|j|-th column.
852 However, if the column has no assigned name, the routine returns
853 \verb|NULL|.
855 \subsection{glp\_get\_row\_type---retrieve row type}
857 \subsubsection*{Synopsis}
859 \begin{verbatim}
860 int glp_get_row_type(glp_prob *lp, int i);
861 \end{verbatim}
863 \subsubsection*{Returns}
865 The routine \verb|glp_get_row_type| returns the type of \verb|i|-th
866 row, i.e. the type of corresponding auxiliary variable, as follows:
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}
876 \subsection{glp\_get\_row\_lb---retrieve row lower bound}
878 \subsubsection*{Synopsis}
880 \begin{verbatim}
881 double glp_get_row_lb(glp_prob *lp, int i);
882 \end{verbatim}
884 \subsubsection*{Returns}
886 The routine \verb|glp_get_row_lb| returns the lower bound of
887 \verb|i|-th row, i.e. the lower bound of corresponding auxiliary
888 variable. However, if the row has no lower bound, the routine returns
889 \verb|-DBL_MAX|.
891 \subsection{glp\_get\_row\_ub---retrieve row upper bound}
893 \subsubsection*{Synopsis}
895 \begin{verbatim}
896 double glp_get_row_ub(glp_prob *lp, int i);
897 \end{verbatim}
899 \subsubsection*{Returns}
901 The routine \verb|glp_get_row_ub| returns the upper bound of
902 \verb|i|-th row, i.e. the upper bound of corresponding auxiliary
903 variable. However, if the row has no upper bound, the routine returns
904 \verb|+DBL_MAX|.
906 \subsection{glp\_get\_col\_type---retrieve column type}
908 \subsubsection*{Synopsis}
910 \begin{verbatim}
911 int glp_get_col_type(glp_prob *lp, int j);
912 \end{verbatim}
914 \subsubsection*{Returns}
916 The routine \verb|glp_get_col_type| returns the type of \verb|j|-th
917 column, i.e. the type of corresponding structural variable, as follows:
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}
927 \subsection{glp\_get\_col\_lb---retrieve column lower bound}
929 \subsubsection*{Synopsis}
931 \begin{verbatim}
932 double glp_get_col_lb(glp_prob *lp, int j);
933 \end{verbatim}
935 \subsubsection*{Returns}
937 The routine \verb|glp_get_col_lb| returns the lower bound of
938 \verb|j|-th column, i.e. the lower bound of corresponding structural
939 variable. However, if the column has no lower bound, the routine returns
940 \verb|-DBL_MAX|.
942 \subsection{glp\_get\_col\_ub---retrieve column upper bound}
944 \subsubsection*{Synopsis}
946 \begin{verbatim}
947 double glp_get_col_ub(glp_prob *lp, int j);
948 \end{verbatim}
950 \subsubsection*{Returns}
952 The routine \verb|glp_get_col_ub| returns the upper bound of
953 \verb|j|-th column, i.e. the upper bound of corresponding structural
954 variable. However, if the column has no upper bound, the routine returns
955 \verb|+DBL_MAX|.
957 \subsection{glp\_get\_obj\_coef---retrieve objective coefficient or\\
958 constant term}
960 \subsubsection*{Synopsis}
962 \begin{verbatim}
963 double glp_get_obj_coef(glp_prob *lp, int j);
964 \end{verbatim}
966 \subsubsection*{Returns}
968 The routine \verb|glp_get_obj_coef| returns the objective coefficient
969 at \verb|j|-th structural variable (column).
971 If the parameter \verb|j| is 0, the routine returns the constant term
972 (``shift'') of the objective function.
974 \subsection{glp\_get\_num\_nz---retrieve number of constraint
975 coefficients}
977 \subsubsection*{Synopsis}
979 \begin{verbatim}
980 int glp_get_num_nz(glp_prob *lp);
981 \end{verbatim}
983 \subsubsection*{Returns}
985 The routine \verb|glp_get_num_nz| returns the number of non-zero
986 elements in the constraint matrix of the specified problem object.
988 \subsection{glp\_get\_mat\_row---retrieve row of the constraint
989 matrix}
991 \subsubsection*{Synopsis}
993 \begin{verbatim}
994 int glp_get_mat_row(glp_prob *lp, int i, int ind[],
995 double val[]);
996 \end{verbatim}
998 \subsubsection*{Description}
1000 The 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
1002 and 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
1005 number of elements in $i$-th row, $n$ is the number of columns.
1007 The parameter \verb|ind| and/or \verb|val| can be specified as
1008 \verb|NULL|, in which case corresponding information is not stored.
1010 \subsubsection*{Returns}
1012 The routine \verb|glp_get_mat_row| returns the length \verb|len|, i.e.
1013 the number of (non-zero) elements in \verb|i|-th row.
1015 \subsection{glp\_get\_mat\_col---retrieve column of the constraint\\
1016 matrix}
1018 \subsubsection*{Synopsis}
1020 \begin{verbatim}
1021 int glp_get_mat_col(glp_prob *lp, int j, int ind[],
1022 double val[]);
1023 \end{verbatim}
1025 \subsubsection*{Description}
1027 The routine \verb|glp_get_mat_col| scans (non-zero) elements of
1028 \verb|j|-th column of the constraint matrix of the specified problem
1029 object 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
1032 number of elements in $j$-th column, $m$ is the number of rows.
1034 The parameter \verb|ind| and/or \verb|val| can be specified as
1035 \verb|NULL|, in which case corresponding information is not stored.
1037 \subsubsection*{Returns}
1039 The routine \verb|glp_get_mat_col| returns the length \verb|len|, i.e.
1040 the number of (non-zero) elements in \verb|j|-th column.
1042 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1044 \newpage
1046 \section{Row and column searching routines}
1048 \subsection{glp\_create\_index---create the name index}
1050 \subsubsection*{Synopsis}
1052 \begin{verbatim}
1053 void glp_create_index(glp_prob *lp);
1054 \end{verbatim}
1056 \subsubsection*{Description}
1058 The routine \verb|glp_create_index| creates the name index for the
1059 specified problem object. The name index is an auxiliary data structure,
1060 which is intended to quickly (i.e. for logarithmic time) find rows and
1061 columns by their names.
1063 This routine can be called at any time. If the name index already
1064 exists, the routine does nothing.
1066 \subsection{glp\_find\_row---find row by its name}
1068 \subsubsection*{Synopsis}
1070 \begin{verbatim}
1071 int glp_find_row(glp_prob *lp, const char *name);
1072 \end{verbatim}
1074 \subsubsection*{Returns}
1076 The routine \verb|glp_find_row| returns the ordinal number of a row,
1077 which is assigned (by the routine \verb|glp_set_row_name|) the specified
1078 symbolic \verb|name|. If no such row exists, the routine returns 0.
1080 \subsection{glp\_find\_col---find column by its name}
1082 \subsubsection*{Synopsis}
1084 \begin{verbatim}
1085 int glp_find_col(glp_prob *lp, const char *name);
1086 \end{verbatim}
1088 \subsubsection*{Returns}
1090 The routine \verb|glp_find_col| returns the ordinal number of a column,
1091 which is assigned (by the routine \verb|glp_set_col_name|) the specified
1092 symbolic \verb|name|. If no such column exists, the routine returns 0.
1094 \subsection{glp\_delete\_index---delete the name index}
1096 \subsubsection*{Synopsis}
1098 \begin{verbatim}
1099 void glp_delete_index(glp_prob *lp);
1100 \end{verbatim}
1102 \subsubsection*{Description}
1104 The routine \verb|glp_delete_index| deletes the name index previously
1105 created by the routine \verb|glp_create_index| and frees the memory
1106 allocated to this auxiliary data structure.
1108 This routine can be called at any time. If the name index does not
1109 exist, the routine does nothing.
1111 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1113 \newpage
1115 \section{Problem scaling routines}
1117 \subsection{Background}
1119 In GLPK the {\it scaling} means a linear transformation applied to the
1120 constraint matrix to improve its numerical properties.\footnote{In many
1121 cases a proper scaling allows making the constraint matrix to be better
1122 conditioned, i.e. decreasing its condition number, that makes
1123 computations numerically more stable.}
1125 The main equality is the following:
1126 $$\widetilde{A}=RAS,\eqno(2.1)$$
1127 where $A=(a_{ij})$ is the original constraint matrix, $R=(r_{ii})>0$ is
1128 a diagonal matrix used to scale rows (constraints), $S=(s_{jj})>0$ is a
1129 diagonal matrix used to scale columns (variables), $\widetilde{A}$ is
1130 the scaled constraint matrix.
1132 From (2.1) it follows that in the {\it scaled} problem instance each
1133 original constraint coefficient $a_{ij}$ is replaced by corresponding
1134 scaled constraint coefficient:
1135 $$\widetilde{a}_{ij}=r_{ii}a_{ij}s_{jj}.\eqno(2.2)$$
1137 Note that the scaling is performed internally and therefore
1138 transparently to the user. This means that on API level the user always
1139 deal with unscaled data.
1141 Scale factors $r_{ii}$ and $s_{jj}$ can be set or changed at any time
1142 either 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
1144 some API routines intended for automatic scaling.
1146 \subsection{glp\_set\_rii---set (change) row scale factor}
1148 \subsubsection*{Synopsis}
1150 \begin{verbatim}
1151 void glp_set_rii(glp_prob *lp, int i, double rii);
1152 \end{verbatim}
1154 \subsubsection*{Description}
1156 The routine \verb|glp_set_rii| sets (changes) the scale factor $r_{ii}$
1157 for $i$-th row of the specified problem object.
1159 \subsection{glp\_set\_sjj---set (change) column scale factor}
1161 \subsubsection*{Synopsis}
1163 \begin{verbatim}
1164 void glp_set_sjj(glp_prob *lp, int j, double sjj);
1165 \end{verbatim}
1167 \subsubsection*{Description}
1169 The routine \verb|glp_set_sjj| sets (changes) the scale factor $s_{jj}$
1170 for $j$-th column of the specified problem object.
1172 \subsection{glp\_get\_rii---retrieve row scale factor}
1174 \subsubsection*{Synopsis}
1176 \begin{verbatim}
1177 double glp_get_rii(glp_prob *lp, int i);
1178 \end{verbatim}
1180 \subsubsection*{Returns}
1182 The routine \verb|glp_get_rii| returns current scale factor $r_{ii}$ for
1183 $i$-th row of the specified problem object.
1185 \subsection{glp\_get\_sjj---retrieve column scale factor}
1187 \subsubsection*{Synopsis}
1189 \begin{verbatim}
1190 double glp_get_sjj(glp_prob *lp, int j);
1191 \end{verbatim}
1193 \subsubsection*{Returns}
1195 The routine \verb|glp_get_sjj| returns current scale factor $s_{jj}$ for
1196 $j$-th column of the specified problem object.
1198 \subsection{glp\_scale\_prob---scale problem data}
1200 \subsubsection*{Synopsis}
1202 \begin{verbatim}
1203 void glp_scale_prob(glp_prob *lp, int flags);
1204 \end{verbatim}
1206 \subsubsection*{Description}
1208 The routine \verb|glp_scale_prob| performs automatic scaling of problem
1209 data for the specified problem object.
1211 The parameter \verb|flags| specifies scaling options used by the
1212 routine. The options can be combined with the bitwise OR operator and
1213 may be the following:
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}
1222 The parameter \verb|flags| may be specified as \verb|GLP_SF_AUTO|, in
1223 which case the routine chooses the scaling options automatically.
1225 \subsection{glp\_unscale\_prob---unscale problem data}
1227 \subsubsection*{Synopsis}
1229 \begin{verbatim}
1230 void glp_unscale_prob(glp_prob *lp);
1231 \end{verbatim}
1233 The routine \verb|glp_unscale_prob| performs unscaling of problem data
1234 for the specified problem object.
1236 ``Unscaling'' means replacing the current scaling matrices $R$ and $S$
1237 by unity matrices that cancels the scaling effect.
1239 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1241 \newpage
1243 \section{LP basis constructing routines}
1245 \subsection{Background}
1247 To start the search the simplex method needs a valid initial basis. In
1248 GLPK the basis is completely defined by a set of {\it statuses} assigned
1249 to {\it all} (auxiliary and structural) variables, where the status may
1250 be one of the following:
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}
1260 The basis is {\it valid}, if the basis matrix, which is a matrix built
1261 of columns of the augmented constraint matrix $(I\:|-A)$ corresponding
1262 to basic variables, is non-singular. This, in particular, means that
1263 the number of basic variables must be the same as the number of rows in
1264 the problem object. (For more details see Section \ref{lpbasis}, page
1265 \pageref{lpbasis}.)
1267 Any initial basis may be constructed (or restored) with the API
1268 routines \verb|glp_set_row_stat| and \verb|glp_set_col_stat| by
1269 assigning appropriate statuses to auxiliary and structural variables.
1270 Another 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
1273 systems and means a heuristic to construct a valid initial basis.} Note
1274 that on normal exit the simplex solver remains the basis valid, so in
1275 case of reoptimization there is no need to construct an initial basis
1276 from scratch.
1278 \subsection{glp\_set\_row\_stat---set (change) row status}
1280 \subsubsection*{Synopsis}
1282 \begin{verbatim}
1283 void glp_set_row_stat(glp_prob *lp, int i, int stat);
1284 \end{verbatim}
1286 \subsubsection*{Description}
1288 The routine \verb|glp_set_row_stat| sets (changes) the current status
1289 of \verb|i|-th row (auxiliary variable) as specified by the parameter
1290 \verb|stat|:
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}
1297 \newpage
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}
1309 \subsection{glp\_set\_col\_stat---set (change) column status}
1311 \subsubsection*{Synopsis}
1313 \begin{verbatim}
1314 void glp_set_col_stat(glp_prob *lp, int j, int stat);
1315 \end{verbatim}
1317 \subsubsection*{Description}
1319 The routine \verb|glp_set_col_stat sets| (changes) the current status
1320 of \verb|j|-th column (structural variable) as specified by the
1321 parameter \verb|stat|:
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}
1335 \subsection{glp\_std\_basis---construct standard initial LP basis}
1337 \subsubsection*{Synopsis}
1339 \begin{verbatim}
1340 void glp_std_basis(glp_prob *lp);
1341 \end{verbatim}
1343 \subsubsection*{Description}
1345 The routine \verb|glp_std_basis| constructs the ``standard'' (trivial)
1346 initial LP basis for the specified problem object.
1348 In the ``standard'' LP basis all auxiliary variables (rows) are basic,
1349 and all structural variables (columns) are non-basic (so the
1350 corresponding basis matrix is unity).
1352 \newpage
1354 \subsection{glp\_adv\_basis---construct advanced initial LP basis}
1356 \subsubsection*{Synopsis}
1358 \begin{verbatim}
1359 void glp_adv_basis(glp_prob *lp, int flags);
1360 \end{verbatim}
1362 \subsubsection*{Description}
1364 The routine \verb|glp_adv_basis| constructs an advanced initial LP
1365 basis for the specified problem object.
1367 The parameter \verb|flags| is reserved for use in the future and must
1368 be specified as zero.
1370 In order to construct the advanced initial LP basis the routine does
1371 the following:
1373 1) includes in the basis all non-fixed auxiliary variables;
1375 2) includes in the basis as many non-fixed structural variables as
1376 possible keeping the triangular form of the basis matrix;
1378 3) includes in the basis appropriate (fixed) auxiliary variables to
1379 complete the basis.
1381 As a result the initial LP basis has as few fixed variables as possible
1382 and the corresponding basis matrix is triangular.
1384 \subsection{glp\_cpx\_basis---construct Bixby's initial LP basis}
1386 \subsubsection*{Synopsis}
1388 \begin{verbatim}
1389 void glp_cpx_basis(glp_prob *lp);
1390 \end{verbatim}
1392 \subsubsection*{Description}
1394 The routine \verb|glp_cpx_basis| constructs an initial basis for the
1395 specified problem object with the algorithm proposed by
1396 R.~Bixby.\footnote{Robert E. Bixby, ``Implementing the Simplex Method:
1397 The Initial Basis.'' ORSA Journal on Computing, Vol. 4, No. 3, 1992,
1398 pp. 267-84.}
1400 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1402 \newpage
1404 \section{Simplex method routines}
1406 The {\it simplex method} is a well known efficient numerical procedure
1407 to solve LP problems.
1409 On each iteration the simplex method transforms the original system of
1410 equaility constraints (1.2) resolving them through different sets of
1411 variables to an equivalent system called {\it the simplex table} (or
1412 sometimes {\it the simplex tableau}), which has the following form:
1413 $$
1414 \begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}
1415 z&=&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 $$
1426 where: $(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
1430 simplex table. (May note that the original LP problem (1.1)---(1.3) also
1431 has the form of a simplex table, where all equalities are resolved
1432 through auxiliary variables.)
1434 From the linear programming theory it is known that if an optimal
1435 solution of the LP problem (1.1)---(1.3) exists, it can always be
1436 written in the form (2.3), where non-basic variables are set on their
1437 bounds while values of the objective function and basic variables are
1438 determined by the corresponding equalities of the simplex table.
1440 A set of values of all basic and non-basic variables determined by the
1441 simplex table is called {\it basic solution}. If all basic variables are
1442 within their bounds, the basic solution is called {\it (primal)
1443 feasible}, otherwise it is called {\it (primal) infeasible}. A feasible
1444 basic solution, which provides a smallest (in case of minimization) or
1445 a largest (in case of maximization) value of the objective function is
1446 called {\it optimal}. Therefore, for solving LP problem the simplex
1447 method tries to find its optimal basic solution.
1449 Primal feasibility of some basic solution may be stated by simple
1450 checking if all basic variables are within their bounds. Basic solution
1451 is optimal if additionally the following optimality conditions are
1452 satisfied for all non-basic variables:
1453 \begin{center}
1454 \begin{tabular}{lcc}
1455 Status 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}
1462 In other words, basic solution is optimal if there is no non-basic
1463 variable, which changing in the feasible direction (i.e. increasing if
1464 it is free or on its lower bound, or decreasing if it is free or on its
1465 upper bound) can improve (i.e. decrease in case of minimization or
1466 increase in case of maximization) the objective function.
1468 If all non-basic variables satisfy to the optimality conditions shown
1469 above (independently on whether basic variables are within their bounds
1470 or not), the basic solution is called {\it dual feasible}, otherwise it
1471 is called {\it dual infeasible}.
1473 It may happen that some LP problem has no primal feasible solution due
1474 to incorrect formulation---this means that its constraints conflict
1475 with each other. It also may happen that some LP problem has unbounded
1476 solution again due to incorrect formulation---this means that some
1477 non-basic variable can improve the objective function, i.e. the
1478 optimality conditions are violated, and at the same time this variable
1479 can infinitely change in the feasible direction meeting no resistance
1480 from basic variables. (May note that in the latter case the LP problem
1481 has no dual feasible solution.)
1483 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1485 \subsection{glp\_simplex---solve LP problem with the primal or dual
1486 simplex method}
1488 \subsubsection*{Synopsis}
1490 \begin{verbatim}
1491 int glp_simplex(glp_prob *lp, const glp_smcp *parm);
1492 \end{verbatim}
1494 \subsubsection*{Description}
1496 The routine \verb|glp_simplex| is a driver to the LP solver based on
1497 the simplex method. This routine retrieves problem data from the
1498 specified problem object, calls the solver to solve the problem
1499 instance, and stores results of computations back into the problem
1500 object.
1502 The simplex solver has a set of control parameters. Values of the
1503 control parameters can be passed in the structure \verb|glp_smcp|,
1504 which the parameter \verb|parm| points to. For detailed description of
1505 this structure see paragraph ``Control parameters'' below.
1506 Before specifying some control parameters the application program
1507 should initialize the structure \verb|glp_smcp| by default values of
1508 all control parameters using the routine \verb|glp_init_smcp| (see the
1509 next subsection). This is needed for backward compatibility, because in
1510 the future there may appear new members in the structure
1511 \verb|glp_smcp|.
1513 The parameter \verb|parm| can be specified as \verb|NULL|, in which
1514 case the solver uses default settings.
1516 \subsubsection*{Returns}
1518 \def\arraystretch{1}
1520 \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
1521 0 & The LP problem instance has been successfully solved. (This code
1522 does {\it not} necessarily mean that the solver has found optimal
1523 solution. It only means that the solution process was successful.) \\
1524 \verb|GLP_EBADB| & Unable to start the search, because the initial basis
1525 specified in the problem object is invalid---the number of basic
1526 (auxiliary and structural) variables is not the same as the number of
1527 rows in the problem object.\\
1528 \verb|GLP_ESING| & Unable to start the search, because the basis matrix
1529 corresponding to the initial basis is singular within the working
1530 precision.\\
1531 \verb|GLP_ECOND| & Unable to start the search, because the basis matrix
1532 corresponding to the initial basis is ill-conditioned, i.e. its
1533 condition number is too large.\\
1534 \verb|GLP_EBOUND| & Unable to start the search, because some
1535 double-bounded (auxiliary or structural) variables have incorrect
1536 bounds.\\
1537 \verb|GLP_EFAIL| & The search was prematurely terminated due to the
1538 solver failure.\\
1539 \verb|GLP_EOBJLL| & The search was prematurely terminated, because the
1540 objective function being maximized has reached its lower limit and
1541 continues decreasing (the dual simplex only).\\
1542 \verb|GLP_EOBJUL| & The search was prematurely terminated, because the
1543 objective function being minimized has reached its upper limit and
1544 continues increasing (the dual simplex only).\\
1545 \verb|GLP_EITLIM| & The search was prematurely terminated, because the
1546 simplex iteration limit has been exceeded.\\
1547 \verb|GLP_ETMLIM| & The search was prematurely terminated, because the
1548 time limit has been exceeded.\\
1549 \verb|GLP_ENOPFS| & The LP problem instance has no primal feasible
1550 solution (only if the LP presolver is used).\\
1551 \verb|GLP_ENODFS| & The LP problem instance has no dual feasible
1552 solution (only if the LP presolver is used).\\
1553 \end{tabular}
1555 \subsubsection*{Built-in LP presolver}
1557 The simplex solver has {\it built-in LP presolver}. It is a subprogram
1558 that transforms the original LP problem specified in the problem object
1559 to an equivalent LP problem, which may be easier for solving with the
1560 simplex method than the original one. This is attained mainly due to
1561 reducing the problem size and improving its numeric properties (for
1562 example, by removing some inactive constraints or by fixing some
1563 non-basic variables). Once the transformed LP problem has been solved,
1564 the presolver transforms its basic solution back to the corresponding
1565 basic solution of the original problem.
1567 Presolving is an optional feature of the routine \verb|glp_simplex|,
1568 and by default it is disabled. In order to enable the LP presolver the
1569 control parameter \verb|presolve| should be set to \verb|GLP_ON| (see
1570 paragraph ``Control parameters'' below). Presolving may be used when
1571 the problem instance is solved for the first time. However, on
1572 performing re-optimization the presolver should be disabled.
1574 The presolving procedure is transparent to the API user in the sense
1575 that all necessary processing is performed internally, and a basic
1576 solution of the original problem recovered by the presolver is the same
1577 as if it were computed directly, i.e. without presolving.
1579 Note that the presolver is able to recover only optimal solutions. If
1580 a computed solution is infeasible or non-optimal, the corresponding
1581 solution of the original problem cannot be recovered and therefore
1582 remains undefined. If you need to know a basic solution even if it is
1583 infeasible or non-optimal, the presolver should be disabled.
1585 \subsubsection*{Terminal output}
1587 Solving large problem instances may take a long time, so the solver
1588 reports some information about the current basic solution, which is sent
1589 to the terminal. This information has the following format:
1591 \begin{verbatim}
1592 nnn: obj = xxx infeas = yyy (ddd)
1593 \end{verbatim}
1595 \noindent
1596 where: `\verb|nnn|' is the iteration number, `\verb|xxx|' is the
1597 current value of the objective function (it is is unscaled and has
1598 correct sign); `\verb|yyy|' is the current sum of primal or dual
1599 infeasibilities (it is scaled and therefore may be used only for visual
1600 estimating), `\verb|ddd|' is the current number of fixed basic
1601 variables.
1603 The symbol preceding the iteration number indicates which phase of the
1604 simplex method is in effect:
1606 {\it Blank} means that the solver is searching for primal feasible
1607 solution using the primal simplex or for dual feasible solution using
1608 the dual simplex;
1610 {\it Asterisk} (\verb|*|) means that the solver is searching for
1611 optimal solution using the primal simplex;
1613 {\it Vertical dash} (\verb/|/) means that the solver is searching for
1614 optimal solution using the dual simplex.
1616 \subsubsection*{Control parameters}
1618 This paragraph describes all control parameters currently used in the
1619 simplex solver. Symbolic names of control parameters are names of
1620 corresponding members in the structure \verb|glp_smcp|.
1622 \medskip
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}
1635 \medskip
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,
1644 switch to the\\
1645 &\verb| |$\:$ primal simplex.\\
1646 \end{tabular}
1648 \medskip
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}
1658 \medskip
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}
1668 \medskip
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
1675 purpose.)\\
1676 \end{tabular}
1678 \medskip
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
1685 purpose.)\\
1686 \end{tabular}
1688 \medskip
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
1695 purpose.)\\
1696 \end{tabular}
1698 \medskip
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
1704 reaches this limit and continues decreasing, the solver terminates the
1705 search. (Used in the dual simplex only.)\\
1706 \end{tabular}
1708 \medskip
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
1714 reaches this limit and continues increasing, the solver terminates the
1715 search. (Used in the dual simplex only.)\\
1716 \end{tabular}
1718 \medskip
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}
1726 \medskip
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}
1734 \medskip
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
1740 frequently the solver sends information about the solution process to
1741 the terminal.\\
1742 \end{tabular}
1744 \medskip
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
1750 solver should delay sending information about the solution process to
1751 the terminal.\\
1752 \end{tabular}
1754 \medskip
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}
1764 \subsubsection*{Example 1}
1766 The following main program reads LP problem instance in fixed MPS
1767 format from file \verb|25fv47.mps|,\footnote{This instance in fixed MPS
1768 format can be found in the Netlib LP collection; see
1769 {\tt ftp://ftp.netlib.org/lp/data/}.} constructs an advanced initial
1770 basis, solves the instance with the primal simplex method (by default),
1771 and writes the solution to file \verb|25fv47.txt|.
1773 \newpage
1775 \begin{footnotesize}
1776 \begin{verbatim}
1777 /* spxsamp1.c */
1779 #include <stdio.h>
1780 #include <stdlib.h>
1781 #include <glpk.h>
1783 int 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 }
1794 /* eof */
1795 \end{verbatim}
1796 \end{footnotesize}
1798 \noindent
1799 Below here is shown the terminal output from this example program.
1801 \begin{footnotesize}
1802 \begin{verbatim}
1803 Reading problem data from `25fv47.mps'...
1804 Problem: 25FV47
1805 Objective: R0000
1806 822 rows, 1571 columns, 11127 non-zeros
1807 6919 records were read
1808 Crashing...
1809 Size 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)
1823 OPTIMAL SOLUTION FOUND
1824 Writing basic solution to `25fv47.txt'...
1825 \end{verbatim}
1826 \end{footnotesize}
1828 \newpage
1830 \subsubsection*{Example 2}
1832 The following main program solves the same LP problem instance as in
1833 Example 1 above, however, it uses the dual simplex method, which starts
1834 from the standard initial basis.
1836 \begin{footnotesize}
1837 \begin{verbatim}
1838 /* spxsamp2.c */
1840 #include <stdio.h>
1841 #include <stdlib.h>
1842 #include <glpk.h>
1844 int 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 }
1857 /* eof */
1858 \end{verbatim}
1859 \end{footnotesize}
1861 \noindent
1862 Below here is shown the terminal output from this example program.
1864 \begin{footnotesize}
1865 \begin{verbatim}
1866 Reading problem data from `25fv47.mps'...
1867 Problem: 25FV47
1868 Objective: R0000
1869 822 rows, 1571 columns, 11127 non-zeros
1870 6919 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)
1889 OPTIMAL SOLUTION FOUND
1890 Writing basic solution to `25fv47.txt'...
1891 \end{verbatim}
1892 \end{footnotesize}
1894 \subsection{glp\_exact---solve LP problem in exact arithmetic}
1896 \subsubsection*{Synopsis}
1898 \begin{verbatim}
1899 int glp_exact(glp_prob *lp, const glp_smcp *parm);
1900 \end{verbatim}
1902 \subsubsection*{Description}
1904 The routine \verb|glp_exact| is a tentative implementation of the
1905 primal two-phase simplex method based on exact (rational) arithmetic.
1906 It is similar to the routine \verb|glp_simplex|, however, for all
1907 internal computations it uses arithmetic of rational numbers, which is
1908 exact in mathematical sense, i.e. free of round-off errors unlike
1909 floating-point arithmetic.
1911 Note that the routine \verb|glp_exact| uses only two control parameters
1912 passed in the structure \verb|glp_smcp|, namely, \verb|it_lim| and
1913 \verb|tm_lim|.
1915 \subsubsection*{Returns}
1917 \def\arraystretch{1}
1919 \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
1920 0 & The LP problem instance has been successfully solved. (This code
1921 does {\it not} necessarily mean that the solver has found optimal
1922 solution. It only means that the solution process was successful.) \\
1923 \verb|GLP_EBADB| & Unable to start the search, because the initial basis
1924 specified in the problem object is invalid---the number of basic
1925 (auxiliary and structural) variables is not the same as the number of
1926 rows in the problem object.\\
1927 \verb|GLP_ESING| & Unable to start the search, because the basis matrix
1928 corresponding to the initial basis is exactly singular.\\
1929 \verb|GLP_EBOUND| & Unable to start the search, because some
1930 double-bounded (auxiliary or structural) variables have incorrect
1931 bounds.\\
1932 \verb|GLP_EFAIL| & The problem instance has no rows/columns.\\
1933 \verb|GLP_EITLIM| & The search was prematurely terminated, because the
1934 simplex iteration limit has been exceeded.\\
1935 \verb|GLP_ETMLIM| & The search was prematurely terminated, because the
1936 time limit has been exceeded.\\
1937 \end{tabular}
1939 \subsubsection*{Comments}
1941 Computations in exact arithmetic are very time consuming, so solving
1942 LP problem with the routine \verb|glp_exact| from the very beginning is
1943 not a good idea. It is much better at first to find an optimal basis
1944 with the routine \verb|glp_simplex| and only then to call
1945 \verb|glp_exact|, in which case only a few simplex iterations need to
1946 be performed in exact arithmetic.
1948 \subsection{glp\_init\_smcp---initialize simplex solver control
1949 parameters}
1951 \subsubsection*{Synopsis}
1953 \begin{verbatim}
1954 int glp_init_smcp(glp_smcp *parm);
1955 \end{verbatim}
1957 \subsubsection*{Description}
1959 The routine \verb|glp_init_smcp| initializes control parameters, which
1960 are used by the simplex solver, with default values.
1962 Default values of the control parameters are stored in a \verb|glp_smcp|
1963 structure, which the parameter \verb|parm| points to.
1965 \subsection{glp\_get\_status---determine generic status of basic
1966 solution}
1968 \subsubsection*{Synopsis}
1970 \begin{verbatim}
1971 int glp_get_status(glp_prob *lp);
1972 \end{verbatim}
1974 \subsubsection*{Returns}
1976 The routine \verb|glp_get_status| reports the generic status of the
1977 current basic solution for the specified problem object as follows:
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}
1988 More detailed information about the status of basic solution can be
1989 retrieved with the routines \verb|glp_get_prim_stat| and
1990 \verb|glp_get_dual_stat|.
1992 \newpage
1994 \subsection{glp\_get\_prim\_stat---retrieve status of primal basic
1995 solution}
1997 \subsubsection*{Synopsis}
1999 \begin{verbatim}
2000 int glp_get_prim_stat(glp_prob *lp);
2001 \end{verbatim}
2003 \subsubsection*{Returns}
2005 The routine \verb|glp_get_prim_stat| reports the status of the primal
2006 basic solution for the specified problem object as follows:
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}
2015 \subsection{glp\_get\_dual\_stat---retrieve status of dual basic
2016 solution}
2018 \subsubsection*{Synopsis}
2020 \begin{verbatim}
2021 int glp_get_dual_stat(glp_prob *lp);
2022 \end{verbatim}
2024 \subsubsection*{Returns}
2026 The routine \verb|glp_get_dual_stat| reports the status of the dual
2027 basic solution for the specified problem object as follows:
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}
2036 \subsection{glp\_get\_obj\_val---retrieve objective value}
2038 \subsubsection*{Synopsis}
2040 \begin{verbatim}
2041 double glp_get_obj_val(glp_prob *lp);
2042 \end{verbatim}
2044 \subsubsection*{Returns}
2046 The routine \verb|glp_get_obj_val| returns current value of the
2047 objective function.
2049 \subsection{glp\_get\_row\_stat---retrieve row status}
2051 \subsubsection*{Synopsis}
2053 \begin{verbatim}
2054 int glp_get_row_stat(glp_prob *lp, int i);
2055 \end{verbatim}
2057 \subsubsection*{Returns}
2059 The routine \verb|glp_get_row_stat| returns current status assigned to
2060 the auxiliary variable associated with \verb|i|-th row as follows:
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}
2070 \subsection{glp\_get\_row\_prim---retrieve row primal value}
2072 \subsubsection*{Synopsis}
2074 \begin{verbatim}
2075 double glp_get_row_prim(glp_prob *lp, int i);
2076 \end{verbatim}
2078 \subsubsection*{Returns}
2080 The routine \verb|glp_get_row_prim| returns primal value of the
2081 auxiliary variable associated with \verb|i|-th row.
2083 \subsection{glp\_get\_row\_dual---retrieve row dual value}
2085 \subsubsection*{Synopsis}
2087 \begin{verbatim}
2088 double glp_get_row_dual(glp_prob *lp, int i);
2089 \end{verbatim}
2091 \subsubsection*{Returns}
2093 The routine \verb|glp_get_row_dual| returns dual value (i.e. reduced
2094 cost) of the auxiliary variable associated with \verb|i|-th row.
2096 \newpage
2098 \subsection{glp\_get\_col\_stat---retrieve column status}
2100 \subsubsection*{Synopsis}
2102 \begin{verbatim}
2103 int glp_get_col_stat(glp_prob *lp, int j);
2104 \end{verbatim}
2106 \subsubsection*{Returns}
2108 The routine \verb|glp_get_col_stat| returns current status assigned to
2109 the structural variable associated with \verb|j|-th column as follows:
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}
2119 \subsection{glp\_get\_col\_prim---retrieve column primal value}
2121 \subsubsection*{Synopsis}
2123 \begin{verbatim}
2124 double glp_get_col_prim(glp_prob *lp, int j);
2125 \end{verbatim}
2127 \subsubsection*{Returns}
2129 The routine \verb|glp_get_col_prim| returns primal value of the
2130 structural variable associated with \verb|j|-th column.
2132 \subsection{glp\_get\_col\_dual---retrieve column dual value}
2134 \subsubsection*{Synopsis}
2136 \begin{verbatim}
2137 double glp_get_col_dual(glp_prob *lp, int j);
2138 \end{verbatim}
2140 \subsubsection*{Returns}
2142 The routine \verb|glp_get_col_dual| returns dual value (i.e. reduced
2143 cost) of the structural variable associated with \verb|j|-th column.
2145 \newpage
2147 \subsection{glp\_get\_unbnd\_ray---determine variable causing\\
2148 unboundedness}
2150 \subsubsection*{Synopsis}
2152 \begin{verbatim}
2153 int glp_get_unbnd_ray(glp_prob *lp);
2154 \end{verbatim}
2156 \subsubsection*{Returns}
2158 The routine \verb|glp_get_unbnd_ray| returns the number $k$ of
2159 a variable, which causes primal or dual unboundedness.
2160 If $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
2162 the number of rows, $n$ is the number of columns in the problem object.
2163 If such variable is not defined, the routine returns 0.
2165 \subsubsection*{Comments}
2167 If it is not exactly known which version of the simplex solver
2168 detected unboundedness, i.e. whether the unboundedness is primal or
2169 dual, it is sufficient to check the status of the variable
2170 with the routine \verb|glp_get_row_stat| or \verb|glp_get_col_stat|.
2171 If the variable is non-basic, the unboundedness is primal, otherwise,
2172 if the variable is basic, the unboundedness is dual (the latter case
2173 means that the problem has no primal feasible dolution).
2175 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2177 \newpage
2179 \section{Interior-point method routines}
2181 {\it Interior-point methods} (also known as {\it barrier methods}) are
2182 more modern and powerful numerical methods for large-scale linear
2183 programming. Such methods are especially efficient for very sparse LP
2184 problems and allow solving such problems much faster than the simplex
2185 method.
2187 In brief, the GLPK interior-point solver works as follows.
2189 At first, the solver transforms the original LP to a {\it working} LP
2190 in the standard format:
2192 \medskip
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}
2200 a_{11}x_{m+1}&+&a_{12}x_{m+2}&+ \dots +&a_{1n}x_{m+n}&=&b_1 \\
2201 a_{21}x_{m+1}&+&a_{22}x_{m+2}&+ \dots +&a_{2n}x_{m+n}&=&b_2 \\
2202 \multicolumn{7}{c}
2203 {.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .} \\
2204 a_{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)$$
2209 where: $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
2211 of the objective function;\linebreak $a_{11}$, \dots, $a_{mn}$ are
2212 constraint coefficients; $b_1$, \dots, $b_m$ are right-hand sides.
2214 Using vector and matrix notations the working LP (2.4)---(2.6) can be
2215 written 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)$$
2219 where: $x=(x_j)$ is $n$-vector of variables, $c=(c_j)$ is $n$-vector of
2220 objective coefficients, $A=(a_{ij})$ is $m\times n$-matrix of
2221 constraint coefficients, and $b=(b_i)$ is $m$-vector of right-hand
2222 sides.
2224 Karush--Kuhn--Tucker optimality conditions for LP (2.7)---(2.9) are the
2225 following:
2227 \newpage
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)$$
2233 where: $\pi$ is $m$-vector of Lagrange multipliers (dual variables) for
2234 equality constraints (2.8), $\lambda$ is $n$-vector of Lagrange
2235 multipliers (dual variables) for non-negativity constraints (2.9),
2236 (2.10) is the primal feasibility condition, (2.11) is the dual
2237 feasibility condition, (2.12) is the primal-dual complementarity
2238 condition, and (2.13) is the non-negativity conditions.
2240 The main idea of the primal-dual interior-point method is based on
2241 finding a point in the primal-dual space (i.e. in the space of all
2242 primal and dual variables $x$, $\pi$, and $\lambda$), which satisfies
2243 to all optimality conditions (2.10)---(2.13). Obviously, $x$-component
2244 of such point then provides an optimal solution to the working LP
2245 (2.7)---(2.9).
2247 To find the optimal point $(x^*,\pi^*,\lambda^*)$ the interior-point
2248 method attempts to solve the system of equations (2.10)---(2.12), which
2249 is 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$.
2251 Due to condition (2.12) this system of equations is non-linear, so it
2252 can be solved with a version of {\it Newton's method} provided with
2253 additional rules to keep the current point within the positive orthant
2254 as required by the non-negativity conditions (2.13).
2256 Finally, once the optimal point $(x^*,\pi^*,\lambda^*)$ has been found,
2257 the solver performs inverse transformations to recover corresponding
2258 solution to the original LP passed to the solver from the application
2259 program.
2261 \subsection{glp\_interior---solve LP problem with the interior-point
2262 method}
2264 \subsubsection*{Synopsis}
2266 \begin{verbatim}
2267 int glp_interior(glp_prob *P, const glp_iptcp *parm);
2268 \end{verbatim}
2270 \subsubsection*{Description}
2272 The routine \verb|glp_interior| is a driver to the LP solver based on
2273 the primal-dual interior-point method. This routine retrieves problem
2274 data from the specified problem object, calls the solver to solve the
2275 problem instance, and stores results of computations back into the
2276 problem object.
2278 The interior-point solver has a set of control parameters. Values of
2279 the control parameters can be passed in the structure \verb|glp_iptcp|,
2280 which the parameter \verb|parm| points to. For detailed description of
2281 this structure see paragraph ``Control parameters'' below. Before
2282 specifying some control parameters the application program should
2283 initialize the structure \verb|glp_iptcp| by default values of all
2284 control parameters using the routine \verb|glp_init_iptcp| (see the
2285 next subsection). This is needed for backward compatibility, because in
2286 the future there may appear new members in the structure
2287 \verb|glp_iptcp|.
2289 The parameter \verb|parm| can be specified as \verb|NULL|, in which
2290 case the solver uses default settings.
2292 \subsubsection*{Returns}
2294 \def\arraystretch{1}
2296 \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
2297 0 & The LP problem instance has been successfully solved. (This code
2298 does {\it not} necessarily mean that the solver has found optimal
2299 solution. 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
2304 system.\\
2305 \end{tabular}
2307 \subsubsection*{Comments}
2309 The routine \verb|glp_interior| implements an easy version of
2310 the primal-dual interior-point method based on Mehrotra's
2311 technique.\footnote{S. Mehrotra. On the implementation of a primal-dual
2312 interior point method. SIAM J. on Optim., 2(4), pp. 575-601, 1992.}
2314 Note that currently the GLPK interior-point solver does not include
2315 many important features, in particular:
2317 $\bullet$ it is not able to process dense columns. Thus, if the
2318 constraint matrix of the LP problem has dense columns, the solving
2319 process may be inefficient;
2321 $\bullet$ it has no features against numerical instability. For some
2322 LP problems premature termination may happen if the matrix $ADA^T$
2323 becomes singular or ill-conditioned;
2325 $\bullet$ it is not able to identify the optimal basis, which
2326 corresponds to the interior-point solution found.
2328 \newpage
2330 \subsubsection*{Terminal output}
2332 Solving large LP problems may take a long time, so the solver reports
2333 some information about every interior-point iteration,\footnote{Unlike
2334 the simplex method the interior point method usually needs 30---50
2335 iterations (independently on the problem size) in order to find an
2336 optimal solution.} which is sent to the terminal. This information has
2337 the following format:
2339 \begin{verbatim}
2340 nnn: obj = fff; rpi = ppp; rdi = ddd; gap = ggg
2341 \end{verbatim}
2343 \noindent where: \verb|nnn| is iteration number, \verb|fff| is the
2344 current value of the objective function (in the case of maximization it
2345 has wrong sign), \verb|ppp| is the current relative primal
2346 infeasibility (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)$$
2352 and $[x^{(k)},\pi^{(k)},\lambda^{(k)}]$ is the current point on $k$-th
2353 iteration, $k=0,1,2,\dots$\ . Note that all solution components are
2354 internally scaled, so information sent to the terminal is suitable only
2355 for visual inspection.
2357 \subsubsection*{Control parameters}
2359 This paragraph describes all control parameters currently used in the
2360 interior-point solver. Symbolic names of control parameters are names of
2361 corresponding members in the structure \verb|glp_iptcp|.
2363 \medskip
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}
2376 \medskip
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}
2388 \subsubsection*{Example}
2390 The following main program reads LP problem instance in fixed MPS
2391 format from file \verb|25fv47.mps|,\footnote{This instance in fixed MPS
2392 format can be found in the Netlib LP collection; see
2393 {\tt ftp://ftp.netlib.org/lp/data/}.} solves it with the interior-point
2394 solver, and writes the solution to file \verb|25fv47.txt|.
2396 \begin{footnotesize}
2397 \begin{verbatim}
2398 /* iptsamp.c */
2400 #include <stdio.h>
2401 #include <stdlib.h>
2402 #include <glpk.h>
2404 int 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 }
2414 /* eof */
2415 \end{verbatim}
2416 \end{footnotesize}
2418 \noindent
2419 Below here is shown the terminal output from this example program.
2421 \begin{footnotesize}
2422 \begin{verbatim}
2423 Reading problem data from `25fv47.mps'...
2424 Problem: 25FV47
2425 Objective: R0000
2426 822 rows, 1571 columns, 11127 non-zeros
2427 6919 records were read
2428 Original LP has 822 row(s), 1571 column(s), and 11127 non-zero(s)
2429 Working LP has 821 row(s), 1876 column(s), and 10705 non-zero(s)
2430 Matrix A has 10705 non-zeros
2431 Matrix S = A*A' has 11895 non-zeros (upper triangle)
2432 Minimal degree ordering...
2433 Computing Cholesky factorization S = L'*L...
2434 Matrix L has 35411 non-zeros
2435 Guessing initial point...
2436 Optimization 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
2466 OPTIMAL SOLUTION FOUND
2467 Writing interior-point solution to `25fv47.txt'...
2468 \end{verbatim}
2469 \end{footnotesize}
2471 \subsection{glp\_init\_iptcp---initialize interior-point solver control
2472 parameters}
2474 \subsubsection*{Synopsis}
2476 \begin{verbatim}
2477 int glp_init_iptcp(glp_iptcp *parm);
2478 \end{verbatim}
2480 \subsubsection*{Description}
2482 The routine \verb|glp_init_iptcp| initializes control parameters, which
2483 are used by the interior-point solver, with default values.
2485 Default values of the control parameters are stored in the structure
2486 \verb|glp_iptcp|, which the parameter \verb|parm| points to.
2488 \subsection{glp\_ipt\_status---determine solution status}
2490 \subsubsection*{Synopsis}
2492 \begin{verbatim}
2493 int glp_ipt_status(glp_prob *lp);
2494 \end{verbatim}
2496 \subsubsection*{Returns}
2498 The routine \verb|glp_ipt_status| reports the status of a solution
2499 found by the interior-point solver as follows:
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}
2508 \subsection{glp\_ipt\_obj\_val---retrieve objective value}
2510 \subsubsection*{Synopsis}
2512 \begin{verbatim}
2513 double glp_ipt_obj_val(glp_prob *lp);
2514 \end{verbatim}
2516 \subsubsection*{Returns}
2518 The routine \verb|glp_ipt_obj_val| returns value of the objective
2519 function for interior-point solution.
2521 \subsection{glp\_ipt\_row\_prim---retrieve row primal value}
2523 \subsubsection*{Synopsis}
2525 \begin{verbatim}
2526 double glp_ipt_row_prim(glp_prob *lp, int i);
2527 \end{verbatim}
2529 \subsubsection*{Returns}
2531 The routine \verb|glp_ipt_row_prim| returns primal value of the
2532 auxiliary variable associated with \verb|i|-th row.
2534 \newpage
2536 \subsection{glp\_ipt\_row\_dual---retrieve row dual value}
2538 \subsubsection*{Synopsis}
2540 \begin{verbatim}
2541 double glp_ipt_row_dual(glp_prob *lp, int i);
2542 \end{verbatim}
2544 \subsubsection*{Returns}
2546 The routine \verb|glp_ipt_row_dual| returns dual value (i.e. reduced
2547 cost) of the auxiliary variable associated with \verb|i|-th row.
2549 \subsection{glp\_ipt\_col\_prim---retrieve column primal value}
2551 \subsubsection*{Synopsis}
2553 \begin{verbatim}
2554 double glp_ipt_col_prim(glp_prob *lp, int j);
2555 \end{verbatim}
2557 \subsubsection*{Returns}
2559 The routine \verb|glp_ipt_col_prim| returns primal value of the
2560 structural variable associated with \verb|j|-th column.
2562 \subsection{glp\_ipt\_col\_dual---retrieve column dual value}
2564 \subsubsection*{Synopsis}
2566 \begin{verbatim}
2567 double glp_ipt_col_dual(glp_prob *lp, int j);
2568 \end{verbatim}
2570 \subsubsection*{Returns}
2572 The routine \verb|glp_ipt_col_dual| returns dual value (i.e. reduced
2573 cost) of the structural variable associated with \verb|j|-th column.
2575 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2577 \newpage
2579 \section{Mixed integer programming routines}
2581 \subsection{glp\_set\_col\_kind---set (change) column kind}
2583 \subsubsection*{Synopsis}
2585 \begin{verbatim}
2586 void glp_set_col_kind(glp_prob *mip, int j, int kind);
2587 \end{verbatim}
2589 \subsubsection*{Description}
2591 The 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|:
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}
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.
2605 Setting a column to \verb|GLP_BV| has the same effect as if it were
2606 set to \verb|GLP_IV|, its lower bound were set 0, and its upper bound
2607 were set to 1.
2609 \subsection{glp\_get\_col\_kind---retrieve column kind}
2611 \subsubsection*{Synopsis}
2613 \begin{verbatim}
2614 int glp_get_col_kind(glp_prob *mip, int j);
2615 \end{verbatim}
2617 \subsubsection*{Returns}
2619 The routine \verb|glp_get_col_kind| returns the kind of \verb|j|-th
2620 column (structural variable) as follows:
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}
2628 \subsection{glp\_get\_num\_int---retrieve number of integer columns}
2630 \subsubsection*{Synopsis}
2632 \begin{verbatim}
2633 int glp_get_num_int(glp_prob *mip);
2634 \end{verbatim}
2636 \subsubsection*{Returns}
2638 The routine \verb|glp_get_num_int| returns the number of columns
2639 (structural variables), which are marked as integer. Note that this
2640 number {\it does} include binary columns.
2642 \subsection{glp\_get\_num\_bin---retrieve number of binary columns}
2644 \subsubsection*{Synopsis}
2646 \begin{verbatim}
2647 int glp_get_num_bin(glp_prob *mip);
2648 \end{verbatim}
2650 \subsubsection*{Returns}
2652 The routine \verb|glp_get_num_bin| returns the number of columns
2653 (structural variables), which are marked as integer and whose lower
2654 bound is zero and upper bound is one.
2656 \subsection{glp\_intopt---solve MIP problem with the branch-and-cut
2657 method}
2659 \subsubsection*{Synopsis}
2661 \begin{verbatim}
2662 int glp_intopt(glp_prob *mip, const glp_iocp *parm);
2663 \end{verbatim}
2665 \subsubsection*{Description}
2667 The routine \verb|glp_intopt| is a driver to the MIP solver based on
2668 the branch-and-cut method, which is a hybrid of branch-and-bound and
2669 cutting plane methods.
2671 If the presolver is disabled (see paragraph ``Control parameters''
2672 below), on entry to the routine \verb|glp_intopt| the problem object,
2673 which the parameter \verb|mip| points to, should contain optimal
2674 solution to LP relaxation (it can be obtained, for example, with the
2675 routine \verb|glp_simplex|). Otherwise, if the presolver is enabled, it
2676 is not necessary.
2678 The MIP solver has a set of control parameters. Values of the control
2679 parameters can be passed in the structure \verb|glp_iocp|, which the
2680 parameter \verb|parm| points to. For detailed description of this
2681 structure see paragraph ``Control parameters'' below. Before specifying
2682 some control parameters the application program should initialize the
2683 structure \verb|glp_iocp| by default values of all control parameters
2684 using the routine \verb|glp_init_iocp| (see the next subsection). This
2685 is needed for backward compatibility, because in the future there may
2686 appear new members in the structure \verb|glp_iocp|.
2688 The parameter \verb|parm| can be specified as \verb|NULL|, in which case
2689 the solver uses default settings.
2691 Note that the GLPK branch-and-cut solver is not perfect, so it is unable
2692 to solve hard or very large scale MIP instances for a reasonable time.
2694 \subsubsection*{Returns}
2696 \def\arraystretch{1}
2698 \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
2699 0 & The MIP problem instance has been successfully solved. (This code
2700 does {\it not} necessarily mean that the solver has found optimal
2701 solution. It only means that the solution process was successful.) \\
2702 \verb|GLP_EBOUND| & Unable to start the search, because some
2703 double-bounded variables have incorrect bounds or some integer variables
2704 have non-integer (fractional) bounds.\\
2705 \verb|GLP_EROOT| & Unable to start the search, because optimal basis for
2706 initial LP relaxation is not provided. (This code may appear only if the
2707 presolver is disabled.)\\
2708 \verb|GLP_ENOPFS| & Unable to start the search, because LP relaxation
2709 of the MIP problem instance has no primal feasible solution. (This code
2710 may appear only if the presolver is enabled.)\\
2711 \verb|GLP_ENODFS| & Unable to start the search, because LP relaxation
2712 of the MIP problem instance has no dual feasible solution. In other
2713 word, this code means that if the LP relaxation has at least one primal
2714 feasible solution, its optimal solution is unbounded, so if the MIP
2715 problem has at least one integer feasible solution, its (integer)
2716 optimal solution is also unbounded. (This code may appear only if the
2717 presolver is enabled.)\\
2718 \verb|GLP_EFAIL| & The search was prematurely terminated due to the
2719 solver failure.\\
2720 \verb|GLP_EMIPGAP| & The search was prematurely terminated, because the
2721 relative mip gap tolerance has been reached.\\
2722 \verb|GLP_ETMLIM| & The search was prematurely terminated, because the
2723 time 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}
2728 \subsubsection*{Built-in MIP presolver}
2730 The branch-and-cut solver has {\it built-in MIP presolver}. It is
2731 a subprogram that transforms the original MIP problem specified in the
2732 problem object to an equivalent MIP problem, which may be easier for
2733 solving with the branch-and-cut method than the original one. For
2734 example, the presolver can remove redundant constraints and variables,
2735 whose optimal values are known, perform bound and coefficient reduction,
2736 etc. Once the transformed MIP problem has been solved, the presolver
2737 transforms its solution back to corresponding solution of the original
2738 problem.
2740 Presolving is an optional feature of the routine \verb|glp_intopt|, and
2741 by default it is disabled. In order to enable the MIP presolver, the
2742 control parameter \verb|presolve| should be set to \verb|GLP_ON| (see
2743 paragraph ``Control parameters'' below).
2745 \subsubsection*{Advanced solver interface}
2747 The routine \verb|glp_intopt| allows the user to control the
2748 branch-and-cut search by passing to the solver a user-defined callback
2749 routine. For more details see Chapter ``Branch-and-Cut API Routines''.
2751 \subsubsection*{Terminal output}
2753 Solving a MIP problem may take a long time, so the solver reports some
2754 information about best known solutions, which is sent to the terminal.
2755 This information has the following format:
2757 \begin{verbatim}
2758 +nnn: mip = xxx <rho> yyy gap (ppp; qqq)
2759 \end{verbatim}
2761 \noindent
2762 where: `\verb|nnn|' is the simplex iteration number; `\verb|xxx|' is a
2763 value of the objective function for the best known integer feasible
2764 solution (if no integer feasible solution has been found yet,
2765 `\verb|xxx|' is the text `\verb|not found yet|'); `\verb|rho|' is the
2766 string `\verb|>=|' (in case of minimization) or `\verb|<=|' (in case of
2767 maximization); `\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|'
2769 to `\verb|yyy|'); `\verb|gap|' is the relative mip gap, in percents,
2770 computed 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
2772 number of subproblems in the active list, `\verb|qqq|' is the number of
2773 subproblems which have been already fathomed and therefore removed from
2774 the branch-and-bound search tree.
2776 \subsubsection{Control parameters}
2778 This paragraph describes all control parameters currently used in the
2779 MIP solver. Symbolic names of control parameters are names of
2780 corresponding members in the structure \verb|glp_iocp|.
2782 \medskip
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}
2795 \medskip
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}
2808 \medskip
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}
2820 \medskip
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}
2831 \medskip
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}
2841 \medskip
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}
2850 \medskip
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}
2859 \medskip
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}
2868 \medskip
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}
2877 \medskip
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
2882 relaxation is integer feasible. (Do not change this parameter without
2883 detailed understanding its purpose.)\\
2884 \end{tabular}
2886 \medskip
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
2891 solution to the current LP relaxation is not better than in the best
2892 known integer feasible solution. (Do not change this parameter without
2893 detailed understanding its purpose.)\\
2894 \end{tabular}
2896 \medskip
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
2901 known best integer feasible solution falls below this tolerance, the
2902 solver terminates the search. This allows obtainig suboptimal integer
2903 feasible solutions if solving the problem to optimality takes too long
2904 time.\\
2905 \end{tabular}
2907 \medskip
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}
2914 \medskip
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
2919 frequently the solver sends information about the solution process to
2920 the terminal.\\
2921 \end{tabular}
2923 \medskip
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
2928 solver should delay sending information about solution of the current
2929 LP relaxation with the simplex method to the terminal.\\
2930 \end{tabular}
2932 \medskip
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
2939 the advanced solver interface is not used. For more details see Chapter
2940 ``Branch-and-Cut API Routines''.\\
2941 \end{tabular}
2943 \medskip
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}
2950 \medskip
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
2955 branch-and-bound tree to store application-specific data. On creating
2956 a node these bytes are initialized by binary zeros.\\
2957 \end{tabular}
2959 \medskip
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}
2968 \medskip
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}
2977 \subsection{glp\_init\_iocp---initialize integer optimizer control
2978 parameters}
2980 \subsubsection*{Synopsis}
2982 \begin{verbatim}
2983 void glp_init_iocp(glp_iocp *parm);
2984 \end{verbatim}
2986 \subsubsection*{Description}
2988 The routine \verb|glp_init_iocp| initializes control parameters, which
2989 are used by the branch-and-cut solver, with default values.
2991 Default values of the control parameters are stored in a \verb|glp_iocp|
2992 structure, which the parameter \verb|parm| points to.
2994 \subsection{glp\_mip\_status---determine status of MIP solution}
2996 \subsubsection*{Synopsis}
2998 \begin{verbatim}
2999 int glp_mip_status(glp_prob *mip);
3000 \end{verbatim}
3002 \subsubsection*{Returns}
3004 The routine \verb|glp_mip_status| reports the status of a MIP solution
3005 found by the MIP solver as follows:
3007 \smallskip
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}
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}
3022 \subsection{glp\_mip\_obj\_val---retrieve objective value}
3024 \subsubsection*{Synopsis}
3026 \begin{verbatim}
3027 double glp_mip_obj_val(glp_prob *mip);
3028 \end{verbatim}
3030 \subsubsection*{Returns}
3032 The routine \verb|glp_mip_obj_val| returns value of the objective
3033 function for MIP solution.
3035 \subsection{glp\_mip\_row\_val---retrieve row value}
3037 \subsubsection*{Synopsis}
3039 \begin{verbatim}
3040 double glp_mip_row_val(glp_prob *mip, int i);
3041 \end{verbatim}
3043 \subsubsection*{Returns}
3045 The routine \verb|glp_mip_row_val| returns value of the auxiliary
3046 variable associated with \verb|i|-th row for MIP solution.
3048 \subsection{glp\_mip\_col\_val---retrieve column value}
3050 \subsubsection*{Synopsis}
3052 \begin{verbatim}
3053 double glp_mip_col_val(glp_prob *mip, int j);
3054 \end{verbatim}
3056 \subsubsection*{Returns}
3058 The routine \verb|glp_mip_col_val| returns value of the structural
3059 variable associated with \verb|j|-th column for MIP solution.
3061 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3063 \newpage
3065 \section{Additional routines}
3067 \subsection{lpx\_check\_kkt---check Karush-Kuhn-Tucker optimality
3068 conditions}
3070 \subsubsection*{Synopsis}
3072 \begin{verbatim}
3073 void lpx_check_kkt(glp_prob *lp, int scaled, LPXKKT *kkt);
3074 \end{verbatim}
3076 \subsubsection*{Description}
3078 The routine \verb|lpx_check_kkt| checks Karush-Kuhn-Tucker optimality
3079 conditions for basic solution. It is assumed that both primal and dual
3080 components of basic solution are valid.
3082 If the parameter \verb|scaled| is zero, the optimality conditions are
3083 checked for the original, unscaled LP problem. Otherwise, if the
3084 parameter \verb|scaled| is non-zero, the routine checks the conditions
3085 for an internally scaled LP problem.
3087 The parameter \verb|kkt| is a pointer to the structure \verb|LPXKKT|,
3088 to which the routine stores results of the check. Members of this
3089 structure are shown in the table below.
3091 \begin{table}[h]
3092 \begin{center}
3093 \begin{tabular}{@{}c|l|l@{}}
3094 Condition & 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}
3143 The routine performs all computations using only components of the
3144 given LP problem and the current basic solution.
3146 \subsubsection*{Background}
3148 The first condition checked by the routine is:
3149 $$x_R - A x_S = 0, \eqno{\rm (KKT.PE)}$$
3150 where $x_R$ is the subvector of auxiliary variables (rows), $x_S$ is the
3151 subvector of structural variables (columns), $A$ is the constraint
3152 matrix. This condition expresses the requirement that all primal
3153 variables must satisfy to the system of equality constraints of the
3154 original LP problem. In case of exact arithmetic this condition would be
3155 satisfied for any basic solution; however, in case of inexact
3156 (floating-point) arithmetic, this condition shows how accurate the
3157 primal basic solution is, that depends on accuracy of a representation
3158 of the basis matrix used by the simplex method routines.
3160 The 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)}$$
3163 where $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,
3165 lower and upper bounds of the variable $x_k$ (including cases of
3166 infinite bounds). This condition expresses the requirement that all
3167 primal variables must satisfy to bound constraints of the original LP
3168 problem. Since in case of basic solution all non-basic variables are
3169 placed on their bounds, actually the condition (KKT.PB) needs to be
3170 checked for basic variables only. If the primal basic solution has
3171 sufficient accuracy, this condition shows primal feasibility of the
3172 solution.
3174 The third condition checked by the routine is:
3175 $${\rm grad}\;Z = c = (\tilde{A})^T \pi + d,$$
3176 where $Z$ is the objective function, $c$ is the vector of objective
3177 coefficients, $(\tilde{A})^T$ is a matrix transposed to the expanded
3178 constraint matrix $\tilde{A} = (I|-A)$, $\pi$ is a vector of Lagrange
3179 multipliers that correspond to equality constraints of the original LP
3180 problem, $d$ is a vector of Lagrange multipliers that correspond to
3181 bound constraints for all (auxiliary and structural) variables of the
3182 original LP problem. Geometrically the third condition expresses the
3183 requirement that the gradient of the objective function must belong to
3184 the orthogonal complement of a linear subspace defined by the equality
3185 and active bound constraints, i.e. that the gradient must be a linear
3186 combination of normals to the constraint planes, where Lagrange
3187 multipliers $\pi$ and $d$ are coefficients of that linear combination.
3189 To 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 $$
3195 or, 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 $$
3202 Then substituting the vector $\pi$ from the first equation into the
3203 second one we have:
3204 $$A^T (d_R - c_R) + (d_S - c_S) = 0, \eqno{\rm (KKT.DE)}$$
3205 where $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,
3208 respectively, auxiliary and structural variables, $A^T$ is a matrix
3209 transposed to the constraint matrix of the original LP problem. In case
3210 of exact arithmetic this condition would be satisfied for any basic
3211 solution; however, in case of inexact (floating-point) arithmetic, this
3212 condition shows how accurate the dual basic solution is, that depends on
3213 accuracy of a representation of the basis matrix used by the simplex
3214 method routines.
3216 The last, fourth condition checked by the routine is (KKT.DB):
3218 \medskip
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}
3231 \medskip
3233 \noindent
3234 for all $k=1,\dots,m+n$, where $d_k$ is a reduced cost (Lagrange
3235 multiplier) of auxiliary ($1\leq k\leq m$) or structural
3236 ($m+1\leq k\leq m+n$) variable $x_k$. Geometrically this condition
3237 expresses the requirement that constraints of the original problem must
3238 "hold" the point preventing its movement along the anti-gradient (in
3239 case of minimization) or the gradient (in case of maximization) of the
3240 objective function. Since in case of basic solution reduced costs of
3241 all basic variables are placed on their (zero) bounds, actually the
3242 condition (KKT.DB) needs to be checked for non-basic variables only.
3243 If the dual basic solution has sufficient accuracy, this condition shows
3244 dual feasibility of the solution.
3246 Should note that the complete set of Karush-Kuhn-Tucker optimality
3247 conditions also includes the fifth, so called complementary slackness
3248 condition, which expresses the requirement that at least either a primal
3249 variable $x_k$ or its dual counterpart $d_k$ must be on its bound for
3250 all $k=1,\dots,m+n$. However, being always satisfied by definition for
3251 any basic solution that condition is not checked by the routine.
3253 To check the first condition (KKT.PE) the routine computes a vector of
3254 residuals:
3255 $$g = x_R - A x_S,$$
3256 determines component of this vector that correspond to largest absolute
3257 and relative errors:
3259 \medskip
3261 \hspace{30mm}
3262 \verb|pe_ae_max| $\displaystyle{= \max_{1\leq i\leq m}|g_i|}$,
3264 \medskip
3266 \hspace{30mm}
3267 \verb|pe_re_max| $\displaystyle{= \max_{1\leq i\leq m}
3268 \frac{|g_i|}{1+|(x_R)_i|}}$,
3270 \medskip
3272 \noindent
3273 and stores these quantities and corresponding row indices to the
3274 structure \verb|LPXKKT|.
3276 To check the second condition (KKT.PB) the routine computes a vector
3277 of residuals:
3278 $$
3279 h_k = \left\{
3280 \begin{array}{ll}
3281 0, & {\rm if}\ l_k \leq x_k \leq u_k \\
3282 x_k - l_k, & {\rm if}\ x_k < l_k \\
3283 x_k - u_k, & {\rm if}\ x_k > u_k \\
3284 \end{array}
3285 \right.
3286 $$
3287 for all $k=1,\dots,m+n$, determines components of this vector that
3288 correspond to largest absolute and relative errors:
3290 \medskip
3292 \hspace{30mm}
3293 \verb|pb_ae_max| $\displaystyle{= \max_{1\leq k \leq m+n}|h_k|}$,
3295 \medskip
3297 \hspace{30mm}
3298 \verb|pb_re_max| $\displaystyle{= \max_{1\leq k \leq m+n}
3299 \frac{|h_k|}{1+|x_k|}}$,
3301 \medskip
3303 \noindent
3304 and stores these quantities and corresponding variable indices to the
3305 structure \verb|LPXKKT|.
3307 To check the third condition (KKT.DE) the routine computes a vector of
3308 residuals:
3309 $$u = A^T (d_R - c_R) + (d_S - c_S),$$
3310 determines components of this vector that correspond to largest
3311 absolute and relative errors:
3313 \medskip
3315 \hspace{30mm}
3316 \verb|de_ae_max| $\displaystyle{= \max_{1\leq j\leq n}|u_j|}$,
3318 \medskip
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|}}$,
3324 \medskip
3326 \noindent
3327 and stores these quantities and corresponding column indices to the
3328 structure \verb|LPXKKT|.
3330 To check the fourth condition (KKT.DB) the routine computes a vector
3331 of residuals:
3333 $$
3334 v_k = \left\{
3335 \begin{array}{ll}
3336 0, & {\rm if}\ d_k\ {\rm has\ correct\ sign} \\
3337 d_k, & {\rm if}\ d_k\ {\rm has\ wrong\ sign} \\
3338 \end{array}
3339 \right.
3340 $$
3341 for all $k=1,\dots,m+n$, determines components of this vector that
3342 correspond to largest absolute and relative errors:
3344 \medskip
3346 \hspace{30mm}
3347 \verb|db_ae_max| $\displaystyle{= \max_{1\leq k\leq m+n}|v_k|}$,
3349 \medskip
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|}}$,
3355 \medskip
3357 \noindent
3358 and stores these quantities and corresponding variable indices to the
3359 structure \verb|LPXKKT|.
3361 Using the relative errors for all the four conditions listed above the
3362 routine
3363 \verb|lpx_check_kkt| also estimates a "quality" of the basic solution
3364 from the standpoint of these conditions and stores corresponding
3365 quality indicators to the structure \verb|LPXKKT|:
3367 \verb|pe_quality|---quality of primal solution;
3369 \verb|pb_quality|---quality of primal feasibility;
3371 \verb|de_quality|---quality of dual solution;
3373 \verb|db_quality|---quality of dual feasibility.
3375 Each of these indicators is assigned to one of the following four
3376 values:
3378 \verb|'H'| means high quality,
3380 \verb|'M'| means medium quality,
3382 \verb|'L'| means low quality, or
3384 \verb|'?'| means wrong or infeasible solution.
3386 If all the indicators show high or medium quality (for an internally
3387 scaled LP problem, i.e. when the parameter \verb|scaled| in a call to
3388 the routine \verb|lpx_check_kkt| is non-zero), the user can be sure that
3389 the obtained basic solution is quite accurate.
3391 If some of the indicators show low quality, the solution can still be
3392 considered as relevant, though an additional analysis is needed
3393 depending on which indicator shows low quality.
3395 If the indicator \verb|pe_quality| is assigned to \verb|'?'|, the
3396 primal solution is wrong. If the indicator \verb|de_quality| is assigned
3397 to \verb|'?'|, the dual solution is wrong.
3399 If the indicator \verb|db_quality| is assigned to \verb|'?'| while
3400 other indicators show a good quality, this means that the current
3401 basic solution being primal feasible is not dual feasible. Similarly,
3402 if the indicator \verb|pb_quality| is assigned to \verb|'?'| while
3403 other indicators are not, this means that the current basic solution
3404 being dual feasible is not primal feasible.
3406 %* eof *%