Solving a Min/Max equation set In solving a certain game, I've ended up with a set of equalities like these:

a == Max[b,c]/2+Max[d,e]/2
b == Min[f,g]/2+Min[h,i]/2
...
o == (1-d)/2+r/2
p == (1-d)/2
q == s/2+1/2
r == Max[1-h,1-i]/2+Max[t,u]/2
...


I create 2^N different equation sets, where N is the number of Max statements, and try to solve them individually using gaussian elimination or something like that. That would be something like $O(2^N*n^3)$.

By considering disjoin cycles and other heuristics, I could perhaps get it a bit faster, but I would still only be able to solve very simple games.

Are you aware of any algorithms, deterministic or approximate, that could make the above problem feasible for 30-50 or maybe even more Max statements?

Update:


Each equation is a simple linear combination of variables, constants and Max/Mins of two (or more) variables. The number of terms in each equation is constant
It is known, that there is an unique solution {a,b,c,...}
All variables are fractions in (0,1).


I can reduce the system by using Max[a,b] = (a+b-|a-b|)/2 and Snowie showed how to eliminate Max[a,b] by adding two inequalities and a binary variable. The complexity still seams to be O(2^N).
To follow up on Snowie's post:

For each term max(v1, v2) introduce a new variable $x_i$, subject to the constraints $x_i \geq v_1, x \geq v_2$

For each term min(v1,v2) introduce a variable $y_i$ subject to $y_i \leq v_1, y_i \leq v_2$.

Next, minimize the linear constraint $l = \sum x_i - \sum y_i$
subject to the inequations $x \geq v, y \geq v$, the linear equations $0 \leq v \leq 1$, AND the original linear system of equations.

This is a linear program, hence solvable in polynomial time. As the number of such constraints is polynomial, the entire system is solved in polynomial time.