A branch-and-price-and-cut method for computing an optimal bramble

Sibel B. Sonuc, J. Cole Smith, Illya V. Hicks

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

Given an undirected graph, a bramble is a set of connected subgraphs (called bramble elements) such that every pair of subgraphs either contains a common node, or such that an edge (i,j) exists with node i belonging to one subgraph and node j belonging to the other. In this paper we examine the problem of finding the bramble number of a graph, along with a set of bramble elements that yields this number. The bramble number is the largest cardinality of a minimum hitting set over all bramble elements on this graph. A graph with bramble number k has a treewidth of k-1. We provide a branch-and-price-and-cut method that generates columns corresponding to bramble elements, and rows corresponding to hitting sets. We then examine the computational efficacy of our algorithm on a randomly generated data set.

Original languageEnglish (US)
Pages (from-to)168-188
Number of pages21
JournalDiscrete Optimization
Volume18
DOIs
StatePublished - Nov 1 2015
Externally publishedYes

Keywords

  • Bramble
  • Branch-and-price
  • Integer programming
  • Treewidth

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A branch-and-price-and-cut method for computing an optimal bramble'. Together they form a unique fingerprint.

  • Cite this