On Finding Integer Solutions to Linear Programs

摘要

The primary goal of this paper was to discuss the methods - mathematical and computational - which surround the problem of finding integer solutions to linear programs. Perhaps the most important part of the paper is an up to date survey of computational experience with integer programming algorithms. It is argued that this experience should be viewed as strong encouragement for the applied mathematician seeking solutions of particular combinatorial problems to use existing programs; or better yet, to develop new codes. In any case, experience indicates that solutions to large practical problems can be found in 'reasonable' time. This is contrary to what the folklore of the field will make one believe. Furthermore, the computational experience seems to point to a number of interesting questions for the combinatorial mathematician.