Improving Discrete Model Representations via Symmetry Considerations

Hanif D. Sherali () and J. Cole Smith ()
Additional contact information
Hanif D. Sherali: Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061
J. Cole Smith: Department of Systems and Industrial Engineering, University of Arizona, P.O. Box 210020, Tucson, Arizona 85721-0020

Management Science, 2001, vol. 47, issue 10, 1396-1407

Abstract: In this paper, we focus on a useful modeling concept that is frequently ignored while formu lating discrete optimization problems. Very often, there exists a natural symmetry inherent in the problem itself that, if propagated to the model, can hopelessly mire a branch-and-bound solver by burdening it to explore and eliminate such alternative symmetric solutions. We discuss three applications where such a symmetry arises: a telecommunications network design problem, a noise pollution problem, and a machine procurement and operation problem. For each case, we identify the indistinguishable objects in the model that create the problem symmetry and show how imposing certain decision hierarchies within the model significantly enhances its solvability, while using a popular modern-day commercial branch-and-cut software (CPLEX 6.5).

Keywords: Integer Programming; Modeling; Tight Representation; Symmetry; Reformulation (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (53)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.47.10.1396.10265 (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:47:y:2001:i:10:p:1396-1407

Access Statistics for this article

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