lrslib1

Usage

Overview

A polyhedron can be described by a list of inequalities (H-representation) or as by a list of its vertices and extreme rays (V-representation). lrslib is a C library containing programs to manipulate these representations. All computations are done in exact arithmetic. lrs converts an H-representation of a polyhedron to its V-representation and vice versa, known respectively as the vertex enumeration and facet enumeration problems (see Example (1) below). lrs can also be used to solve a linear program, remove linearities from a system, and extract a subset of columns. redund removes redundant inequalities in an input H-representation and outputs the remaining inequalities. For a V-representation input it outputs all extreme points and extreme rays. Both outputs can be piped directly into lrs. redund is a link to lrs which performs these functions via the redund and redund_list options. mplrs is Skip Jordan's parallel wrapper for lrs/redund. lrsnash is Terje Lensberg's application of lrs for finding Nash-equilibria in 2-person games. hvref/xvref produce a cross reference list between H- and V-representations.

Arithmetic

From version 7.1 lrs/redund/mplrs use hybrid arithmetic with overflow checking, starting in 64bit integers, moving to 128bit (if available) and then GMP. Overflow checking is conservative to improve performance: eg. with 64 bit arithmetic, a*b triggers overflow if either a or b is at least 2^31, and a+b triggers an overflow if either a or b is at least 2^62. Typically problems that can be solved in 64bits run 3-4 times faster than with GMP and inputs solvable in 128bits run twice as fast as GMP. Various arithmetic versions are available and can be built from the makefile:

Notes

User's guide for lrslib