A polyhedral study of integer variable upper bounds

Diego Klabjan*, George L. Nemhauser

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

We study the polyhedron of the single node capacitated network design model with integer variable upper bounds. We first give a characterization of valid inequalities that is useful in proving the validity of several classes of inequalities. Next we derive several classes of valid inequalities and we give conditions for them to be facet-defining. Sequence independent lifting is used to obtain additional facets. We conclude by reporting computational results with a branch-and-cut algorithm.

Original languageEnglish (US)
Pages (from-to)711-739
Number of pages29
JournalMathematics of Operations Research
Volume27
Issue number4
DOIs
StatePublished - Jan 1 2002

Keywords

  • Branch-and-cut
  • Flow cover inequality
  • Integer programming
  • Integer variable upper bound

ASJC Scopus subject areas

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'A polyhedral study of integer variable upper bounds'. Together they form a unique fingerprint.

Cite this