This is joint work with graduate research assistants, J. Warren and D. Warrier. A branch-and-price approach for certain NP-hard graph problems is presented. The approach uses a Dantzig-Wolfe decomposition and partitions the input graph into subgraphs. The original problem is then solved on the subgraphs to produce feasible columns for the master problem. Focusing on the maximum weight independent set problem, a number of ways to partition the graph and to solve subproblems are investigated. Preliminary computational results are presented.
展开▼
