Enumeration of PLCP-orientations of the 4-cube

The linear complementarity problem (LCP) provides a unified approach to many problems such as linear programs, convex quadratic programs, and bimatrix games. The general LCP is known to be NP-hard, but there are some promising results that suggest the possibility that the LCP with a P-matrix (PLCP) may be polynomial-time solvable. However, no polynomial-time algorithm for the PLCP has been found yet and the computational complexity of the PLCP remains open. Simple principal pivoting (SPP) algorithms, also known as Bard-type algorithms, are candidates for polynomial-time algorithms for the PLCP. In 1978, Stickney and Watson interpreted SPP algorithms as a family of algorithms that seek the sink of unique-sink orientations of $n$-cubes. They performed the enumeration of the arising orientations of the $3$-cube, hereafter called PLCP-orientations. In this paper, we present the enumeration of PLCP-orientations of the $4$-cube.The enumeration is done via construction of oriented matroids generalizing P-matrices and realizability classification of oriented matroids.Some insights obtained in the computational experiments are presented as well.

Definition 1.1 A P-matrix is a matrix M ∈ R n×n whose principal minors are all positive. P-matrices admit several characterizations. In the following, let [n] for n ∈ N denote the set {1, . . . , n}. Let A := (I n , −M ) and A B for B ⊆ [n] be the square submatrix of A whose ith column is the ith column of −M if i ∈ B, and the ith column of the identity matrix I n otherwise. Let ⊕ denote the symmetric difference operator of sets. Theorem 1.2 A matrix M ∈ R n×n is a P-matrix if and only if one of the following equivalent conditions holds. Equivalence of (A) and the P-matrix property has been obtained by Samelson, Thrall and Wesler [42], Ingleton [27], and Murty [38] independently. Characterization (B) is a restatement of Definition 1.1 in terms of the matrix (I n , −M ). Characterization (C) is due to Fiedler and Pták [10]. There are many other characterizations of P-matrices. The reader can find good surveys in [17,46]. The following result by Megiddo has encouraged researchers to seek a polynomial-time algorithm for the PLCP.

Simple principal pivoting (SPP) algorithms
Regarding pivoting approaches to the LCP, simple principal pivoting (SPP) algorithms [48,1], Lemke's algorithm [32], and the criss-cross method [28,22] have been proposed as solving methods. When focusing on the PLCP, Lemke's algorithm and the criss-cross method can also be viewed as SPP algorithms 1 . SPP algorithms were first introduced by Zoutendijk [48] and Bard [1], and are also called Bard-type algorithms. In the following, we shall explain SPP algorithms.
For a PLCP(M, q), let A B be as defined above. We denote by A B [i, q] for i ∈ [n] the n × n matrix that coincides with A B except that the ith column is replaced by q. First, we pick any B ⊆ [n]. Since A B is nonsingular, we call B a basis. Let for all i ∈ [n]. If A −1 B q ≥ 0, then z := (z 1 , . . . , z n ) T and w := (w 1 , . . . , w n ) T is the unique solution. If A −1 B q ≥ 0, then w − M z = q and w T z = 0 are satisfied, but w, z ≥ 0 fails. To improve the situation, we choose an index i ∈ SPP algorithms keep pivoting until a solution is found. We obtain different algorithms by the choice of a pivot rule, which uniquely selects an index i with (A −1 B q) i < 0 in each iteration. Some rules can cause cycles, and thus a pivot rule has to be chosen carefully so that the algorithm will terminate in a finite number of iterations. The first finite pivot rule has been proposed by Murty [39]. Till this day, neither a deterministic nor randomized (simple) pivot rule is known that is guaranteed to terminate in a polynomial number in n of pivot steps. Such a rule would yield a strongly polynomial-time solving method for the PLCP.

PLCP-orientations
Stickney and Watson [45] The orientation of the edge is in correspondence with the orientation computed from the viewpoint of B ⊕ {i}. There is a unique sink, which is the vertex S ⊆ [n] with A −1 S q ≥ 0 corresponding to the unique solution to the PLCP. In this model, SPP algorithms behave as path-following algorithms that seek the sink. The orientations of n-cubes arising in this way from PLCPs have some good combinatorial properties: the unique-sink orientation property [45] and the Holt-Klee property [23]. We call them PLCPorientations in the remainder. They are also known as P-matrix unique-sink orientation (P-USOs) in the literature.

Unique-sink orientations (USOs)
An orientation of a polytopal graph is a unique-sink orientation (USO) if it has a unique source and unique sink in every nonempty face. USOs provide a combinatorial model for many optimization problems, such as linear programming (LP) and the smallest enclosing ball (SEB) problem [43]. An LP-orientation is a USO of a polytopal graph arising from a linear objective function. USOs of n-cubes are particularly interesting. They not just model the PLCP, but also the SEB problem. Even general LP can be reduced to finding the sink of a USO of the n-cube [25]. Szabó and Welzl [43] proved that finding the sink of a general USO of the n-cube can be done by evaluating O(1.61 n ) vertices.
PLCP-orientations build a proper subclass of the USOs of the n-cube, which follows from enumeration results [45] and counting results [15] on USO classes. It is unknown whether there exists a combinatorial characterization of PLCP-orientations.
Our contribution SPP algorithms have been studied extensively as candidates for polynomial-time algorithms for the PLCP. However, no efficient pivot rule is known, and thus further investigation of PLCP-orientations is of importance. It would therefore be useful to have a database of PLCP-orientations available. In this paper, we study the enumeration of PLCP-orientations.
Problem: Enumerate all PLCP-orientations of the n-cube.
We proceed in two steps. Since no combinatorial characterization of PLCP-orientations is known, we first enumerate a suitable superset. Todd [46] introduced a combinatorial abstraction of the LCP in terms of oriented matroids, which is known as the oriented matroid complementarity problem (OMCP). Oriented matroids are characterized by simple axioms, and efficient enumeration algorithms are available [3,13,14]. The PLCP-orientations are combinatorial objects, and thus extend to the setting of oriented matroids. We then speak of POMCP-orientations.
After the enumeration of POMCP-orientations is completed, we check realizability of the associated oriented matroids in order to identify the PLCP-orientations. In general, checking oriented matroids for realizability is as difficult as solving general polynomial equality and inequality systems with integer coefficients [36]. We use the method that has been recently proposed by Fukuda, Miyata, and Moriyama [21], which decides realizability in reasonable time for small instances. In this way, enumeration of PLCPorientations of the 4-cube is performed. The related data is available at https://sites.google.com/site/hmiyata1984/lcp.
Through the computational experiments, we also gained new insights into the combinatorial structure of P-matrices. Furthermore, we came across an interesting subclass of P-matrices whose characterization is completely combinatorial. The related details are discussed in Section 4.

Related work
The first study of PLCP-orientations is due to Stickney and Watson [45], who enumerated the PLCPorientations and the USOs of the 3-cube. Gärtner and Kaibel [24] enumerated the LP-orientations of the 3-cube. Morris [37] proved that every LP-orientation of the n-cube is a PLCP-orientation. Schurr [44] enumerated the USOs of the 4-cube. The results are summarized in Table 1

Preliminaries on oriented matroids
Oriented matroids are a useful tool for analyzing pivoting methods for LP and the LCP. Here, we summarize the basics of oriented matroids. For a complete overview on oriented matroids, the reader is referred to [2]. Before presenting axiomatic systems for oriented matroids, we introduce some operations on sign vectors. Let E be a finite set, hereinafter referred to as the ground set. For X, Y ∈ {+, −, 0} E , the composition X • Y ∈ {+, −, 0} E is given by The separation set of X and Y is the set Multiplication of signs is analogous to the multiplication of elements in {1, −1, 0}. Sign vector X conforms to Y , denoted by X Y , if X e = Y e or X e = 0 for all e ∈ E.
Definition 2.1 (Vector axioms) Let E be the ground set. An oriented matroid in vector representation is a pair M = (E, V), where V ⊆ {+, −, 0} E , that satisfies the following axioms.
An element of the set V is a vector of M.
Suppose that |E| = n. The rank of an oriented matroid (E, V) is r, where n − r is the length of a maximal chain of vectors: 0 ≺ X 1 ≺ · · · ≺ X n−r for X 1 , . . . , X n−r ∈ V. Let OM(r, n) denote the set of all rank r oriented matroids with n elements.
Oriented matroids can be specified by alternative axiomatic systems. They, for instance, admit a characterization in terms of basis orientations.

Definition 2.2 (Chirotope axioms)
Let E be the ground set and r ∈ N such that r ≤ |E|. A chirotope of rank r is a map χ : E r → {+, −, 0} that satisfies the following properties.
We remark that (C3) can be replaced by the following axiom.
Consider a vector configuration is a chirotope of rank r and specifies an oriented matroid M : Many oriented matroid cannot be represented in terms of any vector configuration. A rank r oriented matroid M = ([n], {χ, −χ}) is realizable if there exists a vector configuration V ∈ R r×n such that χ = χ V , and nonrealizable otherwise. In the former case, matrix V is a realization of M.
For F ⊆ E, the pair (F, {χ| F , −χ| F }) is an oriented matroid. It is the restriction of M by F and denoted by M| F .
A single-element extension of M is a rank r oriented matroid M on ground set E ∪ {p} for p / ∈ E that satisfies M| E = M. In the remainder, whenever speaking of an extension, we refer to a single-element extension.
There are several natural concepts of isomorphism for oriented matroids.
is an oriented matroid. It is denoted by σ · M.
• For any A ⊆ E, the pair (E, is an oriented matroid. It is denoted by −A M Two oriented matroids M and N on E are relabeling equivalent if N = σ · M for some permutation σ on E. They are reorientation equivalent if M and −A N are relabeling equivalent for some A ⊆ E. These notions motivate the definition of a relabeling class and reorientation class of oriented matroids. Both operations preserve realizability.

The oriented matroid complementarity problem (OMCP)
For a matrix M ∈ R n×n and a vector q ∈ R n , the collection of sign vectors satisfies the vector axioms of an oriented matroid. Once a sign vector X ∈ V(M, q) with X ≥ 0, X 2n+1 = +, and X i = 0 or X i+n = 0 for each i ∈ [n] is known, a solution to the LCP(M, q) is obtained in polynomial time. This motivates the generalization of the LCP in the setting of oriented matroids, which is due to Todd [46].
For n ∈ N, we consider ground sets [2n] and [2n + 1], where the pairs (i, i + n) for i ∈ [n] are the complementary elements. The complement of any For an oriented matroid M = ([2n + 1], V), the oriented matroid complementarity problem (OMCP) is defined as follows.
Many solving methods for the LCP translate into the setting of oriented matroids. Todd [46] generalized Lemke's algorithm [32]. Klafszky and Terlaky [28] and Fukuda and Terlaky [22] proposed the criss-cross method. Foniok, Fukuda, and Klaus [17] proved that every SPP algorithm terminates in linear number of pivot steps on K-matroid OMCPs, which generalizes an algebraic result in [16].
Todd [46] considered an abstraction of P-matrices and gave several alternative characterizations. (B) Let χ be a chirotope of M. Then, we have (C) For every X ∈ V, we have X i = Xī = 0 for some i ∈ [n].
Other equivalent definitions can be found in [17,46]. For every P-matrix M ∈ R n×n , matrix (I n , −M ) realizes a P-matroid. Conversely, for every realization Since SPP algorithms make combinatorial decisions, they immediately translate into the oriented matroid setting. The model of an n-cube digraph applies again. Consider any nondegenerate POMCP( M).
where b j = j + n for j ∈ B and b j = j otherwise for all j ∈ [n]. Compare (2) with (1). Vertex B is a sink if and only if which is equivalent to the existence of the solution vector X to the POMCP( M ) with X i = + for i ∈ {b 1 , . . . , b n , 2n + 1}, 0 otherwise.
The arising orientations of the n-cube satisfy the USO property [29]. We call them POMCPorientations. Every PLCP-orientation is obviously a POMCP-orientation. Proposition 2.5 Every POMCP-orientation arising from a realizable oriented matroid is a PLCPorientation.

Proof.
Consider any realizable rank n oriented matroid M that defines a POMCP-orientation. Let (A B , −A N , −q) for A B , A N ∈ R n×n and q ∈ R n be a realization of M. Since M| [2n] is a P-matroid, we have χ(1, . . . , n) = 0 and thus det( induces the same orientation as M.

Enumeration of PLCP-orientations
Since no combinatorial characterization of PLCP-orientations is known, we first begin with an enumeration of POMCP-orientations. The following is an overview of our algorithm.
2. Partition the set of uniform P-matroids in OM(n, 2n) with respect to a certain equivalence relation and store representatives. There are exactly n!2 n isomorphisms of the n-cube and thus isomorphism test of its orientations is relatively easy for small n. Hence, we will not pay much attention to this issue.
The enumeration of P-matroids can be viewed as a variant of the matroid polytope completion problem, for which a software package based on a backtracking method is available [4]. In this paper, however, we focus on enumerations of the PLCP-orientations of the 3-cube and the 4-cube, and thus it suffices to consider P-matroids in OM(3, 6) and OM (4,8), which are covered by the database of oriented matroids by Finschi and Fukuda [12,13,14]. The database consists of representatives for the reorientation classes.
Note that if M is realizable, then there always exists a perturbed oriented matroid M ǫ that is realizable.
To reduce the number of P-matroids in the computation, we partition the set of P-matroids into certain equivalence classes. • M and N are CFS-equivalent if they can be transformed into each other by a combination of the above two operations.
The concept of C-equivalence is related to isomorphisms of USOs. The definition of FS-equivalence is motivated by the notion of face switches for USOs introduced by Stickney and Watson [45]. In this paper, however, we use the terminology facet switch instead. PLCP-orientations are closed under isomorphism and facet switches [45]. This convenient property translates into the setting of oriented matroids. It follows as a corollary of Proposition 3.5 below.
Proposition 3.4 Let M be a P-matroid. Every oriented matroid N that is C-or FS-equivalent to M is a P-matroid.
Proof.  . . . , b i−1 ,ī, b i+1 , . . . , b n ). (1) For every C-equivalent N to M, there exists an extension inducing an orientation that is isomorphic to the one induced by M.
where b j := j + n if j ∈ B and b j := j otherwise for all j ∈ [n]. By (C2) in Definition 2.2, the orientation therefore corresponds to the orientation of the edge in the USO induced by M that connects C with C ⊕ {σ(b i ) mod n}, where C := {σ(b j ) − n | σ(b j ) > n, j ∈ [n]}. In other words, the permutation σ induces an isomorphism between the oriented n-cubes. Let Π be the set of CFS-equivalence classes of P-matroids in OM(n, 2n). For each π ∈ Π, we store the representative P-matroid M π , which is determined by lexicographic comparison of the reverse lexicographic expressions of chirotopes.
The next step is to enumerate all uniform extensions of the CFS-equivalence class representatives M π obtained in Step 2. We use the algorithm by Finschi and Fukuda [13,14] with a slight modification. In order to reduce the workload, we make use of the following relation between the extensions of reorientation equivalent oriented matroids.
Proposition 3.6 Let M and N be rank r oriented matroids on E with N = −A (σ · M) for any permutation σ on E and subset A ⊆ E. There is a one-to-one correspondence between the extensions of M and those of N : where M is an extension of M on the ground set E ∪ {p} and σ is the permutation on E ∪ {p} with σ| E = σ and σ(p) = p.
Proof. Pick an arbitrary extension M of M. Since the oriented matroid N : it is an extension of N . Conversely, for any extension N of N , oriented matroid M := σ −1 · ( −A N ) is an extension of M.
We take the following approach to enumerate all uniform extensions of the CFS-equivalence class representatives obtained in Step 2. First, we partition Π with respect to reorientation equivalence. For each reorientation class θ, we store a representative M θ along with information to recover the CFSequivalence class representatives M π contained in θ. For every representative M θ , we then compute all uniform extensions using Finschi and Fukuda's algorithm [13,14]. Finally, the uniform extensions of CFS-equivalence class representatives M π contained in θ are obtained using Proposition 3.6.
Once having obtained all uniform extensions, it is easy to find the induced POMCP-orientations using (2). We group the extensions of CFS-equivalence class representatives M π such that extensions inducing the same orientation build one group.
We do not know which POMCP-orientations actually correspond to PLCP-orientations so far. A POMCPorientation O is a PLCP-orientation if and only if there is at least one realizable oriented matroid in the group of extensions that induce O. Therefore, deciding whether O arises from a PLCP is done by checking realizability of oriented matroids. Recall that PLCP-orientations are closed under isomorphism and facet switches [45]. We partition the set of POMCP-orientations accordingly, and remember representative USOs. It then suffices to check for each representative USO whether it is a PLCP-orientation. This is done by looking for a realizable oriented matroid in the group of inducing extensions. We check realizability by using the method in [21].

Experimental results
In the first step, the P-matroids in OM (3,6) and OM (4,8) were extracted from the database provided by Finschi and Fukuda [12]. Then, we partitioned the set of the P-matroids with respect to CFS-equivalence and computed all extensions. We observed that there exists at least one class of CFS-equivalent Pmatroids in every reorientation class of uniform oriented matroids in OM (3,6) and OM (4,8). The results are summarized in Table 3.
Next, we computed the induced POMCP-orientations and built the classes defined by isomorphism and facet switches. See row 1 in Table 4. For each class of USOs, we randomly picked inducing oriented matroids and checked realizability. For POMCP-orientations of the 3-cube (resp. 4-cube), we have to investigate realizability of oriented matroids in OM(3, 7) (resp. OM (4,9)). Since every oriented matroid in OM(3, 7) is realizable [5,26], all 8 POMCP-orientations of the 3-cube are PLCP-orientations. Up to isomorphism only, there are 17 POMCP-orientations of the the 3-cube. Among them, 16 are acyclic and OM (3,6) OM (4,8) P-matroids up to C-equivalence 19 156,691 P-matroids up to CFS-equivalence 13 19,076 P-matroid extensions 1,920 1,334,887,042  Develin [9] presented a scheme to construct 2 Ω(2 n / √ n) USOs of the n-cube that satisfy the Holt-Klee property. All 4 (resp. 8) USOs of the 3-cube (resp. 4-cube) in the family are PLCP-orientations. There are at most 2 O(n 3 ) PLCP-orientations of the n-cube [15]. Thus, some higher dimensional USOs in the family are not PLCP-orientations. It would be interesting to investigate whether each one is a POMCP-orientation.

Other insights
As remarked in the previous subsection, every uniform oriented matroid in OM (4,8) has a reorientation that is a P-matroid. This leads to the following open question.
• For any n ∈ N, does every uniform oriented matroid in OM(n, 2n) has a reorientation that is a P-matroid?
In case the answer is "yes," the combinatorial structure of P-matrices can be arbitrary complicated. The following related questions arise.
• Is the number of rank n P-matroids of the same order of magnitude as the number of uniform oriented matroids of rank n on 2n elements?
• In [2, Section 7.4], they construct 2 cr(n−r) r−1 , where c r = ( 1 2(r−1) ) r−1 , uniform oriented matroids of rank r on n elements. Does each oriented matroid in this family with n = 2m and r = m for m ∈ N has a reorientation that is a P-matroid?
But then again, many PLCP-orientations can be generated from some specific class of coefficient matrices. We observed that 6, 077 of the 6, 910 PLCP-orientations of the 4-cube arise from POMCPs where at least one of the underlying P-matroids is a reorientation of the alternating matroid A 4,8 . The alternating matroid A r,n is the rank r oriented matroid on the ground set [n] whose chirotope χ satisfies χ(i 1 , . . . , i r ) = + for all 1 ≤ i 1 < · · · < i r ≤ n.
Every alternating matroid is realized by a cyclic polytope.
Let a cyclic-P-matroid be a P-matroid of rank n that is reorientation equivalent to the alternating matroid A n,2n . Since alternating matroids have a good characterization and their extensions are wellstudied [47], investigation of the POMCP-orientations arising from cyclic-P-matroids becomes interesting. In [20,29], it is proven that the class of cyclic-P-matroids is closed under CFS-equivalence and some minor operations. A characterization of the reorientations of alternating matroids A n,2n that yield P-matroids is presented as well.

Conclusions
In this paper, we presented the complete enumeration of PLCP-orientations of the 4-cube through solving the realizability problem of oriented matroids. The related data, including the PLCP-orientations of the 4-cube and the corresponding realizing oriented matroids, is uploaded to https://sites.google.com/site/hmiyata1984/lcp.
As mentioned, every POMCP-orientation of the 4-cube is a PLCP-orientation. It is an open question whether there is a gap between the two classes in higher dimensions.
The computational experiments suggest that the combinatorial structure of P-matrices can be complicated. The experiments also point us to the interesting class of cyclic-P-matrix LCPs [20,29].
Another possibility to make use of the database might be to improve on various bounds on the runtime complexity of algorithms for the PLCP. Let t(n) be the smallest (among all strategies) maximum (among all USOs and choices of initial vertices) number of vertex evaluations necessary to find the sink of a USO of the n-cube. Szabó and Welzl [43] proposed the Improved Fibonacci Seesaw algorithm. The runtime analysis yields the recurrence relation t(n) ≤ 2 + n−5 i=0 t(i) + 5t(n − 4) for n ≥ 5. They provide the initial values t(0) = 1, t(1) = 2, t(2) = 3, t(3) = 5, and t(4) ≤ 7 to obtain a bound of O(1.61 n ) vertex evaluations. The database may be used to find good initial values in similar contexts. In this particular case, the question is whether the sink of PLCP-orientations of the 4-cube can be found by evaluating at most 6 vertices.
Finally, we remark that enumeration of the LP-orientations of the 4-cube might also be possible. Recall that for any LP min c T x subject to Ax ≤ b and x ≥ 0, the reduced cost vectors, which determine the LP-orientation, do not depend on the right-hand side b. There is hope that the LP-orientations of the 4-cube can be obtained through considering oriented matroids of rank 4 on 9 elements. In fact, Foniok, Fukuda, and Klaus [18,29] established a relation between the hidden K-matroid OMCP of order n and the oriented matroid programming [19] over n-cubes. In the realizable case, the LP-orientations of the n-cube coincide with the USOs arising from the hidden K-matrix LCPs of order n [18,29,41]. Hence, one approach is to first identify the hidden K-matroids among the P-matroids in OM (4,8), then to create all extensions, and finally to check realizability. Since hidden K-matroids of rank n, unlike P-matroids, admit realizations (I n , −M ) ∈ R n×2n where M is not a hidden K-matrix, such an approach is likely to result in a proper superset of the LP-orientations. Another possibility would be to check for every acyclic PLCP-orientation of the 4-cube whether it is an LP-orientation. Such a problem reduces to the realizability question for rank 5 oriented matroids on 10 elements. The method in [21] cannot handle instances of that size, which might change with some algorithmic improvements.