Options

The following options are available for cdd. These options are set if they appear in input file after the ``end'' command. Independent options can be set simultaneously, but each option must be written separately in one line, and two options should not be written in one line. When two or more non-independent options are specified, the last one overrides the others. Also note that options are case-sensitive.

hull

option
This old option exists only for the sake of backward compatibility. This is to enforce the computation to be convex hull computation, interpreting the current data as a V-representation. Use V-representation instead.

verify_input

option
When this option is chosen, the program will output the input problem as cdd+ interpreted. The default output file is ``*.solved''. This option helps user to verify what problem is actually solved. The default for this option is off. See the sample files verifyinput1.ine and verifyinput2.ine

dynout_off

option
When this option is chosen, the program will not output vertices and rays to the CRT in real time. The default is dynout_on.

stdout_off

option
When this option is chosen, the program will not output any progress report of computation (iteration number. etc). The default is stdout_on.

logfile_on

option
When this option is chosen, the program will output to a specified file (*.ddl) some information on the computation history. This can be useful when the user does not know which hyperplane order (mincutoff, maxcutoff, mixcutoff, lexmin, lexmax, minindex, random) is efficient for computation.

incidence, input_incidence, #incidence

options
When the incidence option is selected, the incidence relation for each output with respect to input will be generated. The default filename is *.icd if output is inequalities (i.e. *.ine), and *.ecd ¹if output is extreme points and rays (i.e. *.ext).

When the input_incidence option is selected, the incidence relation for each input with respect to output will be generated. The default filename is *.icd if input is inequalities (i.e. *.ine), and *.ecd if input is extreme points and rays (i.e. *.ext). This option was added to cdd+ ver. 0.74 and not available in cdd.

Here, an extreme point is said to be incident with an inequality if the inequality is satisfied by equality. An extreme ray $r$ is said to be incident with an inequality $a^T \; x \le b$ if $a^T \; r = 0$.

For example, since the incidence option was set for the example input file ucube.ine in the previous section, the program outputs the following ucube.ecd file:

*Incidences of output(=vertices/rays) and input (=hyperplanes)
*   for each output, #incidence and the set of hyperplanes containing it
*   or its complement with its cardinality with minus sign
*cdd input file : ucube.ine  (6 x 4)
*cdd output file: ucube.ext
begin
  5  6  7
 3 :  1 4 5
 3 :  3 4 5
 3 :  2 3 5
 -3 :  3 4 7
 -1 :  5
end

After ``begin'', there are three numbers $5 \quad 6 \quad 7$. The first number $5$ is a number of output (vertices and rays). The next number $6$ is $m$, the number of inequalities in the input file. The last number $7$ is usually $m+1$, and $m$ if the input linear inequality system is homogeneous (i.e., has zero RHS) or the hull option is chosen. The number $m+1$ corresponds to the infinity constraint which is added for vertex/ray enumeration when the input system is not homogeneous.

The incidence data starts right after these three numbers. At each line, the cardinality of incident inequalities and the list of their indices are given. There is an exception that, when there are more incident inequalities than non-incident ones, then the program outputs the list of non-incident inequalities with its size with negative sign. This is to save space of output.

For example, the first output line $3 \; : \; 1 \; 4 \; 5$ corresponds to the first vertex of ucube.ext file in previous section, that is, the vertex $(2,1,1)$. The first number $3$ is simply the number of incident inequalities and the rest is the indices of those inequalities, and so the 1st, 4th and 5th inequalities are satisfied by equality at this vertex. The last output $-1 \; : \; 5$ corresponds to the ray $(0,0,1)$. Since all inequalities except the last (5th) inequality are incident with this ray, the output is the (shorter) complementary list with its cardinality (=1) with negative sign. Note that the full list would be $6 \; : \; 1 \; 2 \; 3 \; 4 \; 6 \; 7$, where $6$ is the infinity plane. One can ignore the infinity plane for some purposes, but for analyzing the combinatorial structure of polyhedra, it is very important information.

Also, since the input_incidence option was set for the example input file ucube.ine in the previous section, the program outputs the following ucube.icd file:

*cdd input file : ucube.ine (6 x 4)
*cdd output file: ucube.ext
*Incidence of input (=inequalities/facets) w.r.t. output (=vertices/rays).
*row 7 is redundant;dominated by: 1 2 3 4 6
*row 6 is redundant;dominated by: 1 2
begin
  6  5  5
 -2 : 2 3
 -2 : 1 2
 -2 : 1 4
 -2 : 3 4
 -1 : 5
 2 : 4 5
 1 : 5
end

After ``begin'', there are three numbers $6 \quad 5 \quad 5$. The first number $6$ is a number of input (inequalities). The next number $5$ is $m$, the number of vertices and rays in the output file. The last number $5$ is always $m$ for all *.icd files. The remaining lines can be interpreted similarly with ucube.ecd file. The input_incidence option is not available in cdd.

The #incidence option can be used when you do not wish to output the incidence file but to output only the cardinality of incidence for each output, at the end of each output line.

The incidence files (adjacency file, input_adjacency as well) can be created independently after *.ext file is created, see ``postanalysis'' option.

nondegenerate

option
When this option is set, the program assumes that the input system is not degenerate, i.e., there is no point in the space $R^d$ satisfying more than $d$ inequalities of input with equality. It will run faster with this option, but of course, if this option is set for degenerate inputs, it is quite possible that the output is incorrect. The default is this option being off.

adjacency

option
This option can be used when you want to output the adjacency of output. When the output is the list of vertices and rays, the program will output the adjacency list. For the example input ``ucube.ine'', the following extra file ``ucube.ead'' ² will be created:

*Adjacency List of output (=vertices/rays)
*cdd input file : ucube.ine (6 x 4)
*cdd output file: ucube.ext
begin
  5
 1 3 : 2 4 5
 2 3 : 1 3 5
 3 3 : 2 4 5
 4 3 : 1 3 5
 5 4 : 1 2 3 4
end

The first number $5$ is simply the number of outputs of cdd, the number of vertices and rays in this case. The second line $1 \quad 3 \quad : 2 \quad 4 \quad 5$ says that the first output of ucube.ext file has degree (valency) $3$, and its three neighbors are 2nd, 4th and 5th output.

When the computation is to obtain the hull (inequality system), the adjacency is of course that of inequalities (i.e. facets).

The adjacency file (incidence file, input_adjacency file) can be created independently after *.ext file is created, see ``postanalysis'' option.

input_adjacency

option
This is for cdd+ and not available in cdd. This option is for outputing the adjacency of input inequalities. Here, two inequalities are defined to be adjacent if they are nonredundant and there is no third input inequality which is satisfied with equality at all points of the polyhedron that satisfy the two inequalities with equality. In more intuitive language, two inequalities are adjacent if each determine a facet of the polyhedron and the intersection of the two facets is not contained in any other facet.

The default file name for this output is *.iad. This file lists the redundancy information of input also. For the example ``ucube.ine'' above, the following ``ucube.iad'' will be generated:

*Adjacency List of input (=inequalities/facets)
*cdd input file : ucube.ine (6 x 4)
*cdd output file: ucube.ext
*row 7 is redundant;dominated by: 1 2 3 4 6
*row 6 is redundant;dominated by: 1 2
begin
  7
 1 3 : 2 4 5
 2 3 : 1 3 5
 3 3 : 2 4 5
 4 3 : 1 3 5
 5 4 : 1 2 3 4
 6 0 :
 7 0 :
end

Observe that the 6th inequality and the artificially added 7th inequality (infinity) are found redundant. The 7th inequality is redundant because the first four facets intersects at a single infinity point (corresponding to a unique extreme ray) and hence the polyhedron has no infinity facet, although the polyhedron is not bounded.

The input_adjacency file can be created independently after *.ext file is created, see ``postanalysis'' option.

While cdd+ uses both *.ine and *.ext files to compute the adjacency of input, it can be computed very efficiently by linear programming technique, using only the input data. This will be explained in the Polyhedral computation FAQ [Fuk04].

postanalysis

option
It is often more desirable to compute the adjacency, input_adjacency, incidence and input_incidence relations independently from the main (and often heavy) computation of enumerating all vertices and extreme rays. The ``postanalysis'' option can be used together with ``adjacency'' and/or ``incidence'' options for this purpose to create *.adj and/or *.icd files from both *.ine and *.ext files. If *.ine file contains this option, cdd+ will open the corresponding *.ext file and output requested *.adj, *.iad and/or *.icd files. An error occurs when *.ext file does not exist in the current directory.

lexmin, lexmax, minindex,mincutoff, maxcutoff, mixcutoff, random

options
The double description is an incremental algorithm which computes the vertices/rays of a polyhedron given by some $k$ of original inequalities from the precomputed vertices/rays of a polyhedron given by $k-1$ inequalities. It is observed that the efficiency of the algorithm depends strongly on how one selects the ordering of inequalities, although a little can be said theoretically. These options are to select the ordering of inequalities to be added at each iteration, and it is recommended to do small experiment to select good ordering for a specific type of problems. Unfortunately, a good ordering depends on the problem and there does not seem to be THE BEST ordering for every computation. From our experiences, lexmin, lexmax, mincutoff, maxcuoff work quite well in general.

The default is lexmin ordering which simply order inequalities with respect to lexico-graphic ordering of rows of $(b, -A)$. The lexmax is reverse of lexmin. The mincutoff (maxcutoff) option selects an inequality which cuts off the minimum (maximum) number of vertices/rays of the $(k-1)$st polyhedron. The mixcutoff option is the mixture of mincutoff and maxcutoff which selects an inequality which cuts off the $(k-1)$st polytope as unbalanced as possible. The maxcutoff option might be efficient if the input contains many redundant inequalities (many interior points for hull computation). The minindex option selects the hyperplanes from the top of the input.

The random option selects the inequalities in a random order. This option must be followed by a random seed which is positive integer (less than 65536). For example, random 123 specifies the random option with the random seed 123.

initbasis_at_bottom

option
When this option is set, the program tries to select the initial set of rows for the double description method from the bottom of the input. This means that if the last (d+1) rows are independent, they will be chosen to initiate the algorithm.

This option is not default. The default follows the same ordering as the ordering of inequalities chosen. This means that if lexmin is the ordering of inequalities, then the initial independent rows will be chosen sequentially with lexico-min ordering. There are exceptions when this rule is not applicable, i.e. when one of mincutoff or maxcutoff options is chosen. In such cases, lexmin ordering will be chosen.

maximize, minimize

options
When maximize option is set with an objective vector $c_0\: c_1 \: c_2 \ldots c_d$, the program simply solves the linear program: $\max c_0 + c_1 x_1 + c_2 x_2 +\cdots + c_d x_d$ over the input polyhedron $P$. The grammar is simply

various comments
H-representation
begin
$m$	$d+1$	numbertype
$b$	$-A$
end
maximize
$c_0 \quad c_1 \quad c_2 \quad \cdots \quad c_d$

The minimize option works exactly same way for minimization of a linear objective function. See the sample input file ``lptest.ine''. The program cdd will output both primal and dual optimal solutions if the LP is solvable. If the LP is infeasible (dual infeasible), then it will output an evidence.

For the moment, one can use either the dual simplex method (option ``dual-simplex'', default) or the criss-cross method by Terlaky-Wang. The latter method can be specified by option ``criss-cross'' and is very sensible to the ordering of inequalities. The ordering options such as maxindex, lexmin and random will affect the behavior of this solver. Try to use a different ordering, if the computation takes too much time.

Also, in order to see the intermediate LP sign tableau one can use ``show_tableau'' option. Also use ``manual_pivot'' option to select pivots manually. Of course, these options are intended for very small problems.

The minimize and maximize options should be used only in H-representation (*.ine) files, and the output filename is ``*.lps''.

find_interior

option
This is for cdd+ and not available in cdd. When this option is set, the program solves the linear program: $\max x_{d+1}$ subject to $A x + e x_{d+1} \le b$, where $e$ is the column vector of all $1$'s. If the optimum value is zero, the polyhedron has no interior point. If the optimum value is negative then the polyhedron is empty. If the LP is dual inconsistent, then the polyhedron admits unbounded inscribed balls. To find any interior point in this last case, one must add some inequality(ies) to bound the polyhedron.

This option should be used only in H-representation (*.ine) files, and the output filename is ``*.lps''.

facet_listing, vertex_listing

options
These are for cdd+ and not available in cdd. When the option ``facet_listing'' is set, the program checks for each i-th row of the input whether the associated inequality $A_i x \le b_i$ determines a facet of the polyhedron. This option should be used only in H-representation (*.ine) files, and the output filename is ``*.fis''.

When the option ``vertex_listing'' is set, the program checks for each i-th row of the input whether the associated point $v_i$ determines a vertex of the polyhedron. This option should be used only in V-representation (*.ext) files, and the output filename is ``*.vis''.

After *.vis or *.fis file (say test.vis) is obtained, one can get the minimal nonredundant system by using the included gawk script get_essential:

% get_essential <  test.vis >test\_ess.ine

You must have a gnu gawk command accessible at the current unix directory. One must edit the new file test_ess.ine slightly according to the instruction written in the file.

facet_listing_external, vertex_listing_external

options
These options can be used to apply facet_listing and vertex_listing with a (possibly large) external file. When the option facet_listing_external is set with *.ine file, cdd+ will open an external file *.ine.external (in H-format) and verify for each inequality of the external file whether it changes the original polyhedron (represented by *.ine) if it is added. The option vertex_listing_external can be set in *.ext file and works similarly. Since cdd+ reads each line of the external file one by one, the file can be very large, say of few hundred thousands lines.

tope_listing

option
This is for cdd+ and not available in cdd. When this option is set, the program generates all full-dimensional regions (which are sometimes called topes) of the arrangement of hyperplanes $\{ h_i : i = 1,2, \ldots, m \}$, where $h_i = \{ x : A_i x \le b_i \}$. Each tope will be represented by its location vector, i.e. a sign vector in $\{+, -\} ^m$ whose $i$-component indicates the (positive or negative) side of the hyperplane $h_i$ the tope is located. This procedure assumes that the input polyhedron is full-dimensional and thus the vector of all $+$'s determines a tope. This option should be used only in H-representation (*.ine) files, and the output filename is ``*.tis''.

partial_enumeration, equality, linearity, strict_inequality

options
With partial_enumeration option (or equivalently equality or linearity options), one can enumerate only those vertices and rays that are lying on the set of hyperplanes associated with specified inequality numbers. If you want to compute all vertices/rays lying on hyperplanes associated with $k$ inequalities $i_1, i_2, \ldots, i_k$ ( $1 \le i_j \le m$), then the option should be specified as

various comments
H-representation
begin
$m$	$d+1$	numbertype
$b$	$-A$
end
partial_enumeration
$k \quad i_1 \quad i_2 \quad \cdots \quad i_k$

The strict_inequality option follows the same grammar as partial_enumeration or equality. With this, cdd outputs only those vertices and rays not satisfying any of the specified inequalities with equality. See the sample files, partialtest1.ine and partialtest2.ine.

These options make no effect on LP maximization or minimization.

preprojection

option
This option is for a preprocessing of orthogonal projection of the polyhedron to the subspace of $R^d$ spanned by a subset of variables. That is, if the inequality inequality system is of two-block form $A_1 x_1 + A_2 x_2 \le b$, and the variable indices for $x_1$, say $1, 4, 6, 7$, are listed in the input file as

H-representation
begin
$m$	$d+1$	numbertype
$b$	$-A$
end
preprojection
$4 \quad 1 \quad 4 \quad 6 \quad7$

Then, cdd+ will output the inequality system, $A_1 x_1 \le b$, together with the list $R$ of extreme rays of the homogeneous cone $\{z: z \ge 0 \mbox{ and } z^T A_2 = 0 \}$. Consequently, the inequality system $\{ \quad r^T A_1 x_1 \le r^T b : \quad r \in R \}$ represents the projection of the original polyhedron onto $x_1$-space with possible redundancy. The default file names for the inequality system output and the extremal ray output are *sub.ine and *.ext, respectively if the input file is named *.ine.

There is a supplementary C program, called domcheck, written by F. Margot, EPFL, which generates quickly a minimal (i.e. nonredundant) system from these two outputs. This program can be obtained from the standard ftp site for cdd.

zero_tolerance

option
This option is for cdd+ and not available in cdd. This affects only the floating-point computation with cddf+. This is to change the zero tolerance for floating point computation to a user-specified value. The default value is set in cddtype.h file as $10^{-6}$. This should not be changed if you are not familiar with pitfalls of floating-point computation. A tolerance value should follow the option with blank(s) or a line break. If a tolerance is too small (e.g. $10^{-20}$), or if it is too big (e.g. $0.1$), the computation will most likely fail.

round_output_off, output_digits

options
These options are for cdd+ and not available in cdd. This affects only the floating-point computation with cddf+. This is to modify the default output format of numbers. The default is to output a number with 8 digits in scientific notation, except when the nearest integer is within $10^{-6}$, it outputs the integer. The first option is to cancel the latter rounding. This is recommended when zero_tolerance option above is used to change the tolerance. The second option followed by a positive integer will set the number of digits for each number to the integer.