Improving discrete model representations via symmetry considerations

Hanif D. Sherali, J. Cole Smith

Research output: Contribution to journalArticle

141 Scopus citations

Abstract

In this paper, we focus on a useful modeling concept that is frequently ignored while formulating 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).

Original languageEnglish (US)
Pages (from-to)1396-1407
Number of pages12
JournalManagement Science
Volume47
Issue number10
DOIs
StatePublished - Oct 2001
Externally publishedYes

Keywords

  • Integer Programming
  • Modeling
  • Reformulation
  • Symmetry
  • Tight Representation

ASJC Scopus subject areas

  • Strategy and Management
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Improving discrete model representations via symmetry considerations'. Together they form a unique fingerprint.

Cite this