Analysis of Lagrangian Lower Bounds for a Graph Partitioning Problem

The capacitated network design problem is a multicommodity minimal cost network flow problem with fixed charges on the arcs and is well known to be NP-hard. The problem type is very common in the context of transportation networks, telecommunication ...

This paper studies a topical and economically significant capacitated network design problem that arises in the telecommunications industry. In this problem, given point-to-point communication demand in a network must be met by installing loading ...

We propose a general branch-and-bound algorithm for discrete optimization in which binary decision diagrams BDDs play the role of the traditional linear programming relaxation. In particular, relaxed BDD representations of the problem provide bounds and ...