Slipping on the strongest surrogate constraint
Rodney D. Hunley · Digital Collections of Colorado (Colorado State University) · 1972
A heuristic procedure for solving linear binary integer programming problems has been developed through a modification of the original 5-step schema developed by Geoffrion and Glover.Although the original 5-step schema is an optimal procedure, the revised procedure can not guarantee optimality.The revised 5-step schema uses a linear programming algorithm and a binary knapsack algorithm imbedded in an implicit enumeration procedure.The strongest surrogate constraint, determined by the linear programming algorithm, combined with the objective function of the original linear binary integer programming problem form a knapsack problem which is solved by the binary knapsack algorithm.The knapsack solution is then used as an augmentation procedure in the revised 5-step schema.The heuristic procedure found feasible solutions for 23 of 24 test problems and found optimal solutions for 20 of 24 test problems.The computational results indicate that the heuristic procedure gives good computation times for some, but not all of the test problems.