On the Storage and Handling of Binary Data Using FORTRAN with Applications to Integer Programming

Most integer programming algorithms involve at least some binary data handling, e.g., set membership, intersection, and union. This paper presents some of the important concerns involved in implementation. When the algorithms are coded for the computer an effort is sometimes made to take advantage of the basic binary configuration of the digital computer to aid in the storage and handling of such data. In the past this has meant the use of assembly language subroutines. This paper demonstrates a procedure for achieving the same objectives in the main program using FORTRAN. The obvious advantage of the procedure is the elimination of the several storage and retrieval operations for register values as the program shifts control from the main routine to the subroutine and back again. Of particular interest are (1) the use of the computer arithmetic to achieve the relative complement operation and (2) the importance of additional savings due to overhead reduction when bit storage is used. Computational results are presented comparing various regimes for storing and handling binary data. In addition, an analytic procedure for comparing the storage requirements and execution times of different data structures is demonstrated for a particular integer programming application. This paper should serve as a useful tutorial for anyone developing and/or implementing integer programming algorithms.