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

Name: A branch-and-price-and-cut method for computing an optimal bramble
Author: Sonuç, Sibel Bilge, Smith, J. C., Hicks, I. V.

İsim	A branch-and-price-and-cut method for computing an optimal bramble
Yazar	Sonuç, Sibel Bilge, Smith, J. C., Hicks, I. V.
Basım Tarihi:	2015
Basım Yeri	- Elsevier
Konu	Bramble, Branch-and-price, Treewidth, Integer programming
Tür	Süreli Yayın
Dil	İngilizce
Dijital	Evet
Yazma	Hayır
Kütüphane:	Özyeğin Üniversitesi
Demirbaş Numarası	1873-636X
Kayıt Numarası	b890101e-2adf-41df-acc7-5f1e7a33d54d
Lokasyon	Industrial Engineering
Tarih	2015
Notlar	Due to copyright restrictions, the access to the full text of this article is only available via subscription.
Örnek Metin	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.
DOI	10.1016/j.disopt.2015.09.005
Cilt	18

Kaynağa git Özyeğin Üniversitesi

Aramaya Dön

Özyeğin Üniversitesi

Kaynağa git

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

Yazar Sonuç, Sibel Bilge, Smith, J. C., Hicks, I. V.

Basım Tarihi 2015

Basım Yeri - Elsevier

Konu Bramble, Branch-and-price, Treewidth, Integer programming

Tür Süreli Yayın

Dil İngilizce

Dijital Evet

Yazma Hayır

Kütüphane Özyeğin Üniversitesi

Demirbaş Numarası 1873-636X

Kayıt Numarası b890101e-2adf-41df-acc7-5f1e7a33d54d

Lokasyon Industrial Engineering

Tarih 2015

Notlar Due to copyright restrictions, the access to the full text of this article is only available via subscription.

Örnek Metin 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.

DOI 10.1016/j.disopt.2015.09.005

Cilt 18