Procedures for Estimating Optimal Solution Values for Large Combinatorial Problems

This study focuses attention on methods for generating useful solution standards for large combinatorial problems. In particular, several procedures that provide point estimates of the value of the optimum solution are suggested and tested. These concepts are applied to a representative combinatorial problem: flow shop sequencing. Detailed computational results are presented.