304. Non-Standard Benders Decomposition for the Multiple Knapsack Assignment Problem
Invited abstract in session MC-15: Relaxation and Decomposition, stream Combinatorial Optimization.
Monday, 12:30-14:00Room: Esther Simpson 1.08
Authors (first author is the speaker)
| 1. | Adam Letchford
|
| Department of Management Science, Lancaster University | |
| 2. | Laura Galli
|
| Mathematics, Alma Mater Studiorum Università di Bologna |
Abstract
The Multiple Knapsack Assignment Problem (MKAP) is a strongly NP-hard combinatorial optimisation problem, with several practical applications. We present a new exact algorithm for the MKAP, based on Benders decomposition. For reasons which will become clear, we use a non-standard decomposition strategy, together with specialised feasibility cuts and a primal heuristic. Our preliminary computational results suggest that our new approach works very well when the number of knapsacks is relatively large.
Keywords
- Combinatorial Optimization
- Algorithms
Status: accepted
Back to the list of papers