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

Authors

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

Keywords:

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

Abstract

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

Downloads

Published

2008-03-25

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

Issue

Vol. 3 No. 1 (2008)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.