A Transitive Reduction Approach to the Precedence-Constrained Knapsack Problem

Abstract We are concerned with the precedence-constrained knapsack problem (PCKP), which is a knapsack problem defined on a directed acyclic graph (DAG). It is often the case that the original problem includes redundant constraints, and by eliminating these we obtain a PCKP of (much) smaller size. We show that such a reduction can be explained in terms of the ‘transitive reduction’ of the DAG associated with the original PCKP. Thus, we present a transitive reduction approach to solve PCKP, where PCKP is first reduced in size by applying transitive reduction, and then the reduced problem is solved using MIP solvers. In numerical experiments, we were able to solve PCKPs with thousands of items within a few seconds on an ordinary computing environment