dc.contributor.advisor | Wilhelm, Wilbert E. | |
dc.creator | Warrier, Deepak | |
dc.date.accessioned | 2007-09-17T19:33:52Z | |
dc.date.available | 2007-09-17T19:33:52Z | |
dc.date.created | 2003-05 | |
dc.date.issued | 2007-09-17 | |
dc.identifier.uri | https://hdl.handle.net/1969.1/5814 | |
dc.description.abstract | 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. | en |
dc.format.extent | 641353 bytes | en |
dc.format.medium | electronic | en |
dc.format.mimetype | application/pdf | |
dc.language.iso | en_US | |
dc.publisher | Texas A&M University | |
dc.subject | BRANCH AND PRICE | en |
dc.subject | INDEPENDENT SET PROBLEM | en |
dc.subject | LIFT & PROJECT | en |
dc.subject | LIFTING | en |
dc.subject | STABILIZATION | en |
dc.title | A branch, price, and cut approach to solving the maximum weighted independent set problem | en |
dc.type | Book | en |
dc.type | Thesis | en |
thesis.degree.department | Industrial and Systems Engineering | en |
thesis.degree.discipline | Industrial Engineering | en |
thesis.degree.grantor | Texas A&M University | en |
thesis.degree.name | Doctor of Philosophy | en |
thesis.degree.level | Doctoral | en |
dc.contributor.committeeMember | Butenko, Sergiy | |
dc.contributor.committeeMember | Chen, Jianer | |
dc.contributor.committeeMember | Hicks, Illya V. | |
dc.type.genre | Electronic Dissertation | en |
dc.type.material | text | en |
dc.format.digitalOrigin | born digital | en |