A Linear System of Both Equations and Inequalities in Max-Algebra

1. Introduction

The aim of this chapter is to present a system of linear equation and inequalities in max-algebra. Max-algebra is an analogue of linear algebra developed on the pair of operations $(\oplus ,\otimes )$ extended to matrices and vectors, where $a\oplus b=max(a,b)$ and $a\otimes b=a+b$ for $a,b\in ℝ$. The system of equations $A\otimes x=c$ and inequalities $B\otimes x\le d$ have each been studied in the literature. We will present necessary and sufficient conditions for the solvability of a system consisting of these two systems and also develop a polynomial algorithm for solving max-linear program whose constraints are max-linear equations and inequalities. Moreover, some solvability concepts of an inteval system of linear equations and inequalities will also be presented.

Max-algebraic linear systems were investigated in the first publications which deal with the introduction of algebraic structures called (max,+) algebras. Systems of equations with variables only on one side were considered in these publications [1], [2] and [3]. Other systems with a special structure were investigated in the context of solving eigenvalue problems in correspondence with algebraic structures or synchronisation of discrete event systems, see [4] and also [1] for additional information. Given a matrix $A$, a vector $b$ of an appropriate size, using the notation $\oplus =max$, $\otimes =plus$, the studied systems had one of the following forms: $A\otimes x=b$, $A\otimes x=x$ or $A\otimes x=x\oplus b$. An infinite dimensional generalisation can be found in [5].

In [1] Cuninghame-Green showed that the problem $A\otimes x=b$ can be solved using residuation [6]. That is the equality in $A\otimes x=b$ be relaxed so that the set of its sub-solutions is studied. It was shown that the greatest solution of $A\otimes x\le b$ is given by $\overline{x}$ where

$${\overline{x}}_j=\underset{i\in M}{min}(b_i\otimes a_{ij}^{-1})forallj\in N$$

The equation $A\otimes x=b$ is also solved using the above result as follows: The equation $A\otimes x=b$ has solution if and only if $A\otimes \overline{x}=b$. Also, Gaubert [7] proposed a method for solving the one-sided system $x=A\otimes x\oplus b$ using rational calculus.

Zimmermann [3] developed a method for solving $A\otimes x=b$ by set covering and also presented an algorithm for solving max-linear programs with one sided constraints. This method is proved to has a computational complexity of $O\left(mn\right)$, where $m,n$ are the number of rows and columns of input matrices respectively. Akian, Gaubert and Kolokoltsov [5] extended Zimmermann's solution method by set covering to the case of functional Galois connections.

Butkovic [8] developed a max-algebraic method for finding all solutions to a system of inequalities $x_i-x_j>b_{ij},i,j=1,...,n$ using $n$ generators. Using this method Butkovic [8] developed a pseudopolynomial algorithm which either finds a bounded mixed-integer solution, or decides that no such solution exists. Summary of these results can be found in [9] and [10]

Cechl$\acute{a}$rova and Diko [11] proposed a method for resolving infeasibility of the system $A\otimes x=b$ . The techniques presented in this method are to modify the right-hand side as little as possible or to omit some equations. It was shown that the problem of finding the minimum number of those equations is NP-complete.

2. Max-algebra and some basic definitions

In this section we introduce max-algebra, give the essential definitions and show how the operations of max-algebra can be extended to matrices and vectors.

In max-algebra, we replace addition and multiplication, the binary operations in conventional linear algebra, by maximum and addition respectively. For any problem that involves adding numbers together and taking the maximum of numbers, it may be possible to describe it in max-algebra. A problem that is nonlinear when described in conventional terms may be converted to a max-algebraic problem that is linear with respect to $(\oplus ,\otimes )=(max,+)$.

Definition 1 The max-plus semiring $\overline{ℝ}$ is the set $ℝ\cup \{-\infty \}$, equipped with the addition $(a,b)\mapsto max(a,b)$ and multiplication $(a,b)\mapsto a+b$ denoted by $\oplus$ and $\otimes$ respectively. That is $a\oplus b=max(a,b)$ and $a\otimes b=a+b$. The identity element for the addition (or zero) is $-\infty$, and the identity element for the multiplication (or unit) is 0.

Definition 2 The min-plus semiring ${ℝ}_{min}$ is the set $ℝ\cup \{+\infty \}$, equipped with the addition $(a,b)\mapsto min(a,b)$ and multiplication $(a,b)\mapsto a+b$ denoted by ${\oplus }^{{}^{\text{'}}}$ and ${\otimes }^{{}^{\text{'}}}$ respectively. The zero is $+\infty$, and the unit is 0. The name tropical semiring is also used as a synonym of min-plus when the ground set is $\mathbb{N}$.

The completed max-plus semiring ${\overline{ℝ}}_{max}$ is the set $ℝ\cup \{\pm \infty \}$, equipped with the addition $(a,b)\mapsto max(a,b)$ and multiplication $(a,b)\mapsto a+b$, with the convention that $-\infty +(+\infty )=+\infty +(-\infty )=-\infty$. The completed min-plus semiring ${\overline{ℝ}}_{min}$ is defined in the dual way.

Proposition 1 The following properties hold for all $a,b,c\in \overline{ℝ}$:

$$\begin{array}{cc}\hfill a\oplus b& =b\oplus a\hfill \\ \hfill a\otimes b& =b\otimes a\hfill \\ \hfill a\oplus (b\oplus c)& =(a\oplus b)\oplus c\hfill \\ \hfill a\otimes (b\otimes c)& =(a\otimes b)\otimes c\hfill \end{array}$$

$$\begin{array}{cc}\hfill a\otimes (b\oplus c)& =a\otimes b\oplus a\otimes c\hfill \\ \hfill a\oplus (-\infty )& =-\infty =(-\infty )\oplus a\hfill \\ \hfill a\otimes 0& =a=0\otimes a\hfill \\ \hfill a\otimes a^{-1}& =0,a,a^{-1}\in ℝ\hfill \end{array}$$

The statements follow from the definitions.

Proposition 2 For all $a,b,c\in \overline{ℝ}$ the following properties hold:

$$\begin{array}{cc}\hfill a\le b& ⟹a\oplus c\le b\oplus c\hfill \\ \hfill a\le b& ⟺a\otimes c\le b\otimes c,c\in ℝ\hfill \\ \hfill a\le b& ⟺a\oplus b=b\hfill \\ \hfill a>b& ⟺a\otimes c>b\otimes c,-\infty <c<+\infty \hfill \end{array}$$

The statements follow from definitions. The pair of operations ($\oplus$,$\otimes$) is extended to matrices and vectors as in the conventional linear algebra as follows: For $A=\left(a_{ij}\right),B=\left(b_{ij}\right)$ of compatible sizes and $\alpha \in ℝ$ we have:

$$\begin{array}{cc}\hfill A\oplus B& =(a_{ij}\oplus b_{ij})\hfill \\ \hfill A\otimes B& =\left({\sum _k}^{\oplus }{a}_{ik}\otimes b_{kj}\right)\hfill \\ \hfill \alpha \otimes A& =(\alpha \otimes a_{ij})\hfill \end{array}$$

Example 1

$$\begin{array}{c}\hfill \left(\begin{array}{ccc}3& 1& 5\\ 2& 1& 5\end{array}\right)\oplus \left(\begin{array}{ccc}\hfill -1& \hfill 0& 2\\ \hfill 6& \hfill -5& 4\end{array}\right)=\left(\begin{array}{ccc}3& 1& 5\\ 6& 1& 5\end{array}\right)\end{array}$$

Example 2

$$\begin{array}{cc}\hfill & \left(\begin{array}{ccc}\hfill -4& 1& \hfill -5\\ \hfill 3& 0& \hfill 8\end{array}\right)\otimes \left(\begin{array}{cc}-1& 2\\ 1& 7\\ 3& 1\end{array}\right)\hfill \\ & =\left(\begin{array}{cc}(-4+(-1\left)\right)\oplus (1+1)\oplus (-5+3)& (-4+2)\oplus (1+7)\oplus (-5+1)\\ (3+(-1\left)\right)\oplus (0+1)\oplus (8+3)& (3+2)\oplus (0+7)\oplus (8+1)\end{array}\right)=\left(\begin{array}{cc}2& 8\\ 11& 9\end{array}\right)\hfill \end{array}$$

Example 3

$$\begin{array}{c}\hfill 10\otimes \left(\begin{array}{ccc}7& \hfill -3& 2\\ 6& \hfill 1& 0\end{array}\right)=\left(\begin{array}{ccc}17& 7& 12\\ 16& 11& 10\end{array}\right)\end{array}$$

Proposition 3

For $A,B,C\in {\overline{ℝ}}^{m\times n}$ of compatible sizes, the following properties hold:

$$\begin{array}{cc}\hfill A\oplus B& =B\oplus A\hfill \\ \hfill A\oplus (B\oplus C)& =(A\oplus B)\oplus C\hfill \\ \hfill A\otimes (B\otimes C)& =(A\otimes B)\otimes C\hfill \\ \hfill A\otimes (B\oplus C)& =A\otimes B\oplus A\otimes C\hfill \\ \hfill (A\oplus B)\otimes C& =A\otimes C\oplus B\otimes C\hfill \end{array}$$

The statements follow from the definitions.

Proposition 4

The following hold for $A,B,C$, $a,b,c,x,y$ of compatible sizes and $\alpha ,\beta \in ℝ$:

$$\begin{array}{cc}\hfill A\otimes (\alpha \otimes B)& =\alpha \otimes (A\otimes B)\hfill \\ \hfill \alpha \otimes (A\oplus B)& =\alpha \otimes A\oplus \alpha \otimes B\hfill \\ \hfill (\alpha \oplus \beta )\otimes A& =\alpha \otimes A\oplus \beta \otimes B\hfill \\ \hfill x^T\otimes \alpha \otimes y& =\alpha \otimes x^T\otimes y\hfill \\ \hfill a\le b& ⟹c^T\otimes a\le c^T\otimes b\hfill \\ \hfill A\le B& ⟹A\oplus C\le B\oplus C\hfill \\ \hfill A\le B& ⟹A\otimes C\le B\otimes C\hfill \\ \hfill A\le B& ⟺A\oplus B=B\hfill \end{array}$$

The statements follow from the definition of the pair of operations ($\oplus$,$\otimes$).

Definition 3 Given real numbers $a,b,c,\cdots$, a max-algebraic diagonal matrix is defined as:

$$\begin{array}{c}\hfill diag(a,b,c,\cdots )=\left(\begin{array}{ccccc}a& & & & \\ & b& & -\infty & \\ & & c& & \\ & -\infty & & \ddots & \\ & & & & \ddots \end{array}\right)\end{array}$$

Given a vector $d=(d_1,d_2,\cdots ,d_n)$, the diagonal of the vector $d$ is denoted as $diag\left(d\right)=diag(d_1,d_2,\cdots ,d_n)$.

Definition 4 Max-algebraic identity matrix is a diagonal matrix with all diagonal entries zero. We denote by $I$ an identity matrix. Therefore, identity matrix $I=diag(0,0,0,\cdots )$.

It is obvious that $A\otimes I=I\otimes A$ for any matrices $A$ and $I$ of compatible sizes.

Definition 5 Any matrix that can be obtained from the identity matrix, $I$, by permuting its rows and or columns is called a permutation matrix. A matrix arising as a product of a diagonal matrix and a permutation matrix is called a generalised permutation matrix [12].

Definition 6 A matrix $A\in {\overline{ℝ}}^{n\times n}$ is invertible if there exists a matrix $B\in {\overline{ℝ}}^{n\times n}$, such that $A\otimes B=B\otimes A=I$. The matrix $B$ is unique and will be called the inverse of $A$. We will henceforth denote $B$ by $A^{-1}$.

It has been shown in [1] that a matrix is invertible if and only if it is a generalised permutation matrix.

If $x=(x_1,\cdots ,x_n)$ we will denote $x^{-1}=(x_1^{-1},\cdots ,x_n^{-1})$, that is $x^{-1}=-x$, in conventional notation.

Example 4

Consider the following matrices

$$\begin{array}{c}\hfill A=\left(\begin{array}{ccc}\hfill -\infty & \hfill -\infty & \hfill 3\\ \hfill 5& \hfill -\infty & \hfill -\infty \\ \hfill -\infty & \hfill 8& \hfill -\infty \end{array}\right)andB=\left(\begin{array}{ccc}-\infty & -5& -\infty \\ -\infty & -\infty & -8\\ -3& -\infty & -\infty \end{array}\right)\end{array}$$

The matrix $B$ is an inverse of $A$ because,

$$\begin{array}{c}\hfill A\otimes B=\left(\begin{array}{ccc}\hfill -\infty & \hfill -\infty & \hfill 3\\ \hfill 5& \hfill -\infty & \hfill -\infty \\ \hfill -\infty & \hfill 8& \hfill -\infty \end{array}\right)\otimes \left(\begin{array}{ccc}\hfill -\infty & \hfill -5& \hfill -\infty \\ \hfill -\infty & \hfill -\infty & \hfill -8\\ \hfill 3& \hfill -\infty & \hfill -\infty \end{array}\right)=\left(\begin{array}{ccc}\hfill 0& \hfill -\infty & \hfill -\infty \\ \hfill -\infty & \hfill 0& \hfill -\infty \\ \hfill -\infty & \hfill -\infty & \hfill 0\end{array}\right)\end{array}$$

Given a matrix $A=\left(a_{ij}\right)\in \overline{ℝ}$, the transpose of $A$ will be denoted by $A^T$, that is $A^T=\left(a_{ji}\right)$. Structures of discrete-event dynamic systems may be represented by square matrices $A$ over the semiring:

$$\overline{ℝ}=(\{-\infty \}\cup ℝ,\oplus ,\otimes )=(\{-\infty \}\cup ℝ,max,+)$$

The system $\Re$ is embeddable in the self-dual system:

$$\overline{\overline{ℝ}}=(\{-\infty \}\cup ℝ\{+\infty \},\oplus ,\otimes ,{\oplus }^{{}^{\text{'}}},{\otimes }^{{}^{\text{'}}})=(\{-\infty \}\cup ℝ\{+\infty \},max,+,min,+)$$

Basic algebraic properties for ${\oplus }^{{}^{\text{'}}}$ and ${\otimes }^{{}^{\text{'}}}$ are similar to those of $\oplus$ and $\otimes$ described earlier. These are obtained by swapping $\le$ and $\ge$ . Extension of the pair $({\oplus }^{{}^{\text{'}}},{\otimes }^{{}^{\text{'}}})$ to matrices and vectors is as follows:

Given $A,B$ of compatible sizes and $\alpha \in ℝ$, we define the following:

$$\begin{array}{cc}\hfill A{\oplus }^{{}^{\text{'}}}B& =\left(a_{ij}{\oplus }^{{}^{\text{'}}}{b}_{ij}\right)\hfill \\ \hfill A{\otimes }^{{}^{\text{'}}}B& =\left({\sum _k}^{{\oplus }^{{}^{\text{'}}}}{a}_{ik}{\otimes }^{{}^{\text{'}}}{b}_{kj}\right)=\underset{k}{min}(a_{ik}+b_{kj})\hfill \\ \hfill \alpha {\otimes }^{{}^{\text{'}}}A& =\left(\alpha {\otimes }^{{}^{\text{'}}}{a}_{ij}\right)\hfill \end{array}$$

Also, properties of matrices for the pair $({\oplus }^{{}^{\text{'}}},{\otimes }^{{}^{\text{'}}})$ are similar to those of $(\oplus ,\otimes )$, just swap $\le$ and $\ge$. For any matrix $A=\left[a_{ij}\right]$ over $\overline{\overline{ℝ}}$, the conjugate matrix is $A^{*}=[-a_{ji}]$ obtained by negation and transposition, that is $A=-A^T$.

Proposition 5 The following relations hold for any matrices $U,V,W$ over $\overline{\overline{ℝ}}$ .

$$\left(U{\otimes }^{{}^{\text{'}}}V\right)\otimes W\le U{\otimes }^{{}^{\text{'}}}(V\otimes W)$$uid16

$$U\otimes \left(U^{*}{\otimes }^{{}^{\text{'}}}W\right)\le W$$uid17

$$U\otimes \left(U^{*}{\otimes }^{{}^{\text{'}}}(U\otimes W)\right)=U\otimes W$$uid18

Follows from the definitions.

3. The Multiprocessor Interactive System (MPIS): A practical application

Linear equations and inequalities in max-algebra have a considerable number of applications, the model we present here is called the multiprocessor interactive system (MPIS) which is formulated as follows:

Products $P_1,\cdots ,P_m$ are prepared using $n$ processors, every processor contributing to the completion of each product by producing a partial product. It is assumed that every processor can work on all products simultaneously and that all these actions on a processor start as soon as the processor is ready to work. Let $a_{ij}$ be the duration of the work of the $j^{th}$ processor needed to complete the partial product for $P_i$ $(i=1,\cdots ,m;j=1,\cdots ,n)$. Let us denote by $x_j$ the starting time of the $j^{th}$ processor $(j=1,\cdots ,n)$. Then, all partial products for $P_i$ $(i=1,\cdots ,m;j=1,\cdots ,n)$ will be ready at time $max(a_{i1}+x_1,\cdots ,a_{in}+x_n)$. If the completion times $b_1,\cdots ,b_m$ are given for each product then the starting times have to satisfy the following system of equations:

$$max(a_{i1}+x_1,\cdots ,a_{in}+x_n)=b_{i}foralli\in M$$

Using the notation $a\oplus b=max(a,b)$ and $a\otimes b=a+b$ for $a,b\in ℝ$ extended to matrices and vectors in the same way as in linear algebra, then this system can be written as

$$A\otimes x=b$$uid19

Any system of the form (▭) is called 'one-sided max-linear system'. Also, if the requirement is that each product is to be produced on or before the completion times $b_1,\cdots ,b_m$, then the starting times have to satisfy

$$max(a_{i1}+x_1,\cdots ,a_{in}+x_n)\le b_{i}foralli\in M$$

which can also be written as

$$A\otimes x\le b$$uid20

The system of inequalities (▭) is called 'one-sided max-linear system of inequalities'.

4. Linear equations and inequalities in max-algebra

In this section we will present a system of linear equation and inequalities in max-algebra. Solvability conditions for linear system and inequalities will each be presented. A system consisting of max-linear equations and inequalities will also be discussed and necessary and sufficient conditions for the solvability of this system will be presented.

4.1. System of equations

In this section we present a solution method for the system $A\otimes x=b$ as given in [3], [1], [13] and also in the monograph [10]. Results concerning the existence and uniqueness of solution to the system will also be presented.

Given $A=\left(a_{ij}\right)\in {\overline{ℝ}}^{m\times n}$ and $b={(b_1,\cdots ,b_m)}^T\in {\overline{ℝ}}^m$, a system of the form

$$A\otimes x=b$$uid22

is called a one-sided max-linear system, some times we may omit 'max-linear' and say one-sided system. This system can be written using the conventional notation as follows

$$\underset{j=1,\cdots ,n}{max}(a_{ij}+x_j)=b_i,i\in M$$uid23

The system in (▭) can be written after subtracting the right-hand sides constants as

$$\underset{j=1,\cdots ,n}{max}(a_{ij}\otimes b_i^{-1}+x_j)=0,i\in M$$

A one-sided max-linear system whose all right hand side constants are zero is called normalised max-linear system or just normalised and the process of subtracting the right-hand side constants is called normalisation. Equivalently, normalisation is the process of multiplying the system (▭) by the matrix $B^{{}^{\text{'}}}$ from the left. That is

$$B^{{}^{\text{'}}}\otimes A\otimes x=B^{{}^{\text{'}}}\otimes b=0$$

where,

$$B^{{}^{\text{'}}}=diag(b_1^{-1},b_2^{-1},\cdots ,b_m^{-1})=diag\left(b^{-1}\right)$$

For instance, consider the following one-sided system:

$$\begin{array}{c}\hfill \left(\begin{array}{ccc}\hfill -2& 1& 3\\ \hfill 3& 0& 2\\ \hfill 1& 2& 1\end{array}\right)\otimes \left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)=\left(\begin{array}{c}5\\ 6\\ 3\end{array}\right)\end{array}$$uid24

After normalisation, this system is equivalent to

$$\begin{array}{c}\hfill \left(\begin{array}{ccc}-7& -4& -2\\ -3& -6& -4\\ -2& -1& -2\end{array}\right)\otimes \left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 0\end{array}\right)\end{array}$$

That is after multiplying the system (▭) by

$$\begin{array}{c}\hfill \left(\begin{array}{ccc}\hfill -5& \hfill -\infty & \hfill -\infty \\ \hfill -\infty & \hfill -6& \hfill -\infty \\ \hfill -\infty & \hfill -\infty & \hfill -3\end{array}\right)\end{array}$$

Consider the first equation of the normalised system above, that is $max(x_1-7,x_2-4,x_3-2)=0$. This means that if ${(x_1,x_2,x_3)}^T$ is a solution to this system then $x_1\le 7$,$x_2\le 4$, $x_3\le 2$ and at least one of these inequalities will be satisfied with equality. From the other equations of the system, we have for $x_1\le 3$, $x_1\le 2$, hence we have $x_1\le min(7,3,2)=-max(-7,-3,-2)=-{\overline{x}}_1$ where $-{\overline{x}}_1$ is the column 1 maximum. It is clear that for all $j$ then $x_j\le {\overline{x}}_j$, where $-{\overline{x}}_j$ is the column $j$ maximum. At the same time equality must be attained in some of these inequalities so that in every row there is at least one column maximum which is attained by $x_j$. This observation was made in [3].

Definition 7 A matrix $A$ is called doubly $ℝ$-astic [14], [15], if it has at least one finite element on each row and on each column.

We introduce the following notations

$$\begin{array}{cc}\hfill S(A,b)& =\{x\in {\overline{ℝ}}^n;A\otimes x=b\}\hfill \\ \hfill M_j& =\{k\in M;b_k\otimes a_{kj}^{-1}=\underset{i}{max}(b_i\otimes a_{ij}^{-1})\}forallj\in N\hfill \\ \hfill \overline{x}{(A,b)}_j& =\underset{i\in M}{min}(b_i\otimes a_{ij}^{-1})forallj\in N\hfill \end{array}$$

We now consider the cases when $A=-\infty$ and/or $b=-\infty$. Suppose that $b=-\infty$. Then $S(A,b)$ can simply be written as

$$S(A,b)=\{x\in {\overline{ℝ}}^n;x_j=-\infty ,if{A}_j\ne -\infty ,j\in N\}$$

Therefore if $A=-\infty$ we have $S(A,b)={\overline{ℝ}}^n$ . Now, if $A=-\infty$ and $b\ne -\infty$ then $S(A,b)=\varnothing$. Thus, we may assume in this section that $A=-\infty$ and $b\ne -\infty$. If $b_k=-\infty$ for some $k\in M$ then for any $x\in S(A,b)$ we have $x_j=-\infty$ if $a_{kj}\ne -\infty$, $j\in N$, as a result the $k^{th}$ equation could be removed from the system together with every column $j$ in the matrix $A$ where $a_{kj}\ne -\infty$ (if any), and set the corresponding $x_j=-\infty$. Consequently, we may assume without loss of generality that $b\in {ℝ}^m$.

Moreover, if $b\in {ℝ}^m$ and $A$ has an $-\infty$ row then $S(A,b)=\varnothing$. If there is an $-\infty$ column $j$ in $A$ then $x_j$ may take on any value in a solution $x$. Thus, in what follows we assume without loss of generality that $A$ is doubly $ℝ-astic$ and $b\in {ℝ}^m$.

Theorem 1 Let $A=\left(a_{ij}\right)\in {\overline{ℝ}}^{m\times n}$ be doubly $ℝ-astic$ and $b\in {ℝ}^m$. Then $x\in S(A,b)$ if and only if

$$\begin{array}{cc}\hfill i)& x\le \overline{x}(A,b)and\hfill \\ \hfill ii)& \bigcup _{j\in N_x}{M}_j=Mwhere{N}_x=\{j\in N;x_j=\overline{x}{(A,b)}_j\}\hfill \end{array}$$

Suppose $x\in S(A,b)$. Thus we have,

$$\begin{array}{cc}& A\otimes x=b\hfill \\ & ⟺\underset{j}{max}(a_{ij}+x_j)=b_{i}foralli\in M\hfill \\ & ⟺a_{ij}+x_j=b_{i}forsomej\in N\hfill \\ & ⟺x_j\le b_i\otimes a_{ij}^{-1}foralli\in M\hfill \\ & ⟺x_j\le \underset{i\in M}{min}(b_i\otimes a_{ij}^{-1})forallj\in N\hfill \end{array}$$

Hence, $x\le \overline{x}$ .

Now that $x\in S(A,b)$. Since $M_j\subseteq M$ we only need to show that $M\subseteq {\bigcup }_{j\in N_x}{M}_j$. Let $k\in M$. Since $b_k=a_{kj}\otimes x_j>-\infty$ for some $j\in N$ and $x_j^{-1}\ge {\overline{x}}_j^{-1}\ge a_{ij}\otimes b_i^{-1}$ for every $i\in M$ we have $x_j^{-1}=a_{kj}\otimes b_k^{-1}={max}_{i\in M}{a}_{ij}\otimes b_i^{-1}$. Hence $k\in M_j$ and $x_j={\overline{x}}_j$.

Suppose that $x\le \overline{x}$ and ${\bigcup }_{j\in N_x}{M}_j=M$. Let $k\in M$, $j\in N$. Then $a_{kj}\otimes x_j\le b_k$ if $a_{kj}=-\infty$. If $a_{kj}\ne -\infty$ then

$$a_{kj}\otimes x_j\le a_{kj}\otimes {\overline{x}}_j\le a_{kj}\otimes b_k\otimes a_{kj}^{-1}=b_k$$uid27

Therefore $A\otimes x\le b$. At the same time $k\in M_j$ for some $j\in N$ satisfying $x_j={\overline{x}}_j$. For this $j$ both inequalities in (▭) are equalities and thus $A\otimes x=b$. The following is a summary of prerequisites proved in [1] and [12]:

Theorem 2 Let $A=\left(a_{ij}\right)\in {\overline{ℝ}}^{m\times n}$ be doubly $ℝ-astic$ and $b\in {ℝ}^m$. The system $A\otimes x=b$ has a solution if and only if $\overline{x}(A,b)$ is a solution.

Follows from Theorem ▭.

Since $\overline{x}(A,b)$ has played an important role in the solution of $A\otimes x=b$. This vector $\overline{x}$ is called the principal solution to $A\otimes x=b$ [1], and we will call it likewise. The principal solution will also be used when studying the systems $A\otimes x\le b$ and also when solving the one-sided system containing both equations and inequalities. The one-sided systems containing both equations and inequalities have been studied in [16] and the result will be presented later in this chapter.

Note that the principal solution may not be a solution to the system $A\otimes x=b$. More precisely, the following are observed in [12]:

Corollary 1 Let $A=\left(a_{ij}\right)\in {\overline{ℝ}}^{m\times n}$ be doubly $ℝ-astic$ and $b\in {ℝ}^m$. Then the following three statements are equivalent:

$$\begin{array}{cc}\hfill i)& S(A,b)\ne \varnothing \hfill \\ \hfill ii)& \overline{x}(A,b)\in S(A,b)\hfill \\ \hfill iii)& \bigcup _{j\in N}{M}_j=M\hfill \end{array}$$

The statements follow from Theorems ▭ and ▭.

For the existence of a unique solution to the max-linear system $A\otimes x=b$ we have the following corollary:

Corollary 2 Let $A=\left(a_{ij}\right)\in {\overline{ℝ}}^{m\times n}$ be doubly $ℝ-astic$ and $b\in {ℝ}^m$. Then $S(A,b)=\left\{\overline{x}(A,b)\right\}$ if and only if

$$\begin{array}{cc}\hfill i)& \bigcup _{j\in N}{M}_j=Mand\hfill \\ \hfill ii)& \bigcup _{j\in N}{M}_j\ne Mforany{N}^{\text{'}}\subseteq N,N^{\text{'}}\ne N\hfill \end{array}$$

Follows from Theorem ▭. The question of solvability and unique solvability of the system $A\otimes x=b$ was linked to the set covering and minimal set covering problem of combinatorics in [12].

4.2. System of inequalities

In this section we show how a solution to the one-sided system of inequalities can be obtained.

Let $A=\left(a_{ij}\right)\in {ℝ}^{m\times n}$ and $b={(b_1,\cdots ,b_m)}^T\in ℝ$. A system of the form:

$$A\otimes x\le b$$uid32

is called one-sided max-linear system of inequalities or just one-sided system of inequalities. The one-sided system of inequalities has received some attention in the past, see [3], [1] and [17] for more information. Here, we will only present a result which shows that the principal solution, $\overline{x}(A,b)$ is the greatest solution to (▭). That is if (▭) has a solution then $\overline{x}(A,b)$ is the greatest of all the solutions. We denote the solution set of (▭) by $S(A,b,\le )$. That is

$$S(A,b,\le )=\{x\in {ℝ}^n;A\otimes x\le b\}$$

Theorem 3 $x\in S(A,b,\le )$ if and only if $x\le \overline{x}(A,b)$.

Suppose $x\in S(A,b,\le )$. Then we have

$$\begin{array}{cc}& A\otimes x\le b\hfill \\ & ⟺\underset{j}{max}(a_{ij}+x_j)\le b_{i}foralli\hfill \\ & ⟺a_{ij}+x_j\le b_{i}foralli,j\hfill \\ & ⟺x_j\le b_i\otimes a_{ij}^{-1}foralli,j\hfill \\ & ⟺x_j\le \underset{i}{min}(b_i\otimes a_{ij}^{-1})forallj\hfill \\ & ⟺x\le \overline{x}(A,b)\hfill \end{array}$$

and the proof is now complete. The system of inequalities

$$\begin{array}{cc}\hfill A\otimes x& \le b\hfill \\ \hfill C\otimes x& \ge d\hfill \end{array}$$uid34

was discussed in [18] where the following result was presented.

Lemma 1 A system of inequalities (▭) has a solution if and only if $C\otimes \overline{x}(A,b)\ge d$

4.3. A system containing of both equations and inequalities

In this section a system containing both equations and inequalities will be presented, the results were taken from [16]. Let $A=\left(a_{ij}\right)\in {ℝ}^{k\times n}$, $C=\left(c_{ij}\right)\in {ℝ}^{r\times n}$, $b={(b_1,\cdots ,b_k)}^T\in {ℝ}^k$ and $d={(d_1,\cdots ,d_r)}^T\in {ℝ}^r$. A one-sided max-linear system with both equations and inequalities is of the form:

$$\begin{array}{cc}\hfill A\otimes x& =b\hfill \\ \hfill C\otimes x& \le d\hfill \end{array}$$uid37

We shall use the following notation throughout this paper

$$\begin{array}{cc}\hfill R& =\{1,2,...,r\}\hfill \\ \hfill S(A,C,b,d)& =\{x\in {ℝ}^n;A\otimes x=bandC\otimes x\le d\}\hfill \\ \hfill S(C,d,\le )& =\{x\in {ℝ}^n;C\otimes x\le d\}\hfill \\ \hfill {\overline{x}}_j(C,d)& =\underset{i\in R}{min}(d_i\otimes c_{ij}^{-1})forallj\in N\hfill \\ \hfill K& =\{1,\cdots ,k\}\hfill \\ \hfill K_j& =\left\{k\in K;b_k\otimes a_{kj}^{-1}=\underset{i\in K}{min}\left(b_i\otimes a_{ij}^{-1}\right)\right\}forallj\in N\hfill \end{array}$$

$$\begin{array}{cc}\hfill {\overline{x}}_j(A,b)& =\underset{i\in K}{min}(b_i\otimes a_{ij}^{-1})forallj\in N\hfill \\ \hfill \overline{x}& ={({\overline{x}}_1,...,{\overline{x}}_n)}^T\hfill \\ \hfill J& =\{j\in N;{\overline{x}}_j(C,d)\ge {\overline{x}}_j(A,b)\}and\hfill \\ \hfill L& =N\setminus J\hfill \end{array}$$

We also define the vector $\widehat{x}={({\widehat{x}}_1,{\widehat{x}}_2,...,{\widehat{x}}_n)}^T$, where

$${\widehat{x}}_j(A,C,b,d)\equiv \left\{\begin{array}{cc}{\overline{x}}_j(A,b)\hfill & \text{if}j\in J\hfill \\ {\overline{x}}_j(C,d)\hfill & \text{if}j\in L\hfill \end{array}\right.$$uid38

and $N_{\widehat{x}}=\{j\in N;{\widehat{x}}_j={\overline{x}}_j\}$.

Theorem 4 Let $A=\left(a_{ij}\right)\in {ℝ}^{k\times n}$, $C=\left(c_{ij}\right)\in {ℝ}^{r\times n}$, $b={(b_1,\cdots ,b_k)}^T\in {ℝ}^k$ and $d={(d_1,\cdots ,d_r)}^T\in {ℝ}^r$. Then the following three statements are equivalent:

$$\begin{array}{cc}\hfill \left(i\right)& S(A,C,b,d)\ne \varnothing \hfill \\ \hfill \left(ii\right)& \widehat{x}(A,C,b,d)\in S(A,C,b,d)\hfill \\ \hfill \left(iii\right)& \bigcup _{j\in J}{K}_j=K\hfill \end{array}$$

$\left(i\right)⟹\left(ii\right)$. Let $x\in S(A,C,b,d)$, therefore $x\in S(A,b)$ and $x\in S(C,d,\le )$. Since $x\in S(C,d,\le )$, it follows from Theorem ▭ that $x\le \overline{x}(C,d)$. Now that $x\in S(A,b)$ and also $x\in S(C,d,\le )$, we need to show that ${\overline{x}}_j(C,d)\ge {\overline{x}}_j(A,b)$ for all $j\in N_x$ (that is $N_x\subseteq J$). Let $j\in N_x$ then $x_j={\overline{x}}_j(A,b)$. Since $x\in S(C,d,\le )$ we have $x\le \overline{x}(C,d)$ and therefore ${\overline{x}}_j(A,b)\le {\overline{x}}_j(C,d)$ thus $j\in J$. Hence, $N_x\subseteq J$ and by Theorem ▭ ${\bigcup }_{j\in J}{K}_j=K$. This also proves $\left(i\right)⟹\left(iii\right)$

$\left(iii\right)⟹\left(i\right)$. Suppose ${\bigcup }_{j\in J}{K}_j=K$. Since $\widehat{x}(A,C,b,d)\le \overline{x}(C,d)$ we have $\widehat{x}(A,C,b,d)\in S(C,d,\le )$. Also $\widehat{x}(A,C,b,d)\le \overline{x}(A,b)$ and $N_{\widehat{x}}\supseteq J$ gives ${\bigcup }_{j\in N_{\widehat{x}(A,C,b,d)}}{K}_j\supseteq {\bigcup }_{j\in J}{K}_j=K$. Hence ${\bigcup }_{j\in N_{\widehat{x}(A,C,b,d)}}{K}_j=K$, therefore $\widehat{x}(A,C,b,d)\in S(A,b)$ and $\widehat{x}(A,C,b,d)\in S(C,d,\le )$. Hence $\widehat{x}(A,C,b,d)\in S(A,C,b,d)$ (that is $S(A,C,b,d)\ne \varnothing$) and this also proves $\left(iii\right)⟹\left(ii\right)$.

Theorem 5 Let $A=\left(a_{ij}\right)\in {ℝ}^{k\times n}$, $C=\left(c_{ij}\right)\in {ℝ}^{r\times n}$, $b={(b_1,\cdots ,b_k)}^T\in {ℝ}^k$ and $d={(d_1,\cdots ,d_r)}^T\in {ℝ}^r$. Then $x\in S(A,C,b,d)$ if and only if

$$\begin{array}{cc}\hfill \left(i\right)& x\le \widehat{x}(A,C,b,d)and\hfill \\ \hfill \left(ii\right)& \bigcup _{j\in N_x}{K}_j=Kwhere{N}_x=\{j\in N;x_j={\overline{x}}_j(A,b)\}\hfill \end{array}$$

($⟹$) Let $x\in S(A,C,b,d)$, then $x\le \overline{x}(A,b)$ and $x\le \overline{x}(C,d)$. Since $\widehat{x}(A,C,b,d)=\overline{x}(A,b){\oplus }^{{}^{\text{'}}}\overline{x}(C,d)$ we have $x\le \widehat{x}(A,C,b,d)$. Also, $x\in S(A,C,b,d)$ implies that $x\in S(C,d,\le )$. It follows from Theorem ▭ that ${\bigcup }_{j\in N_x}{K}_j=K$.

($⟸$) Suppose that $x\le \widehat{x}(A,C,b,d)=\overline{x}(A,b){\oplus }^{{}^{\text{'}}}\overline{x}(C,d)$ and ${\bigcup }_{j\in N_x}{K}_j=K$. It follows from Theorem ▭ that $x\in S(A,b)$, also by Theorem ▭ $x\in S(C,d,\le )$. Thus $x\in S(A,b)\cap S(C,d,\le )=S(A,C,b,d)$.

We introduce the symbol $\left|X\right|$ which stands for the number of elements of the set $X$.

Lemma 2 Let $A=\left(a_{ij}\right)\in {ℝ}^{k\times n}$, $C=\left(c_{ij}\right)\in {ℝ}^{r\times n}$, $b={(b_1,\cdots ,b_k)}^T\in {ℝ}^k$ and $d={(d_1,\cdots ,d_r)}^T\in {ℝ}^r$. If $\left|S\right(A,C,b,d\left)\right|=1$ then $\left|S\right(A,b\left)\right|=1$.

Suppose $\left|S\right(A,C,b,d\left)\right|=1$, that is $S(A,C,b,d)=\left\{x\right\}$ for an $x\in {ℝ}^n$. Since $S(A,C,b,d)=\left\{x\right\}$ we have $x\in S(A,b)$ and thus $S(A,b)\ne \varnothing$. For contradiction, suppose $\left|S\right(A,b\left)\right|>1$. We need to check the following two cases: (i) $L\ne \varnothing$ and (ii) $L=\varnothing$ where $L=N\setminus J$, and show in each case that $\left|S\right(A,C,b,d\left)\right|>1$.

Proof of Case (i), that is $L\ne \varnothing$: Suppose that $L$ contains only one element say $n\in N$ i.e $L=\left\{n\right\}$. Since $x\in S(A,C,b,d)$ it follows from Theorem ▭that $\widehat{x}(A,C,b,d)\in S(A,C,b,d)$. That is $x=\widehat{x}(A,C,b,d)=({\overline{x}}_1(A,b),{\overline{x}}_2(A,b),\cdots ,{\overline{x}}_{n-1}(A,b),{\overline{x}}_n(C,d))\in S(A,C,b,d)$. It can also be seen that, $\overline{x}{(C,d)}_n<{\overline{x}}_n(A,b)$ and any vector of the form $z=({\overline{x}}_1(A,b),{\overline{x}}_2(A,b),\cdots ,{\overline{x}}_{n-1}(A,b),\alpha )\in S(A,C,b,d)$, where $\alpha \le {\overline{x}}_n(C,d)$. Hence $\left|S\right(A,C,b,d\left)\right|>1$. If $L$ contains more than one element, then the proof is done in a similar way.

Proof of Case (ii), that is $L=\varnothing$ $(J=N)$: Suppose that $J=N$. Then we have $\widehat{x}(A,C,b,d)=\overline{x}(A,b)\le \overline{x}(C,d)$. Suppose without loss of generality that $x,x^{{}^{\text{'}}}\in S(A,b)$ such that $x\ne x^{{}^{\text{'}}}$. Then $x\le \overline{x}(A,b)\le \overline{x}(C,d)$ and also $x^{{}^{\text{'}}}\le \overline{x}(A,b)\le \overline{x}(C,d)$. Thus, $x,x^{{}^{\text{'}}}\in S(C,d,\le )$. Consequently, $x$, $x^{{}^{\text{'}}}\in S(A,C,b,d)$ and $x\ne x^{{}^{\text{'}}}$. Hence $\left|S\right(A,C,b,d\left)\right|>1$.

Theorem 6 Let $A=\left(a_{ij}\right)\in {ℝ}^{k\times n}$, $C=\left(c_{ij}\right)\in {ℝ}^{r\times n}$, $b={(b_1,\cdots ,b_k)}^T\in {ℝ}^k$ and $d={(d_1,\cdots ,d_r)}^T\in {ℝ}^r$. If $\left|S\right(A,C,b,d\left)\right|=1$ then $J=N$.

Suppose $\left|S\right(A,C,b,d\left)\right|=1$. It follows from Theorem ▭ that ${\bigcup }_{j\in J}{K}_j=K$. Also, $\left|S\right(A,C,b,d\left)\right|=1$ implies that $\left|S\right(A,b\left)\right|=1$ (Lemma ▭). Moreover, $\left|S\right(A,b\left)\right|=1$ implies that ${\bigcup }_{j\in N}{K}_j=K$ and ${\bigcup }_{j\in N^{{}^{\text{'}}}}{K}_j\ne K,N^{{}^{\text{'}}}\subseteq N,N^{{}^{\text{'}}}\ne N$ (Theorem ▭). Since $J\subseteq N$ and ${\bigcup }_{j\in J}{K}_j=K$, we have $J=N$.

Corollary 3 Let $A=\left(a_{ij}\right)\in {ℝ}^{k\times n}$, $C=\left(c_{ij}\right)\in {ℝ}^{r\times n}$, $b={(b_1,\cdots ,b_k)}^T\in {ℝ}^k$ and $d={(d_1,\cdots ,d_r)}^T\in {ℝ}^r$. If $\left|S\right(A,C,b,d\left)\right|=1$ then $S(A,C,b,d)=\left\{\overline{x}(A,b)\right\}$.

The statement follows from Theorem ▭ and Lemma ▭.

Corollary 4 Let $A=\left(a_{ij}\right)\in {ℝ}^{k\times n}$, $C=\left(c_{ij}\right)\in {ℝ}^{r\times n}$, $b={(b_1,\cdots ,b_k)}^T\in {ℝ}^k$ and $d={(d_1,\cdots ,d_r)}^T\in {ℝ}^k$. Then, the following three statements are equivalent:

$$\begin{array}{cc}\hfill \left(i\right)& \left|S\right(A,C,b,d\left)\right|=1\hfill \\ \hfill \left(ii\right)& \left|S\right(A,b\left)\right|=1andJ=N\hfill \\ \hfill \left(iii\right)& \bigcup _{j\in J}{K}_j=Kand\bigcup _{j\in J^{{}^{\text{'}}}}{K}_j\ne K,forevery{J}^{{}^{\text{'}}}\subseteq J,J^{{}^{\text{'}}}\ne J,andJ=N\hfill \end{array}$$

$\left(i\right)⟹\left(ii\right)$ Follows from Lemma ▭ and Theorem ▭.

$\left(ii\right)⟹\left(i\right)$ Let $J=N$, therefore $\overline{x}\le \overline{x}(C,d)$ and thus $S(A,b)\subseteq S(C,d,\le )$. Therefore we have $S(A,C,b,d)=S(A,b)\cap S(C,d,\le )=S(A,b)$. Hence $\left|S\right(A,C,b,d\left)\right|=1$.

$\left(ii\right)⟹\left(iii\right)$ Suppose that $S(A,b)=\left\{x\right\}$ and $J=N$. It follows from Theorem ▭ that ${\bigcup }_{j\in N}{K}_j=K$ and ${\bigcup }_{j\in N^{{}^{\text{'}}}}{K}_j\ne K,N^{{}^{\text{'}}}\subseteq N,N^{{}^{\text{'}}}\ne N$. Since $J=N$ the statement now follows from Theorem ▭.

$\left(iii\right)⟹\left(ii\right)$ It is immediate that $J=N$ and the statement now follows from Theorem ▭.

Theorem 7 Let $A=\left(a_{ij}\right)\in {ℝ}^{k\times n}$, $C=\left(c_{ij}\right)\in {ℝ}^{r\times n}$, $b={(b_1,\cdots ,b_k)}^T\in {ℝ}^k$ and $d={(d_1,\cdots ,d_r)}^T\in {ℝ}^k$. If $\left|S\right(A,C,b,d\left)\right|>1$ then $\left|S\right(A,C,b,d\left)\right|$ is infinite .

Suppose $\left|S\right(A,C,b,d\left)\right|>1$. By Corollary ▭ we have ${\bigcup }_{j\in J}{K}_j=K$, for some $J\subseteq N$, $J\ne N$(that is $\exists j\in N$ such that ${\overline{x}}_j(A,b)>{\overline{x}}_j(C,d)$). Now $J\subseteq N$ and ${\bigcup }_{j\in J}{K}_j=K$, Theorem ▭ implies that any vector $x={(x_1,x_2,...,x_n)}^T$ of the form

$$x_j\equiv \left\{\begin{array}{cc}{\overline{x}}_j(A,b)\hfill & \text{if}j\in J\hfill \\ y\le {\overline{x}}_j(C,d)\hfill & \text{if}j\in L\hfill \end{array}\right.$$

is in $S(A,C,b,d)$, and the statement follows.

Remark 1 From Theorem ▭ we can say that the number of solutions to the one-sided system containing both equations and inequalities can only be $0,1,or\infty$.

The vector $\widehat{x}(A,C,b,d)$ plays an important role in the solution of the one-sided system containing both equations and inequalities. This role is the same as that of the principal solution $\overline{x}(A,b)$ to the one-sided max-linear system $A\otimes x=b$, see [19] for more details.

5. Max-linear program with equation and inequality constraints

Suppose that the vector $f={(f_1,f_2,...,f_n)}^T\in {ℝ}^n$ is given. The task of minimizing [maximizing]the function $f\left(x\right)=f^T\otimes x=max(f_1+x_1,f_1+x_2...,f_n+x_n)$ subject to (▭) is called max-linear program with one-sided equations and inequalities and will be denoted by $ML{P}_{\le }^{min}$ and [$ML{P}_{\le }^{max}$]. We denote the sets of optimal solutions by $S^{min}(A,C,b,d)$ and $S^{max}(A,C,b,d)$, respectively.

Lemma 3 Suppose $f\in {ℝ}^n$ and let $f\left(x\right)=f^T\otimes x$ be defined on ${ℝ}^n$. Then,

(i) $f\left(x\right)$ is max-linear, i.e. $f(\lambda \otimes x\oplus \mu \otimes y)=\lambda \otimes f\left(x\right)\oplus \mu \otimes f\left(y\right)$

for every $x,y\in {ℝ}^n$.

(ii) $f\left(x\right)$ is isotone, i.e. $f\left(x\right)\le f\left(y\right)$ for every $x,y\in {ℝ}^n$, $x\le y$.

(i) Let $\alpha \in ℝ$. Then we have

$$\begin{array}{cc}\hfill f(\lambda \otimes x\oplus \mu \otimes y)& =f^T\otimes \lambda \otimes x\oplus f^T\otimes \mu \otimes y\hfill \\ & =\lambda \otimes f^T\otimes x\oplus \mu \otimes f^T\otimes y\hfill \\ & =\lambda \otimes f\left(x\right)\oplus \mu \otimes f\left(y\right)\hfill \end{array}$$

and the statement now follows.

(ii) Let $x,y\in {ℝ}^n$ such that $x\le y$. Since $x\le y$, we have

$$\begin{array}{cc}\hfill max\left(x\right)& \le max\left(y\right)\hfill \\ \hfill ⟺f^T\otimes x& \le f^T\otimes y,forany,f\in {ℝ}^n\hfill \\ \hfill ⟺f\left(x\right)& \le f\left(y\right).\hfill \end{array}$$

Note that it would be possible to convert equations to inequalities and conversely but this would result in an increase of the number of constraints or variables and thus increasing the computational complexity. The method we present here does not require any new constraint or variable.

We denote by

$${\left(A\otimes x\right)}_i=\underset{j\in N}{max}(a_{ij}+x_j)$$

A variable $x_j$ will be called active if $x_j=f\left(x\right)$, for some $j\in N$. Also, a variable will be called active on the constraint equation if the value ${(A\otimes x)}_i$ is attained at the term $x_j$ respectively. It follows from Theorem ▭ and Lemma ▭ that $\widehat{x}(A,C,b,d)\in S^{max}(A,C,b,d)$. We now present a polynomial algorithm which finds $x\in S^{min}(A,C,b,d)$ or recognizes that $S^{min}(A,B,c,d)=\varnothing$. Due to Theorem ▭ either $\widehat{x}(A,C,b,d)\in S(A,C,b,d)$ or $S(A,C,b,d)=\varnothing$. Therefore, we assume in the following algorithm that $S(A,C,b,d)\ne \varnothing$ and also $S^{min}(A,C,b,d)\ne \varnothing$. ONEMLP-EI(Max-linear program with one-sided equations and inequalities) $f={(f_1,f_2,...,f_n)}^T\in {ℝ}^n$, $b={(b_1,b_2,...b_k)}^T\in {ℝ}^k$, $d={(d_1,d_2,...d_r)}^T\in {ℝ}^r$, $A=\left(a_{ij}\right)\in R^{k\times n}$ and $C=\left(c_{ij}\right)\in R^{r\times n}$. $x\in S^{min}(A,C,b,d)$.

1. Find $\overline{x}(A,b)$, $\overline{x}(C,d)$, $\widehat{x}(A,C,b,d)$ and $K_j$, $j\in J$;$J=\{j\in N;{\overline{x}}_j(C,d)\ge {\overline{x}}_j(A,b)\}$

2. $x:=\widehat{x}(A,C,b,d)$

3. $H\left(x\right):=\{j\in N;f_j+x_j=f\left(x\right)\}$

4. $J:=J\setminus H\left(x\right)$

5. If

   $$\bigcup _{j\in J}{K}_j\ne K$$

   then stop ($x\in S^{min}(A,C,b,d)$)

6. Set $x_j$ small enough (so that it is not active on any equation or inequality) for every $j\in H\left(x\right)$

7. Go to 3

Theorem 8 The algorithm ONEMLP-EI is correct and its computational complexity is $O\left((k+r)n^2\right)$.

The correctness follows from Theorem ▭ and the computational complexity is computed as follows. In Step 1 $\overline{x}(A,b)$ is $O\left(kn\right)$, while $\overline{x}(C,d)$, $\widehat{x}(A,C,b,d)$ and $K_j$ can be determined in $O\left(rn\right)$, $O(k+r)n$ and $O\left(kn\right)$ respectively. The loop 3-7 can be repeated at most $n-1$ times, since the number of elements in $J$ is at most $n$ and in Step 4 at least one element will be removed at a time. Step 3 is $O\left(n\right)$, Step 6 is $O\left(kn\right)$ and Step 7 is $O\left(n\right)$. Hence loop 3-7 is $O\left(k{n}^2\right)$.

5.1. An example

Consider the following system max-linear program in which $f={(5,6,1,4,-1)}^T$,

$$\begin{array}{c}\hfill A=\left(\begin{array}{ccccc}3& 8& 4& 0& 1\\ 0& 6& 2& 2& 1\\ 0& 1& -2& 4& 8\end{array}\right),b=\left(\begin{array}{c}7\\ 5\\ 7\end{array}\right),\end{array}$$

$$\begin{array}{c}\hfill C=\left(\begin{array}{ccccc}-1& 2& -3& 0& 6\\ 3& 4& -2& 2& 1\\ 1& 3& -2& 3& 4\end{array}\right)andd=\left(\begin{array}{c}5\\ 5\\ 6\end{array}\right).\end{array}$$

We now make a record run of Algorithm ONEMLP-EI. $\overline{x}(A,b)={(5,-1,3,3,-1)}^T$, $\overline{x}(C,d)={(2,1,7,3,-1)}^T$, $\widehat{x}(A,C,b,d)={(2,-1,3,3,-1)}^T$, $J=\{2,3,4,5\}$ and $K_2=\{1,2\}$, $K_3=\{1,2\}$, $K_4=\{2,3\}$ and $K_5=\left\{3\right\}$. $x:=\widehat{x}(A,C,b,d)={(2,-1,3,3,-1)}^T$ and $H\left(x\right)=\{1,4\}$ and $J\neg \subseteq H\left(x\right)$. We also have $J:=J\setminus H\left(x\right)=\{2,3,5\}$ and $K_2\cup K_3\cup K_5=K$. Then set $x_1=x_4={10}^{-4}$ (say) and $x={({10}^{-4},-1,3,{10}^{-4},-1)}^T$. Now $H\left(x\right)=\left\{2\right\}$ and $J:=J\setminus H\left(x\right)=\{3,5\}$. Since $K_3\cup K_5=K$ set $x_2={10}^{-4}$(say) and we have $x={({10}^{-4},{10}^{-4},3,{10}^{-4},-1)}^T$. Now $H\left(x\right)=\left\{3\right\}$ and $J:=J\setminus H\left(x\right)=\left\{5\right\}$. Since $K_5\ne K$ then we stop and an optimal solution is $x={({10}^{-4},{10}^{-4},3,{10}^{-4},-1)}^T$ and $f^{min}=4$.

6. A special case of max-linear program with two-sided constraints

Suppose $c={(c_1,c_2,...,c_m)}^T,d={(d_1,d_2,...,d_m)}^T\in {ℝ}^m,A=\left(a_{ij}\right)$ and $B=\left(b_{ij}\right)\in {ℝ}^{m\times n}$ are given matrices and vectors. The system

$$A\otimes x\oplus c=B\otimes x\oplus d$$uid57

is called non-homogeneous two-sided max-linear system and the set of solutions of this system will be denoted by $S$. Two-sided max-linear systems have been studied in [20], [21], [22] and [23].

Optimization problems whose objective function is max-linear and constraint (▭) are called max-linear programs (MLP). Max-linear programs are studied in [24] and solution methods for both minimization and maximization problems were developed. The methods are proved to be pseudopolynomial if all entries are integer. Also non-linear programs with max-linear constraints were dealt with in [25], where heuristic methods were develeoped and tested for a number of instances.

Consider max-linear programs with two-sided constraints (minimization), $ML{P}^{min}$

$$\begin{array}{cc}& f\left(x\right)=f^T\otimes x⟶min\hfill \\ & subjectto\hfill \\ & A\otimes x\oplus c=B\otimes x\oplus d\hfill \end{array}$$uid58

where $f={(f_1,\cdots ,f_n)}^T\in {ℝ}^n$, $c={(c_1,\cdots ,c_m)}^T,d={(d_1,\cdots ,d_m)}^T\in {ℝ}^m$, $A=\left(a_{ij}\right)$ and $B=\left(b_{ij}\right)\in {ℝ}^{m\times n}$ are given matrices and vectors. We introduce the following:

$$\begin{array}{cc}\hfill y& =(f_1\otimes x_1,f_2\otimes x_2,\cdots ,f_n\otimes x_n)\hfill \\ & =diag\left(f\right)\otimes x\hfill \end{array}$$uid59

$diag\left(f\right)$ means a diagonal matrix whose diagonal elements are $f_1,f_2,...,f_n$ and off diagonal elements are $-\infty$. It therefore follows from (▭) that

$$\begin{array}{cc}\hfill f^T\otimes x& =0^T\otimes y\hfill \\ \hfill ⟺x& =(f_1^{-1}\otimes y_1,f_2^{-1}\otimes y_2,\cdots ,f_n^{-1}\otimes y_n)\hfill \\ & ={\left(diag\left(f\right)\right)}^{-1}\otimes y\hfill \end{array}$$uid60

Hence, by substituting (▭) and (▭) into (▭) we have

$$\begin{array}{cc}& 0^T\otimes y⟶min\hfill \\ & subjectto\hfill \\ & A^{{}^{\text{'}}}\otimes y\oplus c=B^{{}^{\text{'}}}\otimes y\oplus d,\hfill \end{array}$$uid61

where $0^T$ is transpose of the zero vector, $A^{{}^{\text{'}}}=A\otimes {\left(diag\left(f\right)\right)}^{-1}$ and $B^{{}^{\text{'}}}=B\otimes {\left(diag\left(f\right)\right)}^{-1}$

Therefore we assume without loss of generality that $f=0$ and hence (▭) is equivalent to

$$\begin{array}{cc}& f\left(x\right)={\sum _{j=1,\cdots ,n}}^{\oplus }{x}_j⟶min\hfill \\ & subjectto\hfill \\ & A\otimes x\oplus c=B\otimes x\oplus d\hfill \end{array}$$uid62

The set of feasible solutions for (▭) will be denoted by $S$ and the set of optimal solutions by $S^{min}$. A vector is called constant if all its components are equal. That is a vector $x\in {ℝ}^n$ is constant if $x_1=x_2=\cdots =x_n$. For any $x\in S$ we define the set $Q\left(x\right)=\{i\in M;{(A\otimes x)}_i>c_i\}$. We introduce the following notation of matrices. Let $A=\left(a_{ij}\right)\in R^{m\times n}$, $1\le i_1<i_2<\cdots <i_q\le m$ and $1\le j_1<j_2<\cdots <j_r\le n$. Then,

$$\begin{array}{c}\hfill A\left(\begin{array}{c}{i}_1,i_2,\cdots ,i_q\\ j_1,j_2,\cdots ,j_r\end{array}\right)=\left(\begin{array}{c}{a}_{i_1{j}_1}{a}_{i_1{j}_2}\cdots a_{i_1{j}_r}\\ a_{i_2{j}_1}{a}_{i_2{j}_2}\cdots a_{i_2{j}_r}\\ \cdots \\ a_{i_q{j}_1}{a}_{i_q{j}_2}\cdots a_{i_q{j}_r}\end{array}\right)=A(Q,R)\end{array}$$

where, $Q=\{i_1,\cdots ,i_q\}$, $R=\{j_1,\cdots ,j_r\}$. Similar notation is used for vectors $c(i_1,\cdots ,i_r)={(c_{i_1}\cdots c_{i_r})}^T=c\left(R\right)$. Given $ML{P}^{min}$ with $c\ge d$, we define the following sets

$$\begin{array}{cc}\hfill M^{=}& =\{i\in M;c_i=d_i\}and\hfill \\ \hfill M^{>}& =\{i\in M;c_i>d_i\}\hfill \end{array}$$

We also define the following matrices:

$$\begin{array}{cc}\hfill A_{=}=A(M^{=},N),& A_{>}=A(M^{>},N)\hfill \\ \hfill B_{=}=B(M^{=},N),& B_{>}=B(M^{>},N)\hfill \\ \hfill c_{=}=c\left(M^{=}\right),& c_{>}=c\left(M^{>}\right)\hfill \end{array}$$uid63

An easily solvable case arises when there is a constant vector $x\in S$ such that the set $Q\left(x\right)=\varnothing$. This constant vector $x$ satisfies the following equations and inequalities

$$\begin{array}{cc}& A_{=}\otimes x\le c_{=}\hfill \\ & A_{>}\otimes x\le c_{>}\hfill \\ & B_{=}\otimes x\le c_{=}\hfill \\ & B_{>}\otimes x=c_{>}\hfill \end{array}$$uid64

where $A_{=},A_{>},B_{=},B_{>}$, $c_{=}$ and $c_{>}$ are defined in (▭). The one-sided system of equation and inequalities (▭) can be written as

$$\begin{array}{cc}& G\otimes x=p\hfill \\ & H\otimes x\le q\hfill \end{array}$$uid65

where,

$$\begin{array}{cc}& G=\left(B_{>}\right),H=\left(\begin{array}{c}{A}_{=}\\ A_{>}\\ B_{=}\end{array}\right)\hfill \\ & p=c_{>}andq=\left(\begin{array}{c}{c}_{=}\\ c_{>}\\ c_{=}\end{array}\right)\hfill \end{array}$$uid66

Recall that $S(G,H,p,q)$ is the set of solutions for (▭).

Theorem 9 Let $Q\left(x\right)=\varnothing$ for some constant vector $x={(\alpha ,\cdots ,\alpha )}^T\in S$. If $z\in S^{min}$ then $z\in S(G,H,p,q)$.

Let $x={(\alpha ,\cdots ,\alpha )}^T\in S$. Suppose $Q\left(z\right)=\varnothing$ and $z\in S^{min}$. This implies that $f\left(z\right)\le f\left(x\right)=\alpha$. Therefore we have, $\forall j\in N$, $z\le \alpha$. Consequently, $z\le x$ and ${(A\otimes z)}_i\le {(A\otimes x)}_i$ for all $i\in M$. Since, $Q\left(z\right)=\varnothing$ and $z\in S(G,H,p,q)$.

Corollary 5 If $Q\left(x\right)=\varnothing$ for some constant vector $x\in S$ then $S^{min}\subseteq S^{min}(G,H,p,q)$.

The statement follows from Theorem ▭.

7. Some solvability concepts of a linear system containing of both equations and inequalities

System of max-separable linear equations and inequalities arise frequently in several branches of Applied Mathematics: for instance in the description of discrete-event dynamic system [4], [1] and machine scheduling [10]. However, choosing unsuitable values for the matrix entries and right-handside vectors may lead to unsolvable systems. Therefore, methods for restoring solvability suggested in the literature could be employed. These methods include modifying the input data [11], [26] or dropping some equations [11]. Another possibility is to replace each entry by an interval of possible values. In doing so, our question will be shifted to asking about weak solvability, strong solvability and control solvability.

Interval mathematics was championed by Moore [27] as a tool for bounding errors in computer programs. The area has now been developed in to a general methodology for investigating numerical uncertainty in several problems. System of interval equations and inequalities in max-algebra have each been studied in the literature. In [26] weak and strong solvability of interval equations were discussed, control sovability, weak control solvability and universal solvability have been dealt with in [28]. In [29] a system of linear inequality with interval coefficients was discussed. In this section we consider a system consisting of interval linear equations and inequalities and present solvability concepts for such system.

An algebraic structure $(B,\oplus ,\otimes )$ with two binary operations $\oplus$ and $\otimes$ is called max-plus algebra if

$$B=ℝ\cup \{-\infty \},a\oplus b=max\{a,b\},a\otimes b=a+b$$

for any $a,b\in ℝ$.

Let $m,n,r$ be given positive integers and $a\in ℝ$, we use throughout the paper the notation $M=\{1,2,...,m\},N=\{1,2,...,n\},R=\{1,2,...,r\}$ and $a^{-1}=-a$. The set of all $m\times n$, $r\times n$ matrices over $B$ is denoted by $B(m,n)$ and $B(r,n)$ respectively. The set of all $n$-dimensional vectors is denoted by $B\left(n\right)$. Then for each matrix $A\in B(n,m)$ and vector $x\in B\left(n\right)$ the product $A\otimes x$ is define as

$$(A\otimes x)=\underset{j\in N}{max}\left(a_{ij}+x_j\right)$$

For a given matrix interval $𝐀=[\underline{A},\overline{A}]$ with $\underline{A},\overline{A}\in B(k,n),\underline{A}\le \overline{A}$ and given vector interval $𝐛=[\underline{b},\overline{b}]$ with $\underline{b},\overline{b}\in B\left(n\right),\underline{b}\le \overline{b}$ the notation

$$𝐀\otimes x=𝐛$$uid69

represents an interval system of linear max-separable equations of the form

$$A\otimes x=b$$uid70

Similarly, for a given matrix interval $𝐂=[\underline{A},\overline{A}]$ with $\underline{C},\overline{C}\in B(r,n),\underline{C}\le \overline{C}$ and given vector interval $𝐝=[\underline{d},\overline{d}]$ with $\underline{d},\overline{d}\in B\left(n\right),\underline{b}\le \overline{b}$ the notation

$$𝐂\otimes x\le 𝐝$$uid71

represents an interval system of linear max-separable inequalities of the form

$$C\otimes x\le d$$uid72

Interval system of linear max-separable equations and inequalities have each been studied in the literature, for more information the reader is reffered to . The following notation

$$\begin{array}{cc}\hfill 𝐀\otimes x& =𝐛\hfill \\ \hfill 𝐂\otimes x& \le 𝐝\hfill \end{array}$$uid73

represents an interval system of linear max-separable equations and inequalities of the form

$$\begin{array}{cc}\hfill A\otimes x& =b\hfill \\ \hfill C\otimes x& \le d\hfill \end{array}$$uid74

where $A\in 𝐀,C\in 𝐂,b\in 𝐛$ and $d\in 𝐝$.

The aim of this section is to consider a system consisting of max-separable linear equations and inequalities and presents some solvability conditions of such system. Note that it is possible to convert equations to inequalities and conversely, but this would result in an increase in the number of equations and inequalities or an increase in the number of unknowns thus increasing the computational complexity when testing the solvability conditions. Each system of the form (▭) is said to be a subsystem of (▭). An interval system (▭) has constant matrices if $\underline{A}=\overline{A}$ and $\underline{C}=\overline{C}$. Similarly, an interval system has constant right hand side if $\underline{b}=\overline{b}$ and $\underline{d}=\overline{d}$. In what follows we will consider $A\in ℝ(k,n)$ and $C\in ℝ(r,n)$.

7.1. Weak solvability

Definition 8 A vector $y$ is a weak solution to an interval system (▭) if there exists $A\in 𝐀,C\in 𝐂,b\in 𝐛$ and $d\in 𝐝$ such that

$$\begin{array}{cc}\hfill A\otimes y& =b\hfill \\ \hfill C\otimes y& \le d\hfill \end{array}$$uid77

Theorem 10 A vector $x\in {ℝ}^n$ is a weak solution of (▭) if and only if

$$\begin{array}{c}\hfill x=\overline{x}\left(\begin{array}{cc}\underline{A}& \overline{b}\\ \underline{C}& \overline{d}\end{array}\right)\end{array}$$

and

$$\begin{array}{c}\hfill \overline{A}\otimes \overline{x}\left(\begin{array}{cc}\underline{A}& \overline{b}\\ \underline{C}& \overline{d}\end{array}\right)\ge \underline{b}\end{array}$$

Let $i=\{1,...,m\}$ be an arbitrary chosen index and $x={(x_1,x_2,...,x_n)}^T\in {ℝ}^n$ fixed. If $A\in 𝐀$ then ${(A\otimes x)}_i$ is isotone and we have

$${(A\otimes x)}_i\in [{(\underline{A}\otimes x)}_i,{(\overline{A}\otimes x)}_i]\subseteq ℝ$$

Hence, $x$ is a weak solution if and only if

$$[{(\underline{A}\otimes x)}_i,{(\overline{A}\otimes x)}_i]\cap [{\underline{b}}_i,{\overline{b}}_i]$$uid79

Similarly, if $\underline{C}\otimes x\le \overline{d}$ then $x$ is obviously a weak solution to

$$\begin{array}{cc}\hfill \underline{A}\otimes x& \le \overline{b}\hfill \\ \hfill \underline{C}\otimes x& \le \overline{d}\hfill \end{array}$$uid80

That is

$$\begin{array}{c}\hfill x=\overline{x}\left(\begin{array}{cc}\underline{A}& \overline{b}\\ \underline{C}& \overline{d}\end{array}\right)\end{array}$$

Also from (▭) $x$ is a weak solution if and only if

$$[{(\underline{A}\otimes x)}_i,{(\overline{A}\otimes x)}_i]\cap [{\underline{b}}_i,{\overline{b}}_i]\ne \varnothing ,\forall i=1,2,...,m$$

That is

$$\begin{array}{c}\hfill \overline{A}\otimes \overline{x}\left(\begin{array}{cc}\underline{A}& \overline{b}\\ \underline{C}& \overline{d}\end{array}\right)\ge \underline{b}\end{array}$$

Definition 9 An interval system (▭) is weakly solvable if there exists $A\in 𝐀,C\in 𝐂,b\in 𝐛$ and $d\in 𝐝$ such that (▭) is solvable.

Theorem 11 An interval system (▭) with constant matrix $A=\underline{A}=\overline{A}$, $C=\underline{C}=\overline{C}$ is weakly solvable if and only if

$$\begin{array}{c}\hfill A\otimes \overline{x}\left(\begin{array}{cc}A& \overline{b}\\ C& \overline{d}\end{array}\right)\ge \underline{b}\end{array}$$

The (if) part follows from the definition. Conversely, Let

$$\begin{array}{c}\hfill A\otimes \overline{x}\left(\begin{array}{cc}A& b\\ C& d\end{array}\right)=b\end{array}$$

be solvable subsystem for $b\in [{\underline{b}}_i,{\overline{b}}_i]$. Then we have

$$\begin{array}{c}\hfill A\otimes \overline{x}\left(\begin{array}{cc}A& \overline{b}\\ C& \overline{d}\end{array}\right)\ge A\otimes \overline{x}\left(\begin{array}{cc}A& b\\ C& d\end{array}\right)=b\ge \underline{b}\end{array}$$

7.2. Strong solvability

Definition 10 A vector $x$ is a strong solution to an interval system (▭) if for each $A\in 𝐀,C\in 𝐂$ and each $b\in 𝐛,d\in 𝐝$ there is an $x\in ℝ$ such that (▭) holds.

Theorem 12 a vector $x$ is a strong solution to (▭) if and only if it is a solution to

$$\begin{array}{cc}\hfill E\otimes x& =f\hfill \\ \hfill \overline{C}\otimes x& \le \underline{d}\hfill \end{array}$$

where

$$\begin{array}{c}\hfill E=\left(\begin{array}{c}\overline{A}\\ \underline{A}\end{array}\right),f=\left(\begin{array}{c}\underline{b}\\ \overline{b}\end{array}\right)\end{array}$$uid86

If $x$ is a strong solution of (▭), it obviously satisfies (▭). Conversely, suppose $x$ satisfies (▭) and let $\tilde{A}\in 𝐀,\tilde{C}\in 𝐂,\tilde{b}\in 𝐛,\tilde{d}\in 𝐝$ such that $\tilde{A}\otimes x\ne \tilde{b}$ and $\tilde{C}\otimes x>\tilde{d}$. Then $\exists i\in (1,2,...,m)$ such that either ${(\tilde{A}\otimes x)}_i<{\tilde{b}}_i$ or ${(\tilde{A}\otimes x)}_i>{\tilde{b}}_i$ and ${(\tilde{C}\otimes x)}_i>{\tilde{d}}_i$. Therefore, ${(\underline{A}\otimes x)}_i<{(\tilde{A}\otimes x)}_i<b_i$, ${(\overline{A}\otimes x)}_i\ge {(\tilde{A}\otimes x)}_i>b_i$ and ${(\overline{C}\otimes x)}_i>{(\tilde{C}\otimes x)}_i>d_i$ and the theorem statement follows.

Acknowledgement

The author is grateful to the Kano University of Science and Technology, Wudil for paying the publication fee.