An Evolutionary Algorithm for Polishing Mixed Integer Programming Solutions
Edward E. Rothberg · INFORMS journal on computing · 2007
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.
Cited by 156 works. doi:10.1287/ijoc.1060.0189
Authors
References
- Adaptation in Natural and Artificial Systems
- An Introduction to Genetic Algorithms
- Tabu Search
- Simulated Annealing: Theory and Applications
- Tabu Search
- A Computational Study of the Job-Shop Scheduling Problem
- An introduction to genetic algorithms
- Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems
- Recent Advances in Crew-Pairing Optimization at American Airlines
- Local branching