EXPLORING METHODS TO SOLVE THE CONFLICT-RESTRICTED BACKPACK PROBLEM

The Conflict Restricted Backpack Problem (PMRC) is an NP-complete problem that seeks to maximize the value of the items in the backpack while respecting their maximum weight and the conflicts between them. This article shows methods to solve this problem, such as a RVND constructive heuristic. It also presents two instances of the PMRC of different complexities, proposed in other works. The results show that different algorithmic approaches and ordering criteria can influence the quality and efficiency of the solutions, depending on the characteristics of each instance. Thus, the appropriate choice of these elements can help optimize problems similar to PMRC.