| Solution methods for the set covering problem are presented. An extensive literature survey shows that the set covering problem has been applied to crew scheduling, circuit theory, database design, production planning, vehicle routing and location problems.;State space relaxation, an incomplete dynamic programming or tree search technique, is used to compute lower bounds. A new decomposition method can be applied to a wide range of integer programs can also be used to obtain excellent lower bounds, albeit not too quickly. These methods use integer programming duality.;A branching strategy using rows is described. The algorithms are described procedurally and by using an example. Data structures required to implement the algorithms are also given.;All the new algorithms presented here compute lower bounds to the set covering problem that are then embedded in a tree search. Comparisons are made between the new algorithms and previously known methods of Korman, Balas and Ho, and linear programming. Two lower bounds are computed from network flow problems and two from graph theory. These bounds are then improved using subgradient optimization. |
