General information on HOPDM code

This is a short information on the HOPDM library of routines for solving large-scale linear programs with interior point methods. HOPDM stands for Higher Order Primal-Dual Method.

ALGORITHM The code implements a primal-dual logarithmic barrier (interior point) method with multiple correctors of centrality, i.e. the algorithm proposed in the following paper of Jacek Gondzio: "Multiple centrality corrections in a primal-dual method for linear programming", Computational Optimization and Applications 6 (1996) pp. 137-156. Additionally, the code offers several useful options, like e.g. a sophisticated presolve routine, a fast sparsity-exploiting Cholesky decomposition, etc., that are all carefully documented in the references. USE OF HOPDM The simplest usage of the library is to apply it as a stand-alone LP solver that reads LP data (in a widely accepted MPS format), solves the problem and prints the output (in an MPS-like format). This, in fact, reflects the structure of the main (HMAIN2.F) routine. This routine calls the following subroutines of the library: RDSPEC read the problem specifications (several example SPECS files are included eg, for the smallest Netlib problems: AFIRO, ADLITTLE, ...) RDMPS1 read the MPS-formatted LP data. This routine only reads the problem but it does nothing else to it. You can replace it with any other (presumably faster) routine to read different disc file or to directly generate LP data structures in internal format of HOPDM. This internal format is simplified (at this point) just to a collection of sparse columns of matrix A, explicit LOWER and UPPER bounds, explicit indication of the OBJECTIVE row and the RHS vector). RDMPS2 transforms the LP data of the above mentioned format to internal data structures used by the HOPDM library. (Differently to the simplex method, interior point codes require comfortable access to both rows and columns of A.) Here slacks, surplus and artificials are added, FREE variables are split, etc. PRESOL performs an advanced pre_solve analysis of the problem. In particular, it cleans the LP matrix: - determines (and later tightens) bounds on shadow prices, - eliminates dominated (and weakly dominated) variables, - eliminates singleton rows, - eliminates singleton columns (implied FREE variables), - finds identical columns and aggregates them, - finds hidden split FREE variables, - eliminates redundant (dominated or forcing) constraints, - tightens bounds on variables, makes the LP matrix sparser: - pivots out some nonzero entries of A, makes the LP matrix better suited for Cholesky fact.: - splits dense columns into shorter pieces. You may comment out the call of PRESOL routine, but it usually causes some loss (10-30%) of the HOPDM efficiency. PREPRO performs preprocessing for the Cholesky decomposition. In particular, it: - builds an adjacency structure of A*Atranspose matrix, - finds an ordering that minimizes the number of nonzero entries in a Cholesky factor, - reorders rows of A (and all data associated to rows, such as RANGES, RHS etc.) according to the permutation resulting from the minimum degree ordering, - prepares data structures for sparse Cholesky decomposition (i.e. it does the symbolic factorization). You MUST call this routine prior to calling PCPDM solver. SCALEA scales the LP constraint matrix. Simple geometric scaling is repeated twice on the matrix A. RSCALE and CSCALE vectors handle the resulting row and column scaling factors, respectively. You DO NOT HAVE TO call this routine. What is necessary, however, is to initialize scaling factors (to ones). Scaling in 95% of cases improves the numerical properties of the problem to be solved so it is justified to call it. PCPDM (Higher Order Primal-Dual Method) solves the LP problem. This routine implements a primal-dual algorithm with multiple centrality corrections. UNSCLA unscales the LP problem. You HAVE TO call this routine even if you have earlier disabled scaling. POSTSL performs post-solve analysis, i.e., it undoes all the problem modifications that have been done in a PRESOL routine. You HAVE TO call this routine if you earlier called PRESOL. (Otherwise, the solution is printed in a modified form, with e.g. bounds pushed and may not be really readable). WRTSOL writes an MPS-like formatted solution. Generally speaking, all routines of the HOPDM library are well documented source files. To deeply understand some functions, however, you may find it necessary to consult the appropriate publications (their list is almost always supplied in a source code of each routine). COMPILING THE PROGRAM To compile and link the program you have to place all the source routines (*.f files) in the current directory and run make command. An example 'makefile' for SUN SPARC workstations is included. However, you may have to modify it appropriately for your computer. In particular, you may have to change the name of FORTRAN compiler, etc. In principle, HOPDM should be easy to port to any platform. However, you may have some problems with the routines that measure the elapsed time. If this is the case, please change the call in MYTIME routine to the one that is appropriate for your system (or add two C routines written by David Gay and supplied in FTIME.c source file). RUNNING THE PROGRAM To run the program you need at least two files to be present in a current directory: MPS-formatted file with the LP problem data (default name 'mps') SPECS file with basic information on a problem to be solved (default name 'spc'). You are supplied with two smallest LP problems from the Netlib collection: AFIRO and ADLITTLE and the specs files for them. The program ALWAYS reads specifications from the 'spc' file. To run it on AFIRO problem you thus have to - copy afiro.spc onto spc - start the hopdm solver. The minimum 'spc' file has to contain at least the following lines:

begin mps file afiro.mps log file afiro.log solut file afiro.res end

It may additionally contain the limits of rows, columns and nonzero entries, the direction of optimization: minimize or maximize, names of sections in the MPS file if there are more sections of the same type, the required precision of the optimal solution and the level of presolve analysis desired. Our specs file for AFIRO looks like:

begin rows 30 cols 60 elements 120 MPS FILE afiro.mps log file afiro.log SOLUT FILE afiro.res rhs name B objective COST opt tol 1.0d-8 presolve 6 minimize end

although it would suffice to leave only:

begin mps file afiro.mps log file afiro.log solut file afiro.res end

as minimization (to 8 digits exact) and level 6 presolve are default settings of HOPDM. FILES CREATED BY HOPDM HOPDM creates two files associated to a given problem solved. In the above example, these files will be: 'afiro.log' which contains all log information on the process of solving the problem. 'afiro.res' solution of the problem in MPS-like format. You may change their names by appropriate specifications in 'spc' file. Current version of the code writes relatively large output to a '*.log' file as this output usually helps to understand eventual difficulties if such occur in the optimization process. You can skip some of it if you find it superfluous. HANDLING LARGE SCALE PROBLEMS There are no particular limits on the size of problems that can be solved with HOPDM. The user is only expected to adjust parameters appropriately to the amount of virtual memory available on his computer. A few PARAMETER lines at the beginning of HMAIN.F routine offer hints of how this could be done for 32-, 64- and 128-MB computers. Distributed version of the library uses INTEGER*2 arrays to store rows/columns indices. This imposes constraints on the size of problems that can be solved with the program. Their sizes cannot exceed 32767 rows/cols. If you want to solve larger problems, then you should run 'Two2four' script to replace all INTEGER*2 declarations with INTEGER*4 ones, change INTSZ parameter in HMAIN2.F routine accordingly (it should write INTSZ=4), increase appropriate PARAMETERs, and recompile the whole program. Finally, note that MSPLIT array (in COMMON) is used to port some information that is essential for the stability of LDL^T decomposition. COMMON blocks require the arrays have fixed size, hence MSPLIT is everywhere declared as INTEGER*2 MSPLIT(100000). It is an implicit bound on the size of the solvable problems. Their size cannot exceed 100,000 rows. If you want to go further, you have to change carefully the declaration of MSPLIT in all places where it appears. ACKNOWLEDGMENTS The code benefits the presence of the following two routines: - MMD routine is Joseph Liu's implementation of the Multiple Minimum Degree ordering. See: "The evolution of the minimum degree ordering algorithm", SIAM Review 33 (1989), 1, pp. 1-19. NOTE: This routine can be used EXCLUSIVELY for research purposes. - GENQMD routine is an implementation of the Quotient tree Minimum Degree ordering available from SPARSPAK (via Netlib). This routine is based on the book "Computer Solution of Large Sparse Positive Definite Systems" by George and Liu, Prentice Hall 1981.