ON SOME ASPECTS OF INTEGER LINEAR PROGRAMMING
Abstract
A primal feasible (all-integer) integer linear programming algorithm has been developed and programmed, together with a related procedure for obtaining a first feasible solution. Once a feasible solution is found, the algorithm maintains feasibility at each stage, in contrast to other algorithms that have been programmed and are currently available. These other algorithms do not achieve feasibility until the optimal solution is reached. The primal feasible algorithm is based on a particular way of applying the cutting planes previously developed by R. E. GOMORY, and on a specific interpretation of their role. The finiteness of convergence has been established for two-dimensional problems but not for the general case; however, there appears to be at least computational convergence in a considerable fraction of the cases. In addition, a Generalized Euclidean Algorithm for finding the greatest common divisor for more than two numbers is defined. The solution of systems of linear diophantine equations is presented in terms of integer linear programming. Some geometric considerations that help to illuminate the workings of the algorithm, are examined.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1965
- Accession Number
- AD0624553
Entities
People
- Romulo H. Gonzalez-zubieta
Organizations
- Massachusetts Institute of Technology