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

David Bergman ()
Additional contact information
David Bergman: Department of Operations and Information Management, University of Connecticut, Storrs, Connecticut 06268

INFORMS Journal on Computing, 2019, vol. 31, issue 3, 477–492

Abstract: 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.

Keywords: programming; nonlinear; applications; programming: integer: nonlinear; programming: nonlinear: quadratic; quadratic knapsack (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0840 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:31:y:2019:i:3:p:477-492

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().