An algorithm and new penalties for concave integer minimization over a polyhedron

Kurt M. Bretthauer, A. Victor Cabot and M. A. Venkataramanan

Naval Research Logistics (NRL), 1994, vol. 41, issue 3, 435-454

Abstract: We present a branch‐and‐bound algorithm for globally minimizing a concave function over linear constraints and integer variables. Concave cost functions and integer variables arise in many applications, such as production planning, engineering design, and capacity expansion. To reduce the number of subproblems solved during the branch‐and‐bound search, we also develop a framework for computing new and existing penalties. Computational testing indicates that penalties based on the Tuy cutting plane provide large decreases in solution time for some problems. A combination of Driebeek‐Tomlin and Tuy penalties can provide further decreases in solution time. © 1994 John Wiley & Sons, Inc.

Date: 1994
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199404)41:33.0.CO;2-6

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:41:y:1994:i:3:p:435-454

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().