On Solving the Knapsack Problem with Conflicts

Roberto Montemanni () and Derek H. Smith
Additional contact information
Roberto Montemanni: Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia, 42122 Reggio Emilia, Italy
Derek H. Smith: Faculty of Computing, Engineering and Science, University of South Wales, Pontypridd CF37 1DL, UK

Mathematics, 2025, vol. 13, issue 16, 1-12

Abstract: A variant of the well-known Knapsack Problem is studied in this paper. In the classic problem, a set of items is given, with each item characterized by a weight and a profit. A knapsack of a given capacity is provided, and the problem consists of selecting a subset of items such that the total weight does not exceed the capacity of the knapsack, while the total profit is maximized. In the variation considered in the present work, pairs of items are conflicting, and cannot be selected at the same time. The resulting problem, which can be used to model several real applications, is considerably harder to approach than the classic one. In this paper, we consider a mixed-integer linear program representing the problem and we solve it with a state-of-the-art black-box software. A vast experimental procedure on the instances available from the literature, and adopted in the last decade by the community, indicates that the approach we propose achieves results comparable with, and in many cases better than, those of state-of-the-art methods, notwithstanding that the latter are typically based on more complex and problem-specific ideas and algorithms than the idea we propose.

Keywords: knapsack problems; conflict constraints; exact solutions; heuristic solutions (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/16/2674/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/16/2674/ (text/html)

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:gam:jmathe:v:13:y:2025:i:16:p:2674-:d:1728337

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().