The Non Candidate Constraint Method for Reducing the Size of a Linear Program

摘要

A non candidate constraint in a linear program is one which never contains a pivot element during the course of solving the problem. Discovering non candidate constraints is computationally costly since their discovery, in general, depends on the actual sequence of pivots used. Knowing which constraints are non candidate is of great computational benefit since they need not be kept in updated form. Our experience indicates that from 50 to 80 percent of the constraints in randomly problems are non candidates at least part of the time. In this paper we present a learning approach to the identification of non candidate constraints. At each iteration we determine which constraints can potentially be pivotal; these are candidate constraints and all others are non candidate constraints on that step. On proceeding with the simplex method we update only the candidate constraints. If a non candidate constraint becomes candidate on a later step, we update it and add it to the candidate list. Although the constant checking of constraints to see whether they are changing from being candidate to non candidate is computationally costly, we obtain the computational benefit of having to keep in updated form a much smaller tableau. The net benefit of using this strategy is positive and results in a 25 to 50 percent reduction in total computation time. This paper describes the method in detail and gives computational results of testing it on a series of randomly generated problems. (Author)