Rational for lrs_interface::solver, the template parameter for cdd_interface::solver

Prerequisits

#include <cdd_interface.h>
#include <lrs_interface.h>

using namespace polymake::polytope;

Introduction

class lrs_interface::solver;

An interface to the lrslib library, implementing the main LP and convex hull computations with exact arithmetic.

template <typename Coord> class cdd_interface::solver;

An interface to the cddlib library. It has two instances, for Rational and double.

Definitions and methods not qualified by the namespace name in the description below are common for both interfaces.

typedef Coord coord_type;
self-explanatory
solver();
Create an instance of the interface class. It contains only global internal data shared by all LP problems, so you will not usually need multiple instances of solver in your program. Nor they would disturb each other.
typedef std::pair< Matrix<Coord>, Matrix<Coord> > matrix_pair; matrix_pair enumerate_facets (const Matrix<Coord>& Points) throw (infeasible);
Find the convex hull of the given point set. Points must contain homogeneous coordinates of the points; the elements in the first column must be 1 for affine points and 0 for rays.
Return value:
first the facet normals
second the linearity basis (the subspace orthogonal to Points).
Matrix<Coord> enumerate_vertices (const Matrix<Coord>& Inequalities, const Matrix<Coord>& Equations) throw (infeasible, not_pointed);
Dual convex hull problem: find the vertices of a polyhedron given as an intersection of halfspaces (Inequalities∗X>=0) and hyperplanes (Equations∗X=0).
Returns the homogeneous coordinates of the vertices.
long lrs_interface::solver::count_facets (const Matrix<Coord>& Points) throw (infeasible, unbounded); std::pair<long,long> lrs_interface::solver::count_vertices (const Matrix<Rational>& Inequalities, const Matrix<Rational>& Equations, bool only_bounded=false) throw (infeasible, not_pointed);
These functions do practically the same as their enumerate_* cousins, but without storing the coordinates. Only the lrslib solver offers this functionality, since its algorithm indeed does not need internal storage.
Note that count_facets has an additional restriction: it can be used with bounded polytopes only. The reason is that in the unbounded case the lrs algorithm may produce repeating facets, which can't be filtered out without using additional storage.
count_vertices counts the bounded vertices and the rays separately. In the return value, first contains the total number of vertices, and second contains the number of bounded vertices (non-rays). If an optional argument only_bounded is set to true, the rays are not counted at all and the returned first field is zero. The reason for introducing this option is that the reverse search algorithm can generate the same rays multiple times, therefore the duplicates must be filtered out. If the polyhedron has very many rays, the storage consumption grows tremendously, defeating the only advantage of this counting function over the normal convex hull computation.
typedef std::pair<Bitset, Matrix<Coord> > lrs_interface::solver::non_redundant; typedef std::pair<Bitset, ListMatrix< Vector<Coord> > > cdd_interface::solver::non_redundant; find_vertices_among_points (const Matrix<Coord>& Points) throw( infeasible );
Separate the extremal vertices from the redundant points in a given point set. Points must contain homogeneous coordinates. This operation is cheaper than the complete convex hull computation, as it is based on repeating LP solving.
Return value:
first the vertex indices.
second (in lrs_interface::solver) the linearity basis (the subspace orthogonal to Points)
second (in cdd_interface::solver) the co-vertices, that is, normal vectors of hyperplanes separating the corresponding vertex from the rest.
Vector<Rational> lrs_interface::solver::find_a_vertex (const Matrix<Rational>& Inequalities, const Matrix<Rational>& Equations) throw( infeasible, not_pointed ); typedef std::pair< bool, Vector<Rational> > lrs_interface::solver::feasibility_solution; feasibility_solution lrs_interface::solver::check_feasibility (const Matrix<Rational>& Inequalities, const Matrix<Rational>& Equations);
Find an arbitrary vertex for which Inequalities∗X>=0 and Equations∗X=0 hold. Return the homogeneous coordinates.
If the linear system is infeasible, the first method rises an exception, while the second method returns first=false.
typedef std::pair<Coord, Vector<Coord> > lp_solution; lp_solution solve_lp (const Matrix<Coord>& Inequalities, const Matrix<Coord>& Equations, const Vector<Coord>& Objective, bool maximize) throw( infeasible, unbounded );
Solve the linear programming problem Objective∗X→max (min if maximize==false) subject to Inequalities∗X>=0 and Equations∗X=0.
Return value:
first the objective function value
second the extremal vertex