The Quadratic Multiknapsack Problem with Conflicts and Balance Constraints

Philippe Olivier (), Andrea Lodi () and Gilles Pesant ()
Additional contact information
Philippe Olivier: Polytechnique Montréal, Montréal, Québec H3J 3A7, Canada
Andrea Lodi: Polytechnique Montréal, Montréal, Québec H3J 3A7, Canada
Gilles Pesant: Polytechnique Montréal, Montréal, Québec H3J 3A7, Canada

INFORMS Journal on Computing, 2021, vol. 33, issue 3, 949-962

Abstract: The quadratic multiknapsack problem consists of packing a set of items of various weights into knapsacks of limited capacities with profits being associated with pairs of items packed into the same knapsack. This problem has been solved by various heuristics since its inception, and more recently it has also been solved with an exact method. We introduce a generalization of this problem that includes pairwise conflicts as well as balance constraints, among other particularities. We present and compare constraint programming and integer programming approaches for solving this generalized problem. Summary of Contribution : The quadratic multiknapsack problem consists of packing a set of items of various weights into knapsacks of limited capacities -- with profits being associated with pairs of items packed into the same knapsack. This problem has been solved by various heuristics since its inception, and more recently it has also been solved with an exact method. We introduce a generalization of this problem which includes pairwise conflicts as well as balance constraints, among other particularities. We present and compare constraint programming and integer programming approaches for solving this generalized problem. The problem we address is clearly in the core of the operations research applications in which subsets have to be built and, in particular, we add the concept of fairness to the modeling and solution process by computationally evaluating techniques to take fairness into account. This is clearly at the core of computational evaluation of algorithms.

Keywords: quadratic multiknapsack problem; constraint programming; integer programming; balance (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.0983 (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:33:y:2021:i:3:p:949-962

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 ().