[1] | 1 | %* glpk02.tex *% |
---|
| 2 | |
---|
| 3 | \chapter{Basic API Routines} |
---|
| 4 | |
---|
| 5 | This chapter describes GLPK API routines intended for using in |
---|
| 6 | application programs. |
---|
| 7 | |
---|
| 8 | \subsubsection*{Library header} |
---|
| 9 | |
---|
| 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: |
---|
| 14 | |
---|
| 15 | \begin{verbatim} |
---|
| 16 | #include <glpk.h> |
---|
| 17 | \end{verbatim} |
---|
| 18 | |
---|
| 19 | \subsubsection*{Error handling} |
---|
| 20 | |
---|
| 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. |
---|
| 28 | |
---|
| 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. |
---|
| 34 | |
---|
| 35 | \subsubsection*{Thread safety} |
---|
| 36 | |
---|
| 37 | Currently GLPK API routines are non-reentrant and therefore cannot be |
---|
| 38 | used in multi-threaded programs. |
---|
| 39 | |
---|
| 40 | \subsubsection*{Array indexing} |
---|
| 41 | |
---|
| 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. |
---|
| 48 | |
---|
| 49 | In order to avoid indexing errors it is most convenient and most |
---|
| 50 | reliable to declare the array \verb|x| as follows: |
---|
| 51 | |
---|
| 52 | \begin{verbatim} |
---|
| 53 | double x[1+n]; |
---|
| 54 | \end{verbatim} |
---|
| 55 | |
---|
| 56 | \noindent |
---|
| 57 | or to allocate it as follows: |
---|
| 58 | |
---|
| 59 | \begin{verbatim} |
---|
| 60 | double *x; |
---|
| 61 | . . . |
---|
| 62 | x = calloc(1+n, sizeof(double)); |
---|
| 63 | \end{verbatim} |
---|
| 64 | |
---|
| 65 | \noindent |
---|
| 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. |
---|
| 68 | |
---|
| 69 | \section{Problem object} |
---|
| 70 | |
---|
| 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. |
---|
| 74 | |
---|
| 75 | The type \verb|glp_prob| is a data structure declared in the header |
---|
| 76 | file \verb|glpk.h| as follows: |
---|
| 77 | |
---|
| 78 | \begin{verbatim} |
---|
| 79 | typedef struct { ... } glp_prob; |
---|
| 80 | \end{verbatim} |
---|
| 81 | |
---|
| 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). |
---|
| 87 | |
---|
| 88 | \pagebreak |
---|
| 89 | |
---|
| 90 | The problem object consists of five segments, which are: |
---|
| 91 | |
---|
| 92 | $\bullet$ problem segment, |
---|
| 93 | |
---|
| 94 | $\bullet$ basis segment, |
---|
| 95 | |
---|
| 96 | $\bullet$ interior point segment, |
---|
| 97 | |
---|
| 98 | $\bullet$ MIP segment, and |
---|
| 99 | |
---|
| 100 | $\bullet$ control parameters and statistics segment. |
---|
| 101 | |
---|
| 102 | \subsubsection*{Problem segment} |
---|
| 103 | |
---|
| 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: |
---|
| 108 | |
---|
| 109 | $\bullet$ rows (auxiliary variables), |
---|
| 110 | |
---|
| 111 | $\bullet$ columns (structural variables), |
---|
| 112 | |
---|
| 113 | $\bullet$ objective function, and |
---|
| 114 | |
---|
| 115 | $\bullet$ constraint matrix. |
---|
| 116 | |
---|
| 117 | Rows and columns have the same set of the following attributes: |
---|
| 118 | |
---|
| 119 | $\bullet$ ordinal number, |
---|
| 120 | |
---|
| 121 | $\bullet$ symbolic name (1 up to 255 arbitrary graphic characters), |
---|
| 122 | |
---|
| 123 | $\bullet$ type (free, lower bound, upper bound, double bound, fixed), |
---|
| 124 | |
---|
| 125 | $\bullet$ numerical values of lower and upper bounds, |
---|
| 126 | |
---|
| 127 | $\bullet$ scale factor. |
---|
| 128 | |
---|
| 129 | {\it Ordinal numbers} are intended for referencing rows and columns. |
---|
| 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. |
---|
| 134 | |
---|
| 135 | {\it Symbolic names} are intended for informational purposes. They also |
---|
| 136 | can be used for referencing rows and columns. |
---|
| 137 | |
---|
| 138 | {\it Types and bounds} of rows (auxiliary variables) and columns |
---|
| 139 | (structural variables) are explained above (see Section \ref{seclp}, |
---|
| 140 | page \pageref{seclp}). |
---|
| 141 | |
---|
| 142 | {\it Scale factors} are used internally for scaling rows and columns of |
---|
| 143 | the constraint matrix. |
---|
| 144 | |
---|
| 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). |
---|
| 148 | |
---|
| 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. |
---|
| 154 | |
---|
| 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. |
---|
| 158 | |
---|
| 159 | \subsubsection*{Basis segment} |
---|
| 160 | |
---|
| 161 | The {\it basis segment} of the problem object keeps information related |
---|
| 162 | to the current basic solution. It includes: |
---|
| 163 | |
---|
| 164 | $\bullet$ row and column statuses, |
---|
| 165 | |
---|
| 166 | $\bullet$ basic solution statuses, |
---|
| 167 | |
---|
| 168 | $\bullet$ factorization of the current basis matrix, and |
---|
| 169 | |
---|
| 170 | $\bullet$ basic solution components. |
---|
| 171 | |
---|
| 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. |
---|
| 177 | |
---|
| 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. |
---|
| 183 | |
---|
| 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.). |
---|
| 192 | |
---|
| 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. |
---|
| 196 | |
---|
| 197 | \subsubsection*{Interior point segment} |
---|
| 198 | |
---|
| 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. |
---|
| 203 | |
---|
| 204 | \subsubsection*{MIP segment} |
---|
| 205 | |
---|
| 206 | The {\it MIP segment} is used only for MIP problems. This segment |
---|
| 207 | includes: |
---|
| 208 | |
---|
| 209 | $\bullet$ column kinds, |
---|
| 210 | |
---|
| 211 | $\bullet$ MIP solution status, and |
---|
| 212 | |
---|
| 213 | $\bullet$ MIP solution components. |
---|
| 214 | |
---|
| 215 | The {\it column kinds} define which columns (i.e. structural variables) |
---|
| 216 | are integer and which are continuous. |
---|
| 217 | |
---|
| 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. |
---|
| 221 | |
---|
| 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. |
---|
| 225 | |
---|
| 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. |
---|
| 229 | |
---|
| 230 | Currently the search tree is not kept in the MIP segment. Therefore if |
---|
| 231 | the search has been terminated, it cannot be continued. |
---|
| 232 | |
---|
| 233 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
| 234 | |
---|
| 235 | \newpage |
---|
| 236 | |
---|
| 237 | \section{Problem creating and modifying routines} |
---|
| 238 | |
---|
| 239 | \subsection{glp\_create\_prob---create problem object} |
---|
| 240 | |
---|
| 241 | \subsubsection*{Synopsis} |
---|
| 242 | |
---|
| 243 | \begin{verbatim} |
---|
| 244 | glp_prob *glp_create_prob(void); |
---|
| 245 | \end{verbatim} |
---|
| 246 | |
---|
| 247 | \subsubsection*{Description} |
---|
| 248 | |
---|
| 249 | The routine \verb|glp_create_prob| creates a new problem object, which |
---|
| 250 | initially is ``empty'', i.e. has no rows and columns. |
---|
| 251 | |
---|
| 252 | \subsubsection*{Returns} |
---|
| 253 | |
---|
| 254 | The routine returns a pointer to the created object, which should be |
---|
| 255 | used in any subsequent operations on this object. |
---|
| 256 | |
---|
| 257 | \subsection{glp\_set\_prob\_name---assign (change) problem name} |
---|
| 258 | |
---|
| 259 | \subsubsection*{Synopsis} |
---|
| 260 | |
---|
| 261 | \begin{verbatim} |
---|
| 262 | void glp_set_prob_name(glp_prob *lp, const char *name); |
---|
| 263 | \end{verbatim} |
---|
| 264 | |
---|
| 265 | \subsubsection*{Description} |
---|
| 266 | |
---|
| 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. |
---|
| 269 | |
---|
| 270 | If the parameter \verb|name| is \verb|NULL| or empty string, the routine |
---|
| 271 | erases an existing symbolic name of the problem object. |
---|
| 272 | |
---|
| 273 | \subsection{glp\_set\_obj\_name---assign (change) objective function |
---|
| 274 | name} |
---|
| 275 | |
---|
| 276 | \subsubsection*{Synopsis} |
---|
| 277 | |
---|
| 278 | \begin{verbatim} |
---|
| 279 | void glp_set_obj_name(glp_prob *lp, const char *name); |
---|
| 280 | \end{verbatim} |
---|
| 281 | |
---|
| 282 | \subsubsection*{Description} |
---|
| 283 | |
---|
| 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. |
---|
| 287 | |
---|
| 288 | If the parameter \verb|name| is \verb|NULL| or empty string, the routine |
---|
| 289 | erases an existing symbolic name of the objective function. |
---|
| 290 | |
---|
| 291 | \subsection{glp\_set\_obj\_dir---set (change) optimization direction\\ |
---|
| 292 | flag} |
---|
| 293 | |
---|
| 294 | \subsubsection*{Synopsis} |
---|
| 295 | |
---|
| 296 | \begin{verbatim} |
---|
| 297 | void glp_set_obj_dir(glp_prob *lp, int dir); |
---|
| 298 | \end{verbatim} |
---|
| 299 | |
---|
| 300 | \subsubsection*{Description} |
---|
| 301 | |
---|
| 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|: |
---|
| 305 | |
---|
| 306 | \begin{tabular}{@{}ll} |
---|
| 307 | \verb|GLP_MIN| & minimization; \\ |
---|
| 308 | \verb|GLP_MAX| & maximization. \\ |
---|
| 309 | \end{tabular} |
---|
| 310 | |
---|
| 311 | \noindent |
---|
| 312 | (Note that by default the problem is minimization.) |
---|
| 313 | |
---|
| 314 | \subsection{glp\_add\_rows---add new rows to problem object} |
---|
| 315 | |
---|
| 316 | \subsubsection*{Synopsis} |
---|
| 317 | |
---|
| 318 | \begin{verbatim} |
---|
| 319 | int glp_add_rows(glp_prob *lp, int nrs); |
---|
| 320 | \end{verbatim} |
---|
| 321 | |
---|
| 322 | \subsubsection*{Description} |
---|
| 323 | |
---|
| 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. |
---|
| 327 | |
---|
| 328 | Being added each new row is initially free (unbounded) and has empty |
---|
| 329 | list of the constraint coefficients. |
---|
| 330 | |
---|
| 331 | \subsubsection*{Returns} |
---|
| 332 | |
---|
| 333 | The routine \verb|glp_add_rows| returns the ordinal number of the first |
---|
| 334 | new row added to the problem object. |
---|
| 335 | |
---|
| 336 | \newpage |
---|
| 337 | |
---|
| 338 | \subsection{glp\_add\_cols---add new columns to problem object} |
---|
| 339 | |
---|
| 340 | \subsubsection*{Synopsis} |
---|
| 341 | |
---|
| 342 | \begin{verbatim} |
---|
| 343 | int glp_add_cols(glp_prob *lp, int ncs); |
---|
| 344 | \end{verbatim} |
---|
| 345 | |
---|
| 346 | \subsubsection*{Description} |
---|
| 347 | |
---|
| 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. |
---|
| 352 | |
---|
| 353 | Being added each new column is initially fixed at zero and has empty |
---|
| 354 | list of the constraint coefficients. |
---|
| 355 | |
---|
| 356 | \subsubsection*{Returns} |
---|
| 357 | |
---|
| 358 | The routine \verb|glp_add_cols| returns the ordinal number of the first |
---|
| 359 | new column added to the problem object. |
---|
| 360 | |
---|
| 361 | \subsection{glp\_set\_row\_name---assign (change) row name} |
---|
| 362 | |
---|
| 363 | \subsubsection*{Synopsis} |
---|
| 364 | |
---|
| 365 | \begin{verbatim} |
---|
| 366 | void glp_set_row_name(glp_prob *lp, int i, const char *name); |
---|
| 367 | \end{verbatim} |
---|
| 368 | |
---|
| 369 | \subsubsection*{Description} |
---|
| 370 | |
---|
| 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. |
---|
| 374 | |
---|
| 375 | If the parameter \verb|name| is \verb|NULL| or empty string, the routine |
---|
| 376 | erases an existing name of $i$-th row. |
---|
| 377 | |
---|
| 378 | \subsection{glp\_set\_col\_name---assign (change) column name} |
---|
| 379 | |
---|
| 380 | \subsubsection*{Synopsis} |
---|
| 381 | |
---|
| 382 | \begin{verbatim} |
---|
| 383 | void glp_set_col_name(glp_prob *lp, int j, const char *name); |
---|
| 384 | \end{verbatim} |
---|
| 385 | |
---|
| 386 | \subsubsection*{Description} |
---|
| 387 | |
---|
| 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. |
---|
| 391 | |
---|
| 392 | If the parameter \verb|name| is \verb|NULL| or empty string, the routine |
---|
| 393 | erases an existing name of $j$-th column. |
---|
| 394 | |
---|
| 395 | \subsection{glp\_set\_row\_bnds---set (change) row bounds} |
---|
| 396 | |
---|
| 397 | \subsubsection*{Synopsis} |
---|
| 398 | |
---|
| 399 | \begin{verbatim} |
---|
| 400 | void glp_set_row_bnds(glp_prob *lp, int i, int type, |
---|
| 401 | double lb, double ub); |
---|
| 402 | \end{verbatim} |
---|
| 403 | |
---|
| 404 | \subsubsection*{Description} |
---|
| 405 | |
---|
| 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. |
---|
| 408 | |
---|
| 409 | The parameters \verb|type|, \verb|lb|, and \verb|ub| specify the type, |
---|
| 410 | lower bound, and upper bound, respectively, as follows: |
---|
| 411 | |
---|
| 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} |
---|
| 428 | |
---|
| 429 | \noindent |
---|
| 430 | where $x$ is the auxiliary variable associated with $i$-th row. |
---|
| 431 | |
---|
| 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. |
---|
| 437 | |
---|
| 438 | Being added to the problem object each row is initially free, i.e. its |
---|
| 439 | type is \verb|GLP_FR|. |
---|
| 440 | |
---|
| 441 | \newpage |
---|
| 442 | |
---|
| 443 | \subsection{glp\_set\_col\_bnds---set (change) column bounds} |
---|
| 444 | |
---|
| 445 | \subsubsection*{Synopsis} |
---|
| 446 | |
---|
| 447 | \begin{verbatim} |
---|
| 448 | void glp_set_col_bnds(glp_prob *lp, int j, int type, |
---|
| 449 | double lb, double ub); |
---|
| 450 | \end{verbatim} |
---|
| 451 | |
---|
| 452 | \subsubsection*{Description} |
---|
| 453 | |
---|
| 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. |
---|
| 457 | |
---|
| 458 | The parameters \verb|type|, \verb|lb|, and \verb|ub| specify the type, |
---|
| 459 | lower bound, and upper bound, respectively, as follows: |
---|
| 460 | |
---|
| 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} |
---|
| 477 | |
---|
| 478 | \noindent |
---|
| 479 | where $x$ is the structural variable associated with $j$-th column. |
---|
| 480 | |
---|
| 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. |
---|
| 485 | |
---|
| 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. |
---|
| 488 | |
---|
| 489 | \subsection{glp\_set\_obj\_coef---set (change) objective coefficient |
---|
| 490 | or constant term} |
---|
| 491 | |
---|
| 492 | \subsubsection*{Synopsis} |
---|
| 493 | |
---|
| 494 | \begin{verbatim} |
---|
| 495 | void glp_set_obj_coef(glp_prob *lp, int j, double coef); |
---|
| 496 | \end{verbatim} |
---|
| 497 | |
---|
| 498 | \subsubsection*{Description} |
---|
| 499 | |
---|
| 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|. |
---|
| 503 | |
---|
| 504 | If the parameter \verb|j| is 0, the routine sets (changes) the constant |
---|
| 505 | term (``shift'') of the objective function. |
---|
| 506 | |
---|
| 507 | \subsection{glp\_set\_mat\_row---set (replace) row of the constraint |
---|
| 508 | matrix} |
---|
| 509 | |
---|
| 510 | \subsubsection*{Synopsis} |
---|
| 511 | |
---|
| 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} |
---|
| 516 | |
---|
| 517 | \subsubsection*{Description} |
---|
| 518 | |
---|
| 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. |
---|
| 522 | |
---|
| 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. |
---|
| 530 | |
---|
| 531 | If the parameter \verb|len| is 0, the parameters \verb|ind| and/or |
---|
| 532 | \verb|val| can be specified as \verb|NULL|. |
---|
| 533 | |
---|
| 534 | \subsection{glp\_set\_mat\_col---set (replace) column of the |
---|
| 535 | constr\-aint matrix} |
---|
| 536 | |
---|
| 537 | \subsubsection*{Synopsis} |
---|
| 538 | |
---|
| 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} |
---|
| 543 | |
---|
| 544 | \subsubsection*{Description} |
---|
| 545 | |
---|
| 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. |
---|
| 549 | |
---|
| 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. |
---|
| 557 | |
---|
| 558 | If the parameter \verb|len| is 0, the parameters \verb|ind| and/or |
---|
| 559 | \verb|val| can be specified as \verb|NULL|. |
---|
| 560 | |
---|
| 561 | \subsection{glp\_load\_matrix---load (replace) the whole constraint |
---|
| 562 | matrix} |
---|
| 563 | |
---|
| 564 | \subsubsection*{Synopsis} |
---|
| 565 | |
---|
| 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} |
---|
| 570 | |
---|
| 571 | \subsubsection*{Description} |
---|
| 572 | |
---|
| 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. |
---|
| 577 | |
---|
| 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. |
---|
| 586 | |
---|
| 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|. |
---|
| 589 | |
---|
| 590 | \subsection{glp\_check\_dup---check for duplicate elements in sparse |
---|
| 591 | matrix} |
---|
| 592 | |
---|
| 593 | \subsubsection*{Synopsis} |
---|
| 594 | |
---|
| 595 | \begin{verbatim} |
---|
| 596 | int glp_check_dup(int m, int n, int ne, const int ia[], |
---|
| 597 | const int ja[]); |
---|
| 598 | \end{verbatim} |
---|
| 599 | |
---|
| 600 | \subsubsection*{Description} |
---|
| 601 | |
---|
| 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. |
---|
| 605 | |
---|
| 606 | The parameters $m$ and $n$ specifies, respectively, the number of rows |
---|
| 607 | and columns in the matrix, $m\geq 0$, $n\geq 0$. |
---|
| 608 | |
---|
| 609 | The parameter {\it ne} specifies the number of (structurally) non-zero |
---|
| 610 | elements in the matrix, {\it ne} $\geq 0$. |
---|
| 611 | |
---|
| 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. |
---|
| 614 | |
---|
| 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. |
---|
| 618 | |
---|
| 619 | \subsubsection*{Returns} |
---|
| 620 | |
---|
| 621 | The routine \verb|glp_check_dup| returns one of the following values: |
---|
| 622 | |
---|
| 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} |
---|
| 629 | |
---|
| 630 | \subsection{glp\_sort\_matrix---sort elements of the constraint matrix} |
---|
| 631 | |
---|
| 632 | \subsubsection*{Synopsis} |
---|
| 633 | |
---|
| 634 | \begin{verbatim} |
---|
| 635 | void glp_sort_matrix(glp_prob *P); |
---|
| 636 | \end{verbatim} |
---|
| 637 | |
---|
| 638 | \subsubsection*{Description} |
---|
| 639 | |
---|
| 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. |
---|
| 646 | |
---|
| 647 | \subsection{glp\_del\_rows---delete rows from problem object} |
---|
| 648 | |
---|
| 649 | \subsubsection*{Synopsis} |
---|
| 650 | |
---|
| 651 | \begin{verbatim} |
---|
| 652 | void glp_del_rows(glp_prob *lp, int nrs, const int num[]); |
---|
| 653 | \end{verbatim} |
---|
| 654 | |
---|
| 655 | \subsubsection*{Description} |
---|
| 656 | |
---|
| 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$. |
---|
| 661 | |
---|
| 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. |
---|
| 669 | |
---|
| 670 | \subsection{glp\_del\_cols---delete columns from problem object} |
---|
| 671 | |
---|
| 672 | \subsubsection*{Synopsis} |
---|
| 673 | |
---|
| 674 | \begin{verbatim} |
---|
| 675 | void glp_del_cols(glp_prob *lp, int ncs, const int num[]); |
---|
| 676 | \end{verbatim} |
---|
| 677 | |
---|
| 678 | \subsubsection*{Description} |
---|
| 679 | |
---|
| 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$. |
---|
| 684 | |
---|
| 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. |
---|
| 693 | |
---|
| 694 | \subsection{glp\_copy\_prob---copy problem object content} |
---|
| 695 | |
---|
| 696 | \subsubsection*{Synopsis} |
---|
| 697 | |
---|
| 698 | \begin{verbatim} |
---|
| 699 | void glp_copy_prob(glp_prob *dest, glp_prob *prob, int names); |
---|
| 700 | \end{verbatim} |
---|
| 701 | |
---|
| 702 | \subsubsection*{Description} |
---|
| 703 | |
---|
| 704 | The routine \verb|glp_copy_prob| copies the content of the problem |
---|
| 705 | object \verb|prob| to the problem object \verb|dest|. |
---|
| 706 | |
---|
| 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. |
---|
| 710 | |
---|
| 711 | \newpage |
---|
| 712 | |
---|
| 713 | \subsection{glp\_erase\_prob---erase problem object content} |
---|
| 714 | |
---|
| 715 | \subsubsection*{Synopsis} |
---|
| 716 | |
---|
| 717 | \begin{verbatim} |
---|
| 718 | void glp_erase_prob(glp_prob *lp); |
---|
| 719 | \end{verbatim} |
---|
| 720 | |
---|
| 721 | \subsubsection*{Description} |
---|
| 722 | |
---|
| 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. |
---|
| 729 | |
---|
| 730 | \subsection{glp\_delete\_prob---delete problem object} |
---|
| 731 | |
---|
| 732 | \subsubsection*{Synopsis} |
---|
| 733 | |
---|
| 734 | \begin{verbatim} |
---|
| 735 | void glp_delete_prob(glp_prob *lp); |
---|
| 736 | \end{verbatim} |
---|
| 737 | |
---|
| 738 | \subsubsection*{Description} |
---|
| 739 | |
---|
| 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. |
---|
| 743 | |
---|
| 744 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
| 745 | |
---|
| 746 | \newpage |
---|
| 747 | |
---|
| 748 | \section{Problem retrieving routines} |
---|
| 749 | |
---|
| 750 | \subsection{glp\_get\_prob\_name---retrieve problem name} |
---|
| 751 | |
---|
| 752 | \subsubsection*{Synopsis} |
---|
| 753 | |
---|
| 754 | \begin{verbatim} |
---|
| 755 | const char *glp_get_prob_name(glp_prob *lp); |
---|
| 756 | \end{verbatim} |
---|
| 757 | |
---|
| 758 | \subsubsection*{Returns} |
---|
| 759 | |
---|
| 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|. |
---|
| 763 | |
---|
| 764 | \subsection{glp\_get\_obj\_name---retrieve objective function name} |
---|
| 765 | |
---|
| 766 | \subsubsection*{Synopsis} |
---|
| 767 | |
---|
| 768 | \begin{verbatim} |
---|
| 769 | const char *glp_get_obj_name(glp_prob *lp); |
---|
| 770 | \end{verbatim} |
---|
| 771 | |
---|
| 772 | \subsubsection*{Returns} |
---|
| 773 | |
---|
| 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|. |
---|
| 778 | |
---|
| 779 | \subsection{glp\_get\_obj\_dir---retrieve optimization direction flag} |
---|
| 780 | |
---|
| 781 | \subsubsection*{Synopsis} |
---|
| 782 | |
---|
| 783 | \begin{verbatim} |
---|
| 784 | int glp_get_obj_dir(glp_prob *lp); |
---|
| 785 | \end{verbatim} |
---|
| 786 | |
---|
| 787 | \subsubsection*{Returns} |
---|
| 788 | |
---|
| 789 | The routine \verb|glp_get_obj_dir| returns the optimization direction |
---|
| 790 | flag (i.e. ``sense'' of the objective function): |
---|
| 791 | |
---|
| 792 | \begin{tabular}{@{}ll} |
---|
| 793 | \verb|GLP_MIN| & minimization; \\ |
---|
| 794 | \verb|GLP_MAX| & maximization. \\ |
---|
| 795 | \end{tabular} |
---|
| 796 | |
---|
| 797 | \pagebreak |
---|
| 798 | |
---|
| 799 | \subsection{glp\_get\_num\_rows---retrieve number of rows} |
---|
| 800 | |
---|
| 801 | \subsubsection*{Synopsis} |
---|
| 802 | |
---|
| 803 | \begin{verbatim} |
---|
| 804 | int glp_get_num_rows(glp_prob *lp); |
---|
| 805 | \end{verbatim} |
---|
| 806 | |
---|
| 807 | \subsubsection*{Returns} |
---|
| 808 | |
---|
| 809 | The routine \verb|glp_get_num_rows| returns the current number of rows |
---|
| 810 | in the specified problem object. |
---|
| 811 | |
---|
| 812 | \subsection{glp\_get\_num\_cols---retrieve number of columns} |
---|
| 813 | |
---|
| 814 | \subsubsection*{Synopsis} |
---|
| 815 | |
---|
| 816 | \begin{verbatim} |
---|
| 817 | int glp_get_num_cols(glp_prob *lp); |
---|
| 818 | \end{verbatim} |
---|
| 819 | |
---|
| 820 | \subsubsection*{Returns} |
---|
| 821 | |
---|
| 822 | The routine \verb|glp_get_num_cols| returns the current number of |
---|
| 823 | columns the specified problem object. |
---|
| 824 | |
---|
| 825 | \subsection{glp\_get\_row\_name---retrieve row name} |
---|
| 826 | |
---|
| 827 | \subsubsection*{Synopsis} |
---|
| 828 | |
---|
| 829 | \begin{verbatim} |
---|
| 830 | const char *glp_get_row_name(glp_prob *lp, int i); |
---|
| 831 | \end{verbatim} |
---|
| 832 | |
---|
| 833 | \subsubsection*{Returns} |
---|
| 834 | |
---|
| 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|. |
---|
| 839 | |
---|
| 840 | \subsection{glp\_get\_col\_name---retrieve column name} |
---|
| 841 | |
---|
| 842 | \subsubsection*{Synopsis} |
---|
| 843 | |
---|
| 844 | \begin{verbatim} |
---|
| 845 | const char *glp_get_col_name(glp_prob *lp, int j); |
---|
| 846 | \end{verbatim} |
---|
| 847 | |
---|
| 848 | \subsubsection*{Returns} |
---|
| 849 | |
---|
| 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|. |
---|
| 854 | |
---|
| 855 | \subsection{glp\_get\_row\_type---retrieve row type} |
---|
| 856 | |
---|
| 857 | \subsubsection*{Synopsis} |
---|
| 858 | |
---|
| 859 | \begin{verbatim} |
---|
| 860 | int glp_get_row_type(glp_prob *lp, int i); |
---|
| 861 | \end{verbatim} |
---|
| 862 | |
---|
| 863 | \subsubsection*{Returns} |
---|
| 864 | |
---|
| 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: |
---|
| 867 | |
---|
| 868 | \begin{tabular}{@{}ll} |
---|
| 869 | \verb|GLP_FR| & free (unbounded) variable; \\ |
---|
| 870 | \verb|GLP_LO| & variable with lower bound; \\ |
---|
| 871 | \verb|GLP_UP| & variable with upper bound; \\ |
---|
| 872 | \verb|GLP_DB| & double-bounded variable; \\ |
---|
| 873 | \verb|GLP_FX| & fixed variable. \\ |
---|
| 874 | \end{tabular} |
---|
| 875 | |
---|
| 876 | \subsection{glp\_get\_row\_lb---retrieve row lower bound} |
---|
| 877 | |
---|
| 878 | \subsubsection*{Synopsis} |
---|
| 879 | |
---|
| 880 | \begin{verbatim} |
---|
| 881 | double glp_get_row_lb(glp_prob *lp, int i); |
---|
| 882 | \end{verbatim} |
---|
| 883 | |
---|
| 884 | \subsubsection*{Returns} |
---|
| 885 | |
---|
| 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|. |
---|
| 890 | |
---|
| 891 | \subsection{glp\_get\_row\_ub---retrieve row upper bound} |
---|
| 892 | |
---|
| 893 | \subsubsection*{Synopsis} |
---|
| 894 | |
---|
| 895 | \begin{verbatim} |
---|
| 896 | double glp_get_row_ub(glp_prob *lp, int i); |
---|
| 897 | \end{verbatim} |
---|
| 898 | |
---|
| 899 | \subsubsection*{Returns} |
---|
| 900 | |
---|
| 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|. |
---|
| 905 | |
---|
| 906 | \subsection{glp\_get\_col\_type---retrieve column type} |
---|
| 907 | |
---|
| 908 | \subsubsection*{Synopsis} |
---|
| 909 | |
---|
| 910 | \begin{verbatim} |
---|
| 911 | int glp_get_col_type(glp_prob *lp, int j); |
---|
| 912 | \end{verbatim} |
---|
| 913 | |
---|
| 914 | \subsubsection*{Returns} |
---|
| 915 | |
---|
| 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: |
---|
| 918 | |
---|
| 919 | \begin{tabular}{@{}ll} |
---|
| 920 | \verb|GLP_FR| & free (unbounded) variable; \\ |
---|
| 921 | \verb|GLP_LO| & variable with lower bound; \\ |
---|
| 922 | \verb|GLP_UP| & variable with upper bound; \\ |
---|
| 923 | \verb|GLP_DB| & double-bounded variable; \\ |
---|
| 924 | \verb|GLP_FX| & fixed variable. \\ |
---|
| 925 | \end{tabular} |
---|
| 926 | |
---|
| 927 | \subsection{glp\_get\_col\_lb---retrieve column lower bound} |
---|
| 928 | |
---|
| 929 | \subsubsection*{Synopsis} |
---|
| 930 | |
---|
| 931 | \begin{verbatim} |
---|
| 932 | double glp_get_col_lb(glp_prob *lp, int j); |
---|
| 933 | \end{verbatim} |
---|
| 934 | |
---|
| 935 | \subsubsection*{Returns} |
---|
| 936 | |
---|
| 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|. |
---|
| 941 | |
---|
| 942 | \subsection{glp\_get\_col\_ub---retrieve column upper bound} |
---|
| 943 | |
---|
| 944 | \subsubsection*{Synopsis} |
---|
| 945 | |
---|
| 946 | \begin{verbatim} |
---|
| 947 | double glp_get_col_ub(glp_prob *lp, int j); |
---|
| 948 | \end{verbatim} |
---|
| 949 | |
---|
| 950 | \subsubsection*{Returns} |
---|
| 951 | |
---|
| 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|. |
---|
| 956 | |
---|
| 957 | \subsection{glp\_get\_obj\_coef---retrieve objective coefficient or\\ |
---|
| 958 | constant term} |
---|
| 959 | |
---|
| 960 | \subsubsection*{Synopsis} |
---|
| 961 | |
---|
| 962 | \begin{verbatim} |
---|
| 963 | double glp_get_obj_coef(glp_prob *lp, int j); |
---|
| 964 | \end{verbatim} |
---|
| 965 | |
---|
| 966 | \subsubsection*{Returns} |
---|
| 967 | |
---|
| 968 | The routine \verb|glp_get_obj_coef| returns the objective coefficient |
---|
| 969 | at \verb|j|-th structural variable (column). |
---|
| 970 | |
---|
| 971 | If the parameter \verb|j| is 0, the routine returns the constant term |
---|
| 972 | (``shift'') of the objective function. |
---|
| 973 | |
---|
| 974 | \subsection{glp\_get\_num\_nz---retrieve number of constraint |
---|
| 975 | coefficients} |
---|
| 976 | |
---|
| 977 | \subsubsection*{Synopsis} |
---|
| 978 | |
---|
| 979 | \begin{verbatim} |
---|
| 980 | int glp_get_num_nz(glp_prob *lp); |
---|
| 981 | \end{verbatim} |
---|
| 982 | |
---|
| 983 | \subsubsection*{Returns} |
---|
| 984 | |
---|
| 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. |
---|
| 987 | |
---|
| 988 | \subsection{glp\_get\_mat\_row---retrieve row of the constraint |
---|
| 989 | matrix} |
---|
| 990 | |
---|
| 991 | \subsubsection*{Synopsis} |
---|
| 992 | |
---|
| 993 | \begin{verbatim} |
---|
| 994 | int glp_get_mat_row(glp_prob *lp, int i, int ind[], |
---|
| 995 | double val[]); |
---|
| 996 | \end{verbatim} |
---|
| 997 | |
---|
| 998 | \subsubsection*{Description} |
---|
| 999 | |
---|
| 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. |
---|
| 1006 | |
---|
| 1007 | The parameter \verb|ind| and/or \verb|val| can be specified as |
---|
| 1008 | \verb|NULL|, in which case corresponding information is not stored. |
---|
| 1009 | |
---|
| 1010 | \subsubsection*{Returns} |
---|
| 1011 | |
---|
| 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. |
---|
| 1014 | |
---|
| 1015 | \subsection{glp\_get\_mat\_col---retrieve column of the constraint\\ |
---|
| 1016 | matrix} |
---|
| 1017 | |
---|
| 1018 | \subsubsection*{Synopsis} |
---|
| 1019 | |
---|
| 1020 | \begin{verbatim} |
---|
| 1021 | int glp_get_mat_col(glp_prob *lp, int j, int ind[], |
---|
| 1022 | double val[]); |
---|
| 1023 | \end{verbatim} |
---|
| 1024 | |
---|
| 1025 | \subsubsection*{Description} |
---|
| 1026 | |
---|
| 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. |
---|
| 1033 | |
---|
| 1034 | The parameter \verb|ind| and/or \verb|val| can be specified as |
---|
| 1035 | \verb|NULL|, in which case corresponding information is not stored. |
---|
| 1036 | |
---|
| 1037 | \subsubsection*{Returns} |
---|
| 1038 | |
---|
| 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. |
---|
| 1041 | |
---|
| 1042 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
| 1043 | |
---|
| 1044 | \newpage |
---|
| 1045 | |
---|
| 1046 | \section{Row and column searching routines} |
---|
| 1047 | |
---|
| 1048 | \subsection{glp\_create\_index---create the name index} |
---|
| 1049 | |
---|
| 1050 | \subsubsection*{Synopsis} |
---|
| 1051 | |
---|
| 1052 | \begin{verbatim} |
---|
| 1053 | void glp_create_index(glp_prob *lp); |
---|
| 1054 | \end{verbatim} |
---|
| 1055 | |
---|
| 1056 | \subsubsection*{Description} |
---|
| 1057 | |
---|
| 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. |
---|
| 1062 | |
---|
| 1063 | This routine can be called at any time. If the name index already |
---|
| 1064 | exists, the routine does nothing. |
---|
| 1065 | |
---|
| 1066 | \subsection{glp\_find\_row---find row by its name} |
---|
| 1067 | |
---|
| 1068 | \subsubsection*{Synopsis} |
---|
| 1069 | |
---|
| 1070 | \begin{verbatim} |
---|
| 1071 | int glp_find_row(glp_prob *lp, const char *name); |
---|
| 1072 | \end{verbatim} |
---|
| 1073 | |
---|
| 1074 | \subsubsection*{Returns} |
---|
| 1075 | |
---|
| 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. |
---|
| 1079 | |
---|
| 1080 | \subsection{glp\_find\_col---find column by its name} |
---|
| 1081 | |
---|
| 1082 | \subsubsection*{Synopsis} |
---|
| 1083 | |
---|
| 1084 | \begin{verbatim} |
---|
| 1085 | int glp_find_col(glp_prob *lp, const char *name); |
---|
| 1086 | \end{verbatim} |
---|
| 1087 | |
---|
| 1088 | \subsubsection*{Returns} |
---|
| 1089 | |
---|
| 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. |
---|
| 1093 | |
---|
| 1094 | \subsection{glp\_delete\_index---delete the name index} |
---|
| 1095 | |
---|
| 1096 | \subsubsection*{Synopsis} |
---|
| 1097 | |
---|
| 1098 | \begin{verbatim} |
---|
| 1099 | void glp_delete_index(glp_prob *lp); |
---|
| 1100 | \end{verbatim} |
---|
| 1101 | |
---|
| 1102 | \subsubsection*{Description} |
---|
| 1103 | |
---|
| 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. |
---|
| 1107 | |
---|
| 1108 | This routine can be called at any time. If the name index does not |
---|
| 1109 | exist, the routine does nothing. |
---|
| 1110 | |
---|
| 1111 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
| 1112 | |
---|
| 1113 | \newpage |
---|
| 1114 | |
---|
| 1115 | \section{Problem scaling routines} |
---|
| 1116 | |
---|
| 1117 | \subsection{Background} |
---|
| 1118 | |
---|
| 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.} |
---|
| 1124 | |
---|
| 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. |
---|
| 1131 | |
---|
| 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)$$ |
---|
| 1136 | |
---|
| 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. |
---|
| 1140 | |
---|
| 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. |
---|
| 1145 | |
---|
| 1146 | \subsection{glp\_set\_rii---set (change) row scale factor} |
---|
| 1147 | |
---|
| 1148 | \subsubsection*{Synopsis} |
---|
| 1149 | |
---|
| 1150 | \begin{verbatim} |
---|
| 1151 | void glp_set_rii(glp_prob *lp, int i, double rii); |
---|
| 1152 | \end{verbatim} |
---|
| 1153 | |
---|
| 1154 | \subsubsection*{Description} |
---|
| 1155 | |
---|
| 1156 | The routine \verb|glp_set_rii| sets (changes) the scale factor $r_{ii}$ |
---|
| 1157 | for $i$-th row of the specified problem object. |
---|
| 1158 | |
---|
| 1159 | \subsection{glp\_set\_sjj---set (change) column scale factor} |
---|
| 1160 | |
---|
| 1161 | \subsubsection*{Synopsis} |
---|
| 1162 | |
---|
| 1163 | \begin{verbatim} |
---|
| 1164 | void glp_set_sjj(glp_prob *lp, int j, double sjj); |
---|
| 1165 | \end{verbatim} |
---|
| 1166 | |
---|
| 1167 | \subsubsection*{Description} |
---|
| 1168 | |
---|
| 1169 | The routine \verb|glp_set_sjj| sets (changes) the scale factor $s_{jj}$ |
---|
| 1170 | for $j$-th column of the specified problem object. |
---|
| 1171 | |
---|
| 1172 | \subsection{glp\_get\_rii---retrieve row scale factor} |
---|
| 1173 | |
---|
| 1174 | \subsubsection*{Synopsis} |
---|
| 1175 | |
---|
| 1176 | \begin{verbatim} |
---|
| 1177 | double glp_get_rii(glp_prob *lp, int i); |
---|
| 1178 | \end{verbatim} |
---|
| 1179 | |
---|
| 1180 | \subsubsection*{Returns} |
---|
| 1181 | |
---|
| 1182 | The routine \verb|glp_get_rii| returns current scale factor $r_{ii}$ for |
---|
| 1183 | $i$-th row of the specified problem object. |
---|
| 1184 | |
---|
| 1185 | \subsection{glp\_get\_sjj---retrieve column scale factor} |
---|
| 1186 | |
---|
| 1187 | \subsubsection*{Synopsis} |
---|
| 1188 | |
---|
| 1189 | \begin{verbatim} |
---|
| 1190 | double glp_get_sjj(glp_prob *lp, int j); |
---|
| 1191 | \end{verbatim} |
---|
| 1192 | |
---|
| 1193 | \subsubsection*{Returns} |
---|
| 1194 | |
---|
| 1195 | The routine \verb|glp_get_sjj| returns current scale factor $s_{jj}$ for |
---|
| 1196 | $j$-th column of the specified problem object. |
---|
| 1197 | |
---|
| 1198 | \subsection{glp\_scale\_prob---scale problem data} |
---|
| 1199 | |
---|
| 1200 | \subsubsection*{Synopsis} |
---|
| 1201 | |
---|
| 1202 | \begin{verbatim} |
---|
| 1203 | void glp_scale_prob(glp_prob *lp, int flags); |
---|
| 1204 | \end{verbatim} |
---|
| 1205 | |
---|
| 1206 | \subsubsection*{Description} |
---|
| 1207 | |
---|
| 1208 | The routine \verb|glp_scale_prob| performs automatic scaling of problem |
---|
| 1209 | data for the specified problem object. |
---|
| 1210 | |
---|
| 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: |
---|
| 1214 | |
---|
| 1215 | \begin{tabular}{@{}ll} |
---|
| 1216 | \verb|GLP_SF_GM| & perform geometric mean scaling;\\ |
---|
| 1217 | \verb|GLP_SF_EQ| & perform equilibration scaling;\\ |
---|
| 1218 | \verb|GLP_SF_2N| & round scale factors to nearest power of two;\\ |
---|
| 1219 | \verb|GLP_SF_SKIP| & skip scaling, if the problem is well scaled.\\ |
---|
| 1220 | \end{tabular} |
---|
| 1221 | |
---|
| 1222 | The parameter \verb|flags| may be specified as \verb|GLP_SF_AUTO|, in |
---|
| 1223 | which case the routine chooses the scaling options automatically. |
---|
| 1224 | |
---|
| 1225 | \subsection{glp\_unscale\_prob---unscale problem data} |
---|
| 1226 | |
---|
| 1227 | \subsubsection*{Synopsis} |
---|
| 1228 | |
---|
| 1229 | \begin{verbatim} |
---|
| 1230 | void glp_unscale_prob(glp_prob *lp); |
---|
| 1231 | \end{verbatim} |
---|
| 1232 | |
---|
| 1233 | The routine \verb|glp_unscale_prob| performs unscaling of problem data |
---|
| 1234 | for the specified problem object. |
---|
| 1235 | |
---|
| 1236 | ``Unscaling'' means replacing the current scaling matrices $R$ and $S$ |
---|
| 1237 | by unity matrices that cancels the scaling effect. |
---|
| 1238 | |
---|
| 1239 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
| 1240 | |
---|
| 1241 | \newpage |
---|
| 1242 | |
---|
| 1243 | \section{LP basis constructing routines} |
---|
| 1244 | |
---|
| 1245 | \subsection{Background} |
---|
| 1246 | |
---|
| 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: |
---|
| 1251 | |
---|
| 1252 | \begin{tabular}{@{}ll} |
---|
| 1253 | \verb|GLP_BS| & basic variable;\\ |
---|
| 1254 | \verb|GLP_NL| & non-basic variable having active lower bound;\\ |
---|
| 1255 | \verb|GLP_NU| & non-basic variable having active upper bound;\\ |
---|
| 1256 | \verb|GLP_NF| & non-basic free variable;\\ |
---|
| 1257 | \verb|GLP_NS| & non-basic fixed variable.\\ |
---|
| 1258 | \end{tabular} |
---|
| 1259 | |
---|
| 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}.) |
---|
| 1266 | |
---|
| 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. |
---|
| 1277 | |
---|
| 1278 | \subsection{glp\_set\_row\_stat---set (change) row status} |
---|
| 1279 | |
---|
| 1280 | \subsubsection*{Synopsis} |
---|
| 1281 | |
---|
| 1282 | \begin{verbatim} |
---|
| 1283 | void glp_set_row_stat(glp_prob *lp, int i, int stat); |
---|
| 1284 | \end{verbatim} |
---|
| 1285 | |
---|
| 1286 | \subsubsection*{Description} |
---|
| 1287 | |
---|
| 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|: |
---|
| 1291 | |
---|
| 1292 | \begin{tabular}{@{}lp{104.2mm}@{}} |
---|
| 1293 | \verb|GLP_BS| & make the row basic (make the constraint inactive); \\ |
---|
| 1294 | \verb|GLP_NL| & make the row non-basic (make the constraint active); \\ |
---|
| 1295 | \end{tabular} |
---|
| 1296 | |
---|
| 1297 | \newpage |
---|
| 1298 | |
---|
| 1299 | \begin{tabular}{@{}lp{104.2mm}@{}} |
---|
| 1300 | \verb|GLP_NU| & make the row non-basic and set it to the upper bound; |
---|
| 1301 | if the row is not double-bounded, this status is equivalent to |
---|
| 1302 | \verb|GLP_NL| (only in the case of this routine); \\ |
---|
| 1303 | \verb|GLP_NF| & the same as \verb|GLP_NL| (only in the case of this |
---|
| 1304 | routine); \\ |
---|
| 1305 | \verb|GLP_NS| & the same as \verb|GLP_NL| (only in the case of this |
---|
| 1306 | routine). \\ |
---|
| 1307 | \end{tabular} |
---|
| 1308 | |
---|
| 1309 | \subsection{glp\_set\_col\_stat---set (change) column status} |
---|
| 1310 | |
---|
| 1311 | \subsubsection*{Synopsis} |
---|
| 1312 | |
---|
| 1313 | \begin{verbatim} |
---|
| 1314 | void glp_set_col_stat(glp_prob *lp, int j, int stat); |
---|
| 1315 | \end{verbatim} |
---|
| 1316 | |
---|
| 1317 | \subsubsection*{Description} |
---|
| 1318 | |
---|
| 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|: |
---|
| 1322 | |
---|
| 1323 | \begin{tabular}{@{}lp{104.2mm}@{}} |
---|
| 1324 | \verb|GLP_BS| & make the column basic; \\ |
---|
| 1325 | \verb|GLP_NL| & make the column non-basic; \\ |
---|
| 1326 | \verb|GLP_NU| & make the column non-basic and set it to the upper |
---|
| 1327 | bound; if the column is not double-bounded, this status is equivalent |
---|
| 1328 | to \verb|GLP_NL| (only in the case of this routine); \\ |
---|
| 1329 | \verb|GLP_NF| & the same as \verb|GLP_NL| (only in the case of this |
---|
| 1330 | routine); \\ |
---|
| 1331 | \verb|GLP_NS| & the same as \verb|GLP_NL| (only in the case of this |
---|
| 1332 | routine). |
---|
| 1333 | \end{tabular} |
---|
| 1334 | |
---|
| 1335 | \subsection{glp\_std\_basis---construct standard initial LP basis} |
---|
| 1336 | |
---|
| 1337 | \subsubsection*{Synopsis} |
---|
| 1338 | |
---|
| 1339 | \begin{verbatim} |
---|
| 1340 | void glp_std_basis(glp_prob *lp); |
---|
| 1341 | \end{verbatim} |
---|
| 1342 | |
---|
| 1343 | \subsubsection*{Description} |
---|
| 1344 | |
---|
| 1345 | The routine \verb|glp_std_basis| constructs the ``standard'' (trivial) |
---|
| 1346 | initial LP basis for the specified problem object. |
---|
| 1347 | |
---|
| 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). |
---|
| 1351 | |
---|
| 1352 | \newpage |
---|
| 1353 | |
---|
| 1354 | \subsection{glp\_adv\_basis---construct advanced initial LP basis} |
---|
| 1355 | |
---|
| 1356 | \subsubsection*{Synopsis} |
---|
| 1357 | |
---|
| 1358 | \begin{verbatim} |
---|
| 1359 | void glp_adv_basis(glp_prob *lp, int flags); |
---|
| 1360 | \end{verbatim} |
---|
| 1361 | |
---|
| 1362 | \subsubsection*{Description} |
---|
| 1363 | |
---|
| 1364 | The routine \verb|glp_adv_basis| constructs an advanced initial LP |
---|
| 1365 | basis for the specified problem object. |
---|
| 1366 | |
---|
| 1367 | The parameter \verb|flags| is reserved for use in the future and must |
---|
| 1368 | be specified as zero. |
---|
| 1369 | |
---|
| 1370 | In order to construct the advanced initial LP basis the routine does |
---|
| 1371 | the following: |
---|
| 1372 | |
---|
| 1373 | 1) includes in the basis all non-fixed auxiliary variables; |
---|
| 1374 | |
---|
| 1375 | 2) includes in the basis as many non-fixed structural variables as |
---|
| 1376 | possible keeping the triangular form of the basis matrix; |
---|
| 1377 | |
---|
| 1378 | 3) includes in the basis appropriate (fixed) auxiliary variables to |
---|
| 1379 | complete the basis. |
---|
| 1380 | |
---|
| 1381 | As a result the initial LP basis has as few fixed variables as possible |
---|
| 1382 | and the corresponding basis matrix is triangular. |
---|
| 1383 | |
---|
| 1384 | \subsection{glp\_cpx\_basis---construct Bixby's initial LP basis} |
---|
| 1385 | |
---|
| 1386 | \subsubsection*{Synopsis} |
---|
| 1387 | |
---|
| 1388 | \begin{verbatim} |
---|
| 1389 | void glp_cpx_basis(glp_prob *lp); |
---|
| 1390 | \end{verbatim} |
---|
| 1391 | |
---|
| 1392 | \subsubsection*{Description} |
---|
| 1393 | |
---|
| 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.} |
---|
| 1399 | |
---|
| 1400 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
| 1401 | |
---|
| 1402 | \newpage |
---|
| 1403 | |
---|
| 1404 | \section{Simplex method routines} |
---|
| 1405 | |
---|
| 1406 | The {\it simplex method} is a well known efficient numerical procedure |
---|
| 1407 | to solve LP problems. |
---|
| 1408 | |
---|
| 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.) |
---|
| 1433 | |
---|
| 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. |
---|
| 1439 | |
---|
| 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. |
---|
| 1448 | |
---|
| 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. |
---|
| 1467 | |
---|
| 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}. |
---|
| 1472 | |
---|
| 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.) |
---|
| 1482 | |
---|
| 1483 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
| 1484 | |
---|
| 1485 | \subsection{glp\_simplex---solve LP problem with the primal or dual |
---|
| 1486 | simplex method} |
---|
| 1487 | |
---|
| 1488 | \subsubsection*{Synopsis} |
---|
| 1489 | |
---|
| 1490 | \begin{verbatim} |
---|
| 1491 | int glp_simplex(glp_prob *lp, const glp_smcp *parm); |
---|
| 1492 | \end{verbatim} |
---|
| 1493 | |
---|
| 1494 | \subsubsection*{Description} |
---|
| 1495 | |
---|
| 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. |
---|
| 1501 | |
---|
| 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|. |
---|
| 1512 | |
---|
| 1513 | The parameter \verb|parm| can be specified as \verb|NULL|, in which |
---|
| 1514 | case the solver uses default settings. |
---|
| 1515 | |
---|
| 1516 | \subsubsection*{Returns} |
---|
| 1517 | |
---|
| 1518 | \def\arraystretch{1} |
---|
| 1519 | |
---|
| 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} |
---|
| 1554 | |
---|
| 1555 | \subsubsection*{Built-in LP presolver} |
---|
| 1556 | |
---|
| 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. |
---|
| 1566 | |
---|
| 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. |
---|
| 1573 | |
---|
| 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. |
---|
| 1578 | |
---|
| 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. |
---|
| 1584 | |
---|
| 1585 | \subsubsection*{Terminal output} |
---|
| 1586 | |
---|
| 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: |
---|
| 1590 | |
---|
| 1591 | \begin{verbatim} |
---|
| 1592 | nnn: obj = xxx infeas = yyy (ddd) |
---|
| 1593 | \end{verbatim} |
---|
| 1594 | |
---|
| 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. |
---|
| 1602 | |
---|
| 1603 | The symbol preceding the iteration number indicates which phase of the |
---|
| 1604 | simplex method is in effect: |
---|
| 1605 | |
---|
| 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; |
---|
| 1609 | |
---|
| 1610 | {\it Asterisk} (\verb|*|) means that the solver is searching for |
---|
| 1611 | optimal solution using the primal simplex; |
---|
| 1612 | |
---|
| 1613 | {\it Vertical dash} (\verb/|/) means that the solver is searching for |
---|
| 1614 | optimal solution using the dual simplex. |
---|
| 1615 | |
---|
| 1616 | \subsubsection*{Control parameters} |
---|
| 1617 | |
---|
| 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|. |
---|
| 1621 | |
---|
| 1622 | \medskip |
---|
| 1623 | |
---|
| 1624 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 1625 | \multicolumn{2}{@{}l}{{\tt int msg\_lev} (default: {\tt GLP\_MSG\_ALL})} |
---|
| 1626 | \\ |
---|
| 1627 | &Message level for terminal output:\\ |
---|
| 1628 | &\verb|GLP_MSG_OFF|---no output;\\ |
---|
| 1629 | &\verb|GLP_MSG_ERR|---error and warning messages only;\\ |
---|
| 1630 | &\verb|GLP_MSG_ON |---normal output;\\ |
---|
| 1631 | &\verb|GLP_MSG_ALL|---full output (including informational messages). |
---|
| 1632 | \\ |
---|
| 1633 | \end{tabular} |
---|
| 1634 | |
---|
| 1635 | \medskip |
---|
| 1636 | |
---|
| 1637 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 1638 | \multicolumn{2}{@{}l}{{\tt int meth} (default: {\tt GLP\_PRIMAL})} |
---|
| 1639 | \\ |
---|
| 1640 | &Simplex method option:\\ |
---|
| 1641 | &\verb|GLP_PRIMAL|---use two-phase primal simplex;\\ |
---|
| 1642 | &\verb|GLP_DUAL |---use two-phase dual simplex;\\ |
---|
| 1643 | &\verb|GLP_DUALP |---use two-phase dual simplex, and if it fails, |
---|
| 1644 | switch to the\\ |
---|
| 1645 | &\verb| |$\:$ primal simplex.\\ |
---|
| 1646 | \end{tabular} |
---|
| 1647 | |
---|
| 1648 | \medskip |
---|
| 1649 | |
---|
| 1650 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 1651 | \multicolumn{2}{@{}l}{{\tt int pricing} (default: {\tt GLP\_PT\_PSE})} |
---|
| 1652 | \\ |
---|
| 1653 | &Pricing technique:\\ |
---|
| 1654 | &\verb|GLP_PT_STD|---standard (textbook);\\ |
---|
| 1655 | &\verb|GLP_PT_PSE|---projected steepest edge.\\ |
---|
| 1656 | \end{tabular} |
---|
| 1657 | |
---|
| 1658 | \medskip |
---|
| 1659 | |
---|
| 1660 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 1661 | \multicolumn{2}{@{}l}{{\tt int r\_test} (default: {\tt GLP\_RT\_HAR})} |
---|
| 1662 | \\ |
---|
| 1663 | &Ratio test technique:\\ |
---|
| 1664 | &\verb|GLP_RT_STD|---standard (textbook);\\ |
---|
| 1665 | &\verb|GLP_RT_HAR|---Harris' two-pass ratio test.\\ |
---|
| 1666 | \end{tabular} |
---|
| 1667 | |
---|
| 1668 | \medskip |
---|
| 1669 | |
---|
| 1670 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 1671 | \multicolumn{2}{@{}l}{{\tt double tol\_bnd} (default: {\tt 1e-7})} |
---|
| 1672 | \\ |
---|
| 1673 | &Tolerance used to check if the basic solution is primal feasible. |
---|
| 1674 | (Do not change this parameter without detailed understanding its |
---|
| 1675 | purpose.)\\ |
---|
| 1676 | \end{tabular} |
---|
| 1677 | |
---|
| 1678 | \medskip |
---|
| 1679 | |
---|
| 1680 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 1681 | \multicolumn{2}{@{}l}{{\tt double tol\_dj} (default: {\tt 1e-7})} |
---|
| 1682 | \\ |
---|
| 1683 | &Tolerance used to check if the basic solution is dual feasible. |
---|
| 1684 | (Do not change this parameter without detailed understanding its |
---|
| 1685 | purpose.)\\ |
---|
| 1686 | \end{tabular} |
---|
| 1687 | |
---|
| 1688 | \medskip |
---|
| 1689 | |
---|
| 1690 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 1691 | \multicolumn{2}{@{}l}{{\tt double tol\_piv} (default: {\tt 1e-10})} |
---|
| 1692 | \\ |
---|
| 1693 | &Tolerance used to choose eligble pivotal elements of the simplex table. |
---|
| 1694 | (Do not change this parameter without detailed understanding its |
---|
| 1695 | purpose.)\\ |
---|
| 1696 | \end{tabular} |
---|
| 1697 | |
---|
| 1698 | \medskip |
---|
| 1699 | |
---|
| 1700 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 1701 | \multicolumn{2}{@{}l}{{\tt double obj\_ll} (default: {\tt -DBL\_MAX})} |
---|
| 1702 | \\ |
---|
| 1703 | &Lower limit of the objective function. If the objective function |
---|
| 1704 | reaches this limit and continues decreasing, the solver terminates the |
---|
| 1705 | search. (Used in the dual simplex only.)\\ |
---|
| 1706 | \end{tabular} |
---|
| 1707 | |
---|
| 1708 | \medskip |
---|
| 1709 | |
---|
| 1710 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 1711 | \multicolumn{2}{@{}l}{{\tt double obj\_ul} (default: {\tt +DBL\_MAX})} |
---|
| 1712 | \\ |
---|
| 1713 | &Upper limit of the objective function. If the objective function |
---|
| 1714 | reaches this limit and continues increasing, the solver terminates the |
---|
| 1715 | search. (Used in the dual simplex only.)\\ |
---|
| 1716 | \end{tabular} |
---|
| 1717 | |
---|
| 1718 | \medskip |
---|
| 1719 | |
---|
| 1720 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 1721 | \multicolumn{2}{@{}l}{{\tt int it\_lim} (default: {\tt INT\_MAX})} |
---|
| 1722 | \\ |
---|
| 1723 | &Simplex iteration limit.\\ |
---|
| 1724 | \end{tabular} |
---|
| 1725 | |
---|
| 1726 | \medskip |
---|
| 1727 | |
---|
| 1728 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 1729 | \multicolumn{2}{@{}l}{{\tt int tm\_lim} (default: {\tt INT\_MAX})} |
---|
| 1730 | \\ |
---|
| 1731 | &Searching time limit, in milliseconds.\\ |
---|
| 1732 | \end{tabular} |
---|
| 1733 | |
---|
| 1734 | \medskip |
---|
| 1735 | |
---|
| 1736 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 1737 | \multicolumn{2}{@{}l}{{\tt int out\_frq} (default: {\tt 500})} |
---|
| 1738 | \\ |
---|
| 1739 | &Output frequency, in iterations. This parameter specifies how |
---|
| 1740 | frequently the solver sends information about the solution process to |
---|
| 1741 | the terminal.\\ |
---|
| 1742 | \end{tabular} |
---|
| 1743 | |
---|
| 1744 | \medskip |
---|
| 1745 | |
---|
| 1746 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 1747 | \multicolumn{2}{@{}l}{{\tt int out\_dly} (default: {\tt 0})} |
---|
| 1748 | \\ |
---|
| 1749 | &Output delay, in milliseconds. This parameter specifies how long the |
---|
| 1750 | solver should delay sending information about the solution process to |
---|
| 1751 | the terminal.\\ |
---|
| 1752 | \end{tabular} |
---|
| 1753 | |
---|
| 1754 | \medskip |
---|
| 1755 | |
---|
| 1756 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 1757 | \multicolumn{2}{@{}l}{{\tt int presolve} (default: {\tt GLP\_OFF})} |
---|
| 1758 | \\ |
---|
| 1759 | &LP presolver option:\\ |
---|
| 1760 | &\verb|GLP_ON |---enable using the LP presolver;\\ |
---|
| 1761 | &\verb|GLP_OFF|---disable using the LP presolver.\\ |
---|
| 1762 | \end{tabular} |
---|
| 1763 | |
---|
| 1764 | \subsubsection*{Example 1} |
---|
| 1765 | |
---|
| 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|. |
---|
| 1772 | |
---|
| 1773 | \newpage |
---|
| 1774 | |
---|
| 1775 | \begin{footnotesize} |
---|
| 1776 | \begin{verbatim} |
---|
| 1777 | /* spxsamp1.c */ |
---|
| 1778 | |
---|
| 1779 | #include <stdio.h> |
---|
| 1780 | #include <stdlib.h> |
---|
| 1781 | #include <glpk.h> |
---|
| 1782 | |
---|
| 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 | } |
---|
| 1793 | |
---|
| 1794 | /* eof */ |
---|
| 1795 | \end{verbatim} |
---|
| 1796 | \end{footnotesize} |
---|
| 1797 | |
---|
| 1798 | \noindent |
---|
| 1799 | Below here is shown the terminal output from this example program. |
---|
| 1800 | |
---|
| 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} |
---|
| 1827 | |
---|
| 1828 | \newpage |
---|
| 1829 | |
---|
| 1830 | \subsubsection*{Example 2} |
---|
| 1831 | |
---|
| 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. |
---|
| 1835 | |
---|
| 1836 | \begin{footnotesize} |
---|
| 1837 | \begin{verbatim} |
---|
| 1838 | /* spxsamp2.c */ |
---|
| 1839 | |
---|
| 1840 | #include <stdio.h> |
---|
| 1841 | #include <stdlib.h> |
---|
| 1842 | #include <glpk.h> |
---|
| 1843 | |
---|
| 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 | } |
---|
| 1856 | |
---|
| 1857 | /* eof */ |
---|
| 1858 | \end{verbatim} |
---|
| 1859 | \end{footnotesize} |
---|
| 1860 | |
---|
| 1861 | \noindent |
---|
| 1862 | Below here is shown the terminal output from this example program. |
---|
| 1863 | |
---|
| 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} |
---|
| 1893 | |
---|
| 1894 | \subsection{glp\_exact---solve LP problem in exact arithmetic} |
---|
| 1895 | |
---|
| 1896 | \subsubsection*{Synopsis} |
---|
| 1897 | |
---|
| 1898 | \begin{verbatim} |
---|
| 1899 | int glp_exact(glp_prob *lp, const glp_smcp *parm); |
---|
| 1900 | \end{verbatim} |
---|
| 1901 | |
---|
| 1902 | \subsubsection*{Description} |
---|
| 1903 | |
---|
| 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. |
---|
| 1910 | |
---|
| 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|. |
---|
| 1914 | |
---|
| 1915 | \subsubsection*{Returns} |
---|
| 1916 | |
---|
| 1917 | \def\arraystretch{1} |
---|
| 1918 | |
---|
| 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} |
---|
| 1938 | |
---|
| 1939 | \subsubsection*{Comments} |
---|
| 1940 | |
---|
| 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. |
---|
| 1947 | |
---|
| 1948 | \subsection{glp\_init\_smcp---initialize simplex solver control |
---|
| 1949 | parameters} |
---|
| 1950 | |
---|
| 1951 | \subsubsection*{Synopsis} |
---|
| 1952 | |
---|
| 1953 | \begin{verbatim} |
---|
| 1954 | int glp_init_smcp(glp_smcp *parm); |
---|
| 1955 | \end{verbatim} |
---|
| 1956 | |
---|
| 1957 | \subsubsection*{Description} |
---|
| 1958 | |
---|
| 1959 | The routine \verb|glp_init_smcp| initializes control parameters, which |
---|
| 1960 | are used by the simplex solver, with default values. |
---|
| 1961 | |
---|
| 1962 | Default values of the control parameters are stored in a \verb|glp_smcp| |
---|
| 1963 | structure, which the parameter \verb|parm| points to. |
---|
| 1964 | |
---|
| 1965 | \subsection{glp\_get\_status---determine generic status of basic |
---|
| 1966 | solution} |
---|
| 1967 | |
---|
| 1968 | \subsubsection*{Synopsis} |
---|
| 1969 | |
---|
| 1970 | \begin{verbatim} |
---|
| 1971 | int glp_get_status(glp_prob *lp); |
---|
| 1972 | \end{verbatim} |
---|
| 1973 | |
---|
| 1974 | \subsubsection*{Returns} |
---|
| 1975 | |
---|
| 1976 | The routine \verb|glp_get_status| reports the generic status of the |
---|
| 1977 | current basic solution for the specified problem object as follows: |
---|
| 1978 | |
---|
| 1979 | \begin{tabular}{@{}ll} |
---|
| 1980 | \verb|GLP_OPT| & solution is optimal; \\ |
---|
| 1981 | \verb|GLP_FEAS| & solution is feasible; \\ |
---|
| 1982 | \verb|GLP_INFEAS| & solution is infeasible; \\ |
---|
| 1983 | \verb|GLP_NOFEAS| & problem has no feasible solution; \\ |
---|
| 1984 | \verb|GLP_UNBND| & problem has unbounded solution; \\ |
---|
| 1985 | \verb|GLP_UNDEF| & solution is undefined. \\ |
---|
| 1986 | \end{tabular} |
---|
| 1987 | |
---|
| 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|. |
---|
| 1991 | |
---|
| 1992 | \newpage |
---|
| 1993 | |
---|
| 1994 | \subsection{glp\_get\_prim\_stat---retrieve status of primal basic |
---|
| 1995 | solution} |
---|
| 1996 | |
---|
| 1997 | \subsubsection*{Synopsis} |
---|
| 1998 | |
---|
| 1999 | \begin{verbatim} |
---|
| 2000 | int glp_get_prim_stat(glp_prob *lp); |
---|
| 2001 | \end{verbatim} |
---|
| 2002 | |
---|
| 2003 | \subsubsection*{Returns} |
---|
| 2004 | |
---|
| 2005 | The routine \verb|glp_get_prim_stat| reports the status of the primal |
---|
| 2006 | basic solution for the specified problem object as follows: |
---|
| 2007 | |
---|
| 2008 | \begin{tabular}{@{}ll} |
---|
| 2009 | \verb|GLP_UNDEF| & primal solution is undefined; \\ |
---|
| 2010 | \verb|GLP_FEAS| & primal solution is feasible; \\ |
---|
| 2011 | \verb|GLP_INFEAS| & primal solution is infeasible; \\ |
---|
| 2012 | \verb|GLP_NOFEAS| & no primal feasible solution exists. \\ |
---|
| 2013 | \end{tabular} |
---|
| 2014 | |
---|
| 2015 | \subsection{glp\_get\_dual\_stat---retrieve status of dual basic |
---|
| 2016 | solution} |
---|
| 2017 | |
---|
| 2018 | \subsubsection*{Synopsis} |
---|
| 2019 | |
---|
| 2020 | \begin{verbatim} |
---|
| 2021 | int glp_get_dual_stat(glp_prob *lp); |
---|
| 2022 | \end{verbatim} |
---|
| 2023 | |
---|
| 2024 | \subsubsection*{Returns} |
---|
| 2025 | |
---|
| 2026 | The routine \verb|glp_get_dual_stat| reports the status of the dual |
---|
| 2027 | basic solution for the specified problem object as follows: |
---|
| 2028 | |
---|
| 2029 | \begin{tabular}{@{}ll} |
---|
| 2030 | \verb|GLP_UNDEF| & dual solution is undefined; \\ |
---|
| 2031 | \verb|GLP_FEAS| & dual solution is feasible; \\ |
---|
| 2032 | \verb|GLP_INFEAS| & dual solution is infeasible; \\ |
---|
| 2033 | \verb|GLP_NOFEAS| & no dual feasible solution exists. \\ |
---|
| 2034 | \end{tabular} |
---|
| 2035 | |
---|
| 2036 | \subsection{glp\_get\_obj\_val---retrieve objective value} |
---|
| 2037 | |
---|
| 2038 | \subsubsection*{Synopsis} |
---|
| 2039 | |
---|
| 2040 | \begin{verbatim} |
---|
| 2041 | double glp_get_obj_val(glp_prob *lp); |
---|
| 2042 | \end{verbatim} |
---|
| 2043 | |
---|
| 2044 | \subsubsection*{Returns} |
---|
| 2045 | |
---|
| 2046 | The routine \verb|glp_get_obj_val| returns current value of the |
---|
| 2047 | objective function. |
---|
| 2048 | |
---|
| 2049 | \subsection{glp\_get\_row\_stat---retrieve row status} |
---|
| 2050 | |
---|
| 2051 | \subsubsection*{Synopsis} |
---|
| 2052 | |
---|
| 2053 | \begin{verbatim} |
---|
| 2054 | int glp_get_row_stat(glp_prob *lp, int i); |
---|
| 2055 | \end{verbatim} |
---|
| 2056 | |
---|
| 2057 | \subsubsection*{Returns} |
---|
| 2058 | |
---|
| 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: |
---|
| 2061 | |
---|
| 2062 | \begin{tabular}{@{}ll} |
---|
| 2063 | \verb|GLP_BS| & basic variable; \\ |
---|
| 2064 | \verb|GLP_NL| & non-basic variable on its lower bound; \\ |
---|
| 2065 | \verb|GLP_NU| & non-basic variable on its upper bound; \\ |
---|
| 2066 | \verb|GLP_NF| & non-basic free (unbounded) variable; \\ |
---|
| 2067 | \verb|GLP_NS| & non-basic fixed variable. \\ |
---|
| 2068 | \end{tabular} |
---|
| 2069 | |
---|
| 2070 | \subsection{glp\_get\_row\_prim---retrieve row primal value} |
---|
| 2071 | |
---|
| 2072 | \subsubsection*{Synopsis} |
---|
| 2073 | |
---|
| 2074 | \begin{verbatim} |
---|
| 2075 | double glp_get_row_prim(glp_prob *lp, int i); |
---|
| 2076 | \end{verbatim} |
---|
| 2077 | |
---|
| 2078 | \subsubsection*{Returns} |
---|
| 2079 | |
---|
| 2080 | The routine \verb|glp_get_row_prim| returns primal value of the |
---|
| 2081 | auxiliary variable associated with \verb|i|-th row. |
---|
| 2082 | |
---|
| 2083 | \subsection{glp\_get\_row\_dual---retrieve row dual value} |
---|
| 2084 | |
---|
| 2085 | \subsubsection*{Synopsis} |
---|
| 2086 | |
---|
| 2087 | \begin{verbatim} |
---|
| 2088 | double glp_get_row_dual(glp_prob *lp, int i); |
---|
| 2089 | \end{verbatim} |
---|
| 2090 | |
---|
| 2091 | \subsubsection*{Returns} |
---|
| 2092 | |
---|
| 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. |
---|
| 2095 | |
---|
| 2096 | \newpage |
---|
| 2097 | |
---|
| 2098 | \subsection{glp\_get\_col\_stat---retrieve column status} |
---|
| 2099 | |
---|
| 2100 | \subsubsection*{Synopsis} |
---|
| 2101 | |
---|
| 2102 | \begin{verbatim} |
---|
| 2103 | int glp_get_col_stat(glp_prob *lp, int j); |
---|
| 2104 | \end{verbatim} |
---|
| 2105 | |
---|
| 2106 | \subsubsection*{Returns} |
---|
| 2107 | |
---|
| 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: |
---|
| 2110 | |
---|
| 2111 | \begin{tabular}{@{}ll} |
---|
| 2112 | \verb|GLP_BS| & basic variable; \\ |
---|
| 2113 | \verb|GLP_NL| & non-basic variable on its lower bound; \\ |
---|
| 2114 | \verb|GLP_NU| & non-basic variable on its upper bound; \\ |
---|
| 2115 | \verb|GLP_NF| & non-basic free (unbounded) variable; \\ |
---|
| 2116 | \verb|GLP_NS| & non-basic fixed variable. \\ |
---|
| 2117 | \end{tabular} |
---|
| 2118 | |
---|
| 2119 | \subsection{glp\_get\_col\_prim---retrieve column primal value} |
---|
| 2120 | |
---|
| 2121 | \subsubsection*{Synopsis} |
---|
| 2122 | |
---|
| 2123 | \begin{verbatim} |
---|
| 2124 | double glp_get_col_prim(glp_prob *lp, int j); |
---|
| 2125 | \end{verbatim} |
---|
| 2126 | |
---|
| 2127 | \subsubsection*{Returns} |
---|
| 2128 | |
---|
| 2129 | The routine \verb|glp_get_col_prim| returns primal value of the |
---|
| 2130 | structural variable associated with \verb|j|-th column. |
---|
| 2131 | |
---|
| 2132 | \subsection{glp\_get\_col\_dual---retrieve column dual value} |
---|
| 2133 | |
---|
| 2134 | \subsubsection*{Synopsis} |
---|
| 2135 | |
---|
| 2136 | \begin{verbatim} |
---|
| 2137 | double glp_get_col_dual(glp_prob *lp, int j); |
---|
| 2138 | \end{verbatim} |
---|
| 2139 | |
---|
| 2140 | \subsubsection*{Returns} |
---|
| 2141 | |
---|
| 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. |
---|
| 2144 | |
---|
| 2145 | \newpage |
---|
| 2146 | |
---|
| 2147 | \subsection{glp\_get\_unbnd\_ray---determine variable causing\\ |
---|
| 2148 | unboundedness} |
---|
| 2149 | |
---|
| 2150 | \subsubsection*{Synopsis} |
---|
| 2151 | |
---|
| 2152 | \begin{verbatim} |
---|
| 2153 | int glp_get_unbnd_ray(glp_prob *lp); |
---|
| 2154 | \end{verbatim} |
---|
| 2155 | |
---|
| 2156 | \subsubsection*{Returns} |
---|
| 2157 | |
---|
| 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. |
---|
| 2164 | |
---|
| 2165 | \subsubsection*{Comments} |
---|
| 2166 | |
---|
| 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). |
---|
| 2174 | |
---|
| 2175 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
| 2176 | |
---|
| 2177 | \newpage |
---|
| 2178 | |
---|
| 2179 | \section{Interior-point method routines} |
---|
| 2180 | |
---|
| 2181 | {\it Interior-point methods} (also known as {\it barrier methods}) are |
---|
| 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. |
---|
| 2186 | |
---|
| 2187 | In brief, the GLPK interior-point solver works as follows. |
---|
| 2188 | |
---|
| 2189 | At first, the solver transforms the original LP to a {\it working} LP |
---|
| 2190 | in the standard format: |
---|
| 2191 | |
---|
| 2192 | \medskip |
---|
| 2193 | |
---|
| 2194 | \noindent |
---|
| 2195 | \hspace{.5in} minimize |
---|
| 2196 | $$z = c_1x_{m+1} + c_2x_{m+2} + \dots + c_nx_{m+n} + c_0 \eqno (2.4)$$ |
---|
| 2197 | \hspace{.5in} subject to linear constraints |
---|
| 2198 | $$ |
---|
| 2199 | \begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}l} |
---|
| 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. |
---|
| 2213 | |
---|
| 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. |
---|
| 2223 | |
---|
| 2224 | Karush--Kuhn--Tucker optimality conditions for LP (2.7)---(2.9) are the |
---|
| 2225 | following: |
---|
| 2226 | |
---|
| 2227 | \newpage |
---|
| 2228 | |
---|
| 2229 | $$Ax=b,\eqno(2.10)$$ |
---|
| 2230 | $$A^T\pi+\lambda=c,\eqno(2.11)$$ |
---|
| 2231 | $$\lambda^Tx=0,\eqno(2.12)$$ |
---|
| 2232 | $$x\geq 0,\ \ \lambda\geq 0,\eqno(2.13)$$ |
---|
| 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. |
---|
| 2239 | |
---|
| 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). |
---|
| 2246 | |
---|
| 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). |
---|
| 2255 | |
---|
| 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. |
---|
| 2260 | |
---|
| 2261 | \subsection{glp\_interior---solve LP problem with the interior-point |
---|
| 2262 | method} |
---|
| 2263 | |
---|
| 2264 | \subsubsection*{Synopsis} |
---|
| 2265 | |
---|
| 2266 | \begin{verbatim} |
---|
| 2267 | int glp_interior(glp_prob *P, const glp_iptcp *parm); |
---|
| 2268 | \end{verbatim} |
---|
| 2269 | |
---|
| 2270 | \subsubsection*{Description} |
---|
| 2271 | |
---|
| 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. |
---|
| 2277 | |
---|
| 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|. |
---|
| 2288 | |
---|
| 2289 | The parameter \verb|parm| can be specified as \verb|NULL|, in which |
---|
| 2290 | case the solver uses default settings. |
---|
| 2291 | |
---|
| 2292 | \subsubsection*{Returns} |
---|
| 2293 | |
---|
| 2294 | \def\arraystretch{1} |
---|
| 2295 | |
---|
| 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} |
---|
| 2306 | |
---|
| 2307 | \subsubsection*{Comments} |
---|
| 2308 | |
---|
| 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.} |
---|
| 2313 | |
---|
| 2314 | Note that currently the GLPK interior-point solver does not include |
---|
| 2315 | many important features, in particular: |
---|
| 2316 | |
---|
| 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; |
---|
| 2320 | |
---|
| 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; |
---|
| 2324 | |
---|
| 2325 | $\bullet$ it is not able to identify the optimal basis, which |
---|
| 2326 | corresponds to the interior-point solution found. |
---|
| 2327 | |
---|
| 2328 | \newpage |
---|
| 2329 | |
---|
| 2330 | \subsubsection*{Terminal output} |
---|
| 2331 | |
---|
| 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: |
---|
| 2338 | |
---|
| 2339 | \begin{verbatim} |
---|
| 2340 | nnn: obj = fff; rpi = ppp; rdi = ddd; gap = ggg |
---|
| 2341 | \end{verbatim} |
---|
| 2342 | |
---|
| 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. |
---|
| 2356 | |
---|
| 2357 | \subsubsection*{Control parameters} |
---|
| 2358 | |
---|
| 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|. |
---|
| 2362 | |
---|
| 2363 | \medskip |
---|
| 2364 | |
---|
| 2365 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2366 | \multicolumn{2}{@{}l}{{\tt int msg\_lev} (default: {\tt GLP\_MSG\_ALL})} |
---|
| 2367 | \\ |
---|
| 2368 | &Message level for terminal output:\\ |
---|
| 2369 | &\verb|GLP_MSG_OFF|---no output;\\ |
---|
| 2370 | &\verb|GLP_MSG_ERR|---error and warning messages only;\\ |
---|
| 2371 | &\verb|GLP_MSG_ON |---normal output;\\ |
---|
| 2372 | &\verb|GLP_MSG_ALL|---full output (including informational messages). |
---|
| 2373 | \\ |
---|
| 2374 | \end{tabular} |
---|
| 2375 | |
---|
| 2376 | \medskip |
---|
| 2377 | |
---|
| 2378 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2379 | \multicolumn{2}{@{}l}{{\tt int ord\_alg} (default: {\tt GLP\_ORD\_AMD})} |
---|
| 2380 | \\ |
---|
| 2381 | &Ordering algorithm used prior to Cholesky factorization:\\ |
---|
| 2382 | &\verb|GLP_ORD_NONE |---use natural (original) ordering;\\ |
---|
| 2383 | &\verb|GLP_ORD_QMD |---quotient minimum degree (QMD);\\ |
---|
| 2384 | &\verb|GLP_ORD_AMD |---approximate minimum degree (AMD);\\ |
---|
| 2385 | &\verb|GLP_ORD_SYMAMD|---approximate minimum degree (SYMAMD).\\ |
---|
| 2386 | \end{tabular} |
---|
| 2387 | |
---|
| 2388 | \subsubsection*{Example} |
---|
| 2389 | |
---|
| 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|. |
---|
| 2395 | |
---|
| 2396 | \begin{footnotesize} |
---|
| 2397 | \begin{verbatim} |
---|
| 2398 | /* iptsamp.c */ |
---|
| 2399 | |
---|
| 2400 | #include <stdio.h> |
---|
| 2401 | #include <stdlib.h> |
---|
| 2402 | #include <glpk.h> |
---|
| 2403 | |
---|
| 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 | } |
---|
| 2413 | |
---|
| 2414 | /* eof */ |
---|
| 2415 | \end{verbatim} |
---|
| 2416 | \end{footnotesize} |
---|
| 2417 | |
---|
| 2418 | \noindent |
---|
| 2419 | Below here is shown the terminal output from this example program. |
---|
| 2420 | |
---|
| 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} |
---|
| 2470 | |
---|
| 2471 | \subsection{glp\_init\_iptcp---initialize interior-point solver control |
---|
| 2472 | parameters} |
---|
| 2473 | |
---|
| 2474 | \subsubsection*{Synopsis} |
---|
| 2475 | |
---|
| 2476 | \begin{verbatim} |
---|
| 2477 | int glp_init_iptcp(glp_iptcp *parm); |
---|
| 2478 | \end{verbatim} |
---|
| 2479 | |
---|
| 2480 | \subsubsection*{Description} |
---|
| 2481 | |
---|
| 2482 | The routine \verb|glp_init_iptcp| initializes control parameters, which |
---|
| 2483 | are used by the interior-point solver, with default values. |
---|
| 2484 | |
---|
| 2485 | Default values of the control parameters are stored in the structure |
---|
| 2486 | \verb|glp_iptcp|, which the parameter \verb|parm| points to. |
---|
| 2487 | |
---|
| 2488 | \subsection{glp\_ipt\_status---determine solution status} |
---|
| 2489 | |
---|
| 2490 | \subsubsection*{Synopsis} |
---|
| 2491 | |
---|
| 2492 | \begin{verbatim} |
---|
| 2493 | int glp_ipt_status(glp_prob *lp); |
---|
| 2494 | \end{verbatim} |
---|
| 2495 | |
---|
| 2496 | \subsubsection*{Returns} |
---|
| 2497 | |
---|
| 2498 | The routine \verb|glp_ipt_status| reports the status of a solution |
---|
| 2499 | found by the interior-point solver as follows: |
---|
| 2500 | |
---|
| 2501 | \begin{tabular}{@{}p{25mm}p{91.3mm}@{}} |
---|
| 2502 | \verb|GLP_UNDEF| & interior-point solution is undefined. \\ |
---|
| 2503 | \verb|GLP_OPT| & interior-point solution is optimal. \\ |
---|
| 2504 | \verb|GLP_INFEAS|& interior-point solution is infeasible. \\ |
---|
| 2505 | \verb|GLP_NOFEAS|& no feasible primal-dual solution exists.\\ |
---|
| 2506 | \end{tabular} |
---|
| 2507 | |
---|
| 2508 | \subsection{glp\_ipt\_obj\_val---retrieve objective value} |
---|
| 2509 | |
---|
| 2510 | \subsubsection*{Synopsis} |
---|
| 2511 | |
---|
| 2512 | \begin{verbatim} |
---|
| 2513 | double glp_ipt_obj_val(glp_prob *lp); |
---|
| 2514 | \end{verbatim} |
---|
| 2515 | |
---|
| 2516 | \subsubsection*{Returns} |
---|
| 2517 | |
---|
| 2518 | The routine \verb|glp_ipt_obj_val| returns value of the objective |
---|
| 2519 | function for interior-point solution. |
---|
| 2520 | |
---|
| 2521 | \subsection{glp\_ipt\_row\_prim---retrieve row primal value} |
---|
| 2522 | |
---|
| 2523 | \subsubsection*{Synopsis} |
---|
| 2524 | |
---|
| 2525 | \begin{verbatim} |
---|
| 2526 | double glp_ipt_row_prim(glp_prob *lp, int i); |
---|
| 2527 | \end{verbatim} |
---|
| 2528 | |
---|
| 2529 | \subsubsection*{Returns} |
---|
| 2530 | |
---|
| 2531 | The routine \verb|glp_ipt_row_prim| returns primal value of the |
---|
| 2532 | auxiliary variable associated with \verb|i|-th row. |
---|
| 2533 | |
---|
| 2534 | \newpage |
---|
| 2535 | |
---|
| 2536 | \subsection{glp\_ipt\_row\_dual---retrieve row dual value} |
---|
| 2537 | |
---|
| 2538 | \subsubsection*{Synopsis} |
---|
| 2539 | |
---|
| 2540 | \begin{verbatim} |
---|
| 2541 | double glp_ipt_row_dual(glp_prob *lp, int i); |
---|
| 2542 | \end{verbatim} |
---|
| 2543 | |
---|
| 2544 | \subsubsection*{Returns} |
---|
| 2545 | |
---|
| 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. |
---|
| 2548 | |
---|
| 2549 | \subsection{glp\_ipt\_col\_prim---retrieve column primal value} |
---|
| 2550 | |
---|
| 2551 | \subsubsection*{Synopsis} |
---|
| 2552 | |
---|
| 2553 | \begin{verbatim} |
---|
| 2554 | double glp_ipt_col_prim(glp_prob *lp, int j); |
---|
| 2555 | \end{verbatim} |
---|
| 2556 | |
---|
| 2557 | \subsubsection*{Returns} |
---|
| 2558 | |
---|
| 2559 | The routine \verb|glp_ipt_col_prim| returns primal value of the |
---|
| 2560 | structural variable associated with \verb|j|-th column. |
---|
| 2561 | |
---|
| 2562 | \subsection{glp\_ipt\_col\_dual---retrieve column dual value} |
---|
| 2563 | |
---|
| 2564 | \subsubsection*{Synopsis} |
---|
| 2565 | |
---|
| 2566 | \begin{verbatim} |
---|
| 2567 | double glp_ipt_col_dual(glp_prob *lp, int j); |
---|
| 2568 | \end{verbatim} |
---|
| 2569 | |
---|
| 2570 | \subsubsection*{Returns} |
---|
| 2571 | |
---|
| 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. |
---|
| 2574 | |
---|
| 2575 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
| 2576 | |
---|
| 2577 | \newpage |
---|
| 2578 | |
---|
| 2579 | \section{Mixed integer programming routines} |
---|
| 2580 | |
---|
| 2581 | \subsection{glp\_set\_col\_kind---set (change) column kind} |
---|
| 2582 | |
---|
| 2583 | \subsubsection*{Synopsis} |
---|
| 2584 | |
---|
| 2585 | \begin{verbatim} |
---|
| 2586 | void glp_set_col_kind(glp_prob *mip, int j, int kind); |
---|
| 2587 | \end{verbatim} |
---|
| 2588 | |
---|
| 2589 | \subsubsection*{Description} |
---|
| 2590 | |
---|
| 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|: |
---|
| 2594 | |
---|
| 2595 | \begin{tabular}{@{}ll} |
---|
| 2596 | \verb|GLP_CV| & continuous variable; \\ |
---|
| 2597 | \verb|GLP_IV| & integer variable; \\ |
---|
| 2598 | \verb|GLP_BV| & binary variable. \\ |
---|
| 2599 | \end{tabular} |
---|
| 2600 | |
---|
| 2601 | %If a column is set to \verb|GLP_IV|, its bounds must be exact integer |
---|
| 2602 | %numbers with no tolerance, such that the condition |
---|
| 2603 | %\verb|bnd == floor(bnd)| would hold. |
---|
| 2604 | |
---|
| 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. |
---|
| 2608 | |
---|
| 2609 | \subsection{glp\_get\_col\_kind---retrieve column kind} |
---|
| 2610 | |
---|
| 2611 | \subsubsection*{Synopsis} |
---|
| 2612 | |
---|
| 2613 | \begin{verbatim} |
---|
| 2614 | int glp_get_col_kind(glp_prob *mip, int j); |
---|
| 2615 | \end{verbatim} |
---|
| 2616 | |
---|
| 2617 | \subsubsection*{Returns} |
---|
| 2618 | |
---|
| 2619 | The routine \verb|glp_get_col_kind| returns the kind of \verb|j|-th |
---|
| 2620 | column (structural variable) as follows: |
---|
| 2621 | |
---|
| 2622 | \begin{tabular}{@{}ll} |
---|
| 2623 | \verb|GLP_CV| & continuous variable; \\ |
---|
| 2624 | \verb|GLP_IV| & integer variable; \\ |
---|
| 2625 | \verb|GLP_BV| & binary variable. \\ |
---|
| 2626 | \end{tabular} |
---|
| 2627 | |
---|
| 2628 | \subsection{glp\_get\_num\_int---retrieve number of integer columns} |
---|
| 2629 | |
---|
| 2630 | \subsubsection*{Synopsis} |
---|
| 2631 | |
---|
| 2632 | \begin{verbatim} |
---|
| 2633 | int glp_get_num_int(glp_prob *mip); |
---|
| 2634 | \end{verbatim} |
---|
| 2635 | |
---|
| 2636 | \subsubsection*{Returns} |
---|
| 2637 | |
---|
| 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. |
---|
| 2641 | |
---|
| 2642 | \subsection{glp\_get\_num\_bin---retrieve number of binary columns} |
---|
| 2643 | |
---|
| 2644 | \subsubsection*{Synopsis} |
---|
| 2645 | |
---|
| 2646 | \begin{verbatim} |
---|
| 2647 | int glp_get_num_bin(glp_prob *mip); |
---|
| 2648 | \end{verbatim} |
---|
| 2649 | |
---|
| 2650 | \subsubsection*{Returns} |
---|
| 2651 | |
---|
| 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. |
---|
| 2655 | |
---|
| 2656 | \subsection{glp\_intopt---solve MIP problem with the branch-and-cut |
---|
| 2657 | method} |
---|
| 2658 | |
---|
| 2659 | \subsubsection*{Synopsis} |
---|
| 2660 | |
---|
| 2661 | \begin{verbatim} |
---|
| 2662 | int glp_intopt(glp_prob *mip, const glp_iocp *parm); |
---|
| 2663 | \end{verbatim} |
---|
| 2664 | |
---|
| 2665 | \subsubsection*{Description} |
---|
| 2666 | |
---|
| 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. |
---|
| 2670 | |
---|
| 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. |
---|
| 2677 | |
---|
| 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|. |
---|
| 2687 | |
---|
| 2688 | The parameter \verb|parm| can be specified as \verb|NULL|, in which case |
---|
| 2689 | the solver uses default settings. |
---|
| 2690 | |
---|
| 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. |
---|
| 2693 | |
---|
| 2694 | \subsubsection*{Returns} |
---|
| 2695 | |
---|
| 2696 | \def\arraystretch{1} |
---|
| 2697 | |
---|
| 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} |
---|
| 2727 | |
---|
| 2728 | \subsubsection*{Built-in MIP presolver} |
---|
| 2729 | |
---|
| 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. |
---|
| 2739 | |
---|
| 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). |
---|
| 2744 | |
---|
| 2745 | \subsubsection*{Advanced solver interface} |
---|
| 2746 | |
---|
| 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''. |
---|
| 2750 | |
---|
| 2751 | \subsubsection*{Terminal output} |
---|
| 2752 | |
---|
| 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: |
---|
| 2756 | |
---|
| 2757 | \begin{verbatim} |
---|
| 2758 | +nnn: mip = xxx <rho> yyy gap (ppp; qqq) |
---|
| 2759 | \end{verbatim} |
---|
| 2760 | |
---|
| 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. |
---|
| 2775 | |
---|
| 2776 | \subsubsection{Control parameters} |
---|
| 2777 | |
---|
| 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|. |
---|
| 2781 | |
---|
| 2782 | \medskip |
---|
| 2783 | |
---|
| 2784 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2785 | \multicolumn{2}{@{}l}{{\tt int msg\_lev} (default: {\tt GLP\_MSG\_ALL})} |
---|
| 2786 | \\ |
---|
| 2787 | &Message level for terminal output:\\ |
---|
| 2788 | &\verb|GLP_MSG_OFF|---no output;\\ |
---|
| 2789 | &\verb|GLP_MSG_ERR|---error and warning messages only;\\ |
---|
| 2790 | &\verb|GLP_MSG_ON |---normal output;\\ |
---|
| 2791 | &\verb|GLP_MSG_ALL|---full output (including informational messages). |
---|
| 2792 | \\ |
---|
| 2793 | \end{tabular} |
---|
| 2794 | |
---|
| 2795 | \medskip |
---|
| 2796 | |
---|
| 2797 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2798 | \multicolumn{2}{@{}l}{{\tt int br\_tech} (default: {\tt GLP\_BR\_DTH})} |
---|
| 2799 | \\ |
---|
| 2800 | &Branching technique option:\\ |
---|
| 2801 | &\verb|GLP_BR_FFV|---first fractional variable;\\ |
---|
| 2802 | &\verb|GLP_BR_LFV|---last fractional variable;\\ |
---|
| 2803 | &\verb|GLP_BR_MFV|---most fractional variable;\\ |
---|
| 2804 | &\verb|GLP_BR_DTH|---heuristic by Driebeck and Tomlin;\\ |
---|
| 2805 | &\verb|GLP_BR_PCH|---hybrid pseudocost heuristic.\\ |
---|
| 2806 | \end{tabular} |
---|
| 2807 | |
---|
| 2808 | \medskip |
---|
| 2809 | |
---|
| 2810 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2811 | \multicolumn{2}{@{}l}{{\tt int bt\_tech} (default: {\tt GLP\_BT\_BLB})} |
---|
| 2812 | \\ |
---|
| 2813 | &Backtracking technique option:\\ |
---|
| 2814 | &\verb|GLP_BT_DFS|---depth first search;\\ |
---|
| 2815 | &\verb|GLP_BT_BFS|---breadth first search;\\ |
---|
| 2816 | &\verb|GLP_BT_BLB|---best local bound;\\ |
---|
| 2817 | &\verb|GLP_BT_BPH|---best projection heuristic.\\ |
---|
| 2818 | \end{tabular} |
---|
| 2819 | |
---|
| 2820 | \medskip |
---|
| 2821 | |
---|
| 2822 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2823 | \multicolumn{2}{@{}l}{{\tt int pp\_tech} (default: {\tt GLP\_PP\_ALL})} |
---|
| 2824 | \\ |
---|
| 2825 | &Preprocessing technique option:\\ |
---|
| 2826 | &\verb|GLP_PP_NONE|---disable preprocessing;\\ |
---|
| 2827 | &\verb|GLP_PP_ROOT|---perform preprocessing only on the root level;\\ |
---|
| 2828 | &\verb|GLP_PP_ALL |---perform preprocessing on all levels.\\ |
---|
| 2829 | \end{tabular} |
---|
| 2830 | |
---|
| 2831 | \medskip |
---|
| 2832 | |
---|
| 2833 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2834 | \multicolumn{2}{@{}l}{{\tt int fp\_heur} (default: {\tt GLP\_OFF})} |
---|
| 2835 | \\ |
---|
| 2836 | &Feasibility pump heuristic option:\\ |
---|
| 2837 | &\verb|GLP_ON |---enable applying the feasibility pump heuristic;\\ |
---|
| 2838 | &\verb|GLP_OFF|---disable applying the feasibility pump heuristic.\\ |
---|
| 2839 | \end{tabular} |
---|
| 2840 | |
---|
| 2841 | \medskip |
---|
| 2842 | |
---|
| 2843 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2844 | \multicolumn{2}{@{}l}{{\tt int gmi\_cuts} (default: {\tt GLP\_OFF})}\\ |
---|
| 2845 | &Gomory's mixed integer cut option:\\ |
---|
| 2846 | &\verb|GLP_ON |---enable generating Gomory's cuts;\\ |
---|
| 2847 | &\verb|GLP_OFF|---disable generating Gomory's cuts.\\ |
---|
| 2848 | \end{tabular} |
---|
| 2849 | |
---|
| 2850 | \medskip |
---|
| 2851 | |
---|
| 2852 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2853 | \multicolumn{2}{@{}l}{{\tt int mir\_cuts} (default: {\tt GLP\_OFF})}\\ |
---|
| 2854 | &Mixed integer rounding (MIR) cut option:\\ |
---|
| 2855 | &\verb|GLP_ON |---enable generating MIR cuts;\\ |
---|
| 2856 | &\verb|GLP_OFF|---disable generating MIR cuts.\\ |
---|
| 2857 | \end{tabular} |
---|
| 2858 | |
---|
| 2859 | \medskip |
---|
| 2860 | |
---|
| 2861 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2862 | \multicolumn{2}{@{}l}{{\tt int cov\_cuts} (default: {\tt GLP\_OFF})}\\ |
---|
| 2863 | &Mixed cover cut option:\\ |
---|
| 2864 | &\verb|GLP_ON |---enable generating mixed cover cuts;\\ |
---|
| 2865 | &\verb|GLP_OFF|---disable generating mixed cover cuts.\\ |
---|
| 2866 | \end{tabular} |
---|
| 2867 | |
---|
| 2868 | \medskip |
---|
| 2869 | |
---|
| 2870 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2871 | \multicolumn{2}{@{}l}{{\tt int clq\_cuts} (default: {\tt GLP\_OFF})}\\ |
---|
| 2872 | &Clique cut option:\\ |
---|
| 2873 | &\verb|GLP_ON |---enable generating clique cuts;\\ |
---|
| 2874 | &\verb|GLP_OFF|---disable generating clique cuts.\\ |
---|
| 2875 | \end{tabular} |
---|
| 2876 | |
---|
| 2877 | \medskip |
---|
| 2878 | |
---|
| 2879 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2880 | \multicolumn{2}{@{}l}{{\tt double tol\_int} (default: {\tt 1e-5})}\\ |
---|
| 2881 | &Absolute tolerance used to check if optimal solution to the current LP |
---|
| 2882 | relaxation is integer feasible. (Do not change this parameter without |
---|
| 2883 | detailed understanding its purpose.)\\ |
---|
| 2884 | \end{tabular} |
---|
| 2885 | |
---|
| 2886 | \medskip |
---|
| 2887 | |
---|
| 2888 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2889 | \multicolumn{2}{@{}l}{{\tt double tol\_obj} (default: {\tt 1e-7})}\\ |
---|
| 2890 | &Relative tolerance used to check if the objective value in optimal |
---|
| 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} |
---|
| 2895 | |
---|
| 2896 | \medskip |
---|
| 2897 | |
---|
| 2898 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2899 | \multicolumn{2}{@{}l}{{\tt double mip\_gap} (default: {\tt 0.0})}\\ |
---|
| 2900 | &The relative mip gap tolerance. If the relative mip gap for currently |
---|
| 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} |
---|
| 2906 | |
---|
| 2907 | \medskip |
---|
| 2908 | |
---|
| 2909 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2910 | \multicolumn{2}{@{}l}{{\tt int tm\_lim} (default: {\tt INT\_MAX})}\\ |
---|
| 2911 | &Searching time limit, in milliseconds.\\ |
---|
| 2912 | \end{tabular} |
---|
| 2913 | |
---|
| 2914 | \medskip |
---|
| 2915 | |
---|
| 2916 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2917 | \multicolumn{2}{@{}l}{{\tt int out\_frq} (default: {\tt 5000})}\\ |
---|
| 2918 | &Output frequency, in milliseconds. This parameter specifies how |
---|
| 2919 | frequently the solver sends information about the solution process to |
---|
| 2920 | the terminal.\\ |
---|
| 2921 | \end{tabular} |
---|
| 2922 | |
---|
| 2923 | \medskip |
---|
| 2924 | |
---|
| 2925 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2926 | \multicolumn{2}{@{}l}{{\tt int out\_dly} (default: {\tt 10000})}\\ |
---|
| 2927 | &Output delay, in milliseconds. This parameter specifies how long the |
---|
| 2928 | solver should delay sending information about solution of the current |
---|
| 2929 | LP relaxation with the simplex method to the terminal.\\ |
---|
| 2930 | \end{tabular} |
---|
| 2931 | |
---|
| 2932 | \medskip |
---|
| 2933 | |
---|
| 2934 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2935 | \multicolumn{2}{@{}l} |
---|
| 2936 | {{\tt void (*cb\_func)(glp\_tree *tree, void *info)} |
---|
| 2937 | (default: {\tt NULL})}\\ |
---|
| 2938 | &Entry point to the user-defined callback routine. \verb|NULL| means |
---|
| 2939 | the advanced solver interface is not used. For more details see Chapter |
---|
| 2940 | ``Branch-and-Cut API Routines''.\\ |
---|
| 2941 | \end{tabular} |
---|
| 2942 | |
---|
| 2943 | \medskip |
---|
| 2944 | |
---|
| 2945 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2946 | \multicolumn{2}{@{}l}{{\tt void *cb\_info} (default: {\tt NULL})}\\ |
---|
| 2947 | &Transit pointer passed to the routine \verb|cb_func| (see above).\\ |
---|
| 2948 | \end{tabular} |
---|
| 2949 | |
---|
| 2950 | \medskip |
---|
| 2951 | |
---|
| 2952 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2953 | \multicolumn{2}{@{}l}{{\tt int cb\_size} (default: {\tt 0})}\\ |
---|
| 2954 | &The number of extra (up to 256) bytes allocated for each node of the |
---|
| 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} |
---|
| 2958 | |
---|
| 2959 | \medskip |
---|
| 2960 | |
---|
| 2961 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2962 | \multicolumn{2}{@{}l}{{\tt int presolve} (default: {\tt GLP\_OFF})}\\ |
---|
| 2963 | &MIP presolver option:\\ |
---|
| 2964 | &\verb|GLP_ON |---enable using the MIP presolver;\\ |
---|
| 2965 | &\verb|GLP_OFF|---disable using the MIP presolver.\\ |
---|
| 2966 | \end{tabular} |
---|
| 2967 | |
---|
| 2968 | \medskip |
---|
| 2969 | |
---|
| 2970 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 2971 | \multicolumn{2}{@{}l}{{\tt int binarize} (default: {\tt GLP\_OFF})}\\ |
---|
| 2972 | &Binarization option (used only if the presolver is enabled):\\ |
---|
| 2973 | &\verb|GLP_ON |---replace general integer variables by binary ones;\\ |
---|
| 2974 | &\verb|GLP_OFF|---do not use binarization.\\ |
---|
| 2975 | \end{tabular} |
---|
| 2976 | |
---|
| 2977 | \subsection{glp\_init\_iocp---initialize integer optimizer control |
---|
| 2978 | parameters} |
---|
| 2979 | |
---|
| 2980 | \subsubsection*{Synopsis} |
---|
| 2981 | |
---|
| 2982 | \begin{verbatim} |
---|
| 2983 | void glp_init_iocp(glp_iocp *parm); |
---|
| 2984 | \end{verbatim} |
---|
| 2985 | |
---|
| 2986 | \subsubsection*{Description} |
---|
| 2987 | |
---|
| 2988 | The routine \verb|glp_init_iocp| initializes control parameters, which |
---|
| 2989 | are used by the branch-and-cut solver, with default values. |
---|
| 2990 | |
---|
| 2991 | Default values of the control parameters are stored in a \verb|glp_iocp| |
---|
| 2992 | structure, which the parameter \verb|parm| points to. |
---|
| 2993 | |
---|
| 2994 | \subsection{glp\_mip\_status---determine status of MIP solution} |
---|
| 2995 | |
---|
| 2996 | \subsubsection*{Synopsis} |
---|
| 2997 | |
---|
| 2998 | \begin{verbatim} |
---|
| 2999 | int glp_mip_status(glp_prob *mip); |
---|
| 3000 | \end{verbatim} |
---|
| 3001 | |
---|
| 3002 | \subsubsection*{Returns} |
---|
| 3003 | |
---|
| 3004 | The routine \verb|glp_mip_status| reports the status of a MIP solution |
---|
| 3005 | found by the MIP solver as follows: |
---|
| 3006 | |
---|
| 3007 | \smallskip |
---|
| 3008 | |
---|
| 3009 | \begin{tabular}{@{}p{25mm}p{91.3mm}@{}} |
---|
| 3010 | \verb|GLP_UNDEF| & MIP solution is undefined. \\ |
---|
| 3011 | \verb|GLP_OPT| & MIP solution is integer optimal. \\ |
---|
| 3012 | \verb|GLP_FEAS| & MIP solution is integer feasible, however, its |
---|
| 3013 | optimality (or non-optimality) has not been proven, perhaps due to |
---|
| 3014 | premature termination of the search. \\ |
---|
| 3015 | \end{tabular} |
---|
| 3016 | |
---|
| 3017 | \begin{tabular}{@{}p{25mm}p{91.3mm}@{}} |
---|
| 3018 | \verb|GLP_NOFEAS| & problem has no integer feasible solution (proven by |
---|
| 3019 | the solver). \\ |
---|
| 3020 | \end{tabular} |
---|
| 3021 | |
---|
| 3022 | \subsection{glp\_mip\_obj\_val---retrieve objective value} |
---|
| 3023 | |
---|
| 3024 | \subsubsection*{Synopsis} |
---|
| 3025 | |
---|
| 3026 | \begin{verbatim} |
---|
| 3027 | double glp_mip_obj_val(glp_prob *mip); |
---|
| 3028 | \end{verbatim} |
---|
| 3029 | |
---|
| 3030 | \subsubsection*{Returns} |
---|
| 3031 | |
---|
| 3032 | The routine \verb|glp_mip_obj_val| returns value of the objective |
---|
| 3033 | function for MIP solution. |
---|
| 3034 | |
---|
| 3035 | \subsection{glp\_mip\_row\_val---retrieve row value} |
---|
| 3036 | |
---|
| 3037 | \subsubsection*{Synopsis} |
---|
| 3038 | |
---|
| 3039 | \begin{verbatim} |
---|
| 3040 | double glp_mip_row_val(glp_prob *mip, int i); |
---|
| 3041 | \end{verbatim} |
---|
| 3042 | |
---|
| 3043 | \subsubsection*{Returns} |
---|
| 3044 | |
---|
| 3045 | The routine \verb|glp_mip_row_val| returns value of the auxiliary |
---|
| 3046 | variable associated with \verb|i|-th row for MIP solution. |
---|
| 3047 | |
---|
| 3048 | \subsection{glp\_mip\_col\_val---retrieve column value} |
---|
| 3049 | |
---|
| 3050 | \subsubsection*{Synopsis} |
---|
| 3051 | |
---|
| 3052 | \begin{verbatim} |
---|
| 3053 | double glp_mip_col_val(glp_prob *mip, int j); |
---|
| 3054 | \end{verbatim} |
---|
| 3055 | |
---|
| 3056 | \subsubsection*{Returns} |
---|
| 3057 | |
---|
| 3058 | The routine \verb|glp_mip_col_val| returns value of the structural |
---|
| 3059 | variable associated with \verb|j|-th column for MIP solution. |
---|
| 3060 | |
---|
| 3061 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
| 3062 | |
---|
| 3063 | \newpage |
---|
| 3064 | |
---|
| 3065 | \section{Additional routines} |
---|
| 3066 | |
---|
| 3067 | \subsection{lpx\_check\_kkt---check Karush-Kuhn-Tucker optimality |
---|
| 3068 | conditions} |
---|
| 3069 | |
---|
| 3070 | \subsubsection*{Synopsis} |
---|
| 3071 | |
---|
| 3072 | \begin{verbatim} |
---|
| 3073 | void lpx_check_kkt(glp_prob *lp, int scaled, LPXKKT *kkt); |
---|
| 3074 | \end{verbatim} |
---|
| 3075 | |
---|
| 3076 | \subsubsection*{Description} |
---|
| 3077 | |
---|
| 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. |
---|
| 3081 | |
---|
| 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. |
---|
| 3086 | |
---|
| 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. |
---|
| 3090 | |
---|
| 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} |
---|
| 3142 | |
---|
| 3143 | The routine performs all computations using only components of the |
---|
| 3144 | given LP problem and the current basic solution. |
---|
| 3145 | |
---|
| 3146 | \subsubsection*{Background} |
---|
| 3147 | |
---|
| 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. |
---|
| 3159 | |
---|
| 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. |
---|
| 3173 | |
---|
| 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. |
---|
| 3188 | |
---|
| 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. |
---|
| 3215 | |
---|
| 3216 | The last, fourth condition checked by the routine is (KKT.DB): |
---|
| 3217 | |
---|
| 3218 | \medskip |
---|
| 3219 | |
---|
| 3220 | \begin{tabular}{r@{}c@{}ll} |
---|
| 3221 | &$\ d_k\ $& $=0,$&if $x_k$ is basic or free non-basic variable \\ |
---|
| 3222 | $0\leq$&$\ d_k\ $&$<+\infty$&if $x_k$ is non-basic on its lower |
---|
| 3223 | (minimization) \\ |
---|
| 3224 | &&&or upper (maximization) bound \\ |
---|
| 3225 | $-\infty<$&$\ d_k\ $&$\leq 0$&if $x_k$ is non-basic on its upper |
---|
| 3226 | (minimization) \\ |
---|
| 3227 | &&&or lower (maximization) bound \\ |
---|
| 3228 | $-\infty<$&$\ d_k\ $&$<+\infty$&if $x_k$ is non-basic fixed variable \\ |
---|
| 3229 | \end{tabular} |
---|
| 3230 | |
---|
| 3231 | \medskip |
---|
| 3232 | |
---|
| 3233 | \noindent |
---|
| 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. |
---|
| 3245 | |
---|
| 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. |
---|
| 3252 | |
---|
| 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: |
---|
| 3258 | |
---|
| 3259 | \medskip |
---|
| 3260 | |
---|
| 3261 | \hspace{30mm} |
---|
| 3262 | \verb|pe_ae_max| $\displaystyle{= \max_{1\leq i\leq m}|g_i|}$, |
---|
| 3263 | |
---|
| 3264 | \medskip |
---|
| 3265 | |
---|
| 3266 | \hspace{30mm} |
---|
| 3267 | \verb|pe_re_max| $\displaystyle{= \max_{1\leq i\leq m} |
---|
| 3268 | \frac{|g_i|}{1+|(x_R)_i|}}$, |
---|
| 3269 | |
---|
| 3270 | \medskip |
---|
| 3271 | |
---|
| 3272 | \noindent |
---|
| 3273 | and stores these quantities and corresponding row indices to the |
---|
| 3274 | structure \verb|LPXKKT|. |
---|
| 3275 | |
---|
| 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: |
---|
| 3289 | |
---|
| 3290 | \medskip |
---|
| 3291 | |
---|
| 3292 | \hspace{30mm} |
---|
| 3293 | \verb|pb_ae_max| $\displaystyle{= \max_{1\leq k \leq m+n}|h_k|}$, |
---|
| 3294 | |
---|
| 3295 | \medskip |
---|
| 3296 | |
---|
| 3297 | \hspace{30mm} |
---|
| 3298 | \verb|pb_re_max| $\displaystyle{= \max_{1\leq k \leq m+n} |
---|
| 3299 | \frac{|h_k|}{1+|x_k|}}$, |
---|
| 3300 | |
---|
| 3301 | \medskip |
---|
| 3302 | |
---|
| 3303 | \noindent |
---|
| 3304 | and stores these quantities and corresponding variable indices to the |
---|
| 3305 | structure \verb|LPXKKT|. |
---|
| 3306 | |
---|
| 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: |
---|
| 3312 | |
---|
| 3313 | \medskip |
---|
| 3314 | |
---|
| 3315 | \hspace{30mm} |
---|
| 3316 | \verb|de_ae_max| $\displaystyle{= \max_{1\leq j\leq n}|u_j|}$, |
---|
| 3317 | |
---|
| 3318 | \medskip |
---|
| 3319 | |
---|
| 3320 | \hspace{30mm} |
---|
| 3321 | \verb|de_re_max| $\displaystyle{= \max_{1\leq j\leq n} |
---|
| 3322 | \frac{|u_j|}{1+|(d_S)_j - (c_S)_j|}}$, |
---|
| 3323 | |
---|
| 3324 | \medskip |
---|
| 3325 | |
---|
| 3326 | \noindent |
---|
| 3327 | and stores these quantities and corresponding column indices to the |
---|
| 3328 | structure \verb|LPXKKT|. |
---|
| 3329 | |
---|
| 3330 | To check the fourth condition (KKT.DB) the routine computes a vector |
---|
| 3331 | of residuals: |
---|
| 3332 | |
---|
| 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: |
---|
| 3343 | |
---|
| 3344 | \medskip |
---|
| 3345 | |
---|
| 3346 | \hspace{30mm} |
---|
| 3347 | \verb|db_ae_max| $\displaystyle{= \max_{1\leq k\leq m+n}|v_k|}$, |
---|
| 3348 | |
---|
| 3349 | \medskip |
---|
| 3350 | |
---|
| 3351 | \hspace{30mm} |
---|
| 3352 | \verb|db_re_max| $\displaystyle{= \max_{1\leq k\leq m+n} |
---|
| 3353 | \frac{|v_k|}{1+|d_k - c_k|}}$, |
---|
| 3354 | |
---|
| 3355 | \medskip |
---|
| 3356 | |
---|
| 3357 | \noindent |
---|
| 3358 | and stores these quantities and corresponding variable indices to the |
---|
| 3359 | structure \verb|LPXKKT|. |
---|
| 3360 | |
---|
| 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|: |
---|
| 3366 | |
---|
| 3367 | \verb|pe_quality|---quality of primal solution; |
---|
| 3368 | |
---|
| 3369 | \verb|pb_quality|---quality of primal feasibility; |
---|
| 3370 | |
---|
| 3371 | \verb|de_quality|---quality of dual solution; |
---|
| 3372 | |
---|
| 3373 | \verb|db_quality|---quality of dual feasibility. |
---|
| 3374 | |
---|
| 3375 | Each of these indicators is assigned to one of the following four |
---|
| 3376 | values: |
---|
| 3377 | |
---|
| 3378 | \verb|'H'| means high quality, |
---|
| 3379 | |
---|
| 3380 | \verb|'M'| means medium quality, |
---|
| 3381 | |
---|
| 3382 | \verb|'L'| means low quality, or |
---|
| 3383 | |
---|
| 3384 | \verb|'?'| means wrong or infeasible solution. |
---|
| 3385 | |
---|
| 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. |
---|
| 3390 | |
---|
| 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. |
---|
| 3394 | |
---|
| 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. |
---|
| 3398 | |
---|
| 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. |
---|
| 3405 | |
---|
| 3406 | %* eof *% |
---|