# Solving a system of linear inequalities

I have a personal problem I want to solve. I have a system of linear inequalities with 97 unknowns and 150000 ineqaulities, I think formal notation of the problem should be something like this

\begin{equation} \begin{bmatrix} x_{00000101} & \cdots & x_{00000197}\\ \vdots & \ddots &\vdots\\ x_{15000001} & \cdots & x_{15000097}\\ \end{bmatrix} \times \left[ \begin{array}{c} y_1 \\ \vdots \\ y_{97} \end{array} \right] = \left[ \begin{array}{c} z_1 \\ \vdots \\ z_{150000} \end{array} \right] \end{equation} \begin{equation} \forall z \in \left\{ z_i | i \in [1,150000]\right\}, z_i > 0 \end{equation} We also know that $\forall x \in$ leftmost matrix $x \in \left\{-1,0,1 \right\}$ (i.e coefficients can only take -1,0,1 as values) and there is exacly $5$ $1$s and $5$ $-1$'s in every row in leftmost matrix. So, each row sums up to $0$.

What I want to do is to determine if I can order $y_i$'s and if so, I want to find an algorithm to order them.

I am considering using a genetic algorithm and by trying arbitrary values for every $y_i$. But I guess that could be computationaly expensive. Is there a way I can deterministically solve this problem?

Some background information: every $y_i$ represents a player in a game, I have a data of 150000 matches of 5 player vs 5 player. I am assuming team's ability to win is sum of the abilities of its players. So I am wondering if I can order the players to best to worse.

• A couple of questions: 1. Does $x_{00000709}=1$ represent that player $9$ was playing for (lacking a better name) the 'home team' in match number 7, $x_{00000709}=-1$ that he/she was playing for the 'away team' in match number 7 and $x_{00000709}=0$ represents that he/she wasn't playing at all. 2. Does $z_{000005}>0$ represent that the home team won match 5, $z_{000005}<0$ that the away won match 5 and $z_{000005}=0$ that it was a draw. 3. Does $y_{25}$ represent the skills of player $25$ (the more positive the number the better the player's skill)? – jkn Mar 6 '13 at 17:07
• $x_{00000709}=1$ represents player 9 was playing for winning side in match 7. $x_{00000709}=-1$ represents player 9 was playing for loser side in match 7. A player with value 0 wasn' playing in that game. So that each row gives you an inequality such that sum of winning team's values minus sum of losing teams values is $z_i$ which is bigger than zero. There is no draws in this game. $y_{25}$ means the skill level of player $25$, and the bigger is the better. – yasar Mar 6 '13 at 17:27
• So, what exactly do you want to do? Find a vector of skills that fits the above scenario (that is, one such that given the matrix of $x$s, $z_i>0$ for all $i$)? In addition, are there any constraints on the $y_i$s? For example, do they have to be strictly positive numbers (can a player have a negative skill level, representing they actually harm more than help?)? – jkn Mar 6 '13 at 17:54
• This is essentially a binary linear integer programming problem. Perhaps searching for that helps, but the "thousands of inequalities" doesn't bode well... – vonbrand Mar 6 '13 at 17:57
• @jkn Yes, I want to find a vector of skills that fits the above scenario. So that I could use that vector to predict future games. There is no constraint on the $y_i$'s. They can be anything that can be ordered – yasar Mar 7 '13 at 10:42