Friday, 11:30 - 11:55 h, Room: H 3005


Erwin Pesch
A branch-and-bound algorithm for the acyclic partitioning problem

Coauthor: Jenny Nossack


We focus on the problem of partitioning the vertex set of a
directed, arc- and vertex-weighted graph into clusters, i.e. disjoint sets. Clusters are to be determined such that the sum of the vertex weights within the clusters satisfies an upper bound and the sum of the arc 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 has been proven to be NP-hard. Real-life applications arise at rail-rail transshipment yards. We propose new integer programming formulations for the acyclic partitioning problem and suggest an exact solution approach based on an integration constraint propagation into a branch-and-bound framework. Computational results are reported to confirm the strength of our approach.


Talk 3 of the invited session Fri.1.H 3005
"Combinatorial optimization in logistics" [...]
Cluster 2
"Combinatorial optimization" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.