Analysis of Lagrangian Lower Bounds for a Graph Partitioning Problem

Gajendra K. Adil and Jay B. Ghosh
Additional contact information
Gajendra K. Adil: Department of Mechanical and Industrial Engineering, University of Manitoba, Winnipeg, Canada
Jay B. Ghosh: Faculty of Business Administration, Bilkent University, Ankara, Turkey

Operations Research, 1999, vol. 47, issue 5, 785-788

Abstract: Recently, Ahmadi and Tang (1991) demonstrated how various manufacturing problems can be modeled and solved as graph partitioning problems. They use Lagrangian relaxation of two different mixed integer programming formulations to obtain both heuristic solutions and lower bounds on optimal solution values. In this note, we point to certain inconsistencies in the reported results. Among other things, we show analytically that the first bound proposed is trivial (i.e., it can never have a value greater than zero) while the second is also trivial for certain sparse graphs. We also present limited empirical results on the behavior of this second bound as a function of graph density.

Keywords: manufacturing; cell formation; tool loading; VLSI design; networks/graphs; partitioning; programming; integer; Lagrangian relaxation (search for similar items in EconPapers)
Date: 1999
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.47.5.785 (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:oropre:v:47:y:1999:i:5:p:785-788

Access Statistics for this article

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