Return to search

A branch, price, and cut approach to solving the maximum weighted independent set problem

The maximum weight-independent set problem (MWISP) is one of the most
well-known and well-studied NP-hard problems in the field of combinatorial
optimization.
In the first part of the dissertation, I explore efficient branch-and-price (B&P)
approaches to solve MWISP exactly. B&P is a useful integer-programming tool for
solving NP-hard optimization problems. Specifically, I look at vertex- and edge-disjoint
decompositions of the underlying graph. MWISP’s on the resulting subgraphs are less
challenging, on average, to solve. I use the B&P framework to solve MWISP on the
original graph G using these specially constructed subproblems to generate columns. I
demonstrate that vertex-disjoint partitioning scheme gives an effective approach for
relatively sparse graphs. I also show that the edge-disjoint approach is less effective than
the vertex-disjoint scheme because the associated DWD reformulation of the latter
entails a slow rate of convergence.
In the second part of the dissertation, I address convergence properties associated
with Dantzig-Wolfe Decomposition (DWD). I discuss prevalent methods for improving the rate of convergence of DWD. I also implement specific methods in application to the
edge-disjoint B&P scheme and show that these methods improve the rate of
convergence.
In the third part of the dissertation, I focus on identifying new cut-generation
methods within the B&P framework. Such methods have not been explored in the
literature. I present two new methodologies for generating generic cutting planes within
the B&P framework. These techniques are not limited to MWISP and can be used in
general applications of B&P. The first methodology generates cuts by identifying faces
(facets) of subproblem polytopes and lifting associated inequalities; the second
methodology computes Lift-and-Project (L&P) cuts within B&P. I successfully
demonstrate the feasibility of both approaches and present preliminary computational
tests of each.

Identiferoai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/5814
Date17 September 2007
CreatorsWarrier, Deepak
ContributorsWilhelm, Wilbert E.
PublisherTexas A&M University
Source SetsTexas A and M University
Languageen_US
Detected LanguageEnglish
TypeBook, Thesis, Electronic Dissertation, text
Format641353 bytes, electronic, application/pdf, born digital

Page generated in 0.0021 seconds