Paroid search: generic local combinatorial optimization

Hill climbing, or local search, has proved to be one of the most successful approaches to nonexact solution of combinatorial optimization problems. However, such methods usually depend on highly problem-specific notions of neighborhoods, and are thus not easily transferred to new models. The goal of this paper is to evolve a more generic approach - one that can give the same conceptual unity to local combinatorial optimization that branch and bound does for exact methods. In Rardin and Sudit (1992) we introduced a new paroid structure designed to provide a canonical format for formulating combinatorial problems so that a neighborhood structure would be implied. In this paper we introduce a new generic local optimization scheme we term paroid search addressing combinatorial optimization problems modeled over the bases of a paroid. Paroid search begins from an initial feasible solution provided as part of the input. The broad "expand and prune" format of paroid search is detailed and a number of properties analyzed. Under quite general conditions paroid search is seen to require only polynomial time to explore the neighborhood of a current solution and to be complete for models with this complexity-theoretic property. Beyond this theoretical completeness, we also demonstrate how paroid search unifies some familiar combinatorial heuristics. Various versions are seen to recover (or dominate) a scheme for vertex packing, the greedy algorithm for independence systems (with its associated performance guarantees), and the famous Lin-Kernighan heuristic for Traveling Salesman.