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