A Lot-Sizing Problem on Trees, Related to Network Design

We describe a capacity expansion problem on trees, which arises in the design of certain communications networks, and is related to the knapsack and the economic lot-sizing problems. One of the main features is that production takes place in fixed (and possibly large) batch sizes. Another feature is that there may be various commodities competing for capacity resources. We present various exact and ε-approximate algorithms for this problem.