The maximum weight stable set problem with a budget constraint

We consider the maximum weight stable set problem with an additional budget constraint (BSS) which is also known as the knapsack problem with conflict-pair constraints. A unifying 0-1 programming formulation is given that subsumes two well-studied formulations for the problem and we analyze the strength of the LP relaxation of this model. Also, we present an alternative view of the extended cover inequalities for the knapsack polytope and using this, along with other upper bounds on the stability number of a graph, strengthened 0-1 linear programming formulations of BSS are presented. Further, we study two binary quadratic formulations of BSS and explore the relationship between its linearizations and our 0-1 linear programming formulations. Results of extensive computational analysis carried out using our models are presented that compares various features of the models and their relative merits.