Groupe d’études et de recherche en analyse des décisions

# Tropical Cones Defined by Max-Linear Inequalities

## Edouard Wagneur, L Truffet, F Faye et M Thiam

We consider an inequality of the type $A\cdot x\le B\cdot x$ over the idempotent semifield $R_{\max}= (R\cup \{-\infty\}, \max, + )$, where A,B are matrices of size m x n with coefficients in $R_{\max}$, and try to determine the set of its solutions. For the case m=1, we show that, for every $k (0\le k\le n)$, the set of solutions to a single inequality with $A=(a_1, \dots , a_n)$, and $B= (b_1,\dots ,b_n)$ form a $R_{\max}$ semi-module of dimension $k (n+1-k)$, and determine its basis, where k<\i> is the number of $a_i\le b_i (0\le i\le n)$. We give the necessary and sufficient conditions for the solution to be non trivial for the cases $n\ge m =2$, and $n\ge m=3$. We also show that, for m=2, the complexity of the problem (i.e. the number of cases to consider) is O($n^4$), and show how the solutions may be computed. We conclude the paper with two examples for m=2, n=7, and m=n=3, respectively.

, 22 pages