Accession Number : AD0761071

Title :   On Algorithms for Discrete Problems.

Descriptive Note : Research rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s) : Jeroslow,R. G.

Report Date : APR 1973

Pagination or Media Count : 14

Abstract : The paper presents a theorem, applicable to many algorithms used in integer programming, which states that, under frequently met hypotheses, arbitrarily close (in the topology on real space) to most well-behaved integer programs there exist integer programs for which the algorithm requires arbitrarily many iterations to solve. Primary among the hypotheses of the theorem is the supposition that, in the determination of the next operation to be undertaken (perhaps addition of a cut row, or a pivot step, etc.), the space of all possible tableaus is partitioned into a countable collection of disjoint sets (not necessarily open or connected), and on each partition element, the operation is continuous. Two other hypotheses of the theorem are frequently met, but are too technical to state here. What is surprising is the generality of the result, and the fact that the elaborateness of the calculations involved in any given iteration of the algorithm does not affect the result. On the other hand, the result is purely qualitative, and does not indicate the kinds of problems for which the algorithm requires many iterations. (Author)

Descriptors :   (*MATHEMATICAL PROGRAMMING, ALGORITHMS), LINEAR PROGRAMMING, TOPOLOGY, MAPPING(TRANSFORMATIONS), SET THEORY, OPTIMIZATION

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE