Accession Number : AD0696950
Title : DENSE SETS OF TWO VARIABLE INTEGER PROGRAMS REQUIRING ARBITRARILY MANY CUTS BY FRACTIONAL ALGORITHMS.
Descriptive Note : Research rept.,
Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Personal Author(s) : Jeroslow,R. G. ; Kortanek,K. O.
Report Date : AUG 1969
Pagination or Media Count : 32
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.
Descriptors : (*LINEAR PROGRAMMING, ALGORITHMS), NUMBER THEORY, SET THEORY, OPTIMIZATION, THEOREMS
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE