Chapter 10 gives an introduction to linear programming on oriented matroids. It does not presuppose any experience with linear programming – but for the operations research practitioner it might offer an alternative view on linear programming from a matroid theory point of view. Our aim is to give the non-expert a smooth, geometric access to the fundamental ideas of oriented matroid programming, as developed in Bland (1974, 1977a). This necessitates extra care at the points where the terminologies from linear programming and from combinatorial geometry clash.

This chapter is intended to demonstrate that the oriented matroid framework can add to the understanding of the combinatorics and of the geometry of the simplex method for linear programming. In fact, the oriented matroid approach gives a geometric language for pivot algorithms, interpreting linear programs as oriented matroid search problems. We find that locally consistent information (orientation of the edges at a vertex) imply the existence of global extrema in pseudoarrangements. We believe that these techniques and results are applicable also to problems in other areas of mathematics.

The oriented matroid framework deals with (pseudo)linear programs, where

– positive cocircuits correspond to feasible vertices, and

– positive circuits correspond to bounding cones.

Both of these are described by oriented matroid bases, corresponding to temporary coordinate systems. Pivot algorithms are now modeled by basis exchanges, and the duality of linear programming becomes a manifestation of oriented matroid duality.

The benefits of geometric understanding are of course not one-sided: the linear programming frame work offers insight into the structure of oriented matroids, and the pivot algorithms of linear programming provide important search techniques for oriented matroids.