Documentation

• Computes 210 facets of the 0/1 cut cone on the complete graph over 6 vertices
• Download sample input file Downloadccc6.ext (EXT, 1 KB)vertical_align_bottom
• File formats of cdd (cdd+, cddlib) and lrs libraries and tools, click here (link no longer available) for description of file formats
• See cdd, cddplus, cddlib homepage (link no longer available)
• See external pagelrs homepagecall_made

Calling polco from another Java program

You can also use polco as library within another Java program. An a example usage is given in the external pagejavadoc comments of the polco.adapter packagecall_made.

Background

The algorithm enumerates extreme rays of a polyhedral cone. The input of the algorithm is a homogeneous system of linear equalities (matrix A) and inequalities (B). The output is a matrix R with extreme rays as column vectors.

Algorithm input and output are formalized below, transformations for inhomogeneous systems (polytopes) and for facet enumerations follow.

We recommend the Polyhedral FAQ homepage to get more information about polyhedral computation.

Standard case

Input: equality matrix A^e×d and inequality matrix B^i×d
Output: extreme ray matrix R^d×n

Polyhedral cone P:

P = { A x = 0 , B x ≥ 0 }
P = { x = R c for some c ≥ 0 }

Inhomogeneous case (vertex enumeration for polyhedron or polytope)

Note: A polytope is a bounded convex polyhedron. We use the term polyhedron in the following.

P' = { A' x = a , B' x ≤ b }

Can be seen as intersection of a d+1 dimensional polyhedral cone P and a hyperplane. To transform into the standard case, we set:

A = [ a , -A' ]
B = [ b , -B' ]

The resulting extreme rays r_j^(d+1)×1 of P (columns in output matrix R) are interpreted as follows:

r_j(1) = 0r'_j = [ r_j(2) , r_j(3) , ... , r_j(d+1) ]^T
is an extreme ray of the polyhedron P' (an unbounded direction)r_j(1) > 0v'_j = [ r_j(2) , r_j(3) , ... , r_j(d+1) ]^T / r_j(1)
is a vertex of the polyhedron P'

Facet enumeration (convex hull)

Input: extreme ray matrix R'
Output: inequality matrix B'

Use standard extreme ray enumeration with input inequality matrix B and output extreme ray matrix R as follows:

B = R'^T
B' = R^T

API / Javadoc & Source files

• Javadoc of the API is available external pageonlinecall_made
• The Downloadpolco-src.jar (JAR, 2 MB)vertical_align_bottom bundle contains the Java source files.

Libraries

• external pagejavasoft.chcall_made (link no longer available) own development for numeric & matrix computations, a simple Java database, logging etc.
• external pagedom4jcall_made easy to use library for XML, XPath and XSLT
• external pagehdf-javacall_made Java wrapper to access the HDF native interface, used to write external pageHDF5call_made files.
• external pageJMatIOcall_made Matlab's MAT-file I/O API in pure Java, supports Matlab 5 MAT-flie format reading and writing