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.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/5814 |
| Date | 17 September 2007 |
| Creators | Warrier, Deepak |
| Contributors | Wilhelm, Wilbert E. |
| Publisher | Texas A&M University |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Dissertation, text |
| Format | 641353 bytes, electronic, application/pdf, born digital |
Page generated in 0.0493 seconds