Clique-based facets for the precedence constrained knapsack problem (Q431007)

The authors present a novel approach for determining facets of the precedence constrained knapsack problem (PCKP) based on clique inequalities. The PCKP is an NP-hard combinatorial optimization problem that finds many interesting applications especially in manufacturing and mining. The main idea is to investigate clique inequalities derived from a directed graph representing pairwise conflict relationships between the integer variables and derive necessary and sufficient conditions under which they represent the convex hull of the associated PCKP polyhedron. There is presented as well a comparison between the previous defined covers and cliques in the conflict graph. In the last part of the paper, there are described applications of the clique-based inequalities in the case of some PCKP examples, showing their relative strengthening effect on the LP relaxation. Computational results are reported in the case of two classes of instances, demonstrating benefits of using the clique constraints to realistic problems, with respect to the reduction of the solution times.