An Evolutionary Algorithm for Polishing Mixed Integer Programming Solutions

Evolutionary algorithms adopt a natural-selection analogy, exploiting concepts such as population, combination, mutation, and selection to explore a diverse space of possible solutions to combinatorial optimization problems while, at the same time, retaining desirable properties from known solutions. This paper describes an evolutionary approach to improving solutions to mixed integer programming (MIP) models. We propose coarse-grained approaches to mutating and combining MIP solutions, both built within a large-neighborhood search framework. These techniques are then integrated within a MIP branch-and-bound framework. The resulting solution-polishing heuristic often finds significantly better feasible solutions to very difficult MIP models than do available alternatives. In contrast to most evolutionary algorithms, our polishing heuristic is domain-independent, requiring no structural information about the underlying combinatorial problem, above and beyond the information contained in the original MIP formulation.