1104. Search Escalation for Heuristic Combinatorial Optimization
Invited abstract in session WB-17: Integer Programming, stream Combinatorial Optimization.
Wednesday, 10:30-12:00Room: Esther Simpson 2.08
Authors (first author is the speaker)
| 1. | Steven Kimbrough
|
| Wharton, University of Pennsylvania | |
| 2. | Kelly Wang
|
| Wharton, University of Pennsylvania |
Abstract
We propose and discuss a concept we call search escalation. It augments heuristic search, as typically conducted by meta-heuristics. Search escalation techniques are methods for broadening and deepening heuristic search undertaken by a given meta-heuristic, such as simulated annealing or evolutionary computation. In a prototypical use case calling for search escalation, (i) running longer or replication of a metaheuristic yields diminishing returns and (ii) the importance of finding better solutions is deemed to be very high. Such is the motivating use case for this work: given a gerrymandered legislative redistricting plan, find multiple plans that are as similar as possible to the source plan but that have attractive properties (e.g., on partisan fairness, respect for administrative boundaries, coherence of communities of interest) from a public interest perspective. We further propose an approach to search escalation that we call PPI (pool of potential incumbents). This is a second-order metaheuristic. Under this approach, promising search paths that appear and are NOT pursued by a first-order meta-heuristic (e.g., tabu search) are retained and potentially used in other, separate first-order meta-heuristic searches. This is a heuristic for examining parts of the global search space that would not otherwise likely be explored by the first-order meta-heuristic. We discuss examples and present computational results.
Keywords
- Algorithms
- Artificial Intelligence
- Combinatorial Optimization
Status: accepted
Back to the list of papers