โ Scribed by R.G. Jeroslow
No coin nor oath required. For personal study only.
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, tL;: operation is continuous. Two other hypotheses of the theorem are frequently met, but are too technical to state here.
Wrat is su:.prising is the generality of the resnlt, and the fact that the elaborateness of the calculations irvolved in any given iteration of the algorithm does not affect the result. On the other hand, t1.e result is purely qualitative, and does not indicate the kinds of problem5 for which the algorithm requires many iterations.
๐ SIMILAR VOLUMES
The bilevel programming problem (BLPP) is an example of a two-stage, noncooperative game in which the first player can influence but not control the actions of the second. This article addresses the linear formulation and presents a new algorithm for solving the zero-one case. We begin by converting