Back to Search
Start Over
An Evolutionary Algorithm for Polishing Mixed Integer Programming Solutions.
- Source :
- INFORMS Journal on Computing; Fall2007, Vol. 19 Issue 4, p534-541, 8p, 1 Diagram, 4 Charts
- Publication Year :
- 2007
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10919856
- Volume :
- 19
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- INFORMS Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 27880146
- Full Text :
- https://doi.org/10.1287/ijoc.1060.0189