Utilizing the surrogate dual bound in capacity planning with economies of scale

Minimizing a nondecreasing separable concave cost function over a polyhedral set arises in capacity planning problems where economies of scale and fixed costs are significant, as well as production planning when a learning effect results in decreasing marginal costs. This is an NP-hard combinatorial problem in which the extreme points of the polyhedral set must be enumerated, each of them a local optimum. Branch-and-bound methods have been frequently used to solve these problems. Although it has been shown that in general the bound provided by the surrogate dual is tighter than that of the Lagrangian dual, the latter has generally been preferred because of the apparent computational intractability of the surrogate dual problem. In this paper we describe a branch-and-bound algorithm that exploits the superior surrogate dual bound in a branch-and-bound algorithm without explicitly solving the dual problem. This is accomplished by determining the feasibility of a set of linear inequalities.