A new surrogate dual multiplier search procedure

Sanjiv Sarin, Mark H. Karwan and Ronald L. Rardin

Naval Research Logistics (NRL), 1987, vol. 34, issue 3, 431-450

Abstract: Efficient computation of tight bounds is of primary concern in any branch‐and‐bound procedure for solving integer programming problems. Many successful branch‐and‐bound approaches use the linear programming relaxation for bounding purposes. Significant interest has been reported in Lagrangian and surrogate duals as alternative sources of bounds. The existence of efficient techniques such as subgradient search for solving Lagrangian duals has led to some very successful applications of Lagrangian duality in solving specially structured problems. While surrogate duals have been theoretically shown to provide stronger bounds, the difficulty of surrogate dual‐multiplier search has discouraged their employment in solving integer programs. Based on the development of a new relationship between surrogate and Lagrangian duality, we suggest a new strategy for computing surrogate dual values. The proposed approach allows us to directly use established Lagrangian search methods for exploring surrogate dual multipliers. Computational experience with randomly generated capital budgeting problems validates the economic feasibility of the proposed ideas.

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

Downloads: (external link)
https://doi.org/10.1002/1520-6750(198706)34:33.0.CO;2-P

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:34:y:1987:i:3:p:431-450

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 ().