Keywords

1 Introduction

It is well-known that any convex polyhedron \(P\subseteq F^d\), where F is an ordered field, can be represented in any of the following two ways:

  1. (1)

    as the set \(P = \{x \in F^d:~ Ax \le b\}\) of solutions to a system of linear inequalities, where \(A \in F^{m \times d}\), \(b\in F^m\) (facet description);

  2. (2)

    as the sum of the conical hull of a set of vectors \(v_1,\dots ,v_s\) in \(F^d\) and the convex hull of a set of points \(w_1,\dots ,w_n\) in \(F^d\) (vertex description).

The problem of finding the representation (1) given the representation (2) is called the convex hull problem. According to the classical theorem of Weyl this problem is equivalent (dual) to the problem of constructing the representation (2) given the representation (1). These two problems are referred to as finding the dual representation of a polyhedron.

The problem of constructing the dual representation of a convex polyhedron plays a central role in the theory of systems of linear inequalities and computational geometry [11, 21]. For some applications, the representation (1) is convenient, while in other cases the representation (2) is more usable, therefore, it is important to quickly move from one description to another. The importance of studying this problem is also emphasized by the fact that it has a variety of applications, the most known of which are linear and integer programming [18], combinatorial optimization [19, 21] and global optimization [15]. Some of the newer applications are biological kinetics [20], analysis and verification of software and hardware [5], identification of dynamic systems [13] and computer algebra [17, 22].

From an algorithmic or theoretical points of view it is convenient to consider these problems only for polyhedral cones. Any polyhedral cone \(C\subseteq F^d\) can be represented in two equivalent ways:

  1. (1)

    as the set \(C = \{x \in F^d:~ Ax \ge 0\}\) of solutions to a homogeneous system of linear inequalities, where \(A \in F^{m \times d}\), or

  2. (2)

    as the conical hull of a set of vectors \(v_1,\dots ,v_s\).

There is a standard method for reducing the problem of finding the dual representation for convex polyhedra to the corresponding one for polyhedral cones. For example, in order to find representation (2) for a polyhedron \(P = \{x \in F^d:~ Ax \le b\}\) it is sufficient to solve the corresponding problem for the polyhedral cone \(\{x=(x_0,x_1,\dots ,x_d) \in F^{d+1}:~ bx_0 - Ax \ge 0,~ x_0 \ge 0\}\), and then set \(x_0 = 1\) (see Section 1.5 in [21]).

There are several known algorithms for solving problems of finding the dual representation. One of the most popular ones is the double description method (DDM) [16], also known as the Motzkin–Burger algorithm [11] or Chernikova’s algorithm [12]. The double description method generally outperforms the other algorithms when applied to degenerate inputs and/or outputs [3].

There are multiple known programs implementing various modifications of the double description method. Among the most well-known are:

Implementations of other algorithms solving the given problem should also be noted:

In this paper we consider the dynamic problem of finding the dual representation. This problem appears in many of the applications listed above. For definiteness, we will deal with the problem of constructing a description (2) if the description (1) is given. In dynamic problem the full list of constraints is not known in advance and the constraints come to the input of the algorithm online as the computation proceeds, and the dual description must be computed at each iteration for the current system of linear inequalities. Such framework does not allow the use of many of the heuristics proposed by various authors (see the references above) to accelerate the algorithm. Nevertheless, we propose such an algorithm (as a version of the double description method) for the dynamic problem, and our algorithm is usually not inferior in performance to other offline algorithms.

The problem of efficient removal of constraints from the double description is considered in [1, 7]. Other issues concerning the dynamic problem are studied in [8].

2 Preliminaries

The material in this section is based on [11, 18, 21]. A polyhedral cone, or simply a cone, in \(F^d\) is defined as a set

$$ C = \left\{ x\in F^d:~ Ax\ge 0\right\} , $$

where F is an ordered field, \(A \in F^{m \times d}\). The system of linear inequalities \(Ax \ge 0\) is said to define the cone C. A cone is called pointed, if it contains no zero subspaces. It is well-known that for a cone to be pointed it is necessary and sufficient that rank A = d, where rank A denotes the rank of matrix A. Any polyhedral cone C can be defined as the conical hull of a finite set of vectors \(v_1, v_2, \dots , v_s\) in \(F^d\), i. e.

$$ C = \left\{ x=\alpha _1 v_1 + \alpha _2 v_2 + \dots + \alpha _s v_s:~\alpha _i \ge 0~(i=1,\dots ,s)\right\} . $$

By writing vectors \(v_1, v_2, \dots , v_s\) as rows of matrix \(V \in F^{s\times d}\) the conical hull can be defined as

$$ C = \left\{ x=\alpha V,~ \alpha \in F^{s},~\alpha \ge 0\right\} , $$

where \(\alpha \) is a row vector. The set of vectors \(v_1, \dots , v_s\) are said to generate the cone C.

A non-zero vector \(u \in C\) is referred to as a ray of the cone C. Two rays u and v are equal (written as \(u \simeq v\)) if for some \(\alpha > 0\) it is true that \(u = \alpha v\). A ray \(u \in C\) is said to be extreme if the condition \(u = \alpha v + \beta w\), where \(\alpha \ge 0\), \(\beta \ge 0\) and \(v, w \in C\) implies \(u\simeq v\simeq w\). Suppose that P is a convex subset of \(F^d\), and for some \(a\in F^d\), \(\alpha \in F\), it holds that \(P \subseteq \left\{ x :~ ax \le \alpha \right\} \). Then \(P \cap \left\{ x :~ ax = \alpha \right\} \) is called a face of the set P. Two different extreme rays u and v of a pointed cone C are said to be adjacent, if no minimal face containing both rays contains any other extreme rays of the cone C.

The problem of constructing the set of vectors generating polyhedral cone \(C = \left\{ x\in F^d:~ Ax\ge 0\right\} \) is reduced to finding the extreme generators of a pointed cone by transition to the orthogonal complement \(L^{\bot }\) of the maximal subspace \(L=\left\{ x\in F^d:~Ax = 0\right\} \) contained inside C. Unfortunately, in our study we cannot take advantage of this fact (as is often the case), since in the process of adding new inequalities, the space L may change.

Notations: \(I_{d\times d}\) is the identity matrix of size \(d\times d\), \(O_{s\times m}\) is the zero matrix of size \(s\times m\), \(A_i\) is the i-th row of matrix A, \(A_{ij}\) is the element from the i-th row and j-th column of matrix A.

3 Dynamic Double Description Method

The dynamic variant of the double description method is based on the regular double description method [11]. The procedure takes a matrix \(A\in F^{m\times d}\) as its input. The output is matrices \(U\in F^{t\times d}\) and \(V\in F^{s\times d}\), the rows of which compose a basis of maximal subspace \(L=\left\{ x\in F^d:~ Ax=0\right\} \) and an irreducible set of vectors generating the cone \(C=\left\{ x\in F^d:~ Ax \ge 0\right\} \) respectively.

figure a

The normalization function Normalize used in the algorithm is necessary to prevent unlimited growth of elements. Its implementation may vary, the one used in this study for integer calculations divides each element of the input vector by their greatest common divisor. The Adjacent function checks a pair of extreme rays for adjacency.

Typically modifications of the double description method alter some of the following three parameters:

  1. (1)

    the order in which the rows of the primal representation are considered

  2. (2)

    the test for adjacency of two extreme rays

  3. (3)

    the moment when the extreme rays are tested for adjacency.

Since the dynamic version of the double description method has to support online input of inequalities, only modifications of the latter two aspects are applicable to this algorithm. Two versions of adjacency test were implemented: the combinatorial test [16], and the graph test [23].

figure b
figure c

Some modifications of the double description method were proposed (e.g. [14]) where the set of adjacent extreme rays is maintained and rebuilt immediately after the list of extreme rays is updated. Instead of iterating over all pairs of rays (u, v) for which \(u A_i^{\top }\cdot v A_i^{\top }< 0\) to generate new extreme rays the algorithm iterates over all pairs of adjacent extreme rays. Below is an adaptation of such a modification for the dynamic version of the algorithm which will be referred to as M1.

figure d

Adjacent.M1\((Q, J_\pm )\) is a simple modification of Adjacent\((Q, J_1, J_2)\) that iterates over \(\{\{j_1, j_2\} : j_1 \in J_\pm , j_2 \in J_\pm , j_1 \ne j_2\}\) rather than \(\{(j_1, j_2) : j_1 \in J_1, j_2 \in J_2\}\).

4 Computational Results

A C++ implementation of the dynamic double description method and its modifications presented above has been developed. The computational experiments were performed on a computer with Intel(R) Core(TM) i7-8700K CPU at 3.70 GHz, Microsoft Windows 10 operating system, using the Microsoft Visual Studio 2017 compiler. The experiments were run using the problem instances described in [14].

Tables 1 and 2 present the performance comparison of DDM-dyn, its modification DDM-dyn.M1 and Skeleton [23], with/without its PlusPlus modification. Since computation time depends significantly on the order in which the rows of the primal representation are considered and which is fixed in the case of the dynamic algorithm, Skeleton was used with the minindex order of consideration. Note that the PlusPlus modification of Skeleton reduces the number of adjacency checks by relying on the fact that the entire primal representation is known ahead of time and, therefore, it cannot be adopted for use with online input of inequalities.

Figures 1, 2 and 3 demonstrate the dependence of the number of adjacency checks on the number of iteration made by DDM-dyn and DDM-dyn.M1 on cube18, mit729-9 and ccc7 problems. The number of the checks varies from one problem instance to another and heavily impacts total computation time.

Table 1. Performance comparison of DDM-dyn and Skeleton, with combinatorial adjacency test (s)
Full size table
Table 2. Performance comparison of DDM-dyn and Skeleton, with graph adjacency test (s)
Full size table
Fig. 1.
figure 1

Number of adjacency checks on cube18

Full size image
Fig. 2.
figure 2

Number of adjacency checks on mit729-9 (first 200 iterations)

Full size image
Fig. 3.
figure 3

Number of adjacency checks on ccc7

Full size image

5 Conclusion

A dynamic version of the double description method for finding extreme rays of a polyhedral cone with online input of inequalities has been proposed. Two known modifications of the algorithm (graph adjacency test and maintaining the edge set to generate new extreme rays) have been adopted for its dynamic variant and tested on multiple problem instances. The results of computational experiments demonstrate better performance with certain configurations than that of Skeleton on a number of problems if the same limitations of input being unknown ahead of time are imposed on both implementations.