Linear programming duality: an introduction to oriented matroids

MaRDI QIDQ1189586zbMATH OpenFDO

Authors Walter Kern, Achim Bachem

Publication date 18 September 1992

Published in Universitext (Search for Journal in Brave)

zbMATH Keywords

dualityFarkas lemmaoriented matroidspartially ordered setspolyhedra

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Linear programming (90C05) Combinatorial optimization (90C27)

Review text

In the same sense as matroids describe abstractly the combinatorial background of linear independence, oriented matroids reveal the combinatorial structure underlying linear programming duality. This textbook develops the theory of oriented matroids from the viewpoint of linear programming and polyhedra. The authors start with a discussion of various versions of the Farkas Lemma, both in the framework of linear algebra and for directed graphs. This discussion leads to the notion of oriented matroids. It is shown what orthogonality, the elimination property and the Farkas lemma mean in this abstract combinatorial setting. Then the authors elaborate that linear programming duality is essential a matter of oriented matroids. As a second application of oriented matroids various properties of polyhedra are studied in this general framework. A further chapter of the book discusses the relations between oriented matroids and partially ordered sets. Finally topological realizations of oriented matroids are discussed, in particular examples for nonlinear oriented matroids are provided.

Recommendations

• Linear quadratic programming in oriented matroids
• scientific article; zbMATH DE number 3908166
• Oriented Matroids
• LINEAR COMPLEMENTARITY AND ORIENTED MATROIDS
• scientific article; zbMATH DE number 53152

Cited in

(26)

• A guided tour through oriented matroid axioms
• Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
• Edges versus circuits: a hierarchy of diameters in polyhedra
• Greedy oriented flows
• Nested cones and onion skins
• Investigations on autark assignments
• Orientations of chain groups
• Universal Gröbner basis associated with the maximum flow problem
• Facets of the cone of totally balanced games
• Facets of the cone of exact games
• Computing complex and real tropical curves using monodromy
• Enzyme allocation problems in kinetic metabolic networks: optimal solutions are elementary flux modes
• scientific article; zbMATH DE number 3906510 (Why is no real title available?)
• scientific article; zbMATH DE number 3908166 (Why is no real title available?)
• scientific article; zbMATH DE number 1182899 (Why is no real title available?)
• scientific article; zbMATH DE number 1889697 (Why is no real title available?)
• scientific article; zbMATH DE number 799945 (Why is no real title available?)
• scientific article; zbMATH DE number 922401 (Why is no real title available?)
• On the bijectivity of families of exponential/generalized polynomial maps
• Redundancy and Helly
• Sufficient Conditions for Linear Stability of Complex-Balanced Equilibria in Generalized Mass-Action Systems
• A SageMath package for elementary and sign vectors with applications to chemical reaction networks
• A theorem on the average number of subfaces in arrangements and oriented matroids
• The central curve in linear programming
• Linear quadratic programming in oriented matroids
• A unified interpretation of several combinatorial dualities

This page was built for publication: Linear programming duality: an introduction to oriented matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1189586)