Show simple item record

dc.contributor.authorMaheshwary, Siddharthaen_US
dc.date.accessioned2009-01-22T15:52:27Z
dc.date.available2009-01-22T15:52:27Z
dc.date.issued2008-08-25en_US
dc.identifier.urihttp://hdl.handle.net/1853/26635
dc.description.abstractWe study the facial structure of the independent set polytope using the concept of conflict hypergraphs. A conflict hypergraph is a hypergraph whose vertices correspond to the binary variables, and edges correspond to covers in the constraint matrix of the independent set polytope. Various structures such as cliques, odd holes, odd anti-holes, webs and anti-webs are identified on the conflict hypergraph. These hypergraph structures are shown to be generalization of traditional graph structures. Valid inequalities are derived from these hypergraph structures, and the facet defining conditions are studied. Chvatal-Gomory ranks are derived for odd hole and clique inequalities. To test the hypergraph cuts, we conduct computational experiments on market-share (also referred to as market-split) problems. These instances consist of 100% dense multiple-knapsack constraints. They are small in size but are extremely hard to solve by traditional means. Their difficult nature is attributed mainly to the dense and symmetrical structure. We employ a special branching strategy in combination with the hypergraph inequalities to solve many of the particularly difficult instances. Results are reported for serial as well as parallel implementations.en_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectFaceten_US
dc.subjectValid inequalityen_US
dc.subjectConflict hypergraphen_US
dc.subjectConflict graphen_US
dc.subjectIndependent set polytopeen_US
dc.subjectIndependent set problemen_US
dc.subjectCombinatorial optimizationen_US
dc.subjectInteger programmingen_US
dc.subjectMarket spliten_US
dc.subjectMarket shareen_US
dc.subjectParallel computingen_US
dc.subject.lcshHypergraphs
dc.titleFacets of conflict hypergraphsen_US
dc.typeDissertationen_US
dc.description.degreePh.D.en_US
dc.contributor.departmentIndustrial and Systems Engineeringen_US
dc.description.advisorCommittee Chair: Lee, Eva K.; Committee Member: Barnes, Earl; Committee Member: Johnson, Ellis; Committee Member: Parker, R. Gary; Committee Member: Wu, D. J.en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record