The separable convex resource allocation problem with nested bound constraints aims to allocate $B$ units of resources to $n$ activities to minimize a separable convex cost function, with lower and upper bounds on the total amount of resources that can be consumed by nested subsets of activities. We develop a new combinatorial algorithm to solve this model exactly. Our algorithm is capable of solving instances of with millions of activities in several minutes. The running time of our algorithm is at most $65\%$ of the running time of the current best algorithm for benchmark instances with three classes of convex objectives. The efficiency of our algorithm derives from the combination of constraint relaxation and use of infeasibility information. In particular, nested bound constraints are relaxed first; if the obtained solution violates some bound constraint, we show that the problem can be divided into two subproblems of the same structure and smaller size, according to the bound constraint with the largest violation.

## Article

Download

View A new combinatorial algorithm for separable convex resource allocation with nested bound constraints