Research Reports from the Department of Operations
Document Type
Report
Publication Date
4-1-1973
Abstract
This work represents the fifth chapter of a forthcoming textbook “Integer Programming” to be written by Harvey M. Salkin and published by Addison-Wesley. The cutting plane algorithm for the integer program presented in this chapter was developed by Ralph Gomory in 1960. Its similarity to the fractional method (Chapter 3) is principally due to the utilization of the lexicographic dual simplex method and to the maintenance of lexicographic positive columns in the tableau. The basic approach is, however, different from the fractional technique. There is no optimization, generating a constraint, reoptimization, etc. Rather, inequalities are generated at each iteration starting with the very first. Furthermore, each of these constraints is used as the pivot row and is constructed so that it has integral coefficients and the pivot is -1. The initial tableau is assumed to be all integer and lexicographic dual feasible. Hence, successive tableaux are also all integer and lexicographic dual feasible. The primal integer solution proceeds towards feasibility, and since dual feasibility is maintained, optimality is reached when it is attained. Note that the method is a direct extension of the classical dual simplex algorithm. The essential difference is that the pivot row in the all-integer algorithm is generated at each iteration and ensures a -1 pivot. Since the technique employs the dual simplex method and maintains all integer tableaux, it is referred to as "dual all-integer." We list the steps.
Keywords
Operations research, Integer programming, Linear programming, Algorithms
Publication Title
Integer Programming (1975) ; Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 230a
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Salkin, Harvey M., "Integer programming : dual all-integer integer programming (Gomory [5])" (1973). Research Reports from the Department of Operations. 159.
https://commons.case.edu/wsom-ops-reports/159