Research Reports from the Department of Operations
Document Type
Report
Publication Date
4-1-1971
Abstract
This work represents the sixth chapter of a forthcoming textbook “Integer Programming” to be written by Harvey M. Salkin. 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 the maintenance of (lexicographic) positive columns. 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. Further, 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 dual feasible. Hence, successive tableaux are also all integer and dual feasible. The primal 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. 230
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 [2])" (1971). Research Reports from the Department of Operations. 158.
https://commons.case.edu/wsom-ops-reports/158