A branch-and-bound algorithm for the acyclic partitioning problem. Nossack, J. & Pesch, E. *Computers and Operations Research*, 41(1):174-184, Elsevier, 1, 2014.

Paper Website abstract bibtex

Paper Website abstract bibtex

We focus on the problem of partitioning the vertex set of a directed, edge- and vertex-weighted graph into clusters, i.e., disjoint subsets. Clusters are to be determined such that the sum of the vertex weights within the clusters satisfies an upper bound and such that the sum of the edge weights within the clusters is maximized. Additionally, the graph is enforced to partition into a directed, acyclic graph where the clusters define the vertices. This problem is known as the acyclic partitioning problem and is NP-hard. Real-life applications arise, for example, in VLSI design and at rail-rail transshipment yards. We propose an integer programming formulation for the acyclic partitioning problem and suggest an exact solution approach based on a branch-and-bound framework that integrates constraint propagation. Computational results are reported to confirm the strength of our solution proposal. © 2013 Elsevier Ltd.

@article{ title = {A branch-and-bound algorithm for the acyclic partitioning problem}, type = {article}, year = {2014}, identifiers = {[object Object]}, keywords = {Acyclic graph,Branch-and-bound,Constraint propagation,Container transshipment,Graph partitioning}, pages = {174-184}, volume = {41}, websites = {http://linkinghub.elsevier.com/retrieve/pii/S0305054813002190}, month = {1}, publisher = {Elsevier}, id = {667ca17d-fb4a-3f36-9b27-48202bdd98fb}, created = {2015-03-23T18:50:21.000Z}, accessed = {2014-10-31}, file_attached = {true}, profile_id = {756a70ce-605d-3e50-9cbb-a99c29afcbe8}, group_id = {1f5b486a-d8ac-3a35-9104-56111360dab7}, last_modified = {2017-03-14T11:36:44.206Z}, read = {true}, starred = {false}, authored = {false}, confirmed = {true}, hidden = {false}, citation_key = {Nossack2014}, private_publication = {false}, abstract = {We focus on the problem of partitioning the vertex set of a directed, edge- and vertex-weighted graph into clusters, i.e., disjoint subsets. Clusters are to be determined such that the sum of the vertex weights within the clusters satisfies an upper bound and such that the sum of the edge weights within the clusters is maximized. Additionally, the graph is enforced to partition into a directed, acyclic graph where the clusters define the vertices. This problem is known as the acyclic partitioning problem and is NP-hard. Real-life applications arise, for example, in VLSI design and at rail-rail transshipment yards. We propose an integer programming formulation for the acyclic partitioning problem and suggest an exact solution approach based on a branch-and-bound framework that integrates constraint propagation. Computational results are reported to confirm the strength of our solution proposal. © 2013 Elsevier Ltd.}, bibtype = {article}, author = {Nossack, Jenny and Pesch, Erwin}, journal = {Computers and Operations Research}, number = {1} }

Downloads: 0

{"_id":"bv64irKNxPLgsxiuF","bibbaseid":"nossack-pesch-abranchandboundalgorithmfortheacyclicpartitioningproblem-2014","downloads":0,"creationDate":"2018-03-26T07:07:40.589Z","title":"A branch-and-bound algorithm for the acyclic partitioning problem","author_short":["Nossack, J.","Pesch, E."],"year":2014,"bibtype":"article","biburl":null,"bibdata":{"title":"A branch-and-bound algorithm for the acyclic partitioning problem","type":"article","year":"2014","identifiers":"[object Object]","keywords":"Acyclic graph,Branch-and-bound,Constraint propagation,Container transshipment,Graph partitioning","pages":"174-184","volume":"41","websites":"http://linkinghub.elsevier.com/retrieve/pii/S0305054813002190","month":"1","publisher":"Elsevier","id":"667ca17d-fb4a-3f36-9b27-48202bdd98fb","created":"2015-03-23T18:50:21.000Z","accessed":"2014-10-31","file_attached":"true","profile_id":"756a70ce-605d-3e50-9cbb-a99c29afcbe8","group_id":"1f5b486a-d8ac-3a35-9104-56111360dab7","last_modified":"2017-03-14T11:36:44.206Z","read":"true","starred":false,"authored":false,"confirmed":"true","hidden":false,"citation_key":"Nossack2014","private_publication":false,"abstract":"We focus on the problem of partitioning the vertex set of a directed, edge- and vertex-weighted graph into clusters, i.e., disjoint subsets. Clusters are to be determined such that the sum of the vertex weights within the clusters satisfies an upper bound and such that the sum of the edge weights within the clusters is maximized. Additionally, the graph is enforced to partition into a directed, acyclic graph where the clusters define the vertices. This problem is known as the acyclic partitioning problem and is NP-hard. Real-life applications arise, for example, in VLSI design and at rail-rail transshipment yards. We propose an integer programming formulation for the acyclic partitioning problem and suggest an exact solution approach based on a branch-and-bound framework that integrates constraint propagation. Computational results are reported to confirm the strength of our solution proposal. © 2013 Elsevier Ltd.","bibtype":"article","author":"Nossack, Jenny and Pesch, Erwin","journal":"Computers and Operations Research","number":"1","bibtex":"@article{\n title = {A branch-and-bound algorithm for the acyclic partitioning problem},\n type = {article},\n year = {2014},\n identifiers = {[object Object]},\n keywords = {Acyclic graph,Branch-and-bound,Constraint propagation,Container transshipment,Graph partitioning},\n pages = {174-184},\n volume = {41},\n websites = {http://linkinghub.elsevier.com/retrieve/pii/S0305054813002190},\n month = {1},\n publisher = {Elsevier},\n id = {667ca17d-fb4a-3f36-9b27-48202bdd98fb},\n created = {2015-03-23T18:50:21.000Z},\n accessed = {2014-10-31},\n file_attached = {true},\n profile_id = {756a70ce-605d-3e50-9cbb-a99c29afcbe8},\n group_id = {1f5b486a-d8ac-3a35-9104-56111360dab7},\n last_modified = {2017-03-14T11:36:44.206Z},\n read = {true},\n starred = {false},\n authored = {false},\n confirmed = {true},\n hidden = {false},\n citation_key = {Nossack2014},\n private_publication = {false},\n abstract = {We focus on the problem of partitioning the vertex set of a directed, edge- and vertex-weighted graph into clusters, i.e., disjoint subsets. Clusters are to be determined such that the sum of the vertex weights within the clusters satisfies an upper bound and such that the sum of the edge weights within the clusters is maximized. Additionally, the graph is enforced to partition into a directed, acyclic graph where the clusters define the vertices. This problem is known as the acyclic partitioning problem and is NP-hard. Real-life applications arise, for example, in VLSI design and at rail-rail transshipment yards. We propose an integer programming formulation for the acyclic partitioning problem and suggest an exact solution approach based on a branch-and-bound framework that integrates constraint propagation. Computational results are reported to confirm the strength of our solution proposal. © 2013 Elsevier Ltd.},\n bibtype = {article},\n author = {Nossack, Jenny and Pesch, Erwin},\n journal = {Computers and Operations Research},\n number = {1}\n}","author_short":["Nossack, J.","Pesch, E."],"urls":{"Paper":"https://bibbase.org/service/mendeley/756a70ce-605d-3e50-9cbb-a99c29afcbe8/file/6e824628-5fbd-1b8b-6c61-c9963a59bae8/2014-A_branch-and-bound_algorithm_for_the_acyclic_partitioning_problem.pdf.pdf","Website":"http://linkinghub.elsevier.com/retrieve/pii/S0305054813002190"},"bibbaseid":"nossack-pesch-abranchandboundalgorithmfortheacyclicpartitioningproblem-2014","role":"author","keyword":["Acyclic graph","Branch-and-bound","Constraint propagation","Container transshipment","Graph partitioning"],"downloads":0},"search_terms":["branch","bound","algorithm","acyclic","partitioning","problem","nossack","pesch"],"keywords":["acyclic graph","branch-and-bound","constraint propagation","container transshipment","graph partitioning"],"authorIDs":[]}