Utilizing the Surrogate Dual Bound in Capacity Planning with Economies of Scale


  • Hansuk Sohn New Mexico State University
  • Dennis Bricker The University of Iowa


Surrogate Dual, Capacity Planning, Economies of Scale, Nonconvex, Lagrangian Dual, Branch-and-Bound


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.

Author Biographies

Hansuk Sohn, New Mexico State University

Assistant Professor Industrial Engineering

Dennis Bricker, The University of Iowa

Associate Professor Mechanical and Industrial Engineering




How to Cite

Sohn, H., & Bricker, D. (2008). Utilizing the Surrogate Dual Bound in Capacity Planning with Economies of Scale. Algorithmic Operations Research, 3(1). Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/2313