Improved Penalties for Fixed Cost Linear Programs Using Lagrangean Relaxation

Arevalo Victor and S. Selcuk Erenguc
Additional contact information
S. Selcuk Erenguc: University of Florida, Gainesville, Florida 32611

Management Science, 1986, vol. 32, issue 7, 856-869

Abstract: The most commonly used penalty in branch and bound approaches to integer programming is the Driebeek--Tomlin penalty. It has been used successfully in solving fixed cost linear programs by Kennington and Unger and by Barr, Glover and Klingman. It is well known that the Driebeek--Tomlin penalty can be derived from a Lagrangean relaxation of the integer programming problem. We show, however, that the Lagrangean relaxation for fixed cost problems not only yields the Driebeek--Tomlin penalty, but two penalties which sometimes dominate it. We show the strength of the new penalties by solving a series of text problems and comparing the number of nodes generated on the branch and bound tree and the total computer time needed to solve each problem.

Keywords: programming: integer algorithms; branch and bound (search for similar items in EconPapers)
Date: 1986
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.32.7.856 (application/pdf)

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:inm:ormnsc:v:32:y:1986:i:7:p:856-869

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().