Hybrid Nested Partitions and Math Programming Framework for Large-scale Combinatorial Optimization
Abstract
There are two principal technologies for these large-scale combinatorial optimization problems: 1) exact algorithms and 2) metaheuristic algorithms. This project will integrate concepts from these two technologies to develop generic optimization frameworks to find provably good solutions to large-scale discrete optimization problems often encountered in many real applications. The way that these two sets of methods will be used, and in particular the way in which they will be used together so that each complements the strengths of the other, will be novel and pioneering. In particular, this project will begin by exploring and capitalizing on the links between mixed integer programming decomposition approaches, such as Dantzig Wolfe decomposition and Lagrangian relaxation, and metaheuristics such as the Nested Partitions framework. While the relationship between these seemingly disparate approaches has not been exploited before, there is already evidence to suggest that capitalizing on this relationship to integrate these methods could yield solution frameworks that are more powerful than using either approach on its own.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 31, 2010
- Accession Number
- ADA571384
Entities
People
- Leyuan Shi
Organizations
- University of Wisconsin–Madison