1 Introduction

The tensor complementarity problem, as a generalization of the linear complementarity problem and a special instance of nonlinear complementarity problems, was proposed very recently [17]. A tensor complementarity problem (TCP) can be formulated as follows: finding \(x\in {\mathbb {R}}^n\) such that

$$\begin{aligned} x\ge 0,\quad {{\mathcal {A}}}x^{m-1}+q\ge 0,\quad x^T({{\mathcal {A}}}x^{m-1}+q)=0, \end{aligned}$$
(1)

or showing that no such vector exists, where \({\mathcal {A}}=(a_{i_1\ldots i_m})\) is an mth order n-dimensional tensor whose entries \(a_{i_1\ldots i_m}\in {\mathbb {R}}\) for \(i_j\in [n]:=\{1,\ldots ,n\}\) and \(j\in [m]:=\{1,\ldots ,m\}\), \({\mathcal {A}}x^{m-1}\) is a vector in \({\mathbb {R}}^n\) with the ith component as

$$\begin{aligned} ({\mathcal {A}}x^{m-1})_i:=\sum _{i_2,\ldots ,i_m=1}^{n}a_{ii_2\ldots i_m}x_{i_2}\ldots x_{i_m} \end{aligned}$$

for \(i\in [n]\), and \(q\in {\mathbb {R}}^n\). The TCP problem (1) is denoted as TCP\(({\mathcal {A}},q)\). When \(m=2\), TCP\(({\mathcal {A}},q)\) is just the well-known linear complementarity problem [4]. The notion of the tensor complementarity problem was used firstly by Song and Qi [23] as an application of structured tensors. Recently, many theoretical results about the solution properties of TCP\(({\mathcal {A}},q)\) have been developed [17], including existence of solution [7, 8, 19, 22, 24], global uniqueness of solution [1, 7], boundedness of solution set [3, 5, 20, 21, 24], stability of solution [26], sparsity of solution [13], solution methods [12, 25], and so on. Among them, Song and Qi [22] discussed the solution of TCP\(({\mathcal {A}},q)\) with a strictly semi-positive tensor. Che et al. [3] discussed the existence and uniqueness of solution of TCP\(({\mathcal {A}},q)\) with some special tensors. Song and Yu [20] obtained global upper bounds of the solution of the TCP\(({\mathcal {A}},q)\) with a strictly semi-positive tensor. Luo et al. [13] obtained the sparsest solutions to TCP\(({\mathcal {A}},q)\) with a Z-tensor. Gowda et al. [7] studied the various equivalent conditions for the existence of solution to TCP\(({\mathcal {A}},q)\) with a Z-tensor. Ding et al. [5] showed the properties of TCP\(({\mathcal {A}},q)\) with a P-tensor. Bai et al. [1] considered the global uniqueness and solvability for TCP\(({\mathcal {A}},q)\) with a strong P-tensor. Wang et al. [24] gave the solvability of TCP\(({\mathcal {A}},q)\) with exceptionally regular tensors. Huang, Suo and Wang [8] presented several classes of Q-tensors and discussed the solvability of TCP\(({\mathcal {A}},q)\) corresponding to Q-tensors. In addition, a practical application of TCP\(({\mathcal {A}},q)\) was given in [9]. To the best of our knowledge, the study on solution algorithms for solving TCP\(({\mathcal {A}},q)\) has few results. So how to design efficient solution methods for TCP\(({\mathcal {A}},q)\), via analyzing the structure of the related tensor, is one of very important research issues.

As shown in the above, the tensor complementarity problem TCP\(({\mathcal {A}},q)\) is a natural extension of the linear complementarity problem (LCP), which consists in finding a vector \(x\in {\mathbb {R}}^n\) that satisfies a certain system of inequalities

$$\begin{aligned} x\ge 0,\quad Ax+q\ge 0,\quad x^T(Ax+q)=0 \end{aligned}$$

for given \(q\in {\mathbb {R}}^n\) and \(A\in {\mathbb {R}}^{n\times n}\). The LCP problem has been a subject with a rich mathematical theory, a variety of algorithms, and a wide range of applications in applied science and technology [4]. In past several decades, there have been numerous mathematical workers concerned with LCPs [4, 6]. There are so many well-established and fruitful methods for solving LCPs. Among them, solving LCPs via integer programming problems is an interesting and important approach [14, 15]. The authors in [14, 15] proved that how to solve an LCP problem or verify that a solution does not exist using different equivalent mixed zero-one integer programming formulations. Especially, It was shown that in the general case, the number of zero-one integer variables introduced is equal to the dimension of the LCP problem, and the number of integer variables can be reduced if it was known that a solution exists. Motivated by these interesting results, we will present a new approach to solve TCP\(({\mathcal {A}},q)\) via solving a mixed integer programming in this paper, which is the generalization of the method in [14].

In this paper, we extend the results in [14] to TCPs. We first show that TCP\(({\mathcal {A}},q)\) is solvable if and only if TCP\(({\mathcal {A}},\beta ^{m-1}q)\) has a solution for \(\beta >0\). Based on this conclusion, we reformulate TCP\(({\mathcal {A}},q)\) as a zero-one mixed integer programming (MIP) problem and establish the relationship between TCP\(({\mathcal {A}},q)\) and the MIP problem. Using different mixed zero-one integer programming formulations, we present a necessary and sufficient condition for the solvability of TCP\(({\mathcal {A}},q)\) and a sufficient condition to verify that a solution of TCP\(({\mathcal {A}},q)\) does not exist. We prove that TCP\(({\mathcal {A}},q)\) is equivalent a mixed zero-one integer feasibility problem with n zero-one integer variables. It was proved that for the LCP problem, when it is known that a solution exists, the number of integer variables can be reduced [14]. However, this result can not be extended to the TCP problem (refeqtcp) because the Hessian matrix of the nonlinear function \({{\mathcal {A}}}x^{m-1}+q\) in TCP\(({\mathcal {A}},q)\) is not constant like as LCP. In addition, since TCP\(({\mathcal {A}},q)\) with a positive definite tensor \({\mathcal {A}}\) has a nonempty and compact solution set [3], a concrete bound is given in this paper. Specially, we also prove that if \({\mathcal {A}}\) is a diagonal positive definite tensor then TCP\(({\mathcal {A}},q)\) has a unique solution, which answers Conjecture 5.1 in [3].

This paper is organized as follows. In Sect. 2, we list some preliminaries. In Sect. 3, we propose a mixed integer programming approach to solve TCP\(({\mathcal {A}},q)\) and some properties of TCP\(({\mathcal {A}},q)\) are given. Some numerical results are reported in Sect. 4. In the final section, we give some conclusions.

2 Preliminaries

In this section, we recall some basic definitions and essential conclusions in tensor eigenvalue theory, which are useful in the sequel.

Throughout this paper, we assume that m and n are integers, and \(m,n\ge 2\). Denote \({\mathbb {R}}^n:=\{(x_1,x_2,\ldots ,x_n)^T: x_i\in {\mathbb {R}}, i\in [n]\}\), where \({\mathbb {R}}\) is the set of real numbers. Define \(e:=(1,\ldots ,1)^T\in {\mathbb {R}}^n\). The set of all mth order n-dimensional real tensors is denoted as \(T_{m,n}\). For any tensor \({\mathcal {A}}=(a_{i_1\ldots i_m})\in T_{m,n}\), if its entries \(a_{i_1\dots i_m}\) are invariant under any permutation of their indices, then \(\mathcal {A}\) is called a symmetric tensor. The set of all mth order n-dimensional real symmetric tensors is denoted as \(S_{m,n}\). For a tensor \({\mathcal {A}}=(a_{i_1\ldots i_m})\in T_{m,n}\), entries \(a_{i\ldots i}\) are called diagonal entries of \({\mathcal {A}}\), for \(i\in [n]\). The other entries of \({\mathcal {A}}\) are called off-diagonal entries of \({\mathcal {A}}\). A tensor \({\mathcal {A}}\) is called diagonal if all of its off-diagonal entries are zero. Clearly, a diagonal tensor is a symmetric tensor.

Let \({\mathcal {A}}=(a_{i_1\ldots i_m})\in T_{m,n}\) and \(x\in {\mathbb {R}}^n\). Denote \(\Vert x\Vert \) as 2-norm of x and \(x^T\) as the transpose of x. Define \(\Vert x\Vert _\infty =\max \{|x_1|,\ldots ,|x_n|\}\) and

$$\begin{aligned} \Vert {\mathcal {A}}\Vert _\infty :=\max _{\Vert x\Vert _\infty =1}\Vert {\mathcal {A}}x^{m-1}\Vert _\infty . \end{aligned}$$
(2)

Apparently, we have \(\Vert {\mathcal {A}}x^{m-1}\Vert _\infty \le \Vert {\mathcal {A}}\Vert _\infty \Vert x\Vert ^{m-1}_\infty \) for any \(x\in {\mathbb {R}}^n\) [17].

Define

$$\begin{aligned} {\mathcal {A}}x^m:=\sum _{i_1,\ldots ,i_m=1}^na_{i_1\ldots i_m}x_{i_1}\ldots x_{i_m}. \end{aligned}$$

Clearly, \({\mathcal {A}}x^m\) is a homogeneous polynomial of degree m. If \({\mathcal {A}}x^m> 0\) for all \(x\in {\mathbb {R}}^n, x\ne 0\), then we say that the tensor \({\mathcal {A}}\) is positive definite. Clearly, when m is odd, there is no nontrivial positive definite tensor. This is only meaningful for even-order tensors.

In the following, we recall the definitions of E-eigenvalues and Z-eigenvalues of tensors in \(T_{m,n}\) [2, 10, 16]. Denote \({\mathbb {C}}^n:= \{(x_1,x_2,\ldots ,x_n)^T: x_i\in {\mathbb {C}}, i\in [n]\}\), where \({\mathbb {C}}\) is the set of complex numbers. For a tensor \({\mathcal {A}}\in T_{m,n}\), if there is a nonzero vector \(x\in {\mathbb {C}}^n\) and a number \(\lambda \in {\mathbb {C}}\) such that

$$\begin{aligned} {\mathcal {A}}x^{m-1} = \lambda x, \quad x^T x=1, \end{aligned}$$
(3)

then \(\lambda \) is called an E-eigenvalue of \({\mathcal {A}}\) and x is called an E-eigenvector of \({\mathcal {A}}\), associated with \(\lambda \). If the E-eigenvector x is real, then the E-eigenvalue \(\lambda \) is also real. In this case, \(\lambda \) and x are called a Z-eigenvalue and a Z-eigenvector of \({\mathcal {A}}\), respectively. For a symmetric tensor, Z-eigenvalues always exist. It has been shown that for any tensor \({\mathcal {A}}\in S_{m,n}\) with even order m, \({\mathcal {A}}\) is positive definite if and only if all its Z-eigenvalues are positive [16]. By [16, Theorem 5], for both the largest Z-eigenvalue \(\lambda _{max}\) and the smallest Z-eigenvalue \(\lambda _{min}\) of a symmetric tensor \(\mathcal {A}\), we have

$$\begin{aligned} \lambda _{\max }=\max \left\{ {\mathcal {A}}x^m: x^T x=1\right\} \end{aligned}$$
(4)

and

$$\begin{aligned} \lambda _{\min }=\min \left\{ {\mathcal {A}}x^m: x^T x=1\right\} . \end{aligned}$$
(5)

3 A mixed integer programming method

In this section, we first discuss the solution existence of TCP\(({\mathcal {A}},q)\) corresponding to a diagonal tensor \({\mathcal {A}}\) and we prove that the TCP\(({\mathcal {A}},q)\) with a positive definite diagonal tensor \({\mathcal {A}}\) has a unique solution, which gives a confirmed answer to [3, Conjecture 5.1]. We reformulate the TCP\(({\mathcal {A}},q)\) as a mixed integer programming and gives a necessary and sufficient condition for the solution existence of TCP\(({\mathcal {A}},q)\). We also propose an approach to solve TCP\(({\mathcal {A}},q)\) via solving a mixed integer programming.

Clearly, TCP\(({\mathcal {A}},q)\) is equivalent to the following constrained optimization problem with optimal value 0,

$$\begin{aligned} \min&\phi (x):=x^T(q+{{\mathcal {A}}}x^{m-1})\nonumber \\ \text{ s.t. }&x\ge 0,\quad q+{{\mathcal {A}}}x^{m-1}\ge 0. \end{aligned}$$
(6)

It is easy to see that \(\phi (x)\ge 0\) if the feasible region of (6) is nonempty, that is, the problem (6) is bounded from below.

Based on the model (6), some properties of the solution set of TCP\(({\mathcal {A}},q)\) are easily obtained in some special cases:

  • Let \(q\ge 0\). It is clear that \(x=0\) is a trivial solution of TCP\(({\mathcal {A}},q)\) for any tensor \(\mathcal {A}\in T_{m,n}\). So, in general, we assume that \(q\ngeq 0\).

  • Let \(\mathcal {A}=(a_{i_1\ldots i_m})\in T_{m,n}\) be a diagonal tensor. In this case, the constrained optimization problem (6) is reduced as follows:

    $$\begin{aligned} \min&\sum _{i=1}^{n}(a_{i\ldots i}x_{i}^{m-1}+q_i)x_i \\ \text{ s.t. }&x_i\ge 0, \quad a_{i\ldots i}x_{i}^{m-1}+q_i\ge 0, \quad i\in [n]. \end{aligned}$$

    From the above model, we know that if there exists \(i_0\in [n] \) such that \(a_{i_0\cdots i_0}\le 0\) and \( q_{i_0}<0\), then TCP\(({\mathcal {A}},q)\) is infeasible. Moreover, if for any \(i\in [n], q_i\ge 0\), or \( q_{i}<0\) and \(a_{i\cdots i}>0\), then TCP\(({\mathcal {A}},q)\) has a solution \(x^*\) with the ith component:

    $$\begin{aligned} x^*_i=\left\{ \begin{array}{ll} 0,&{} \hbox { if}\ q_i\ge 0. \\ \left( \frac{-q_i}{a_{i\cdots i}}\right) ^{\frac{1}{m-1}},&{} \hbox { if}\ q_i<0\hbox { and }a_{i\ldots i}>0. \end{array} \right. \end{aligned}$$
    (7)

  • In [3, Conjecture 5.1], Che, Qi and Wei proposed a conjecture that if a diagonal tensor \({\mathcal {A}}\) is positive definite then TCP\(({\mathcal {A}},q)\) has a unique solution. Here, we can give a confirmed answer to this conjecture. Since the diagonal tensor \({\mathcal {A}}\) is positive definite, \(a_{i\ldots i}>0\) for \(i\in [n]\) and every solution x of TCP\(({\mathcal {A}},q)\) satisfies

    $$\begin{aligned} x_i\ge 0,\quad a_{i\ldots i}x_{i}^{m-1}+q_i\ge 0, \quad (a_{i\ldots i}x_{i}^{m-1}+q_i)x_i=0, \quad i\in [n]. \end{aligned}$$
    (8)

    When \(q\ge 0\), we claim \(x=0\). In fact, if there exists some \(i^*\in [n]\) such that \(x_{i^*}>0\), then \(a_{i^*\ldots i^*}x_{i^*}^{m-1}+q_{i^*}>0\). This is a contradiction with (8). When \(q<0\), we know

    $$\begin{aligned} x_i=\left( \frac{-q_i}{a_{i\cdots i}}\right) ^{\frac{1}{m-1}}>0, \quad i\in [n]. \end{aligned}$$

    In fact, if there exists some \(i^*\in [n]\) such that \(x_{i^*}=0\), then \(a_{i^*\ldots i^*}x_{i^*}^{m-1}+q_{i^*}=q_{i^*}<0\). This is a contradiction with (8). In other cases, it follows from (8) that the ith component of the solution x must be in the form:

    $$\begin{aligned} x_i=\left\{ \begin{array}{ll} 0,&{} \hbox { if}\ q_i\ge 0, \\ \left( \frac{-q_i}{a_{i\cdots i}}\right) ^{\frac{1}{m-1}},&{} \hbox { if}\ q_i<0, \end{array} \right. \end{aligned}$$

    for \(i\in [n]\). Hence, TCP\(({\mathcal {A}},q)\), corresponding to a positive definite diagonal tensor \({\mathcal {A}}\), has a unique solution.

We summarize the above discussions in the following theorem.

Theorem 1

For a given TCP\(({\mathcal {A}},q)\), if the vector \(q\ge 0\) then TCP\(({\mathcal {A}},q)\) has a trivial solution. If \({\mathcal {A}}\) be a diagonal tensor and there exists some \(i\in [n]\) such that \(q_i<0\) and \(a_{i\ldots i}\le 0\), then TCP\(({\mathcal {A}},q)\) has no solution. Otherwise, TCP\(({\mathcal {A}},q)\) with a diagonal tensor \({\mathcal {A}}\) has a solution in the form of (7). Furthermore, if the diagonal tensor \({\mathcal {A}}\) is positive definite then TCP\(({\mathcal {A}},q)\) has a unique solution \(x^*\in {\mathbb {R}}^n\) with the ith component:

$$\begin{aligned} x^*_i={\left\{ \begin{array}{ll} 0, &{}\hbox { if}\ q_i\ge 0,\\ \left( \frac{-q_i}{a_{i\cdots i}}\right) ^{\frac{1}{m-1}},&{} \hbox { if}\ q_i<0, \end{array}\right. } \quad i\in [n]. \end{aligned}$$

Given a general TCP\(({\mathcal {A}},q)\) with \({\mathcal {A}}\in T_{m,n}\) and \(q\in {\mathbb {R}}^n\), we now show that it can always be solved by solving a mixed integer programming. Moreover, every tensor complementarity problem can be written as an equivalent mixed integer feasibility problem. These results are based on the following lemma.

Lemma 1

TCP\(({\mathcal {A}},q)\) has a solution if and only if TCP\(({\mathcal {A}},\beta ^{m-1}q)\) has a solution, where \(\beta >0\) is a real number.

Proof

We assume that \(x\in {\mathbb {R}}^n\) is a solution of TCP\(({\mathcal {A}},q)\). By (1) we have

$$\begin{aligned} x_i\ge 0,\quad ({\mathcal {A}}x^{m-1})_i+q_i\ge 0,\quad x_i\left( ({\mathcal {A}}x^{m-1})_i+q_i\right) =0,\quad i\in [n]. \end{aligned}$$
(9)

For any \(\beta >0\), taking \(y=\beta x\), (9) yields for \(i\in [n]\),

$$\begin{aligned} y_i\ge 0,\quad ({\mathcal {A}}y^{m-1})_i+\beta ^{m-1}q_i\ge 0,\quad y_i\left( ({\mathcal {A}}y^{m-1})_i+\beta ^{m-1}q_i\right) =0,\quad i\in [n], \end{aligned}$$
(10)

which implies that y solves TCP\(({\mathcal {A}},\beta ^{m-1}q)\). Hence, TCP\(({\mathcal {A}},\beta ^{m-1}q)\) has a solution.

On the other hand, we assume that \(y\in {\mathbb {R}}^n\) is a solution of TCP\(({\mathcal {A}},\beta ^{m-1}q)\). Hence, (10) holds. Let \(x=y/\beta \), it follows from (10) that x satisfies (9). Hence, x solves TCP\(({\mathcal {A}},q)\). Thus, TCP\(({\mathcal {A}},q)\) has a solution. \(\square \)

Consider the following mixed integer programming (MIP):

$$\begin{aligned} \max _{\alpha ,y,z}&\alpha ^{m-1} \nonumber \\ \text{ s.t. }&0\le {\mathcal {A}}y^{m-1}+\alpha ^{m-1}q\le e-z, \nonumber \\&0\le y\le z,\quad \alpha \ge 0, \nonumber \\&z\in \{0,1\}^n. \end{aligned}$$
(11)

Clearly, \(\alpha =0\), \(y=0\) and \(z=0\) is a feasible solution of MIP (11). The following theorem shows the relationship between TCP\(({\mathcal {A}},q)\) and MIP (11).

Theorem 2

Let \((\alpha ^*,y^*,z^*)\) be any optimal solution of MIP (11). If \(\alpha ^*>0\), then \(x={y^*}/{\alpha ^*}\) solves TCP\(({\mathcal {A}},q)\). If \(\alpha ^*=0\), then TCP\(({\mathcal {A}},q)\) has no solution.

Proof

For any given \({\mathcal {A}}\in T_{m,n}\) and \(q\in {\mathbb {R}}^n\) with \(q\ngeq 0\), MIP (11) always has the feasible solution \(\alpha =0\), \(y=0\) and \(z_i=0\) or 1 for \(i\in [n]\). For any feasible solution \((\alpha ,y,z)\) of MIP (11), it follows from the feasibility constraints and (2) that

$$\begin{aligned} \alpha \le \left( \frac{1+\Vert {\mathcal {A}}\Vert _{\infty }}{\Vert q\Vert _{\infty }}\right) ^{\frac{1}{m-1}}. \end{aligned}$$
(12)

Hence, MIP (11) is feasible and bounded. Suppose MIP (11) has an optimal solution \((\alpha ^*,y^*,z^*)\) with \(\alpha ^*>0\). Let \(x={y^*}/{\alpha ^*}\), then we have \(x\ge 0\) and

$$\begin{aligned} (\alpha ^*)^{m-1}({\mathcal {A}}x^{m-1}+q)={\mathcal {A}}(y^*)^{m-1}+(\alpha ^*)^{m-1}q\ge 0\quad \Rightarrow \quad {\mathcal {A}}x^{m-1}+q\ge 0. \end{aligned}$$

Furthermore, for each \(i\in [n]\), either \(x_i=0\) or \(({\mathcal {A}}x^{m-1})_i+q_i=0\), so that \(x^T({\mathcal {A}}x^{m-1}+q)=0\). That is, x solves TCP\(({\mathcal {A}},q)\).

Let \((\alpha ^*,y^*,z^*)\) be an optimal solution of MIP (11). If \(\alpha ^*=0\), then we will show that TCP\(({\mathcal {A}},q)\) has no solution. Proof by contradiction, we assume that TCP\(({\mathcal {A}},q)\) has a solution. By Lemma 1, TCP\(({\mathcal {A}},\beta ^{m-1}q)\) has a solution. That is, for any \(\beta >0\), there exists \(y\ge 0\) such that

$$\begin{aligned} {\mathcal {A}}y^{m-1}+\beta ^{m-1}q\ge 0,\quad y^T({\mathcal {A}}y^{m-1}+\beta ^{m-1}q)=0. \end{aligned}$$

This implies that \((\beta ,y,z)\) with \(z_i=0\) if \(y_i=0\) and \(z_i=1\) otherwise for \(i\in [n]\), is a feasible solution of MIP (11). Hence, \(\alpha ^*\ge \beta >0\). This is a contradiction and hence TCP\(({\mathcal {A}},q)\) has no solution. \(\square \)

By Theorem 2, every feasible solution \((\alpha ,y,z)\) with \(\alpha >0\) of MIP (11) corresponds to a solution of TCP\(({\mathcal {A}},q)\). Therefore, solving MIP (11), we may generate several solutions of TCP\(({\mathcal {A}},q)\).

We now show that every tensor complementarity problem can be written as an equivalent mixed integer feasibility problem. The next theorem gives a sufficient condition for TCP\(({\mathcal {A}},q)\) without solutions.

Theorem 3

Given a general TCP\(({\mathcal {A}},q)\) with \({\mathcal {A}}\in T_{m,n}\) and \(q\in {\mathbb {R}}^n\), then TCP\(({\mathcal {A}},q)\) has no solution if the system of inequalities

$$\begin{aligned} 0\le {\mathcal {A}}x^{m-1}+q \le \tau e-u,\quad 0\le x\le \tau ^{\frac{m-2}{1-m}}u,\quad 0\le u\le \tau e,\quad \tau \ge 1, \end{aligned}$$
(13)

is infeasible.

Proof

We assume by contradiction that TCP\(({\mathcal {A}},q)\) has a solution. By Lemma 1, TCP\(({\mathcal {A}},\beta ^{m-1} q)\) also has a solution for any \(\beta >0\). By Theorem 2, MIP (11) has an optimal solution \((\alpha , y,z)\) with \(\alpha >0\). Without loss of generality, we may assume that \(\alpha \le 1\) due to (12). Hence,

$$\begin{aligned}&0\le {\mathcal {A}}y^{m-1}+\alpha ^{m-1}q \le e-z,\\&0\le y\le z,\quad z\in \{0,1\}^n,\\&0<\alpha \le 1. \end{aligned}$$

In the above system, we set

$$\begin{aligned} \tau =\frac{1}{\alpha ^{m-1}},\quad x=\frac{y}{\alpha },\quad u=\frac{z}{\alpha ^{m-1}}. \end{aligned}$$

Then \((\tau , x,u)\) is a solution to the following system

$$\begin{aligned} 0\le {\mathcal {A}}x^{m-1}+q \le \tau e-u,\quad 0\le x\le \tau ^{\frac{m-2}{1-m}}u,\quad u\in \{0,\tau \}^n,\quad \tau \ge 1. \end{aligned}$$

Hence, the system (13) is feasible, which is a contradiction. \(\square \)

By Theorem 3, if TCP\(({\mathcal {A}},q)\) is solvable then the corresponding system (13) is feasible. More generally, the following theorem gives a necessary and sufficient condition for the solvability of TCP\(({\mathcal {A}},q)\).

Theorem 4

Given a general TCP\(({\mathcal {A}},q)\) with \({\mathcal {A}}\in T_{m,n}\) and \(q\in {\mathbb {R}}^n\), then TCP\(({\mathcal {A}},q)\) is solvable if and only if the system

$$\begin{aligned}&0\le {\mathcal {A}}x^{m-1}+q \le \tau e-u, \quad 0\le x\le \tau ^{\frac{m-2}{1-m}}u, \nonumber \\&u\in \{0,\tau \}^n,\quad \tau \ge 1, \end{aligned}$$
(14)

is feasible.

Proof

The necessary condition is easily obtained from the proof line of Theorem 3. We now show the sufficient condition. Since the system (14) is feasible, let \((x^*,u^*,\tau ^*)\) be a feasible point of (14). Clearly, we have

$$\begin{aligned} x^*\ge 0,\quad {\mathcal {A}}(x^*)^{m-1}+q\ge 0. \end{aligned}$$

Furthermore, when \(x^*_i>0\) for some \(i\in [n]\), we have \(u^*_i=\tau ^*\) and hence \(({\mathcal {A}}x^{m-1}+q)_i=0\). Thus,

$$\begin{aligned} (x^*)^T\left( {\mathcal {A}}(x^*)^{m-1}+q\right) =0. \end{aligned}$$

Therefore, \(x^*\) is a solution of TCP\(({\mathcal {A}},q)\). That is, TCP\(({\mathcal {A}},q)\) is solvable. This completes the proof. \(\square \)

Let \({\mathcal {A}}\in S_{m,n}\). By [3, Theorem 4.5], we know that if \({\mathcal {A}}\) is positive definite then TCP\(({\mathcal {A}},q)\) is solvable for any \(q\in {\mathbb {R}}^n\) and its solution set is nonempty and compact. Furthermore, the following theorem gives a concrete bound.

Theorem 5

Let \({\mathcal {A}}\in S_{m,n}\) and \(q\in {\mathbb {R}}^n\). If \({\mathcal {A}}\) is positive definite, then the solution set of TCP\(({\mathcal {A}},q)\) is contained in the set

$$\begin{aligned} B=\left\{ x\in {\mathbb {R}}^n:\, \Vert x\Vert \le \left( \frac{\Vert q\Vert }{\lambda _{min}}\right) ^{\frac{1}{m-1}}\right\} , \end{aligned}$$

where \(\lambda _{min}\) is the smallest Z-eigenvalue of \({\mathcal {A}}\).

Proof

Since \({\mathcal {A}}\) is positive definite, by Theorem 4.5 in [3], TCP\(({\mathcal {A}},q)\) has a nonempty and compact solution set. Let S be its solution set. In addition, by Theorem 5 in [16], Z-eigenvalues of \({\mathcal {A}}\) exist and the smallest Z-eigenvalue \(\lambda _{min}>0\). Taking \(x\in S\) and \(x\ne 0\), we have

$$\begin{aligned} 0=x^T q+{\mathcal {A}}x^m. \end{aligned}$$
(15)

Setting \(y=x/{\Vert x\Vert }\), we have \(\Vert y\Vert =1\) and \({\mathcal {A}}x^m=\Vert x\Vert ^m{\mathcal {A}}y^m\). It follows from (5) that

$$\begin{aligned} {\mathcal {A}}x^m\ge \lambda _{min}\Vert x\Vert ^m. \end{aligned}$$
(16)

Combining (15) and (16), we obtain

$$\begin{aligned} 0\ge {\mathcal {A}}x^m-\Vert x\Vert \Vert q\Vert \ge \lambda _{min}\Vert x\Vert ^m-\Vert x\Vert \Vert q\Vert =\Vert x\Vert \left( \lambda _{min}\Vert x\Vert ^{m-1}-\Vert q\Vert \right) , \end{aligned}$$

which yields

$$\begin{aligned} \Vert x\Vert \le \left( \frac{\Vert q\Vert }{\lambda _{min}}\right) ^{\frac{1}{m-1}}. \end{aligned}$$

Hence, \(x\in B\). This completes the proof. \(\square \)

Note that strictly semi-positive tensors were introduced very recently [19]. A tensor \({\mathcal {A}}\in S_{m,n}\) is called strictly semi-positive if for any \(x\ge 0, x\ne 0\) there exists an index \(k\in [n]\) such that \(x_k({\mathcal {A}}x^{m-1})_k>0\). Clearly, a positive definite tensor must be strictly semi-positive. Hence, the result in the above theorem is regards as a special case of [20, Theorem 3.4].

4 Numerical experiments

In this section, we solve some examples of TCP\(({\mathcal {A}},q)\) via solving the related MIP (11). We consider the following examples for numerical experiments with the mixed integer programming method. We implement all experiments using Global Solver in LINGO10 on a laptop with an Intel(R) Core(TM) i5-2520M CPU(2.50 GHz) and RAM of 4.00 GB.

Example 1

Consider TCP\(({\mathcal {A}},q)\), where \(q=(2,2)^T\) and \({\mathcal {A}}=(a_{i_1i_2i_3})\in T_{3,2}\) with its entries \(a_{111}=1, a_{122}=-1, a_{211}=-2, a_{222}=1\) and other \(a_{i_1i_2i_3}=0\).

By straightforward computation, we obtain that the TCP\(({\mathcal {A}},q)\) in Example 1 has two solutions \((0,0)^T\) and \((2,\sqrt{6})^T\). Since \(q=(2,2)^T>0\), the solution \((0,0)^T\) is trivial by Theorem 1. The corresponding MIP is written as follows:

$$\begin{aligned} \max _{\alpha , y, z}&\alpha ^2\\ \text{ s.t. }&0\le y_1^2-{y_2^2}+2\alpha ^2\le 1-z_1,\\&0\le -2{y_1^2}+{y_2^2}+2\alpha ^2\le 1-z_2,\\&0\le y_1\le z_1,\quad 0\le y_2\le z_2,\\&z_1,z_2\in \{0,1\},\quad \alpha \ge 0. \end{aligned}$$

Running the LINGO code, we first obtain a solution of the above MIP:

$$\begin{aligned} \alpha ^*=0.7071068,\quad y^*=(0,0)^T, \quad z^*=(0,0)^T. \end{aligned}$$

By Theorem 2, we obtain the trivial solution (0, 0). We adjust the range of \(\alpha \) in the constraints as \(0\le \alpha <0.5\) and obtain another solution:

$$\begin{aligned} \alpha ^*=0.2,\quad y^*=(0.4,0.4898979)^T,\quad z=(1,1)^T. \end{aligned}$$

By Theorem 2, we obtain a solution of the TCP\(({\mathcal {A}},q)\): \(x^*=y^*/\alpha ^*=(2,2.4494895)^T\approx (2,\sqrt{6})^T\). We try different range of \(\alpha \) in the constrained region and obtain the two solutions. The details are listed in Table 1, where Range denotes the constraint on \(\alpha \) in MIP, Iter denotes total solver iterations, SOL-TCP denotes the solution of TCP\(({\mathcal {A}},q)\).

Table 1 The numerical results for Example 1
Full size table

Example 2

Consider TCP\(({\mathcal {A}},q)\), where \(q=(-2,-3)^T\) and \({\mathcal {A}}=(a_{i_1i_2i_3})\in T_{3,2}\) with \(a_{122}=-2, a_{211}=-1\), and other \(a_{i_1i_2i_3}=0\).

In this example, we have

$$\begin{aligned} {{\mathcal {A}}}x^2+q=\begin{pmatrix} -2x_2^2-2 \\ -x_1^2-3 \\ \end{pmatrix} <0 \end{aligned}$$

for any \(x\in {\mathbb {R}}^2\). Clearly, the TCP\(({\mathcal {A}},q)\) has no solution. The corresponding MIP is written as follows:

$$\begin{aligned} \max _{\alpha , y, z}&\alpha ^2\\ \text{ s.t. }&0\le -2{y_2^2}-2\alpha ^2\le 1-z_1,\\&0\le -{y_1^2}-3\alpha ^2\le 1-z_2,\\&0\le y_1\le z_1,\quad 0\le y_2\le z_2,\\&z_1,z_2\in \{0,1\},\quad \alpha \ge 0. \end{aligned}$$

Running the LINGO code of the above MIP, we obtain the global solution:

$$\begin{aligned} \alpha ^*=0,\quad y^*=(0.5,0)^T, \quad z^*=(1,0)^T. \end{aligned}$$

By Theorem 2, the TCP\(({\mathcal {A}},q)\) in Example 2 has no solution. We take different range of \(\alpha \) in the above MIP and always obtain the same result. The details are listed in Table 2.

Table 2 The numerical results for Example 2
Full size table

Example 3

Consider TCP\(({\mathcal {A}},q)\), where \(q=(0,-1)^T\) and \({{\mathcal {A}}}=(a_{{i_1}{i_2}{i_3}{i_4}})\in T_{4,2}\) with \(a_{1111}=1, a_{1112}=-2, a_{1122}=1,a_{2222}=1,\) and other \(a_{{i_1}{i_2}{i_3}{i_4}}=0\).

This example is taken from [1] and the TCP\(({\mathcal {A}},q)\) has two solutions: \(x^*=(0,1)^T\) and \(x^*=(1,1)^T\). By simple calculating, we have

$$\begin{aligned} {{\mathcal {A}}}x^3+q=\begin{pmatrix} x_1^3-2x_1^2x_2+x_1x_2^2 \\ x_2^3-1 \\ \end{pmatrix} \end{aligned}$$

and its corresponding MIP:

$$\begin{aligned} \max _{\alpha , y, z}&\alpha ^3\\ \text{ s.t. }&0\le y_1^3-2y_1^2y_2+y_1y_2^2\le 1-z_1,\\&0\le y_2^3-\alpha ^3\le 1-z_2,\\&0\le y_1\le z_1,\quad 0\le y_2\le z_2,\\&z_1,z_2\in \{0,1\},\quad \alpha \ge 0. \end{aligned}$$

Running the LINGO code of the above MIP, we obtain the global solution:

$$\begin{aligned} \alpha ^*=1,\quad y^*=(1,1)^T, \quad z^*=(1,1)^T. \end{aligned}$$

By Theorem 2, we can obtain the solution \(x^*=(1,1)^T\). We change different range of \(\alpha \) in its LINGO code and always obtain the solution, and we don’t get another solution (0, 1). The details are listed in Table 3.

Table 3 The numerical results for Example 3
Full size table

We observe the related MIP model carefully and find the first constraint without the term \(\alpha \). Thus, we add a small perturbation \(10^{-5}\alpha ^3\) and run the LINGO code again. Fortunately, we obtain the following solution of the above MIP:

$$\begin{aligned} \alpha ^*=1,\quad y^*=(0,1)^T, \quad z^*=(0,1)^T. \end{aligned}$$

By Theorem 2, we can obtain another solution \(x^*=(0,1)^T\). The details are listed in Table 4.

Table 4 The numerical results with small perturbation for Example 3
Full size table

From Tables 3 and 4 , we see that Global Solver in LINGO10 is very sensitive to solve mixed zero-one integer nonlinear optimization problems. The numerical results reported in the above tables show that our proposed approach is a good way to solve tensor complementarity problems. It would be much better if there are powerful solvers for mixed integer nonlinear programming problems.

5 Concluding remarks

In this paper, we proposed a mixed zero-one integer nonlinear programming method to solve the tensor complementarity problem TCP\(({\mathcal {A}},q)\). For a diagonal tensor \({\mathcal {A}}\), we gave conditions to guarantee the solution existence of TCP\(({\mathcal {A}},q)\). Specially, we proved that TCP\(({\mathcal {A}},q)\) with diagonal positive definite tensor \({\mathcal {A}}\) have a unique solution and then gave a confirmed answer for [3, Conjecture 5.1]. We formulated TCP\(({\mathcal {A}},q)\) as an MIP problem (11), based on the MIP model, we shown that TCP\(({\mathcal {A}},q)\) is equivalent to a mixed integer feasibility problem. Moreover, we gave a sufficient condition for TCP\(({\mathcal {A}},q)\) without solutions, and also a necessary and sufficient condition for the solvability of TCP\(({\mathcal {A}},q)\).

We proved that every feasible solution \((\alpha ,y,z)\) with \(\alpha >0\) of MIP (11) corresponds to a solution of TCP\(({\mathcal {A}},q)\). Therefore, by solving MIP (11), we may generate several solutions of TCP\(({\mathcal {A}},q)\). We also reported some numerical results to show the efficiency of the proposed approach.