An implicit enumeration algorithm employing surrogate constraints for solving linear programs with zero-one variables
Dimitriou, John I.
Young, Richard D.
Master of Arts
In this paper, an implicit enumeration algorithm is illustrated. Surrogate constraints were used in a special way, to modify and thus obtain) another version of implicit enumeration for solving zero-one problems. For unity and completeness of the paper a brief background is given on the basic ideas of implicit enumeration, and on how surrogate constraints are normally used. Then the algorithm and its rules follow, as special cases of the general considerations. Finally a computer code illustrates the practicality of the method. Further research can be done, to determine how surrogate constraints affect the efficiency of the algorithm, the number of iterations and the computational time.