DENSE SETS OF TWO VARIABLE INTEGER PROGRAMS REQUIRING ARBITRARILY MANY CUTS BY FRACTIONAL ALGORITHMS.
Abstract
A class of two variable integer programming problems is defined which are indexed by a continuous parameter t > 0. It is then shown that, given any non-empty open interval I of positive reals and any number N, there can be found a rational value (t sub o) is an element of I, such that the problem indexed by (t sub o) requires at least N cuts before convergence to the integer optimal occurs, using the algorithm of Gomory based on the fractional row cut. This result is derived as a corollary to the main theorem of the paper, which states an entirely parallel result for any Generalized Fractional Algorithm (GFA), a notion defined in the paper and shown to include the algorithm of Gomory as a special case. While the definition of a GFA is very broad, it does not permit the possibility of adding the entire group of cuts to the tableau at each iteration.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1969
- Accession Number
- AD0696950
Entities
People
- K. O. Kortanek
- Robert G. Jeroslow
Organizations
- Carnegie Mellon University