Determining the right-hand vectors of an irredundant linear inequality system

Ramprasad Potluri, Lawrence E. Holloway

Research output: Contribution to journalArticlepeer-review

Abstract

Two methods are discussed for determining the set of all b for which the system Ax {less-than or slanted equal to} b (A-constant) is irredundant. For { n = fixed, m = var } and { m - n = fixed, m = var }, the first method is of polynomial complexity and worked significantly faster. The set turns out to be a convex open unbounded polyhedron.

Original languageEnglish
Pages (from-to)373-381
Number of pages9
JournalOperations Research Letters
Volume34
Issue number4
DOIs
StatePublished - Jul 2006

Bibliographical note

Funding Information:
This work has been supported in part by NSF Grant ECS-9807106, USARO GRANT daah04-96-1-0399, and the Center for Robotics and Manufacturing Systems at the University of Kentucky. IIT Delhi provided computational support. The authors are grateful to Dr. Vincent Loechner for a counterexample to an earlier conjecture, to Dr. Carl Lee (Mathematics, University of Kentucky) for the many hours he spent with them trying to advance the third method, and to Dr. Suresh Chandra (Mathematics, IIT Delhi, India) for discussions. Many thanks to the anonymous referee for raising important questions that helped improve the paper significantly.

Keywords

  • Irredundancy
  • Linear programming
  • Vertex-enumeration

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Determining the right-hand vectors of an irredundant linear inequality system'. Together they form a unique fingerprint.

Cite this