Degeneracy degrees of constraint collections

Gerard Sierksma and Gert A. Tijssen

Mathematical Methods of Operations Research, 2003, vol. 57, issue 3, 437-448

Abstract: This paper presents an unifying approach to the theory of degeneracy of basic feasible solutions, vertices, faces, and all subsets of polyhedra. It is a generalization of the usual concept of degeneracy defined for basic feasible solutions of an LP-problem. We use the concept of degeneracy degree for arbitrary subsets of ℝ n with respect to linear constraint collections. We discuss the connection with the usual definitions, and establish the relationship between minimal representations of polyhedra and the degeneracy of their faces. We also consider a number of complexity aspects of the problem of determining degeneracy degrees. In the last section we show how our definition of degeneracy can be used to analyze the convergence of interior point methods when the optimal solutions are degenerate. Copyright Springer-Verlag Berlin Heidelberg 2003

Keywords: Key words: Linear Optimization; Optimization; Degeneracy; Polyhedron Complexity; Interior Point Method (search for similar items in EconPapers)
Date: 2003
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s001860200259 (text/html)
Access to full text is restricted to subscribers.

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:spr:mathme:v:57:y:2003:i:3:p:437-448

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s001860200259

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().