
doi: 10.1007/bf01681344
In this paper we consider the question: how does the flow algorithm and the simplex algorithm work? The usual answer has two parts: first a description of the "improvement process", and second a proof that if no further improvement can be made by this process, an optimal vector has been found. This second part is usually based on duality a technique not available in the case of an arbitrary integer programming problem. We wish to give a general description of "improvement processes" which will include both the simplex and flow algorithms, which will be applicable to arbitrary integer programming problems, and which will in themselves assure convergence to a solution. Geometrically both the simplex algorithm and the flow algorithm may be described as follows. At the i th stage, we have a vertex (or feasible flow) to which is associated a finite set of vectors, namely the set of edges leaving that vertex (or the set of unsaturated paths). The algorithm proceeds by searching among this special set for a vector along which the gain function is increasing. If such a vector is found, the algorithm continues by moving along this vector as far as is possible while still remaining feasible. The search is then repeated at this new feasible point. We give a precise definition for sets of vectors, called test sets, which will include those sets described above arising in the simplex and flow algorithms. We will then prove that any "improvement process" which searches through a test set at each stage converges to an optimal point in a finite nmnber of steps. We also construct specific test sets which are the natural extensions of the test sets employed by the flow algorithm to arbitrary linear and integer linear programming problems.
Linear programming, Integer programming
Linear programming, Integer programming
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 100 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
