Show simple item record

dc.contributor.advisorWilhelm, Wilbert E.en_US
dc.creatorWarrier, Deepaken_US
dc.date.accessioned2007-09-17T19:33:52Z
dc.date.available2007-09-17T19:33:52Z
dc.date.created2003-05en_US
dc.date.issued2007-09-17
dc.identifier.urihttp://hdl.handle.net/1969.1/5814
dc.description.abstractThe 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_US
dc.format.extent641353 bytes
dc.format.mediumelectronicen_US
dc.format.mimetypeapplication/pdf
dc.language.isoen_USen_US
dc.publisherTexas A&M Universityen_US
dc.subjectBRANCH AND PRICEen_US
dc.subjectINDEPENDENT SET PROBLEMen_US
dc.subjectLIFT & PROJECTen_US
dc.subjectLIFTINGen_US
dc.subjectSTABILIZATIONen_US
dc.titleA branch, price, and cut approach to solving the maximum weighted independent set problemen_US
dc.typeBooken
dc.typeThesisen
thesis.degree.departmentIndustrial and Systems Engineeringen_US
thesis.degree.disciplineIndustrial Engineeringen_US
thesis.degree.grantorTexas A&M Universityen_US
thesis.degree.nameDoctor of Philosophyen_US
thesis.degree.levelDoctoralen_US
dc.contributor.committeeMemberButenko, Sergiyen_US
dc.contributor.committeeMemberChen, Jianeren_US
dc.contributor.committeeMemberHicks, Illya V.en_US
dc.type.genreElectronic Dissertationen_US
dc.type.materialtexten_US
dc.format.digitalOriginborn digitalen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record