Constructive and Destructive Methods in Heuristic Search

Constructive methods are one of the main families of heuristic approaches to combinatorial optimization problems. They usually start from an empty set and subsequently add elements until a promising feasible solution is found. Their advantages are simplicity in design, analysis and implementation, and an intuitive structure. In general, though not always, they also have a limited computational complexity. An obvious counterpart is offered by destructive methods, which start from the whole ground set in which the solutions are embedded, and subsequently remove elements until they reach a promising feasible solution. This chapter describes the systematic development of a number of constructive and destructive methods for the MaxSum and the MaxMinSum diversity problems and their application, both as stand-alone approaches and to initialize an improvement metaheuristic.