The maximum weight stable set problem with a budget constraint

Thesis type
(Thesis) M.Sc.
Date created
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.
Copyright statement
Copyright is held by the author(s).
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Supervisor or Senior Supervisor
Thesis advisor: Punnen, Abraham
Member of collection
Attachment Size
input_data\20942\etd21046.pdf 1.69 MB