Development of a branch and price approach involving vertex cloning to solve the maximum weighted independent set problem
Abstract
We propose a novel branch-and-price (B&P) approach to solve the maximum weighted independent set problem (MWISP). Our approach uses clones of vertices to create edge-disjoint partitions from vertex-disjoint partitions. We solve the MWISP on sub-problems based on these edge-disjoint partitions using a B&P framework, which coordinates sub-problem solutions by involving an equivalence relationship between a vertex and each of its clones. We present test results for standard instances and randomly generated graphs for comparison. We show analytically and computationally that our approach gives tight bounds and it solves both dense and sparse graphs quite quickly.
Subject
integer programmingBranch and Price
maximum weighted independent set problem
partitioning
vertex cloning
Citation
Sachdeva, Sandeep (2004). Development of a branch and price approach involving vertex cloning to solve the maximum weighted independent set problem. Master's thesis, Texas A&M University. Texas A&M University. Available electronically from https : / /hdl .handle .net /1969 .1 /3251.