Back to search

Georgia Institute of Technology

Facets of conflict hypergraphs

Abstract

dc:description.abstract

We 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.

Degree

thesis:*
Department dc:contributor.department
Industrial and Systems Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2008

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Maheshwary, Siddhartha
Advisor dc:contributor.advisor
  • Lee, Eva K.
Committee members dc:contributor.committeemember
  • Barnes, Earl R.
  • Johnson, Ellis L.
  • Parker, R. Gary
  • Wu, D. J.

Subjects

dc:subject × 12

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/26635

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Maheshwary, Siddhartha. Facets of conflict hypergraphs. Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/26635