An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating

摘要

Knapsack problems play a pivotal role in the operations research literature, with various generalizations proposed and studied over the last century. Of recent interest is the quadratic multiknapsack problem (QMKP). Despite a plethora of heuristics, no exact methods for the QMKP have been published in the literature. This paper presents an exact branch-and-price algorithm for the QMKP. Experimental results indicate that the proposed algorithm is far superior, both in terms of solution times and objective function bounds, to state-of-the-art optimization technology solving a standard encoding of the problem. In addition to the algorithmic contribution, this paper studies the optimization problem of seating attendees at events, an operational challenge faced by event organizers. An optimization model for table event seating is shown to be closely related to the QMKP, and computational testing indicates that the proposed algorithm is particularly well suited for this application.